443
《雲數據管理：挑戰與機遇》分布式數據管理
分布式數據管理
雲計算建立在過去幾十年計算機科學領域，尤其是在分布式計算和分布式數據管理領域積累的重要概念、協議和模型的基礎上。本章主要討論分布式係統和數據管理的基本背景，其構成了雲數據庫係統的基礎。我們的主要目標是為讀者提供足夠的背景知識，以幫助讀者理解後麵章節的內容。對這些內容比較熟悉的讀者可以直接跳過這些部分。我們同時也為讀者提供了一些關於分布式數據庫係統的參考資料[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（https://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]。
總之，分布式數據庫中的提交協議可能導致高複雜度和潛在的阻塞問題。實際上，其他站點的故障可能導致本地數據不可用。分布式數據庫需要大量的額外開銷來確保執行的正確性。這種對全局同步機製的依賴會限製係統的可擴展性，並對容錯性和數據可用性產生重要影響。上述所有原因及其他因素（與不同地點的數據權限有關）共同導致分布式數據庫的商業化應用較少。
最後更新：2017-05-19 17:02:26