本文另一地址請見(jiàn)NoSQL數據庫的分布式算法
本文譯自 Distributed Algorithms in NoSQL Databases
系統的可擴展性是推動(dòng)NoSQL運動(dòng)發(fā)展的的主要理由，包含了分布式系統協(xié)調，故障轉移，資源管理和許多其他特性。這么講使得NoSQL聽(tīng)起來(lái)像是一個(gè)大筐，什么都能塞進(jìn)去。盡管NoSQL運動(dòng)并沒(méi)有給分布式數據處理帶來(lái)根本性的技術(shù)變革，但是依然引發(fā)了鋪天蓋地的關(guān)于各種協(xié)議和算法的研究以及實(shí)踐。正是通過(guò)這些嘗試逐漸總結出了一些行之有效的數據庫構建方法。在這篇文章里，我將針對NoSQL數據庫的分布式特點(diǎn)進(jìn)行一些系統化的描述。
接下來(lái)我們將研究一些分布式策略，比如故障檢測中的復制，這些策略用黑體字標出，被分為三段：
眾所周知，分布式系統經(jīng)常會(huì )遇到網(wǎng)絡(luò )隔離或是延遲的情況，在這種情況下隔離的部分是不可用的，因此要保持高可用性而不犧牲一致性是不可能的。這一事實(shí)通常被稱(chēng)作“CAP理論”。然而，一致性在分布式系統中是一個(gè)非常昂貴的東西，所以經(jīng)常需要在這上面做一些讓步，不只是針對可用性，還有多種權衡。為了研究這些權衡，我們注意到分布式系統的一致性問(wèn)題是由數據隔離和復制引起的，所以我們將從研究復制的特點(diǎn)開(kāi)始：
現在讓我們仔細看看常用的復制技術(shù)，并按照描述的特點(diǎn)給他們分一下類(lèi)。第一幅圖描繪了不同技術(shù)之間的邏輯關(guān)系和不同技術(shù)在系統的一致性、擴展性、可用性、延遲性之間的權衡坐標。 第二張圖詳細描繪了每個(gè)技術(shù)。
復本因子是4。讀寫(xiě)協(xié)調者可以是一個(gè)外部客戶(hù)端或是一個(gè)內部代理節點(diǎn)。
我們會(huì )依據一致性從弱到強把所有的技術(shù)過(guò)一遍：
上面分析中的一些權衡有必要再強調一下：
讓我們從以下場(chǎng)景開(kāi)始：
有許多節點(diǎn)，每條數據會(huì )在其中的若干的節點(diǎn)上面存有副本。每個(gè)節點(diǎn)都可以單獨處理更新請求，每個(gè)節點(diǎn)定期和其他節點(diǎn)同步狀態(tài)，如此一段時(shí)間之后所有的副本都會(huì )趨向一致。同步過(guò)程是怎樣進(jìn)行的？同步何時(shí)開(kāi)始？怎樣選擇同步的對象？怎么交換數據？我們假定兩個(gè)節點(diǎn)總是用較新版本的數據覆蓋舊的數據或者兩個(gè)版本都保留以待應用層處理。
這個(gè)問(wèn)題常見(jiàn)于數據一致性維護和集群狀態(tài)同步（如集群成員信息傳播）等場(chǎng)景。雖然引入一個(gè)監控數據庫并制定同步計劃的協(xié)調者可以解決這個(gè)問(wèn)題，但是去中心化的數據庫能夠提供更好的容錯性。去中心化的主要做法是利用精心設計的傳染協(xié)議[7]，這種協(xié)議相對簡(jiǎn)單，但是提供了很好的收斂時(shí)間，而且能夠容忍任何節點(diǎn)的失效和網(wǎng)絡(luò )隔離。盡管有許多類(lèi)型的傳染算法，我們只關(guān)注反熵協(xié)議，因為NoSQL數據庫都在使用它。
反熵協(xié)議假定同步會(huì )按照一個(gè)固定進(jìn)度表執行，每個(gè)節點(diǎn)定期隨機或是按照某種規則選擇另外一個(gè)節點(diǎn)交換數據，消除差異。有三種反風(fēng)格的反熵協(xié)議：推，拉和混合。推協(xié)議的原理是簡(jiǎn)單選取一個(gè)隨機節點(diǎn)然后把數據狀態(tài)發(fā)送過(guò)去。在真實(shí)應用中將全部數據都推送出去顯然是愚蠢的，所以節點(diǎn)一般按照下圖所示的方式工作。
節點(diǎn)A作為同步發(fā)起者準備好一份數據摘要，里面包含了A上數據的指紋。節點(diǎn)B接收到摘要之后將摘要中的數據與本地數據進(jìn)行比較，并將數據差異做成一份摘要返回給A。最后，A發(fā)送一個(gè)更新給B，B再更新數據。拉方式和混合方式的協(xié)議與此類(lèi)似，就如上圖所示的。
反熵協(xié)議提供了足夠好的收斂時(shí)間和擴展性。下圖展示了一個(gè)在100個(gè)節點(diǎn)的集群中傳播一個(gè)更新的模擬結果。在每次迭代中，每個(gè)節點(diǎn)只與一個(gè)隨機選取的對等節點(diǎn)發(fā)生聯(lián)系。
可以看到，拉方式的收斂性比推方式更好，這可以從理論上得到證明[7]。而且推方式還存在一個(gè)“收斂尾巴”的問(wèn)題。在多次迭代之后，盡管幾乎遍歷到了所有的節點(diǎn)，但還是有很少的一部分沒(méi)受到影響。與單純的推和拉方式相比， 混合方式的效率更高，所以實(shí)際應用中通常使用這種方式。反熵是可擴展的，因為平均轉換時(shí)間以集群規模的對數函數形式增長(cháng)。
盡管這些技術(shù)看起來(lái)很簡(jiǎn)單，仍然有許多研究關(guān)注于不同約束條件下反熵協(xié)議的性能表現。其中之一通過(guò)一種更有效的結構使用網(wǎng)絡(luò )拓撲來(lái)取代隨機選取 [10] 。在網(wǎng)絡(luò )帶寬有限的條件下調整傳輸率或使用先進(jìn)的規則來(lái)選取要同步的數據 [9]。摘要計算也面臨挑戰，數據庫會(huì )維護一份最近更新的日志以有助于摘要計算。
在上一節我們假定兩個(gè)節點(diǎn)總是合并他們的數據版本。但要解決更新沖突并不容易，讓所有副本都最終達到一個(gè)語(yǔ)義上正確的值出乎意料的難。一個(gè)眾所周知的例子是Amazon Dynamo數據庫[8]中已經(jīng)刪除的條目可以重現。
我們假設一個(gè)例子來(lái)說(shuō)明這個(gè)問(wèn)題：數據庫維護一個(gè)邏輯上的全局計數器，每個(gè)節點(diǎn)可以增加或者減少計數。雖然每個(gè)節點(diǎn)可以在本地維護一個(gè)自己的值，但這些本地計數卻不能通過(guò)簡(jiǎn)單的加減來(lái)合并。假設這樣一個(gè)例子：有三個(gè)節點(diǎn)A、B和C，每個(gè)節點(diǎn)執行了一次加操作。如果A從B獲得一個(gè)值，并且加到本地副本上，然后C從B獲得值，然后C再從A獲得值，那么C最后的值是4，而這是錯誤的。解決這個(gè)問(wèn)題的方法是用一個(gè)類(lèi)似于向量時(shí)鐘[19]的數據結構為每個(gè)節點(diǎn)維護一對計數器[1]：
1 class Counter { 2 int[] plus 3 int[] minus 4 int NODE_ID 5 6 increment() { 7 plus[NODE_ID]++ 8 } 9 10 decrement() {11 minus[NODE_ID]++12 }13 14 get() {15 return sum(plus) – sum(minus)16 }17 18 merge(Counter other) {19 for i in 1..MAX_ID {20 plus[i] = max(plus[i], other.plus[i])21 minus[i] = max(minus[i], other.minus[i])22 }
23 }24 }
Cassandra用類(lèi)似的方法計數[11]。利用基于狀態(tài)的或是基于操作的復制理論也可以設計出更復雜的最終一致的數據結構。例如，[1]中就提及了一系列這樣的數據結構，包括：
最終一致數據類(lèi)型的功能通常是有限的，還會(huì )帶來(lái)額外的性能開(kāi)銷(xiāo)。
這部分主要關(guān)注控制在分布式數據庫中放置數據的算法。這些算法負責把數據項映射到合適的物理節點(diǎn)上，在節點(diǎn)間遷移數據以及像內存這樣的資源的全局調配。
我們還是從一個(gè)簡(jiǎn)單的協(xié)議開(kāi)始，它可以提供集群節點(diǎn)間無(wú)縫的數據遷移。這常發(fā)生于像集群擴容（加入新節點(diǎn)），故障轉移（一些節點(diǎn)宕機）或是均衡數據（數據在節點(diǎn)間的分布不均衡）這樣的場(chǎng)景。如下圖A中所描繪的場(chǎng)景 - 有三個(gè)節點(diǎn)，數據隨便分布在三個(gè)節點(diǎn)上（假設數據都是key-value型）。
如果數據庫不支持數據內部均衡，就要在每個(gè)節點(diǎn)上發(fā)布數據庫實(shí)例，如上面圖B所示。這需要手動(dòng)進(jìn)行集群擴展，停掉要遷移的數據庫實(shí)例，把它轉移到新節點(diǎn)上，再在新節點(diǎn)上啟動(dòng)，如圖C所示。盡管數據庫能夠監控到每一條記錄，包括MongoDB, Oracle Coherence, 和還在開(kāi)發(fā)中的 Redis Cluster 在內的許多系統仍然使用的是自動(dòng)均衡技術(shù)。也即，將數據分片并把每個(gè)數據分片作為遷移的最小單位，這是基于效率的考慮。很明顯分片數會(huì )比節點(diǎn)數多，數據分片可以在各節點(diǎn)間平均分布。按照一種簡(jiǎn)單的協(xié)議即可實(shí)現無(wú)縫數據遷移，這個(gè)協(xié)議可以在遷移數據分片的時(shí)候重定向客戶(hù)的數據遷出節點(diǎn)和遷入節點(diǎn)。下圖描繪了一個(gè)Redis Cluster中實(shí)現的get（key）邏輯的狀態(tài)機。
假定每個(gè)節點(diǎn)都知道集群拓撲，能夠把任意key映射到相應的數據分片，把數據分片映射到節點(diǎn)。如果節點(diǎn)判斷被請求的key屬于本地分片，就會(huì )在本地查找（上圖中上面的方框）。假如節點(diǎn)判斷請求的key屬于另一個(gè)節點(diǎn)X，他會(huì )發(fā)送一個(gè)永久重定向命令給客戶(hù)端（上圖中下方的方框）。永久重定向意味著(zhù)客戶(hù)端可以緩存分片和節點(diǎn)間的映射關(guān)系。如果分片遷移正在進(jìn)行，遷出節點(diǎn)和遷入節點(diǎn)會(huì )標記相應的分片并且將分片的數據加鎖逐條加鎖然后開(kāi)始移動(dòng)。遷出節點(diǎn)首先會(huì )在本地查找key，如果沒(méi)有找到，重定向客戶(hù)端到遷入節點(diǎn)，假如key已經(jīng)遷移完畢的話(huà)。這種重定向是一次性的，并且不能被緩存。遷入節點(diǎn)在本地處理重定向，但定期查詢(xún)在遷移還沒(méi)完成前被永久重定向。
我們關(guān)注的另一個(gè)問(wèn)題是怎么把記錄映射到物理節點(diǎn)。比較直接的方法是用一張表來(lái)記錄每個(gè)范圍的key與節點(diǎn)的映射關(guān)系，一個(gè)范圍的key對應到一個(gè)節點(diǎn)，或者用key的hash值與節點(diǎn)數取模得到的值作為節點(diǎn)ID。但是hash取模的方法在集群發(fā)生更改的情況下就不是很好用，因為增加或者減少節點(diǎn)都會(huì )引起集群內的數據徹底重排。導致很難進(jìn)行復制和故障恢復。
有許多方法在復制和故障恢復的角度進(jìn)行了增強。最著(zhù)名的就是一致性hash。網(wǎng)上已經(jīng)有很多關(guān)于一致性hash的介紹了，所以在這里我只提供一個(gè)基本介紹，僅僅為了文章內容的完整性。下圖描繪了一致性hash的基本原理：
一致性hash從根本上來(lái)講是一個(gè)鍵值映射結構 - 它把鍵（通常是hash過(guò)的）映射到物理節點(diǎn)。鍵經(jīng)過(guò)hash之后的取值空間是一個(gè)有序的定長(cháng)二進(jìn)制字符串，很顯然每個(gè)在此范圍內的鍵都會(huì )被映射到圖A中A、B、C三個(gè)節點(diǎn)中的某一個(gè)。為了副本復制，將取值空間閉合成一個(gè)環(huán)，沿環(huán)順時(shí)針前行直到所有副本都被映射到合適的節點(diǎn)上，如圖B所示。換句話(huà)說(shuō)，Y將被定位在節點(diǎn)B上，因為它在B的范圍內，第一個(gè)副本應該放置在C，第二個(gè)副本放置在A(yíng)，以此類(lèi)推。
這種結構的好處體現在增加或減少一個(gè)節點(diǎn)的時(shí)候，因為它只會(huì )引起臨接區域的數據重新均衡。如圖C所示，節點(diǎn)D的加入只會(huì )對數據項X產(chǎn)生影響而對Y無(wú)影響。同樣，移除節點(diǎn)B（或者B失效）只會(huì )影響Y和X的副本，而不會(huì )對X自身造成影響。但是，正如參考資料[8]中所提到的，這種做法在帶來(lái)好處的同時(shí)也有弱點(diǎn)，那就是重新均衡的負擔都由鄰節點(diǎn)承受了，它們將移動(dòng)大量的數據。通過(guò)將每個(gè)節點(diǎn)映射到多個(gè)范圍而不是一個(gè)范圍可以一定程度上減輕這個(gè)問(wèn)題帶來(lái)的不利影響，如圖D所示。這是一個(gè)折中，它避免了重新均衡數據時(shí)負載過(guò)于集中，但是與基于模塊的映射相比，保持了總均衡數量適當降低。
給大規模的集群維護一個(gè)完整連貫的hash環(huán)很不容易。對于相對小一點(diǎn)的數據庫集群就不會(huì )有問(wèn)題，研究如何在對等網(wǎng)絡(luò )中將數據放置與網(wǎng)絡(luò )路由結合起來(lái)很有意思。一個(gè)比較好的例子是Chord算法，它使環(huán)的完整性讓步于單個(gè)節點(diǎn)的查找效率。Chord算法也使用了環(huán)映射鍵到節點(diǎn)的理念，在這方面和一致性hash很相似。不同的是，一個(gè)特定節點(diǎn)維護一個(gè)短列表，列表中的節點(diǎn)在環(huán)上的邏輯位置是指數增長(cháng)的（如下圖）。這使得可以使用二分搜索只需要幾次網(wǎng)絡(luò )跳躍就可以定位一個(gè)鍵。
這張圖畫(huà)的是一個(gè)由16個(gè)節點(diǎn)組成的集群，描繪了節點(diǎn)A是如何查找放在節點(diǎn)D上的key的。 (A) 描繪了路由，(B) 描繪了環(huán)針對節點(diǎn)A、B、C的局部圖像。在參考資料[15]中有更多關(guān)于分散式系統中的數據復制的內容。
當只需要通過(guò)主鍵來(lái)訪(fǎng)問(wèn)數據的時(shí)候，一致性hash的數據放置策略很有效，但是當需要按照多個(gè)屬性來(lái)查詢(xún)的時(shí)候事情就會(huì )復雜得多。一種簡(jiǎn)單的做法（MongoDB使用的）是用主鍵來(lái)分布數據而不考慮其他屬性。這樣做的結果是依據主鍵的查詢(xún)可以被路由到接個(gè)合適的節點(diǎn)上，但是對其他查詢(xún)的處理就要遍歷集群的所有節點(diǎn)。查詢(xún)效率的不均衡造成下面的問(wèn)題：
有一個(gè)數據集，其中的每條數據都有若干屬性和相應的值。是否有一種數據分布策略能夠使得限定了任意多個(gè)屬性的查詢(xún)會(huì )被交予盡量少的幾個(gè)節點(diǎn)執行？
HyperDex數據庫提供了一種解決方案?；舅枷胧前衙總€(gè)屬性視作多維空間中的一個(gè)軸，將空間中的區域映射到物理節點(diǎn)上。一次查詢(xún)會(huì )被對應到一個(gè)由空間中多個(gè)相鄰區域組成的超平面，所以只有這些區域與該查詢(xún)有關(guān)。讓我們看看參考資料[6]中的一個(gè)例子：
每一條數據都是一條用戶(hù)信息，有三個(gè)屬性First Name 、Last Name 和Phone Number。這些屬性被視作一個(gè)三維空間，可行的數據分布策略是將每個(gè)象限映射到一個(gè)物理節點(diǎn)。像“First Name = John”這樣的查詢(xún)對應到一個(gè)貫穿4個(gè)象限的平面，也即只有4個(gè)節點(diǎn)會(huì )參與處理此次查詢(xún)。有兩個(gè)屬性限制的查詢(xún)對應于一條貫穿兩個(gè)象限的直線(xiàn)，如上圖所示，因此只有2個(gè)節點(diǎn)會(huì )參與處理。
這個(gè)方法的問(wèn)題是空間象限會(huì )呈屬性數的指數函數增長(cháng)。結果就會(huì )是，只有幾個(gè)屬性限制的查詢(xún)會(huì )投射到許多個(gè)空間區域，也即許多臺服務(wù)器。將一個(gè)屬性較多的數據項拆分成幾個(gè)屬性相對較少的子項，并將每個(gè)子項都映射到一個(gè)獨立的子空間，而不是將整條數據映射到一個(gè)多維空間，這樣可以一定程度上緩解這個(gè)問(wèn)題：
這樣能夠提供更好的查詢(xún)到節點(diǎn)的映射，但是增加了集群協(xié)調的復雜度，因為這種情況下一條數據會(huì )散布在多個(gè)獨立的子空間，而每個(gè)子空間都對應各自的若干個(gè)物理節點(diǎn)，數據更新時(shí)就必須考慮事務(wù)問(wèn)題。參考資料 [6]有這種技術(shù)的更多介紹和實(shí)現細節。
有的應用有很強的隨機讀取要求，這就需要把所有數據放在內存里。在這種情況下，將數據分片并把每個(gè)分片主從復制通常需要兩倍以上的內存，因為每個(gè)數據都要在主節點(diǎn)和從節點(diǎn)上各有一份。為了在主節點(diǎn)失效的時(shí)候起到代替作用，從節點(diǎn)上的內存大小應該和主節點(diǎn)一樣。如果系統能夠容忍節點(diǎn)失效的時(shí)候出現短暫中斷或性能下降，也可以不要分片。
下面的圖描繪了4個(gè)節點(diǎn)上的16個(gè)分片，每個(gè)分片都有一份在內存里，副本存在硬盤(pán)上：
灰色箭頭突出了節點(diǎn)2上的分片復制。其他節點(diǎn)上的分片也是同樣復制的。紅色箭頭描繪了在節點(diǎn)2失效的情況下副本怎樣加載進(jìn)內存。集群內副本的均勻分布使得只需要預留很少的內存就可以存放節點(diǎn)失效情況下激活的副本。在上面的圖里，集群只預留了1/3的內存就可以承受單個(gè)節點(diǎn)的失效。特別要指出的是副本的激活（從硬盤(pán)加載入內存）會(huì )花費一些時(shí)間，這會(huì )造成短時(shí)間的性能下降或者正在恢復中的那部分數據服務(wù)中斷。
在這部分我們將討論與系統協(xié)調相關(guān)的兩種技術(shù)。分布式協(xié)調是一個(gè)比較大的領(lǐng)域，數十年以來(lái)有很多人對此進(jìn)行了深入的研究。這篇文章里只涉及兩種已經(jīng)投入實(shí)用的技術(shù)。關(guān)于分布式鎖，consensus協(xié)議以及其他一些基礎技術(shù)的內容可以在很多書(shū)或者網(wǎng)絡(luò )資源中找到，也可以去看參考資料[17, 18, 21]。
故障檢測是任何一個(gè)擁有容錯性的分布式系統的基本功能。實(shí)際上所有的故障檢測協(xié)議都基于心跳通訊機制，原理很簡(jiǎn)單，被監控的組件定期發(fā)送心跳信息給監控進(jìn)程（或者由監控進(jìn)程輪詢(xún)被監控組件），如果有一段時(shí)間沒(méi)有收到心跳信息就被認為失效了。除此之外，真正的分布式系統還要有另外一些功能要求：
根據重要程度不同來(lái)分層次組織監控區，各區域之間通過(guò)謠言傳播協(xié)議或者中央容錯庫同步，這樣可以滿(mǎn)足擴展性的要求，又可以防止心跳信息在網(wǎng)絡(luò )中泛濫[14]。如下圖所示（6個(gè)故障檢測器組成了兩個(gè)區域，互相之間通過(guò)謠言傳播協(xié)議或者像ZooKeeper這樣的健壯性庫來(lái)聯(lián)系）：
協(xié)調者競選是用于強一致性數據庫的一個(gè)重要技術(shù)。首先，它可以組織主從結構的系統中主節點(diǎn)的故障恢復。其次，在網(wǎng)絡(luò )隔離的情況下，它可以斷開(kāi)處于少數的那部分節點(diǎn)，以避免寫(xiě)沖突。
Bully 算法是一種相對簡(jiǎn)單的協(xié)調者競選算法。MongoDB 用了這個(gè)算法來(lái)決定副本集中主要的那一個(gè)。Bully 算法的主要思想是集群的每個(gè)成員都可以聲明它是協(xié)調者并通知其他節點(diǎn)。別的節點(diǎn)可以選擇接受這個(gè)聲稱(chēng)或是拒絕并進(jìn)入協(xié)調者競爭。被其他所有節點(diǎn)接受的節點(diǎn)才能成為協(xié)調者。節點(diǎn)按照一些屬性來(lái)判斷誰(shuí)應該勝出。這個(gè)屬性可以是一個(gè)靜態(tài)ID，也可以是更新的度量像最近一次事務(wù)ID（最新的節點(diǎn)會(huì )勝出）。
下圖的例子展示了bully算法的執行過(guò)程。使用靜態(tài)ID作為度量，ID值更大的節點(diǎn)會(huì )勝出：
協(xié)調者競選過(guò)程會(huì )統計參與的節點(diǎn)數目并確保集群中至少一半的節點(diǎn)參與了競選。這確保了在網(wǎng)絡(luò )隔離的情況下只有一部分節點(diǎn)能選出協(xié)調者（假設網(wǎng)絡(luò )中網(wǎng)絡(luò )會(huì )被分割成多塊區域，之間互不聯(lián)通，協(xié)調者競選的結果必然會(huì )在節點(diǎn)數相對比較多的那個(gè)區域中選出協(xié)調者，當然前提是那個(gè)區域中的可用節點(diǎn)多于集群原有節點(diǎn)數的半數。如果集群被隔離成幾個(gè)區塊，而沒(méi)有一個(gè)區塊的節點(diǎn)數多于原有節點(diǎn)總數的一半，那就無(wú)法選舉出協(xié)調者，當然這樣的情況下也別指望集群能夠繼續提供服務(wù)了）。
參考資料聯(lián)系客服
