今天，我們將研究一些分布式策略，比如故障檢測中的復(fù)制，這些策略用黑體字標(biāo)出，被分為三段：

• 數(shù)據(jù)一致性。NoSQL需要在分布式系統(tǒng)的一致性，容錯性和性能，低延遲及高可用之間作出權(quán)衡，一般來說，數(shù)據(jù)一致性是一個必選項，所以這一節(jié)主要是關(guān)于 數(shù)據(jù)復(fù)制 和 數(shù)據(jù)恢復(fù) 。
• 數(shù)據(jù)放置。一個數(shù)據(jù)庫產(chǎn)品應(yīng)該能夠應(yīng)對不同的數(shù)據(jù)分布，集群拓?fù)浜陀布渲谩Ｔ谶@一節(jié)我們將討論如何 分布 以及 調(diào)整數(shù)據(jù)分布 才能夠能夠及時解決故障，提供持久化保證，高效查詢和保證集訓(xùn)中的資源(如內(nèi)存和硬盤空間)得到均衡使用。
• 對等系統(tǒng)。像 leader election 這樣的的技術(shù)已經(jīng)被用于多個數(shù)據(jù)庫產(chǎn)品以實現(xiàn)容錯和數(shù)據(jù)強一致性。然而，即使是分散的的數(shù)據(jù)庫(無中心)也要跟蹤它們的全局狀態(tài)，檢測故障和拓?fù)渥兓＿@一節(jié)將介紹幾種使系統(tǒng)保持一致狀態(tài)的技術(shù)。System Coordination. Coordination techniques like leader election are used in

數(shù)據(jù)一致性

眾所周知，分布式系統(tǒng)經(jīng)常會遇到網(wǎng)絡(luò)隔離或是延遲的情況，在這種情況下隔離的部分是不可用的，因此要保持高可用性而不犧牲一致性是不可能的。這一事實通常被稱作“CAP理論”。然而，一致性在分布式系統(tǒng)中是一個非常昂貴的東西，所以經(jīng)常需要在這上面做一些讓步，不只是針對可用性，還有多種權(quán)衡。為了研究這些權(quán)衡，我們注意到分布式系統(tǒng)的一致性問題是由數(shù)據(jù)隔離和復(fù)制引起的，所以我們將從研究復(fù)制的特點開始：

• 可用性。在網(wǎng)絡(luò)隔離的情況下剩余部分仍然可以應(yīng)對讀寫請求。
• 讀寫延遲。讀寫請求能夠在短時間內(nèi)處理。
• 讀寫延展性。讀寫的壓力可由多個節(jié)點均衡分擔(dān)。
• 容錯性。對于讀寫請求的處理不依賴于任何一個特定節(jié)點。
• 數(shù)據(jù)持久性。特定條件下的節(jié)點故障不會造成數(shù)據(jù)丟失。

一致性。一致性比前面幾個特性都要復(fù)雜得多，我們需要詳細(xì)討論一下幾種不同的觀點。 但是我們不會涉及過多的一致性理論和并發(fā)模型，因為這已經(jīng)超出了本文的范疇，我只會使用一些簡單特點構(gòu)成的精簡體系。

讀寫一致性。從讀寫的觀點來看，數(shù)據(jù)庫的基本目標(biāo)是使副本趨同的時間盡可能短(即更新傳遞到所有副本的時間)，保證最終一致性。除了這個較弱的保證，還有一些更強的一致性特點：

寫后讀一致性。在數(shù)據(jù)項X上寫操作的效果總是能夠被后續(xù)的X上的讀操作看見。

讀后讀一致性。在一次對數(shù)據(jù)項X的讀操作之后，后續(xù)對X的讀操作應(yīng)該返回與第一次的返回值相同或是更加新的值。

寫一致性。分區(qū)的數(shù)據(jù)庫經(jīng)常會發(fā)生寫沖突。數(shù)據(jù)庫應(yīng)當(dāng)能處理這種沖突并保證多個寫請求不會被不同的分區(qū)所處理。這方面數(shù)據(jù)庫提供了幾種不同的一致性模型：

原子寫。假如數(shù)據(jù)庫提供了API，一次寫操作只能是一個單獨的原子性的賦值，避免寫沖突的辦法是找出每個數(shù)據(jù)的“最新版本”。這使得所有的節(jié)點都能夠在更新結(jié)束時獲得同一版本，而與更新的順序無關(guān)，網(wǎng)絡(luò)故障和延遲經(jīng)常造成各節(jié)點更新順序不一致。 數(shù)據(jù)版本可以用時間戳或是用戶指定的值來表示。Cassandra用的就是這種方法。

原子化的讀-改-寫。應(yīng)用有時候需要進行 讀-改-寫 序列操作而非單獨的原子寫操作。假如有兩個客戶端讀取了同一版本的數(shù)據(jù)，修改并且把修改后的數(shù)據(jù)寫回，按照原子寫模型，時間上比較靠后的那一次更新將會覆蓋前一次。這種行為在某些情況下是不正確的(例如，兩個客戶端往同一個列表值中添加新值)。數(shù)據(jù)庫提供了至少兩種解決方法：

沖突預(yù)防。 讀-改-寫 可以被認(rèn)為是一種特殊情況下的事務(wù)，所以分布式鎖或是 PAXOS [20, 21] 這樣的一致協(xié)議都可以解決這種問題。這種技術(shù)支持原子讀改寫語義和任意隔離級別的事務(wù)。另一種方法是避免分布式的并發(fā)寫操作，將對特定數(shù)據(jù)項的所有寫操作路由到單個節(jié)點上(可以是全局主節(jié)點或者分區(qū)主節(jié)點)。為了避免沖突，數(shù)據(jù)庫必須犧牲網(wǎng)絡(luò)隔離情況下的可用性。這種方法常用于許多提供強一致性保證的系統(tǒng)(例如大多數(shù)關(guān)系數(shù)據(jù)庫，HBase，MongoDB)。

沖突檢測。數(shù)據(jù)庫跟蹤并發(fā)更新的沖突，并選擇回滾其中之一或是維持兩個版本交由客戶端解決。并發(fā)更新通常用向量時鐘 [19] (這是一種樂觀鎖)來跟蹤，或者維護一個完整的版本歷史。這個方法用于 Riak, Voldemort, CouchDB.

現(xiàn)在讓我們仔細(xì)看看常用的復(fù)制技術(shù)，并按照描述的特點給他們分一下類。第一幅圖描繪了不同技術(shù)之間的邏輯關(guān)系和不同技術(shù)在系統(tǒng)的一致性、擴展性、可用性、延遲性之間的權(quán)衡坐標(biāo)。 第二張圖詳細(xì)描繪了每個技術(shù)。

復(fù)本因子是4。讀寫協(xié)調(diào)者可以是一個外部客戶端或是一個內(nèi)部代理節(jié)點。

我們會依據(jù)一致性從弱到強把所有的技術(shù)過一遍：

(A, 反熵) 一致性最弱，基于策略如下。寫操作的時候選擇任意一個節(jié)點更新，在讀的時候如果新數(shù)據(jù)還沒有通過后臺的反熵協(xié)議傳遞到讀的那個節(jié)點，那么讀到的仍然是舊數(shù)據(jù)。(下一節(jié)會詳細(xì)介紹反熵協(xié)議)。這種方法的主要特點是：

過高的傳播延遲使它在數(shù)據(jù)同步方面不太好用，所以比較典型的用法是只作為輔助性的功能來檢測和修復(fù)計劃外的不一致。Cassandra就使用了反熵算法來在各節(jié)點之間傳遞數(shù)據(jù)庫拓?fù)浜推渌恍┰獢?shù)據(jù)信息。

一致性保證較弱：即使在沒有發(fā)生故障的情況下，也會出現(xiàn)寫沖突與讀寫不一致。

在網(wǎng)絡(luò)隔離下的高可用和健壯性。用異步的批處理替代了逐個更新，這使得性能表現(xiàn)優(yōu)異。

持久性保障較弱因為新的數(shù)據(jù)最初只有單個副本。

(B) 對上面模式的一個改進是在任意一個節(jié)點收到更新數(shù)據(jù)請求的同時異步的發(fā)送更新給所有可用節(jié)點。這也被認(rèn)為是定向的反熵。

與純粹的反熵相比，這種做法只用一點小小的性能犧牲就極大地提高了一致性。然而，正式一致性和持久性保持不變。

假如某些節(jié)點因為網(wǎng)絡(luò)故障或是節(jié)點失效在當(dāng)時是不可用的，更新最終也會通過反熵傳播過程來傳遞到該節(jié)點。

(C) 在前一個模式中，使用提示移交技術(shù) [8] 可以更好地處理某個節(jié)點的操作失敗。對于失效節(jié)點的預(yù)期更新被記錄在額外的代理節(jié)點上，并且標(biāo)明一旦特點節(jié)點可用就要將更新傳遞給該節(jié)點。這樣做提高了一致性，降低了復(fù)制收斂時間。

(D, 一次性讀寫)因為提示移交的責(zé)任節(jié)點也有可能在將更新傳遞出去之前就已經(jīng)失效，在這種情況下就有必要通過所謂的讀修復(fù)來保證一致性。每個讀操作都會啟動一個異步過程，向存儲這條數(shù)據(jù)的所有節(jié)點請求一份數(shù)據(jù)摘要(像簽名或者hash)，如果發(fā)現(xiàn)各節(jié)點返回的摘要不一致則統(tǒng)一各節(jié)點上的數(shù)據(jù)版本。我們用一次性讀寫來命名組合了A、B、C、D的技術(shù)- 他們都沒有提供嚴(yán)格的一致性保證，但是作為一個自備的方法已經(jīng)可以用于實踐了。

(E, 讀若干寫若干) 上面的策略是降低了復(fù)制收斂時間的啟發(fā)式增強。為了保證更強的一致性，必須犧牲可用性來保證一定的讀寫重疊。 通常的做法是同時寫入W個副本而不是一個，讀的時候也要讀R個副本。

首先，可以配置寫副本數(shù)W>1。

其次，因為R+W>N，寫入的節(jié)點和讀取的節(jié)點之間必然會有重疊，所以讀取的多個數(shù)據(jù)副本里至少會有一個是比較新的數(shù)據(jù)(上面的圖中 W=2, R=3, N=4 )。這樣在讀寫請求依序進行的時候(寫執(zhí)行完再讀)能夠保證一致性(對于單個用戶的讀寫一致性)，但是不能保障全局的讀一致性。用下面圖示里的例子來看，R=2，W=2，N=3，因為寫操作對于兩個副本的更新是非事務(wù)的，在更新沒有完成的時候讀就可能讀到兩個都是舊值或者一新一舊：

對于某種讀延遲的要求，設(shè)置R和W的不同值可以調(diào)整寫延遲與持久性，反之亦然。

如果W<=N/2，并發(fā)的多個寫入會寫到不同的若干節(jié)點(如，寫操作A寫前N/2個，B寫后N/2個)。 設(shè)置 W>N/2 可以保證在符合回滾模型的原子讀改寫時及時檢測到?jīng)_突。

嚴(yán)格來講，這種模式雖然可以容忍個別節(jié)點的失效， 但是對于網(wǎng)絡(luò)隔離的容錯性并不好。在實踐中，常使用”近似數(shù)量通過“這樣的方法，通過犧牲一致性來提高某些情景下的可用性。

(F, 讀全部寫若干)讀一致性問題可以通過在讀數(shù)據(jù)的時候訪問所有副本(讀數(shù)據(jù)或者檢查摘要)來減輕。這確保了只要有至少一個節(jié)點上的數(shù)據(jù)更新新的數(shù)據(jù)就能被讀取者看到。但是在網(wǎng)絡(luò)隔離的情況下這種保證就不能起到作用了。

(G, 主從) 這種技術(shù)常被用來提供原子寫或者 沖突檢測持久級別的讀改寫。為了實現(xiàn)沖突預(yù)防級別，必須要用一種集中管理方式或者是鎖。最簡單的策略是用主從異步復(fù)制。對于特定數(shù)據(jù)項的寫操作全部被路由到一個中心節(jié)點，并在上面順序執(zhí)行。這種情況下主節(jié)點會成為瓶頸，所以必須要將數(shù)據(jù)劃分成一個個獨立的片區(qū)(不同片有不同的master)，這樣才能提供擴展性。

(H, Transactional Read Quorum Write Quorum and Read One Write All) 更新多個副本的方法可以通過使用事務(wù)控制技術(shù)來避免寫沖突。 眾所周知的方法是使用兩階段提交協(xié)議。但兩階段提交并不是完全可靠的，因為協(xié)調(diào)者失效可能會造成資源阻塞。 PAXOS提交協(xié)議 [20, 21] 是更可靠的選擇，但會損失一點性能。 在這個基礎(chǔ)上再向前一小步就是讀一個副本寫所有副本，這種方法把所有副本的更新放在一個事務(wù)中，它提供了強容錯一致性但會損失掉一些性能和可用性。

上面分析中的一些權(quán)衡有必要再強調(diào)一下：

一致性與可用性。 嚴(yán)密的權(quán)衡已經(jīng)由CAP理論給出了。在網(wǎng)絡(luò)隔離的情況下，數(shù)據(jù)庫要么將數(shù)據(jù)集中，要么既要接受數(shù)據(jù)丟失的風(fēng)險。
一致性與擴展性。 看得出即使讀寫一致性保證降低了副本集的擴展性，只有在原子寫模型中才可以以一種相對可擴展的方式處理寫沖突。原子讀改寫模型通過給數(shù)據(jù)加上臨時性的全局鎖來避免沖突。這表明， 數(shù)據(jù)或操作之間的依賴，即使是很小范圍內(nèi)或很短時間的，也會損害擴展性。所以精心設(shè)計數(shù)據(jù)模型，將數(shù)據(jù)分片分開存放對于擴展性非常重要。
一致性與延遲。 如上所述，當(dāng)數(shù)據(jù)庫需要提供強一致性或者持久性的時候應(yīng)該偏向于讀寫所有副本技術(shù)。但是很明顯一致性與請求延遲成反比，所以使用若干副本技術(shù)會是比較中允的辦法。
故障轉(zhuǎn)移與一致性/擴展性/延遲。 有趣的是容錯性與一致性、擴展性、延遲的取舍沖突并不劇烈。通過合理的放棄一些性能與一致性，集群可以容忍多達 up to 的節(jié)點失效。這種折中在兩階段提交與 PAXOS 協(xié)議的區(qū)別里體現(xiàn)得很明顯。這種折中的另一個例子是增加特定的一致性保障，比如使用嚴(yán)格會話進程的“讀己所寫”，但這又增加了故障轉(zhuǎn)移的復(fù)雜性 [22]。
反熵協(xié)議， 謠言傳播算法

讓我們從以下場景開始：

有許多節(jié)點，每條數(shù)據(jù)會在其中的若干的節(jié)點上面存有副本。每個節(jié)點都可以單獨處理更新請求，每個節(jié)點定期和其他節(jié)點同步狀態(tài)，如此一段時間之后所有的副本都會趨向一致。同步過程是怎樣進行的?同步何時開始?怎樣選擇同步的對象?怎么交換數(shù)據(jù)?我們假定兩個節(jié)點總是用較新版本的數(shù)據(jù)覆蓋舊的數(shù)據(jù)或者兩個版本都保留以待應(yīng)用層處理。

這個問題常見于數(shù)據(jù)一致性維護和集群狀態(tài)同步(如集群成員信息傳播)等場景。雖然引入一個監(jiān)控數(shù)據(jù)庫并制定同步計劃的協(xié)調(diào)者可以解決這個問題，但是去中心化的數(shù)據(jù)庫能夠提供更好的容錯性。去中心化的主要做法是利用精心設(shè)計的傳染協(xié)議[7]，這種協(xié)議相對簡單，但是提供了很好的收斂時間，而且能夠容忍任何節(jié)點的失效和網(wǎng)絡(luò)隔離。盡管有許多類型的傳染算法，我們只關(guān)注反熵協(xié)議，因為NoSQL數(shù)據(jù)庫都在使用它。

反熵協(xié)議假定同步會按照一個固定進度表執(zhí)行，每個節(jié)點定期隨機或是按照某種規(guī)則選擇另外一個節(jié)點交換數(shù)據(jù)，消除差異。有三種反風(fēng)格的反熵協(xié)議：推，拉和混合。推協(xié)議的原理是簡單選取一個隨機節(jié)點然后把數(shù)據(jù)狀態(tài)發(fā)送過去。在真實應(yīng)用中將全部數(shù)據(jù)都推送出去顯然是愚蠢的，所以節(jié)點一般按照下圖所示的方式工作。

節(jié)點A作為同步發(fā)起者準(zhǔn)備好一份數(shù)據(jù)摘要，里面包含了A上數(shù)據(jù)的指紋。節(jié)點B接收到摘要之后將摘要中的數(shù)據(jù)與本地數(shù)據(jù)進行比較，并將數(shù)據(jù)差異做成一份摘要返回給A。最后，A發(fā)送一個更新給B，B再更新數(shù)據(jù)。拉方式和混合方式的協(xié)議與此類似，就如上圖所示的。

反熵協(xié)議提供了足夠好的收斂時間和擴展性。下圖展示了一個在100個節(jié)點的集群中傳播一個更新的模擬結(jié)果。在每次迭代中，每個節(jié)點只與一個隨機選取的對等節(jié)點發(fā)生聯(lián)系。

可以看到，拉方式的收斂性比推方式更好，這可以從理論上得到證明[7]。而且推方式還存在一個“收斂尾巴”的問題。在多次迭代之后，盡管幾乎遍歷到了所有的節(jié)點，但還是有很少的一部分沒受到影響。與單純的推和拉方式相比， 混合方式的效率更高，所以實際應(yīng)用中通常使用這種方式。反熵是可擴展的，因為平均轉(zhuǎn)換時間以集群規(guī)模的對數(shù)函數(shù)形式增長。

盡管這些技術(shù)看起來很簡單，仍然有許多研究關(guān)注于不同約束條件下反熵協(xié)議的性能表現(xiàn)。其中之一通過一種更有效的結(jié)構(gòu)使用網(wǎng)絡(luò)拓?fù)鋪砣〈S機選取 [10] 。在網(wǎng)絡(luò)帶寬有限的條件下調(diào)整傳輸率或使用先進的規(guī)則來選取要同步的數(shù)據(jù) [9]。摘要計算也面臨挑戰(zhàn)，數(shù)據(jù)庫會維護一份最近更新的日志以有助于摘要計算。

最終一致數(shù)據(jù)類型Eventually Consistent Data Types

在上一節(jié)我們假定兩個節(jié)點總是合并他們的數(shù)據(jù)版本。但要解決更新沖突并不容易，讓所有副本都最終達到一個語義上正確的值出乎意料的難。一個眾所周知的例子是Amazon Dynamo數(shù)據(jù)庫[8]中已經(jīng)刪除的條目可以重現(xiàn)。

我們假設(shè)一個例子來說明這個問題：數(shù)據(jù)庫維護一個邏輯上的全局計數(shù)器，每個節(jié)點可以增加或者減少計數(shù)。雖然每個節(jié)點可以在本地維護一個自己的值，但這些本地計數(shù)卻不能通過簡單的加減來合并。假設(shè)這樣一個例子：有三個節(jié)點A、B和C，每個節(jié)點執(zhí)行了一次加操作。如果A從B獲得一個值，并且加到本地副本上，然后C從B獲得值，然后C再從A獲得值，那么C最后的值是4，而這是錯誤的。解決這個問題的方法是用一個類似于向量時鐘[19]的數(shù)據(jù)結(jié)構(gòu)為每個節(jié)點維護一對計數(shù)器[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)