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

本節書摘來自華章出版社《雲資料管理：挑戰與機遇》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

第2章

分布式資料管理

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