[轉]NoSQL數據庫的分布式算法

[轉]NoSQL數據庫的分布式算法 轉載一篇很不錯的NoSQL數據庫分布式算法，內容如下： 本文英文原文發表于知名技術博客《Highly Scalable Blog》，對NoSQL數據庫中的 分布式 算法和思想進行了詳細的講解。文章很長，由@juliashine進行翻譯投稿。感謝譯者的共享

[轉]NoSQL數據庫的分布式算法

轉載一篇很不錯的nosql數據庫分布式算法，內容如下：?

本文英文原文發表于知名技術博客《Highly Scalable Blog》，對NoSQL數據庫中的分布式算法和思想進行了詳細的講解。文章很長，由@juliashine?進行翻譯投稿。感謝譯者的共享精神！

譯者介紹：Juliashine是多年抓娃工程師，現工作方向是海量數據處理與分析，關注Hadoop與NoSQL生態體系。

英文原文：《Distributed Algorithms in NoSQL Databases》

譯文地址：《NoSQL數據庫的分布式算法》

系統的可擴展性是推動NoSQL運動發展的的主要理由，包含了分布式系統協調，故障轉移，資源管理和許多其他特性。這么講使得NoSQL聽起來像是一個大筐，什么都能塞進去。盡管NoSQL運動并沒有給分布式數據處理帶來根本性的技術變革，但是依然引發了鋪天蓋地的關于各種協議和算法的研究以及實踐。正是通過這些嘗試逐漸總結出了一些行之有效的數據庫構建方法。在這篇文章里，香港服務器租用，我將針對NoSQL數據庫的分布式特點進行一些系統化的描述。

接下來我們將研究一些分布式策略，比如故障檢測中的復制，這些策略用黑體字標出，被分為三段：

數據一致性

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

現在讓我們仔細看看常用的復制技術，并按照描述的特點給他們分一下類。第一幅圖描繪了不同技術之間的邏輯關系和不同技術在系統的一致性、擴展性、可用性、延遲性之間的權衡坐標。 第二張圖詳細描繪了每個技術。

復本因子是4。讀寫協調者可以是一個外部客戶端或是一個內部代理節點。

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

上面分析中的一些權衡有必要再強調一下：

反熵協議， 謠言傳播算法

讓我們從以下場景開始：

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

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

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

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

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

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

盡管這些技術看起來很簡單，仍然有許多研究關注于不同約束條件下反熵協議的性能表現。其中之一通過一種更有效的結構使用網絡拓撲來取代隨機選取 [10] 。在網絡帶寬有限的條件下調整傳輸率或使用先進的規則來選取要同步的數據 [9]。摘要計算也面臨挑戰，數據庫會維護一份最近更新的日志以有助于摘要計算。

最終一致數據類型Eventually Consistent Data Types

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

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

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用類似的方法計數[11]。利用基于狀態的或是基于操作的復制理論也可以設計出更復雜的最終一致的數據結構。例如，[1]中就提及了一系列這樣的數據結構，包括：

最終一致數據類型的功能通常是有限的，還會帶來額外的性能開銷。

數據放置

這部分主要關注控制在分布式數據庫中放置數據的算法。這些算法負責把數據項映射到合適的物理節點上，在節點間遷移數據以及像內存這樣的資源的全局調配。

均衡數據