分布計(jì)算系統(tǒng)-分布式數(shù)據(jù)管理

分布式數(shù)據(jù)管理

8.1一致性模型

一致性模型是進(jìn)程和數(shù)據(jù)存儲之間的一個基本約定。也就是說，如果進(jìn)程對數(shù)據(jù)的訪問遵守特定的規(guī)則，那么數(shù)據(jù)存儲就能夠正確地進(jìn)行。嚴(yán)格一致性

對于嚴(yán)格一致性模型來說，對一個數(shù)據(jù)項(xiàng)所進(jìn)行的任何讀操作所返回的值總是對該數(shù)據(jù)項(xiàng)最近一次進(jìn)行寫操作的結(jié)果。分布式數(shù)據(jù)管理

8.1一致性模型

順序一致性和可線性化一致性

所有進(jìn)程對數(shù)據(jù)項(xiàng)的所有操作可以認(rèn)為是按照某個順序進(jìn)行的，任何進(jìn)程對這個順序的觀點(diǎn)是一樣的。當(dāng)然這個順序不一定是物理意義上順序。分布式數(shù)據(jù)管理

8.1一致性模型

相關(guān)一致性

具有潛在因果關(guān)系的所有寫操作能夠被所有的進(jìn)程以相同的順序看見，而并發(fā)的寫操作可以被不同的進(jìn)程以不同的順序看見。分布式數(shù)據(jù)管理

8.1一致性模型

相關(guān)一致性

具有潛在因果關(guān)系的所有寫操作能夠被所有的進(jìn)程以相同的順序看見，而并發(fā)的寫操作可以被不同的進(jìn)程以不同的順序看見。分布式數(shù)據(jù)管理

8.1一致性模型

FIFO一致性

一個進(jìn)程中的所有寫操作能夠以它在該進(jìn)程中出現(xiàn)的順序被所有其他進(jìn)程看見。但是不同進(jìn)程中的寫操作在不同的進(jìn)程看來具有不同的順序。分布式數(shù)據(jù)管理

8.1一致性模型

FIFO一致性

處理機(jī)一致性模型：在這種模型中，不僅要求一個進(jìn)程中的所有寫操作能夠以它在該進(jìn)程中出現(xiàn)的順序被所有其他進(jìn)程看見，還要求不同進(jìn)程對同一個數(shù)據(jù)項(xiàng)的寫操作，應(yīng)該被所有進(jìn)程以相同的順序看見。分布式數(shù)據(jù)管理

8.1一致性模型

弱一致性弱一致性模型是使用同步變量實(shí)現(xiàn)的一個一致性模型，他有如下三個特性：(1)訪問與數(shù)據(jù)存儲有關(guān)的同步變量時，必須遵守順序一致性模型；(2)以前的所有寫操作在每個副本上沒有完成之前，對同步變量進(jìn)行的操作不允許執(zhí)行；(3)以前的所有對同步變量的操作完成之前，對數(shù)據(jù)項(xiàng)進(jìn)行任何讀或?qū)懖僮鞑辉试S執(zhí)行。分布式數(shù)據(jù)管理

8.1一致性模型

弱一致性分布式數(shù)據(jù)管理

8.1一致性模型

釋放一致性釋放一致性為用戶提供了這兩種同步操作：一種是acquire操作，它用于告訴系統(tǒng)調(diào)用進(jìn)程要進(jìn)入一個臨界區(qū)，在這種情況下，其他進(jìn)程對遠(yuǎn)程副本的修改應(yīng)該傳播到本地，并且要對本地的副本進(jìn)行更新；另一種是release操作，用于告訴系統(tǒng)調(diào)用進(jìn)程要離開一個臨界區(qū)，在這種情況下，本地進(jìn)程對本地數(shù)據(jù)副本的修改應(yīng)該傳播到所有的遠(yuǎn)程副本上。釋放一致性模型，必須遵守如下規(guī)則：(1)前面的所有acquire操作完全成功完成以前，對共享數(shù)據(jù)的讀寫操作不能執(zhí)行；(2)在一個釋放操作被允許執(zhí)行之前，所有以前的讀寫操作必須完成；(3)對同步變量的訪問必須遵守FIFO一致性模型。分布式數(shù)據(jù)管理

8.1一致性模型

釋放一致性分布式數(shù)據(jù)管理

8.1一致性模型

進(jìn)入一致性進(jìn)入一致性模型的數(shù)據(jù)存儲必須符合以下條件：(1)被保護(hù)數(shù)據(jù)的所有更新完成之前，一個進(jìn)程對相應(yīng)同步變量的acquire操作不能執(zhí)行。(2)如果有其他進(jìn)程持有某個同步變量，即使是以非互斥的方式持有這個同步變量，一個進(jìn)程以互斥的方式對這個同步變量的訪問不能執(zhí)行。(3)當(dāng)一個對同步變量的互斥方式訪問完成以后，其他進(jìn)程對這個同步變量的非互斥方式的訪問也不能立即執(zhí)行，除非在這個同步變量的所有者的訪問完成之后。分布式數(shù)據(jù)管理

8.1一致性模型

進(jìn)入一致性分布式數(shù)據(jù)管理

8.1一致性模型

不同一致性模型的主要特性分布式數(shù)據(jù)管理

8.2并發(fā)控制

并發(fā)控制的目標(biāo)與事務(wù)處理

并發(fā)控制的目的是在有多個用戶的情況下允許每個用戶像單個用戶那樣訪問共享資源，多個用戶同時訪問時互相不干擾。并發(fā)控制要解決多個用戶的活動之間的切換，保護(hù)一個用戶的活動不受另一個用戶的活動的影響，以及對相互依賴的若干活動進(jìn)行同步等問題。事務(wù)處理：數(shù)據(jù)庫中的事務(wù)處理(transaction)是施加在共享數(shù)據(jù)上的一組操作，這些操作是結(jié)合在一起的，被當(dāng)作單個活動看待。分布式數(shù)據(jù)管理

8.2并發(fā)控制

并發(fā)控制的目標(biāo)與事務(wù)處理

在無并發(fā)控制的情況下，兩個并發(fā)的事務(wù)處理可能會相互干擾：丟失更新。多個事務(wù)處理同時對一個共同的數(shù)據(jù)對象進(jìn)行寫操作時，就會有丟失更新的現(xiàn)象發(fā)生，并且使數(shù)據(jù)庫處于不一致狀態(tài)。檢索的不一致。檢索的不一致發(fā)生在一個事務(wù)處理讀取數(shù)據(jù)庫中的某些數(shù)據(jù)對象，但是另一個事務(wù)處理對其中一些數(shù)據(jù)對象的修改還沒有完成。分布式數(shù)據(jù)管理

8.2并發(fā)控制

并發(fā)控制的目標(biāo)與事務(wù)處理

丟失更新的例子：分布式數(shù)據(jù)管理

8.2并發(fā)控制

并發(fā)控制的目標(biāo)與事務(wù)處理

檢索不一致的例子：分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

并發(fā)控制正確性標(biāo)準(zhǔn)有兩條：用戶交給系統(tǒng)的每個事務(wù)處理最終將被執(zhí)行，并最終得到完成；多個事務(wù)處理并發(fā)執(zhí)行的結(jié)果和這多個事務(wù)處理串行執(zhí)行的結(jié)果相同。事務(wù)處理的例子：假設(shè)有三個賬戶(對象)A、B、C，最初各有存款￥200、￥100和￥50。現(xiàn)有兩個事務(wù)處理T1和T2等待執(zhí)行，T1是從A取出￥100存入B，T2是從B中取出￥50存入C。分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

T1：

begin read(A) 得到賬戶A的存款數(shù)

read(B) 得到賬戶B的存款數(shù)

write(A) (從A中減去￥100后)寫入A write(B) (加入B中￥100后)寫入BendT2：

begin read(B) 得到賬戶B的存款數(shù)

read(C) 得到賬戶C的存款數(shù)

write(B) (從B中減去￥50后)寫入B write(C) (加入C中￥50后)寫入Cend分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

并發(fā)事務(wù)處理執(zhí)行中的兩種現(xiàn)象：暫時不一致性。在T1和T2的第一次寫操作之后而在第二次寫操作之前，賬戶存款之和是不一致的。沖突。如果事務(wù)處理T2被安排到T1中的兩次寫操作之間運(yùn)行，則賬戶存款總和為￥400，而不是￥350，它包含一個不一致狀態(tài)。暫時不一致性在所有順序計(jì)算過程中是固有的，因此，在一個事務(wù)處理結(jié)束前一般不應(yīng)該要求一致性。為了達(dá)到一致性，必須避免沖突。分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

可串行化調(diào)度：并發(fā)控制就是控制相互沖突操作的相對執(zhí)行順序，完成這種控制的算法也叫同步技術(shù)。我們希望使用這樣的同步技術(shù)，它能使各個非沖突的操作交疊執(zhí)行，以便進(jìn)行各事務(wù)處理時具有最大的并發(fā)性。一組事務(wù)處理中各個操作的交叉次序叫做調(diào)度。如果一個調(diào)度給每個事務(wù)處理一個一致的狀態(tài)觀點(diǎn)，則這種調(diào)度叫做一致調(diào)度。一致調(diào)度的充分條件是這種調(diào)度執(zhí)行的結(jié)果和所有事務(wù)處理串行執(zhí)行的結(jié)果是一樣的。滿足這個條件的調(diào)度叫做可串行化調(diào)度或線性化調(diào)度。分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

調(diào)度的形式化描述：T1=w1(x),w1(y),r1(z)T2=r2(z),r2(y),w2(x)T3=w3(z),r3(z),w3(x)L1=w1(x),r2(z),r2(y),w2(x),w1(y),r1(z),w3(z),r3(z),w3(x)L2=w1(x),w1(y),r1(z),r2(z),r2(y),w2(x),w3(z),r3(z),w3(x)L3=w1(x),w1(y),r1(z),r2(z),w3(z),r2(y),r3(z),w2(x),w3(x)分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

rj(x)讀自wi(x)：如果調(diào)度L有兩個操作wi(x)和rj(x)，我們說rj(x)讀自wi(x)當(dāng)且僅當(dāng)wi(x)＜rj(x)；沒有wk(x)，使得wi(x)＜wk(x)＜rj(x)。分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

兩個調(diào)度等價：在事務(wù)處理系統(tǒng)上兩個調(diào)度等價當(dāng)且僅當(dāng)(1)兩個調(diào)度中每個對應(yīng)的讀操作讀自同一個寫操作；(2)兩個調(diào)度中有同樣的最終寫。在調(diào)度L2還是L3中，r1(z)和r2(z)讀自一個初始的z，r2(y)讀自w1(y)，r3(z)讀自w3(z)。另外w3(x)、w1(y)和w3(z)分別是對數(shù)據(jù)對象x、y和z的最終寫。因此，調(diào)度L2和L3是等價的。L1=w1(x),r2(z),r2(y),w2(x),w1(y),r1(z),w3(z),r3(z),w3(x)L2=w1(x),w1(y),r1(z),r2(z),r2(y),w2(x),w3(z),r3(z),w3(x)L3=w1(x),w1(y),r1(z),r2(z),w3(z),r2(y),r3(z),w2(x),w3(x)分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

一組事務(wù)處理T={T1，T2，…，Tn}，對于一個給定調(diào)度L，串行化圖定義如下：對某個x，如果ri(x)＜wj(x)、wi(x)＜rj(x)，或者wi(x)＜wj(x)，則有一條從Ti到Tj的邊。如果從Ti到Tj有一條路徑存在，則可以刪除從Ti到Tj的邊。分布式數(shù)據(jù)管理

8.2并發(fā)控制

可串行化調(diào)度

L1=w1(x),r2(z),r2(y),w2(x),w1(y),r1(z),w3(z),r3(z),w3(x)L2=w1(x),w1(y),r1(z),r2(z),r2(y),w2(x),w3(z),r3(z),w3(x)L3=w1(x),w1(y),r1(z),r2(z),w3(z),r2(y),r3(z),w2(x),w3(x)分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于鎖的并發(fā)控制

靜態(tài)封鎖和動態(tài)封鎖：在靜態(tài)封鎖方式中，事務(wù)處理在執(zhí)行操作前，對所有需要的數(shù)據(jù)對象封鎖。這個方法相對簡單，然而它限制了并發(fā)性，因?yàn)橛袥_突的事務(wù)處理必須串行執(zhí)行。在動態(tài)封鎖方式中，事務(wù)處理在執(zhí)行的不同階段對不同對象封鎖。封鎖范圍：封鎖范圍是一個很重要的設(shè)計(jì)問題。顯然，既可以對整個文件進(jìn)行封鎖，也可以對特定的記錄進(jìn)行封鎖。封鎖的范圍越小，并發(fā)性越好。如果兩個用戶要修改同一個文件，并且它們是對這個文件的兩個不同部分進(jìn)行修改的話，則可以讓他們同時進(jìn)行。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于鎖的并發(fā)控制

兩階段封鎖：兩階段封鎖可以保證一致性，實(shí)現(xiàn)正確的并發(fā)控制。兩階段封鎖的主要內(nèi)容如下：訪問一個對象前先封鎖它，為此必須先獲得鎖；對所有要訪問的對象封鎖前不對任何對象進(jìn)行解鎖；不要封鎖已經(jīng)被封鎖的對象，為此不同的事務(wù)處理不可同時獲得沖突的鎖；事務(wù)處理執(zhí)行結(jié)束前，為每個被它封鎖的對象解鎖；一旦一個事務(wù)處理釋放一個鎖，該事務(wù)處理就不能再獲得另外的鎖。每個事務(wù)處理鎖的過程可分成兩個階段：鎖的增長階段和鎖的收縮階段。增長階段中事務(wù)處理獲得所有的鎖而不釋放任何鎖；收縮階段釋放所有的鎖而不取得另外的鎖。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于鎖的并發(fā)控制

兩階段封鎖的問題：問題1：在鎖的增長階段會出現(xiàn)死鎖的問題。發(fā)生死鎖是因?yàn)樵诩渔i機(jī)制中，鎖是一種競爭的資源。死鎖問題可以用第六章討論的辦法來解決。問題2：在鎖的收縮階段容易出現(xiàn)層疊回退(cascadedaborts)的問題。層疊回退的問題發(fā)生在一個事務(wù)處理操作失敗后回退，在回退前由于該進(jìn)程已經(jīng)釋放了某些數(shù)據(jù)對象上的鎖，所以其他事務(wù)處理可能已經(jīng)讀取了被這個事務(wù)處理修改過的數(shù)據(jù)對象，這些事務(wù)處理也必須回退。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于鎖的并發(fā)控制

層疊回退的問題可以用嚴(yán)格的兩階段封鎖方案來解決：在這種方案中，事務(wù)處理一直占有所有獲得的鎖直到操作完成，然后在一個單一的原子操作中釋放所有的鎖，但是它降低了并發(fā)程度。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于鎖的并發(fā)控制

加鎖方案，共有三種實(shí)現(xiàn)方法：

(1)集中式加鎖方法。在這種加鎖方式中，鎖管理是集中進(jìn)行的。有一個集中的鎖管理員，它負(fù)責(zé)鎖的分配和釋放。(2)主站點(diǎn)加鎖方法。每個數(shù)據(jù)對象有一個主站點(diǎn)，所有對數(shù)據(jù)對象的更新首先定向到主站點(diǎn)。對某個數(shù)據(jù)對象的加鎖和釋放鎖的管理活動是由該數(shù)據(jù)對象的主站點(diǎn)上的鎖管理員負(fù)責(zé)的。(3)分散式加鎖方法。鎖的管理有所有站點(diǎn)共同完成。事務(wù)處理的執(zhí)行包括許多站點(diǎn)的參與和協(xié)作。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于時間戳的并發(fā)控制

各種時間戳：（1）ts(T)：每個事務(wù)處理T在它啟動的時候被分配一個時間戳ts(T)，一個事務(wù)處理T中的每個操作被加蓋一個時間戳ts(T)；（2）tsRD(x)：對數(shù)據(jù)對象最近一次讀時的時間戳用tsRD(x)表示；（3）tsWR(x)：對數(shù)據(jù)對象最近一次寫時的時間戳用tsWR(x)表示；（4）read(T,x,ts)：read(T,x,ts)表示來自事務(wù)處理T對數(shù)據(jù)對象x讀操作請求，該請求帶有時間戳ts；（5）write(T,x,ts)：write(T,x,ts)表示來自事務(wù)處理T對數(shù)據(jù)對象x寫操作請求，該請求帶有時間戳ts。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于時間戳的并發(fā)控制

讀或?qū)懖僮鞯奶幚矸绞剑?1)讀請求read(T,x,ts)。如果ts＜tsWR(x),說明有一個對x的寫操作發(fā)生在事務(wù)處理T啟動之后，則讀請求被拒絕，事務(wù)處理T被取消。反之，讓T執(zhí)行該讀操作，并把max{tsRD(x),ts}賦給tsRD(x)。(2)寫請求write(T,x,ts)。如果ts＜tsWR(x)，或者ts＜tsRD(x)，說明有一個對x的寫操作或者有一個對x的讀操作發(fā)生在事務(wù)處理T啟動之后，則寫請求被拒絕，事務(wù)處理T被取消。反之，讓T執(zhí)行該寫操作，并把ts賦給tsWR(x)。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于時間戳的并發(fā)控制

實(shí)例：假設(shè)數(shù)據(jù)對象x的最近一次讀和寫的時間戳分別為tsRD(x)=4和tsWR(x)=6，對數(shù)據(jù)對象x有下列讀寫操作順序：read(5,x,5),write(6,x,7),read(7,x,9),read(8,x,8),write(9,x,8)

(1)read(5,x,5)操作請求被拒絕，對應(yīng)的事務(wù)處理5被取消，因?yàn)閠s=5＜tsWR(x)=6；(2)write(6,x,7)操作請求被接受，對應(yīng)的事務(wù)處理6繼續(xù)執(zhí)行，tsWR(x)更新為7；(3)read(7,x,9)被接受，對應(yīng)的事務(wù)處理7繼續(xù)執(zhí)行，tsRD(x)更新為9;(4)read(8,x,8)也被接受，對應(yīng)的事務(wù)處理8繼續(xù)執(zhí)行，但是ts=8＜tsRD(x)=9，所以tsRD(x)=9保持不變;(5)write(9,x,8)操作請求被拒絕，對應(yīng)的事務(wù)處理9被取消，因?yàn)閠s=8＜tsRD(x)=9。分布式數(shù)據(jù)管理

8.2并發(fā)控制

基于時間戳的并發(fā)控制

保守時間戳順序:為了減少或消除事務(wù)處理的取消和重啟，可使用下列保守時間戳順序，所有的站點(diǎn)嚴(yán)格地按照時間戳順序執(zhí)行請求。每個站點(diǎn)有一個寫隊(duì)列(W-queue)和一個讀隊(duì)列(R-queue)。并且按照請求的時間戳排序。(1)如果所有寫隊(duì)列非空，而且每個隊(duì)列的第一個寫的時間戳大于ts，讀請求read(T,x,ts)可以被執(zhí)行；反之，該讀請求在讀隊(duì)列中緩存。(2)如果所有讀隊(duì)列和寫隊(duì)列非空，而且每個隊(duì)列的第一個請求的時間戳大于ts，寫請求write(T,x,ts)可以被執(zhí)行；反之寫請求在寫隊(duì)列中緩存。分布式數(shù)據(jù)管理

8.2并發(fā)控制

樂觀的并發(fā)控制

并發(fā)控制算法首先假設(shè)沒有沖突，所以首先在本地嘗試更新，如果沒有一致性沖突就保留更新并擴(kuò)散更新，這個方法有三個階段：讀、確認(rèn)和寫。讀階段，在臨時存儲空間中讀入相關(guān)數(shù)據(jù)對象并進(jìn)行更新；確認(rèn)階段，檢查所有更新，確認(rèn)是否違反數(shù)據(jù)庫一致性。檢查階段要檢查所有其他事務(wù)處理，確認(rèn)自該事務(wù)處理啟動以來是否有其他的事務(wù)處理對它所訪問的數(shù)據(jù)對象進(jìn)行了修改。如果有則該事務(wù)處理取消，否則檢查通過，進(jìn)入寫階段；寫階段，把所有更新寫進(jìn)數(shù)據(jù)庫。樂觀并發(fā)控制算法的最大優(yōu)點(diǎn)是沒有死鎖，并且可以最大限度地提供并行，因?yàn)闆]有一個事務(wù)處理會等待。它的缺點(diǎn)是一旦在確認(rèn)階段不能通過檢查，事務(wù)處理就要重新執(zhí)行。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的性質(zhì)：原子性(Atomicity)。一個原子事務(wù)處理的執(zhí)行必須確保是完全執(zhí)行完畢或相當(dāng)于完全沒有執(zhí)行。一致性(Consistency)。一個事務(wù)處理必須以一致性的狀態(tài)開始，以一致性的狀態(tài)結(jié)束。不能違背系統(tǒng)的恒定性。孤立性(Isolation)。原子事務(wù)處理所有的中間操作必須以孤立的形式執(zhí)行。只允許在該事務(wù)處理操作的某個數(shù)據(jù)對象達(dá)到一致的狀態(tài)時才能夠被其他事務(wù)處理訪問。也就是說，并發(fā)的事務(wù)處理之間不會發(fā)生相互干擾。孤立性也稱為可串行性。持久性(Durability)。一旦事務(wù)處理已經(jīng)被提交，即使在發(fā)生系統(tǒng)失效的情況下，結(jié)果將永不丟失。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

事務(wù)處理的分類：平面事務(wù)處理：事務(wù)處理都是由一系列基本的操作所組成；一個嵌套事務(wù)處理是由多個子事務(wù)處理組成的，頂層的事務(wù)處理產(chǎn)生多個子事務(wù)處理，這些子事務(wù)處理相互在不同的機(jī)器上并行執(zhí)行。每個子事務(wù)處理也可以產(chǎn)生自己的子事務(wù)處理；分布式事務(wù)處理也是由一些子事務(wù)處理組成的，分布式事務(wù)處理在邏輯上是平面的，是施加在分布式數(shù)據(jù)對象上的一系列在邏輯上不可分的操作組成的；分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的實(shí)現(xiàn)：實(shí)現(xiàn)原子事務(wù)處理必須提供以下幾個組成部分：事務(wù)處理管理員：負(fù)責(zé)使該事務(wù)處理的各個參加者就該事務(wù)處理是否提交或夭折達(dá)成一致意見；恢復(fù)管理員：負(fù)責(zé)在事務(wù)處理失效后恢復(fù)狀態(tài)；緩沖器管理員：負(fù)責(zé)在主存和磁盤間傳送數(shù)據(jù)；運(yùn)行記錄(log)管理員：負(fù)責(zé)各種操作及狀態(tài)的記錄；鎖管理員；負(fù)責(zé)并發(fā)控制；通信管理員：負(fù)責(zé)透明的跨網(wǎng)絡(luò)的通信，在分布式事務(wù)處理中通知事務(wù)處理的管理部分。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的局部恢復(fù)技術(shù)意圖表方法：意圖表方法按順序完成以下操作：(1)把事務(wù)處理要向各數(shù)據(jù)對象施加的所有修改操作都存放在一個表中，該表稱為意圖表；(2)該表被寫入堅(jiān)固存儲器中；(3)事務(wù)處理管理員決定該事務(wù)處理是否提交；(4)若該事務(wù)處理提交，則在表中設(shè)置完整標(biāo)志，開始按照意圖表修改在磁盤中的那些對象；(5)刪除意圖表。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的局部恢復(fù)技術(shù)意圖表方法：失效后的處理方法：(1)若意圖表不存在，則夭折該事務(wù)處理。(2)若意圖表不完整，即在寫意圖表時節(jié)點(diǎn)崩潰，則夭折該事務(wù)處理并刪除此表；(3)若意圖表完整，即在按堅(jiān)固存儲器中的意圖表對數(shù)據(jù)對象進(jìn)行實(shí)際的更新時節(jié)點(diǎn)崩潰，則系統(tǒng)按表中的說明進(jìn)行更新，更新完畢后刪除意圖表。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的局部恢復(fù)技術(shù)先寫運(yùn)行記錄方法：執(zhí)行過程：先寫運(yùn)行記錄的方法在事務(wù)處理的執(zhí)行過程中，對數(shù)據(jù)對象進(jìn)行了實(shí)際的修改。但是在數(shù)據(jù)對象被修改前，需要在運(yùn)行記錄中寫一個記錄項(xiàng)，用于告訴事務(wù)處理管理員對哪個數(shù)據(jù)對象進(jìn)行修改，修改前的值和修改后的值是什么，以便用于失效后的恢復(fù)。只有在這個記錄項(xiàng)正確地寫到運(yùn)行記錄之后，才能對實(shí)際的數(shù)據(jù)對象進(jìn)行修改。該運(yùn)行記錄是放在堅(jiān)固存儲器之中的。恢復(fù)過程：如果事務(wù)處理夭折，運(yùn)行記錄可以用來退回到事務(wù)處理執(zhí)行前的起始狀態(tài)。從運(yùn)行記錄的末尾往回退的過程中，讀取每一個運(yùn)行記錄項(xiàng)，按記錄項(xiàng)的內(nèi)容執(zhí)行恢復(fù)操作，最終會退回到事務(wù)處理執(zhí)行前的狀態(tài)，這個過程叫做卷回(rollback)。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的局部恢復(fù)技術(shù)先寫運(yùn)行記錄方法：實(shí)例：分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

原子事務(wù)處理的局部恢復(fù)技術(shù)先寫運(yùn)行記錄方法：必須遵守的規(guī)則：在把數(shù)據(jù)對象的新值寫入到運(yùn)行記錄之前，先把數(shù)據(jù)對象的舊值寫入運(yùn)行記錄；在對數(shù)據(jù)對象進(jìn)行實(shí)際的更新之前，先把該數(shù)據(jù)對象的舊值和新值寫入到運(yùn)行記錄中。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

分布式提交協(xié)議分布式提交用于保證一個進(jìn)程組中的每一個成員要么都執(zhí)行某一個操作，要么都不執(zhí)行這個操作。分布式提交用于分布式事務(wù)處理的全局恢復(fù)。兩階段提交協(xié)議(2PC)

協(xié)調(diào)者的準(zhǔn)備提交階段：(1)向所有的參加者廣播一個PREPARE(準(zhǔn)備)報文；(2)等待每一個參加者的回答。每個參加者僅在完成此事務(wù)處理中屬于它應(yīng)該完成的那部分工作，同時寫好運(yùn)行記錄之后才發(fā)出一個回答報文。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

兩階段提交協(xié)議(2PC)

協(xié)調(diào)者的提交階段：

如果有一個參加者回答一個ABORT(夭折)，或者有一個參加者超時未回答，則將ABORT項(xiàng)寫入運(yùn)行記錄中，然后向所有參加者廣播一個ABORT報文，在收到參加者的承認(rèn)后，本次協(xié)議的執(zhí)行結(jié)束。如果所有參加者發(fā)來的PREPARED(準(zhǔn)備好了)報文，則進(jìn)行一下操作：(1)在運(yùn)行記錄上寫入一個COMMIT項(xiàng)；(2)向所有的參加者廣播一個COMMIT報文；(3)等待每個參加者做出肯定回答ACK-COMMIT；(4)將COMPLETE(完成)項(xiàng)記入運(yùn)行記錄，本次協(xié)議的執(zhí)行結(jié)束。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

兩階段提交協(xié)議(2PC)

參加者的準(zhǔn)備提交階段：

(1)等待協(xié)調(diào)者的PREPARE報文；(2)完成自己的工作，將運(yùn)行記錄項(xiàng)寫入運(yùn)行記錄；(3)如果成功，則將COMPLETE項(xiàng)記入運(yùn)行記錄，并向協(xié)調(diào)者發(fā)送PREPARED報文；否則發(fā)送ABORT報文。參加者的提交階段：(1)等待協(xié)調(diào)者的裁決報文；(2)向協(xié)調(diào)者發(fā)送回答。如果裁決是ABORT則將事務(wù)處理作廢，同時將ABORT項(xiàng)寫入運(yùn)行記錄中，釋放鎖，發(fā)送夭折承認(rèn)報文ACK-ABORT；如果裁決是COMMIT，在運(yùn)行記錄上寫入一個COMMIT項(xiàng)，釋放鎖，發(fā)送提交承認(rèn)報文ACK-COMMIT。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

兩階段提交協(xié)議(2PC)

恢復(fù)管理員必須遵守以下規(guī)則：(1)如果協(xié)調(diào)者在第二階段的步驟(1)以前崩潰，此時協(xié)調(diào)者的運(yùn)行記錄中未包含COMMIT項(xiàng)，協(xié)調(diào)者重新啟動后向所有參加者發(fā)送ABORT報文；(2)如果協(xié)調(diào)者在第二階段的步驟(1)之后，但在第二階段的步驟(4)以前崩潰，此時協(xié)調(diào)者的運(yùn)行記錄中包含COMMIT項(xiàng)，但是無COMPLETE，協(xié)調(diào)者重新啟動后向所有參加者發(fā)送COMMIT報文；(3)如果協(xié)調(diào)者在第二階段的步驟(4)之后崩潰，此時協(xié)調(diào)者的運(yùn)行記錄中包含COMPLETE項(xiàng)，則此事務(wù)處理已經(jīng)提交，協(xié)調(diào)者的工作已經(jīng)完成，對重新啟動可以不予理睬。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

用于嵌套事務(wù)處理的提交協(xié)議用于嵌套事務(wù)處理的提交協(xié)議也分為兩個階段：準(zhǔn)備提交階段和提交階段。在這種提交協(xié)議中，每個子事務(wù)處理分別提交或夭折。只有在所有的子事務(wù)處理都提交以后，父事務(wù)處理才能夠進(jìn)入提交階段。子事務(wù)處理必須保持事務(wù)處理的ACID特性，子事務(wù)處理提交的結(jié)果只有其父事務(wù)處理才能看見。最后，如果父事務(wù)處理確定它不能進(jìn)入提交階段，那么它及其所有的后代事務(wù)處理都必須卷回。分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

用于嵌套事務(wù)處理的提交協(xié)議準(zhǔn)備提交階段：commitflag=1； //將提交標(biāo)志flag置為1。flagPREPARE-TO-COMMIT(transactiont) //transaction是一個結(jié)構(gòu)變量用于保存

//其用于保存事務(wù)處理t的相關(guān)信息。該

//函數(shù)返回事務(wù)處理t是否準(zhǔn)備好提交。{ IFchildless(transactiont) //如果事務(wù)處理t沒有子事務(wù)處理

THEN flag=flag&Requestcommitment(transactiont) //請求對事物處理t進(jìn)行提交，返回值和

//flag進(jìn)行與操作。只有所有服務(wù)員都同

//意提交，flag的值才能保持為1。

ELSE //如果有子事務(wù)處理，需要遞歸

{ FORALLchildren(transactiont)DO PREPARE-TO-COMMIT(transactiona(currentchild))；

}}分布式數(shù)據(jù)管理

8.3原子事務(wù)處理

用于嵌套事務(wù)處理的提交協(xié)議提交階段：COMMIT-PHASE(transactiont){ IF(flag=1) //準(zhǔn)備提交階段獲得成功，可以進(jìn)入提交階段。

THENIFchildless(transactiont) //如果事務(wù)處理t無子事務(wù)處理

THEN{ Recordinstablestorage(commit,transactiona)；

//將提交記錄項(xiàng)寫入堅(jiān)固存儲器

Notifycommitment(transaction)；

//通知顧客提交階段已經(jīng)開始

} ELSE{ FORALLchildren(transactiona)DO COMMIT-PHASE(transactiona(currentchild))；

}}分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理分布式系統(tǒng)中的系統(tǒng)數(shù)據(jù)庫

系統(tǒng)數(shù)據(jù)庫的分布有三種可能的方式：完全分割方式：數(shù)據(jù)庫的各部分分散到各地點(diǎn)，相互都是不重復(fù)的；完全冗余方式：整個數(shù)據(jù)庫的各個副本分散各處；部分冗余方式：數(shù)據(jù)庫分成若干部分，其中有些部分有副本存放在其他地點(diǎn)。分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理分布式系統(tǒng)中的系統(tǒng)數(shù)據(jù)庫

數(shù)據(jù)庫一致性包含兩個方面：冗余副本的相互一致性和每個副本的內(nèi)部一致性。相互一致性是指整個數(shù)據(jù)庫或其一部分的各副本是相同的。分布式數(shù)據(jù)庫的內(nèi)部一致性是指該數(shù)據(jù)的信息內(nèi)容而言，包含兩個概念：(1)語義完整性：所存儲的數(shù)據(jù)精確地反映該數(shù)據(jù)庫所模仿的客觀世界。這要求檢驗(yàn)對數(shù)據(jù)庫內(nèi)容進(jìn)行修改操作的每個事務(wù)處理在提交任何修改前不違背語義完整性的約束。這實(shí)際上就是我們前面所提到的一致性約束條件。(2)原子事務(wù)處理：作為一個事務(wù)處理的結(jié)果，要求在數(shù)據(jù)庫中和提供給外界的信息中反映出該事務(wù)處理產(chǎn)生的活動，要么全部產(chǎn)生，要么一個也不產(chǎn)生。分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理兼容可串行化

兼容串行化：設(shè)并發(fā)事務(wù)處理T1和T2分別使存儲處理機(jī)P和Q產(chǎn)生活動A1(P)、A1(Q)和A2(P)、A2(Q)，如果A1(P)→A2(P)在P處是正確的串行順序，則在Q處的可兼容串行化應(yīng)為A1(Q)→A2(Q)。復(fù)制控制算法用來保證兼容可串行化，保持?jǐn)?shù)據(jù)庫多副本間的相互一致性。復(fù)制控制算法分為兩大類：表決法和非表決法。表決法是在控制者之間交換報文，對分布式數(shù)據(jù)庫要進(jìn)行的各事務(wù)處理的整個次序達(dá)成一致意見。在同步表決方案中，各控制者對一個給定事務(wù)處理進(jìn)行表決，一旦取得一致意見就共同執(zhí)行此事務(wù)處理的各步驟。在異步表決方案中，允許各控制者和存儲處理機(jī)并發(fā)地對不同事務(wù)處理的請求和執(zhí)行進(jìn)行表決。分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理兼容可串行化

非表決法使用控制優(yōu)先權(quán)，一種方法是在各控制者之間建立主從關(guān)系。分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理主站點(diǎn)方法

一個節(jié)點(diǎn)被指定是主站點(diǎn)，其他是備份的。所有請求直接發(fā)送到主站點(diǎn)。讀請求。主站點(diǎn)只是簡單地讀取并返回結(jié)果。沒有備份站點(diǎn)參與。如果主站點(diǎn)失效，經(jīng)選舉在備份站點(diǎn)中產(chǎn)生一個新的主站點(diǎn)。寫請求。當(dāng)主站點(diǎn)完成更新前收到一個寫請求，它就向至少k個備份站點(diǎn)發(fā)送更新請求。一旦所有站點(diǎn)已經(jīng)收到請求，主站點(diǎn)完成操作再送回結(jié)果。分布式數(shù)據(jù)管理

8.4多副本更新和一致性管理循環(huán)令牌方法

循環(huán)令牌法把全部控制者排成一個虛擬的單向環(huán)，給一個控制者分配一個暫時的唯一的控制優(yōu)先權(quán)。使用循環(huán)令牌方法可以實(shí)現(xiàn)兩種不同的多副本更新協(xié)議：(1)為了在全部控制者/存儲處理機(jī)上發(fā)動執(zhí)行事務(wù)處理，控制者必須等待