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