《雲資料管理：挑戰與機遇》分布式資料管理

本節書摘來自華章出版社《雲資料管理：挑戰與機遇》一書中的第1章，第2節，作者迪衛艾肯特·阿格拉沃爾（divyakant agrawal） 蘇迪皮托·達斯（sudipto das）阿姆魯·埃爾·阿巴迪（amr el abbadi），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

分布式資料管理

雲計算建立在過去幾十年計算機科學領域，尤其是在分布式計算和分布式資料管理領域積累的重要概念、協定和模型的基礎上。本章主要讨論分布式系統和資料管理的基本背景，其構成了雲資料庫系統的基礎。我們的主要目标是為讀者提供足夠的背景知識，以幫助讀者了解後面章節的内容。對這些内容比較熟悉的讀者可以直接跳過這些部分。我們同時也為讀者提供了一些關于分布式資料庫系統的參考資料[gray and reuter，1992，2.1　分布式系統

我們首先介紹分布式系統的一些重要基本概念，這些基本概念也是與雲計算和資料中心有關的相關概念和協定的重要基礎。簡單來說，分布式系統就是一些獨立的計算程序或處理器（常稱作節點）的集合，這些節點基于消息傳遞機制，通過通信網絡互相通信。這意味着節點上的程序沒有共享記憶體，擁有獨立的故障模型，不共享相同的時鐘。節點可能會因系統崩潰、停止運作、甚至人為惡意破壞而失效。網絡可能會出現連接配接故障。一般情況下，系統也可能出現分區失效，也就是說，系統被劃分成若幹個子分區，單個子分區内部的節點之間可以互相通信，但是不同分區之間的節點之間無法通信。分區失效的原因可能包括由于網關故障而引起的連接配接故障和節點故障。

分布式系統也可以分為同步系統和異步系統。在異步分布式系統中，消息傳遞的時間、處理器處理時間和本地時鐘漂移時間的界限是未知的。在同步系統中，這些界限都是已知的，是以，可以利用逾時來進行故障檢測，在必要的情況下，也可以執行相應的操作。

2.1.1　邏輯時間和lamport時鐘

lamport于1978年在他的一篇代表性論文裡提出了一個簡單的分布式系統模型[lamport,

1978]。該模型中，程序被模組化成一個全序事件的序列。事件分為本地（local）事件、發送（send）事件和接收（receive）事件。發送事件負責發送消息，該消息由相應的接收事件接收。本地事件是非通信事件，如，記憶體讀寫、矩陣相乘等。圖2-1展示了一個包括4個程序（p1、p2、p3和p4）的分布式系統示例。事件e2和e4在程序p1上執行，事件e1、e3和e9在程序p2執行，等等。事件e3是程序p2上的本地事件，而事件e1是一個發送事件，e2是相應的接收事件。

若兩個事件e和f滿足下列任一條件，則事件e發生在事件f之間，記作e→f：

1. 如果e和f是發生在同一程序内的兩個事件，并且e發生在f之前，那麼e→f；

2. 如果e代表了某個程序的消息發送事件send(m)，f代表另一程序中針對這同一個消息的接收事件receive(m)，那麼e→f；

3. 如果存在一個事件g，滿足e→g并且g→f，那麼e→f。

圖2-1　事件和消息

“發生在前”（happens-before）關系可以很好地反映任意兩個事件之間的潛在因果依賴關系。并且，如果兩個事件e和f既不存在e→f關系，也不存在f→e關系，那麼e和f是并發的。在圖2-1中，事件e4發生在事件e6之前，而事件e3與事件e2和e4都是并發的。

時間概念以及時間與事件之間的關系對很多分布式系統協定來說都是至關重要的。一般情況下，不一定需要實時時鐘或近似實時時鐘，隻要有一個時間概念能夠捕獲潛在的因果關系就足夠了。lamport引入了一種可以捕獲事件之間的潛在因果關系的邏輯時鐘概念。邏輯時鐘為每一個事件e賦一個值clock(e)，是以，對任意兩個事件e和f，存在如下關系：

如果e→f，那麼clock(e)<clock(f)。

為了能夠實作這種邏輯時鐘，lamport為每一個程序設定了一個時鐘計數器。該計數器在同一程序中的任意兩個事件之間都必須是遞增的，并且，每一個消息都攜帶了發送者的時鐘值。當消息到達目的地之後，本地時鐘計數器被設定為本地值的最大值，同時消息的時間戳加1。這種實作方式可以滿足上述邏輯時鐘的條件。

在圖2-2中，使用與圖2-1相同的例子，為系統中的所有事件都賦一個邏輯時間。

圖2-2　lamport時鐘

因為“發生在前”關系是一個偏序，是以，多個事件可能被指派相同的邏輯時鐘。但是，在很多協定中，為每一個事件賦一個唯一的時間值更為友善。這種情況下，為了打破這種關系，時間值可以設定為<t, p>，其中，t是本地時鐘計數器設定的邏輯時間，p是事件執行所在程序的程序辨別。一般情況下，每一個程序都被指派一個唯一的全序的程序辨別，這些程序辨別可以打破具有相同邏輯時間的事件之間的關系。

2.1.2　向量時鐘

邏輯時鐘可以捕獲潛在的因果關系，但是，這并不意味着一定有因果關系，邏輯時鐘條件隻是一個必要條件，并不是充分條件。分布式系統中的所有事件可能需要一個更強的時鐘條件：

e→f當且僅當clock(e)<clock(f)。

該條件可按如下方式實作：為每一程序i賦一個長度為n的向量vi，n是系統中所有程序的數量。每一個執行的事件都被賦一個本地向量。

每個向量都初始化為0，即：vi[j] = 0，其中i, j

= 1, …, n。程序i在每一個事件之前增加本地向量元素的值，vi[j] = vi[j] +1。當程序i發送消息的時候，會将本地向量vi和消息一起發送。當程序j接收消息時，會将接收向量和本地向量的元素逐個進行比較，并将本地向量設定為兩者之中較大的值，vj[i] = max(vi[i], vj[i]), i = 1, …, n。

給定兩個向量v和v'，v=v'當且僅當v[i] = v'[i], i = 1, …, n，并且v≤v'當且僅當v[i]≤v'[i], i = 1, …, n。如果至少存在一個j(1≤j≤n)，使得v[j]<v'[j]，并且，對所有的i≠j，其中，1≤i≤n，v[i]≤v'[i]，則v<v'。對任意兩個事件e和f，e→f當且僅當v(e)<v(f)。如果既不滿足v(e)<v(f)，又不滿足v(f)<v(e)，那麼兩個事件是并發的。

圖2-3中，我們為圖2-1示例中的所有事件都賦了向量時間值。

圖2-3　向量時鐘

雖然向量時間可以準确地捕獲因果關系，但是向量的大小是網絡大小的函數，可能非常大，并且每一個消息都需要攜帶額外的向量。

2.1.3　互斥和仲裁集

互斥是并發程序通路共享資源時涉及的一個基本概念。互斥是作業系統中的一個重要操作，後來也被擴充到資料庫中。互斥可以按照如下方式進行定義：給定一個程序集合和一個單獨的資源，開發一種協定，該協定可以確定在同一時間，一個資源隻能被一個程序進行排他性通路。針對集中式系統和分布式系統都已經提出了多種解決方案。針對分布式互斥問題的一種簡單的集中式解決方案可以設計如下：指定一個程序為協調者，當程序需要通路資源時，發送一個請求消息給協調者。協調者維護一個等待請求隊列。當協調者接收一個請求消息時，檢查該隊列是否為空，如果隊列為空，協調者就為請求用戶端發送一個回複消息，請求用戶端就可以通路共享資源。否則，請求消息就被添加到等待請求隊列中。程序在共享資源上執行完成以後，向協調者發送一個釋放消息。接收到釋放消息以後，協調者從隊列中移除請求，然後為其他等待的請求檢查隊列。該協定已經被lamport[1978]擴充成分布式協定，很多其他研究人員對該協定進行了優化。

該基本協定的普遍應用需要系統中所有程序的參與。為了克服障礙，gifford提出了仲裁集的概念。比較重要的發現是任意兩個請求都應該有一個共同的程序來充當仲裁者。假定程序pi(pj)從集合qi(qj)中請求許可，其中qi和qi是仲裁集，也可以是系統中所有程序的子集。qi和qj的交集不能為空。例如，包括系統中大部分程序的集合就可以構成一個仲裁集。使用仲裁集，而非系統中的所有程序，基本協定仍然有效，但是有可能出現死鎖[maekawa, 1985]。圖2-4a展示了一個包含7個程序的系統，任意一個大于等于4的集合和另外一個大于等于4的集合一定相交，即對于任意兩個仲裁集， 每一個仲裁集都包含大部分站點，它們的交集一定是非空的。

在資料庫中，仲裁集的概念可以了解成基本的讀、寫操作，讀操作不需要互斥。然而，多個讀操作雖然可以并發執行，但是，針對資料的寫操作仍需要互斥通路。是以，設計了兩種仲裁集：讀仲裁集和寫仲裁集，其中，兩個寫仲裁集之間的交集不能為空，一個讀仲裁集和一個寫仲裁集之間的交集也不能為空，針對兩個讀仲裁集的交集沒有強制性要求。圖2-4b展示了一個包含6個程序的系統，寫仲裁集是大小為4的任意集合，讀仲裁集是大小為3的任意集合。需要注意的是，任意讀仲裁集和寫仲裁集必須相交，任意兩個寫仲裁集也必須相交。但是，讀仲裁集之間不一定相交，是以，多個讀操作可以并行執行。

　

a）互斥仲裁集                                                         

b）讀寫仲裁集

圖2-4　仲裁集

2.1.4　上司者選舉

很多分布式算法都需要一個程序來充當協調者，然而，實際當中選擇哪個程序作為協調者通常并不重要。該問題通常被稱為上司者選舉（leader election），其關鍵在于要確定一個唯一的協調者被選中。該協定非常簡單，通常要求每個程序有一個程序編号，所有的程序編号都是唯一并且完全排序的。我們使用具有代表性的bully算法（bully algorithm [garcia-molina,

1982]）來對該協定進行舉例，該算法假設通信是可靠的。其核心思想是努力選擇具有最大程序編号的程序。任何一個程序，如果該程序剛從故障中恢複，或者該程序懷疑目前的協調者失效了，都可以發起新的選舉。有三類消息可以使用：election、ok和i won。

程序可以同時發起選舉。發起程序p向所有擁有較高id的程序發送一個election消息，并等待ok消息。如果沒有收到任何ok消息，則p成為協調者，并向所有擁有較低id的程序發送i won消息。如果該程序收到ok消息，則退出并等待i won消息。如果一個程序收到了election消息，可以傳回。一個ok消息，并發起一個新的選舉。如果程序收到了一個i won消息，則發送者就是協調者。很容易證明bully算法的正确性。選舉協定也可以利用邏輯通信結構或者覆寫網絡（如環）來實作。chang and roberts [1979]設計了這種協定，該協定把所有的節點組織成一個邏輯環，其中每一個程序都知道它的近鄰，目的也是選擇具有最大id的程序作為協調者。一個程序如果剛剛恢複或者檢測到協調者失效，可以發起新的選舉。該程序按順序對後繼節點進行詢問，直到發現活動節點，就把election消息發送給下遊最近的活動節點。每一個接收到election消息的程序把自己的id添加到該消息中并順着環繼續傳遞。一旦消息傳回到發起者，就選擇具有最大id的節點作為上司者并順着環釋出一個特殊的coordinator消息。注意，多個選舉可以并發執行。

2.1.5　基于廣播和多點傳播的組通信

如果資料被複制到多個節點上進行存儲，資料更新操作需要發送給所有的副本。廣播或多點傳播操作是一種簡單的通信原語。一般來說，廣播方式把同一條消息發送給系統中的所有站點，而多點傳播隻發送給部分站點。不失一般性，我們用多點傳播來表示發送資訊到特定的節點集合。下面将介紹已經提出的多種不同的原語，這些原語已經在分布式系統和資料中心等不同場景中得到了應用。

fifo多點傳播或發送者有序的多點傳播：消息按照被發送的順序傳輸（單個發送者）。

因果序多點傳播：如果發送m1和m2兩個消息，并且m1的發送事件在m2的發送事件之前發生，那麼在所有相同的目的地上，m1都必須先于m2傳輸。

全序（或原子）多點傳播：所有消息都以相同的順序發送給接收者。

實作不同多點傳播協定的關鍵在于如何設計一種方法進而保證順序一緻性限制。假設底層網絡隻支援點對點通信，不支援任何多點傳播原語。另外，需要把網絡中消息的接收者和應用層中消息的實際傳輸者進行區分。接收到一條消息之後，該消息被插入到隊列中，當序列條件滿足時，消息才能開始傳輸。下面将對實作這些原語的協定進行描述。圖2-5展示了一個包含3個因果相關多點傳播e1、e2和e3的示例。如果這些多點傳播都是因果相關多點傳播，那麼，部分消息的傳輸就需要推遲，直到因果序條件得到滿足以後才能繼續傳輸。例如，雖然程序r接收到e2的時間比e1的接收者時間早，但是因為e1發生在e2之前，是以，必須等到r對e1完成接收和傳輸之後才能對e2開始傳輸。同樣，e3必須等到e1和e2傳輸完成之後才能開始傳輸。再看另外一個例子，圖2-6也包含了3個多點傳播e1、e2和e3。盡管e1和e2不是因果相關，并且是從不同的程序p和q發出的，如果它們是全序多點傳播的話，那麼所有的站點都要按照相同的順序進行傳輸，而與它們的接收順序無關。例如，雖然程序r接收e2的時間比接收e1的時間早，而在程序s中該順序剛好相反，但是，所有的站點都必須按照相同的順序來傳輸這兩個多點傳播，比如先傳輸e2，再傳輸e1。需要說明的是，即使發送操作是因果相關的，全序也不需要一定要滿足因果序。例如，e2和e3是因果相關的，并且e2發生在e3之前，但是所有的程序仍可能是先傳輸e3，再傳輸e2。

圖2-5　因果序

圖2-6　全序

fifo多點傳播可以用一種類tcp傳輸協定來簡單地實作，即消息發送者可以設定一個有序的消息辨別符，任意一條消息在其之前的消息完成接收和傳輸之前都需要等待。如果有消息丢失了，接受者可以向發送者請求丢失的消息。

因果多點傳播可以通過如下方式來實作：要求每一個廣播消息都攜帶所有因果前置消息。在傳輸之前，接受者必須通過傳輸任何丢失的因果前置消息來確定因果關系。但是，這種協定的開銷非常大。還有另外一種可供選擇的協定（isis [birman, 1985]），該協定使用向量時鐘來延遲消息的傳輸，直到所有的因果前置消息都被傳輸完成。每一個程序負責維護一個長度為n的向量時鐘v，n是系統中節點的數量。v的元素被初始化為0。當節點i發送一個新的消息m時，對應節點i的元素值就加1。每一個消息都與發送者的本地向量組合在一起。當節點發送消息時，該節點需要利用如下方式對其向量進行更新：選擇本地向量和随消息到達的向量之間的元素的較大值來更新。節點i利用向量vt發送消息m，如果向量vt中與發送者相對應的元素剛好比接收端本地向量中的發送者元素大1（即是下一條消息），并且，本地向量的所有元素都大于等于vt中的對應元素，那麼接收者就接收到了所有的因果前置消息。

全序多點傳播可以通過集中式方法來實作，例如固定的協調者（使用在amoeba [kaashoek et al., 1989]中），或者移動令牌等[défago et al., 2004]。另外，isis [birman, 1985]也提出了分布式協定。在isis分布式協定中，所有程序通過三輪來對序号（或優先級）達成一緻意見。發送者将具有唯一辨別符的消息m發送給所有接收者。接受者會建議一個優先級（序号），并把建議的優先級回報給發送者。發送者收集完所有的優先級建議，并确定一個最終的優先級（通過程序編号打破關系），然後針對消息的重新發送最終達成一緻意見的優先級。最後，接收者再按照最終的優先級來傳輸消息m。

2.1.6　一緻性問題

一緻性是一個基本的分布式系統問題，在出現故障的情況下，需要多個步驟來達成一緻[pease et al., 1980]。該問題經常出現在如下場景中：通信是可靠的，但是由于系統崩潰或認為惡意破壞等原因（即未按照指定的協定或代碼進行響應），站點可能會失效。一般而言，該問題可以使用一個單獨的協調者，或稱general，協調者給n-1個參與者發送一個二進制值，并滿足下列條件：

一緻：所有參與者都認同一個值。

正确：如果general是正确的，那麼每一個參與者都認同general發送的值。

接下來介紹兩個不可能出現的結果。在異步系統中，如果程序由于崩潰而失效，并且程序是通過消息傳遞來進行通信的，fischer et al. [1983, 1985]證明一緻性是不可能解決的。另一方面，在一個存在惡意故障的同步系統中，dolev [1982] 證明了如果一個系統的程序數量小于3f+1，其中，f是故障（惡意）程序的最大值，那麼該系統也無法解決一緻性問題。

已經有多種協定可以用來解決同步系統和異步系統中的一緻性問題。同步系統需要指定惡意故障站點的最大數量的上界，如三分之一。另一方面，異步系統可能無法確定系統能夠終止。近來，lamport [1998, 2001]為異步系統開發的paxos協定廣受歡迎。抽象地講，paxos是一個以上司者為基礎的（leader-based）的協定，每一個程序都可以估計目前的上司者是誰。當一個程序希望在某個值上達成一緻時，程序就把該值發送給上司者。上司者對操作進行排序并通過一緻性算法來實作一緻。通常情況下，該協定經曆兩個階段。在每一個階段，上司者會與大部分站點進行聯系，往往會有多個并發的上司者。用投票來區分不同上司者提供的值。兩個階段的具體過程可以總結如下：第一階段，又稱為準備階段，認為自己是上司者的節點可以選擇一個新的唯一的投票号碼，并把該号碼發送給所有的站點，然後等待來自大部分站點的較小的投票号碼的結果。第二階段，又稱接受階段，上司者根據自己的投票号碼建議一個值。如果上司者能夠獲得大多數支援，那麼該值就會被接受，其他站點也會用對應的投票号碼對該值進行判斷。圖2-7展示了基于paxos協定的不同程序之間的通信模式。

圖2-7　基于paxos協定的通信

2.1.7　cap理論

brewer[2000]提出了下列理論，後來由gilbert and lynch[2002]加以證明：一個分布式共享資料系統最多同時滿足下列三個屬性中的兩種：

一緻性（c）

可用性（a）

網絡分區容忍性（p）

該理論就是著名的cap理論。一般情況下，大規模雲資料中心的分布式系統需要支援分區，以便能夠處理大規模操作。此時，在進行網絡劃分的過程中，根據cap理論的要求，就需要在一緻性和可用性之間做出選擇。傳統的資料庫系統選擇一緻性，而一些最新出現的資料存儲系統，如鍵-值存儲系統，比較偏愛可用性。brewer[2012]對cap理論的其他分支進行了評估，并對該理論中的任意兩個方面的細微差别進行了較長的描述。在分區故障不經常出現的情況下，可以設計一種大部分時間内兼顧一緻性和可用性的系統。但是，當分區故障發生時，就需要采取一定的政策去檢測分區，并開發最合适的政策對這種情況加以處理。另一個需着重強調的重要方面是延遲與分區之間的重要關系，分區歸因于逾時，是以，從使用的觀點來看，分區故障是有時間限制的。gilbert and lynch [2012]對該問題進行了進一步的較長的描述，cap理論被認為是對不可靠分布式系統中安全性和活躍性之間進行均衡的一種描述，這與出現故障的異步系統中不可能存在分布式一緻性有密切關系[fischer et al., 1983]。

2.2　p2p系統

作為傳統的用戶端–伺服器模式的另外一種可替代方式，p2p（peer-to-peer）架構提供了一種可行的方案，p2p系統中的很多技術都已經在資料中心中得到了成功應用。p2p系統的主要目标是在數百萬并發使用者的情況下，確定數十億對象的可用性，如音樂檔案。為了實作上述目标，必須在實體網絡之上建構一層虛拟的或邏輯的覆寫（overlay）網絡。抽象地講，覆寫建構了不同站點之間的互相通信方式以及資料存儲方式。最簡單的形式是一個對象可以看成是一個鍵–值對。覆寫提供了對象檢索方法，并支援兩種基本操作：給定一個鍵和值，可以把鍵–值元組插入（insert）到覆寫中，同時，給定一個鍵值，可以查詢（lookup）并傳回對應的值。覆寫一般可以表示成圖的形式，以站點為節點，用邊來連接配接不同的站點，可以分為結構化覆寫和非結構化覆寫。

非結構化覆寫沒有在節點間的邏輯圖上增加任何特定的結構。集中式方案是這種p2p設計的最簡單實作，最早由napster[carlsson and gustavsson,

2001]加以應用，napster方案用一個中央伺服器來存儲所有的鍵值和用來辨別這些鍵值所在網絡節點的資料庫。每次鍵–值元組的查找都需要通路中央伺服器。napster于1999年釋出，最高同時150萬使用者線上，2001年7月由于法律問題關閉。

除此之外，gnutella（http://en.wikipedia.org/wiki/gnutella）使用了分布式設計，每個節點都有若幹個鄰居，并且在本地資料庫中存儲若幹個鍵。當需要查找鍵k時，某個站點首先檢查自己的本地資料庫，判斷k是否在本地。如果在本地，則直接傳回相應的值，否則，該站點遞歸地詢問鄰居站點。通常情況下，需要使用一個限制門檻值來限定消息的無限制傳播。

另外一方面，結構化覆寫在不同的節點上強加了具有良好定義的資料結構。這種資料結構一般稱作分布式哈希表（distributed hash table, dht），dht可以将對象映射到不同的站點，并且，給定相應的鍵，dht可以快速檢索相應的資料對象。特别是，在結構化覆寫中，邊是按照特定的規則選擇的，資料被存儲在預先确定的站點上。通常情況下，每一個站點負責維護一個表，該表存儲了用于查找操作的下一跳（next-hop）。我們将用一種非常流行的稱為chord[stoica et al.,

2001]的p2p系統來對結構化覆寫進行舉例說明。在chord中，每一個節點都使用一緻性哈希函數（如sha-1）進行哈希，哈希到一個m位的辨別符空間中（2m個id），其中，m一般取160。所有的站點依據各自的id号被組織成一個邏輯環。鍵也被哈希到相同的辨別符空間中，鍵（及其相應的值）存儲在後繼節點中，即下一個具有較大id的節點。

一緻性哈希可以確定：對任何n個節點和k個鍵的集合，一個節點最多負責個(1+∈)k/n鍵。另外，當一個新的節點加入或離開時，o(k/n)個鍵需要移動。為了支援高效和可擴充的查詢，系統中的每一個節點都需要維護一個查詢表（finger table）。節點n的查詢表的第i個元素是第一個後繼節點或者等于n+2i。圖2-8展示了針對不同的網絡規模，一個給定節點的路由表中的指針。換句話說，第i個指針沿着環指向1/2(m–i)方向。當接收到一個針對id項的查詢時，節點首先檢查是否存儲在本地。如果不在本地，則将該查詢往前發送給其查詢表中最大的節點。假設chord環中的節點呈正态分布，每一步中搜尋空間的節點數量減半。是以，查詢跳數的期望值是o(logn)，其中，n是chord環中節點的數量。

圖2-8　chord中的路由表指針

2.3　資料庫系統

本節中，我們将為資料庫系統中的一些主要概念提供一個相當抽象、簡潔和高層次的描述。知識體系與bernstein et al. [1987]一緻。對資料庫知識比較熟悉的讀者可以跳過本部分内容。

2.3.1　預備知識

資料庫由對象的集合組成，如x、y、z。假設每個對象都有一個值，所有對象的值構成了資料庫的狀态。通常情況下，這些狀态必須滿足資料庫的一緻性限制。資料庫對象支援兩種原子操作：針對x的讀和針對x的寫，或者r[x]和w[x]。事務的概念在資料庫系統中至關重要。一個事務是按照一定偏序執行的操作的集合。事務ti執行的操作記作ri[x]和wi[x]。如果一個事務是正确的，即，如果一個事務在一緻資料庫上單獨執行，那麼該事務可以将資料庫轉換成另外一個一緻狀态。

事務的執行必須是原子的，即必須滿足如下兩個屬性：

1. 事務之間互不幹擾。

2. 事務中的操作要麼全部執行，要麼都不執行。

事務ti以commit(ci)或abort(ai)操作結束。并發控制協定可以確定并發執行的事務彼此之間互不影響。恢複協定可以確定all-or-nothing屬性。

如果兩個操作的執行順序對結果有影響，即，如果其中一個是寫操作，那麼這兩個操作是沖突的。給定一個事務集合t，t上的一個曆史h是針對所有事務操作的偏序，該順序反映了操作執行的順序（事務順序和沖突操作順序）。

資料庫管理系統必須滿足acid特性，即

原子性（atomicity）：每個事務要麼全部執行，要麼都不執行，即all-or-none屬性。

一緻性（consistency）：每個事務是一個一緻的執行機關。

隔離型（isolation）：事務之間互不影響。

持久性（durability）：事務的效果是永久的。

當一個并發事務集合執行時，事務的正确性概念必須以每一個事務都是一緻的（acid中的c）為前提，是以，如果事務是隔離執行的，資料庫将從一個一緻狀态轉換成另外一個一緻狀态。是以，如果事務集合串行執行，那麼可以保證其正确性。特别是，對于一個排程h中的任意兩個事務ti和tj，如果ti的所有操作在h中都位于tj的所有操作之前，或者相反，那麼h是串行的。

為了允許事務之間在一定程度上并發執行，産生了可串行化的概念。如果一個曆史的執行結果與一個串行曆史的執行結果等價，那麼該曆史是可串行化的。如果兩個曆史産生相同的結果，即所有的事務寫入相同的值，我們認為這兩個曆史是等價的。由于我們不知道哪些事務執行寫操作，事務就需要從相同的事務中讀資料，最終寫入的值也相同。不幸的是，識别可串行化的曆史是np完全問題[papadimitriou, 1979]。是以，産生了一個更強的可串行性概念，稱之為沖突可串行性。

回想一下，如果針對相同對象的兩個操作中，至少有一個是寫操作，那麼這兩個操作是沖突的。如果兩個曆史h1和h2定義在相同的操作集合之上（相應的事務集合也相同），并且這兩個曆史中所有的沖突操作的順序都一緻，那麼h1和h2是沖突等價的。如果一個曆史h和某一個串行曆史hs是沖突等價的，那麼h就是沖突可串行化的。既然串行執行是正确的，那麼就可以保證沖突可串行化曆史也是正确的。

2.3.2　并發控制

并發控制協定必須能夠保證沖突可串行性。并發控制協定一般可以分為悲觀協定（pessimistic protocol）和樂觀協定（optimistic

protocol）兩種，悲觀協定使用鎖來避免錯誤的操作，而樂觀協定是在送出階段采用驗證器（certifier或validator）來保證正确性。一般情況下，從技術的角度來看，任何并發控制協定都可以很容易地擴充到分布式環境中。

封鎖協定

對于每一個操作，事務（或并發控制排程器）都會申請一個鎖，每個鎖都有兩種模式：讀和寫。兩個讀鎖是相容的，而兩個寫鎖或者一個讀鎖和一個寫鎖是不相容的。如果一個資料項沒有以不相容的模式封鎖，那麼該資料項就可以授予鎖。否則，存在一個鎖沖突，并且事務處于封鎖狀态（會經曆鎖等待）直到目前的鎖持有者釋放鎖。一個操作執行完成後，相應的鎖就會被釋放。鎖本身不足以保證正确性。兩段鎖協定增加了下列條件，以下條件足以保證沖突可串行性[eswaran et al., 1976]：

一旦一個事務釋放了一個鎖，該事務不能随即擷取任何資料項的任何其他鎖。

圖2-9顯示，在擴充階段，事務所需要的鎖的數量不斷增加，在收縮階段，鎖的資料逐漸減少。

圖2-9　兩段鎖

兩段鎖在很多商業化系統中廣受歡迎，尤其是嚴格版本，在事務結束之前（即送出或中斷），保留所有的鎖。然而，兩段鎖可能會出現死鎖。而且由于沖突操作的存在，資料項隊列可能導緻資料沖突。這種沖突可能導緻系統抖動（在正常多道程式設計系統中，資源沖突一般是由記憶體、處理器、i/o通道引起的，而不是資料引起的沖突）。

樂觀協定

如上所述，封鎖可能造成長時間的資源阻塞。樂觀并發控制協定可以允許事務執行所有操作，并使用驗證方法來判斷其他事務是否執行了沖突操作，通過這種方式可以有效避免這種阻塞。最簡單的情況是，事務t1執行其所有操作（寫操作會導緻本地緩存更新）。當事務送出時，排程器會檢查是否有活動的事務執行了沖突操作，如果有，就中止t1。

kung and robinson [1981]對上述簡單思想進行了擴充，通過三個階段來執行每個事務t1：

讀階段。在該階段，事務可以無限制地讀取任何對象，而寫是本地的。

驗證階段。在該節點，排程器通過檢查所有的并發事務t2進而確定沒有沖突發生，即可以檢查事務t2在其寫階段進行寫操作的對象集合與事務t1在其讀階段進行讀操作的對象集合是否重疊，如果有重疊，則中止t1。

寫階段。驗證成功以後，值可以寫入資料庫中。

簡單的正确性證明顯示樂觀并發控制可以確定事務的可串行化執行。該協定出現了很多種變體，而且由于樂觀協定在資料資源上不會産生排它鎖，是以，樂觀協定在雲計算環境中的應用越來越廣泛。

2.3.3　恢複和送出

集中式恢複

故障恢複是資料庫管理系統不可分割的一部分。集中式恢複可以在單站點資料庫在磁盤上存儲所有資料時確定其持久性或永久性。為了在確定原子性的同時實作故障恢複，很多機制在事務執行的過程中都使用持久性儲存設備，如磁盤，進而確定all-or-nothing屬性。下面是3種常用的方案。

1. 影子頁：在磁盤上儲存兩份資料庫備份，其中一個用于事務更新，當事務送出時，原子指針切換到新的資料庫備份。

2. 前像檔案：磁盤日志用來存儲所有更新資料項的前像檔案（before-image），事務會立即更新實體資料庫。一旦故障出現并且事務尚未送出，資料庫就會根據日志恢複到初始狀态。

3. 後像檔案：所有更新操作在後像檔案（after image）日志中執行。事務送出後，根據日志，将所有的後像檔案裝載到資料庫中。

在這些基本概念的基礎上，提出了各種各樣的恢複方法。這些方法以不同的方式對前像檔案日志和後像檔案日志進行組合，進而提高送出事務或中止事務的性能[bernstein and newcomer, 2009, gray and reuter, 1992, weikum and

vossen, 2001]。

從集中式資料庫擴充到分布式資料庫（即對象可能存在于不同的站點上）的關鍵挑戰是：當故障出現時，如何在不同站點之間確定原子性。下面将介紹主要的分布式送出協定。

原子送出（atomic commitment）

送出的根本問題是由于事務在多個伺服器上執行操作而引起的。全局送出需要所有參與者的一緻本地送出。分布式系統可能會部分失效，在特殊情況下，伺服器可能崩潰，極端情況下，會出現網絡故障，進而導緻網絡劃分。這可能會導緻不一緻的決定，即，在某些伺服器上事務完成了送出，而在其他伺服器上，事務卻中止了。

基本的原子送出協定是一種簡單的分布式握手協定，稱為兩階段送出協定（two-phase commit, 2pc）[gray, 1978]。在該協定中，協調者（事務管理者）負責一緻決定：送出或中止。其他所有的執行事務的資料庫伺服器在該協定中都是參與者，都依賴于該協調者。送出時，協調者向所有參與者請求選票。原子送出要求所有程序得到相同的決定，特别是，隻有當所有程序都投贊成（yes）票時，事務才能送出。是以，如果沒有故障發生，并且所有的程序都投贊成（yes）票時，最終結果才可以送出。

該協定執行過程如下。協調者向所有參與者發送投票請求（vote-request）。當參與者接收到投票請求消息時，如果能本地送出，就傳回一個yes消息，如果需要中止該事務（由于死鎖或者無法把本地操作寫到磁盤上），就傳回no消息。協調者收集所有投票，如果都是贊成票（yes），那麼就認為事務已經送出，否則事務就被中止了。協調者将結果發送給所有參與者，參與者相應地對本地事務進行送出或中止。

如果一個站點沒有接收到預期的消息，該站點會怎麼做呢？注意，該協定假設分布式系統是異步的，是以，其中有一個逾時機制。有以下3種情況需要考慮。

1. 參與者等待投票請求：這種情況下，參與者在本地中止事務是安全的。

2. 協調者等待投票：這種情況下，協調者也可以安全地中止事務。

3. 參與者等待最終決定：這是一種不确定的情況，由于事務可能已經送出或者中止，是以，參與者也可能是不确定的，參與者可能不知道實際的決定。而有趣的是，協調者是确定的。

接下來詳細探讨不确定參與者的情況。實際上，該參與者可以向其他參與者詢問最終決定并尋求幫助。一旦任何參與者已送出或中止，該參與者就可以發送送出或中止決定。如果一個參與者尚未投票，那麼它就可以安全地中止該事務，并可以向其他參與者發送中止決定。然而，如果所有參與者都投贊成票（yes），那麼所有活動的參與者都是不确定的。這種情況下，該事務就被認為已阻塞，所有活動的參與者都需要一直等待，直到有足夠多的站點贊成該事務進行恢複的決定。直覺來看，活動的參與者處于不确定狀态，其他一些失敗的參與者可能處于送出狀态，還有一些參與者處于中止狀态。一般來說，兩階段送出協定即使是在簡單的系統崩潰故障情況下也可能存在阻塞問題。

為了解決阻塞問題，可以引入中間緩沖狀态，這樣一來，如果任何運作站點是不确定的，那麼，所有程序都不能送出[skeen and stonebraker,1983]。這種協定就是三階段送出協定，該協定在站點故障情況下是非阻塞的。然而，三階段送出協定不允許分區故障。實際上，可以證明在分區故障情況下，不存在非阻塞原子送出協定[skeen and stonebraker, 1983]。

總之，分布式資料庫中的送出協定可能導緻高複雜度和潛在的阻塞問題。實際上，其他站點的故障可能導緻本地資料不可用。分布式資料庫需要大量的額外開銷來確定執行的正确性。這種對全局同步機制的依賴會限制系統的可擴充性，并對容錯性和資料可用性産生重要影響。上述所有原因及其他因素（與不同地點的資料權限有關）共同導緻分布式資料庫的商業化應用較少。