深入解析NoSQL数据库的分布式算法
深入解析NoSQL數據庫的分布式算法
摘要：盡管NoSQL運動并沒有給分布式數據處理帶來根本性的技術變革，但是依然引發了鋪天蓋地的關于各種協議和算法的研究以及實踐。在這篇文章里，我將針對NoSQL數據庫的分布式特點進行一些系統化的描述。
系統的可擴展性是推動NoSQL運動發展的的主要理由，包含了分布式系統協調，故障轉移，資源管理和許多其他特性。這么講使得NoSQL聽起來像是一個大筐，什么都能塞進去。盡管NoSQL運動并沒有給分布式數據處理帶來根本性的技術變革，但是依然引發了鋪天蓋地的關于各種協議和算法的研究以及實踐。正是通過這些嘗試逐漸總結出了一些行之有效的數據庫構建方法。在這篇文章里，我將針對NoSQL數據庫的分布式特點進行一些系統化的描述。
接下來我們將研究一些分布式策略，比如故障檢測中的復制，這些策略用黑體字標出，被分為三段：
- 數據一致性。NoSQL需要在分布式系統的一致性，容錯性和性能，低延遲及高可用之間作出權衡，一般來說，數據一致性是一個必選項，所以這一節主要是關于數據復制和數據恢復。
- 數據放置。一個數據庫產品應該能夠應對不同的數據分布，集群拓撲和硬件配置。在這一節我們將討論如何分布以及調整數據分布才能夠能夠及時解決故障，提供持久化保證，高效查詢和保證集群中的資源（如內存和硬盤空間）得到均衡使用。
- 對等系統。像 leader election 這樣的的技術已經被用于多個數據庫產品以實現容錯和數據強一致性。然而，即使是分散的的數據庫（無中心）也要跟蹤它們的全局狀態，檢測故障和拓撲變化。這一節將介紹幾種使系統保持一致狀態的技術。
數據一致性
眾所周知，分布式系統經常會遇到網絡隔離或是延遲的情況，在這種情況下隔離的部分是不可用的，因此要保持高可用性而不犧牲一致性是不可能的。這一事實通常被稱作“CAP理論”。然而，一致性在分布式系統中是一個非常昂貴的東西，所以經常需要在這上面做一些讓步，不只是針對可用性，還有多種權衡。為了研究這些權衡，我們注意到分布式系統的一致性問題是由數據隔離和復制引起的，所以我們將從研究復制的特點開始：
- 可用性。在網絡隔離的情況下剩余部分仍然可以應對讀寫請求。
- 讀寫延遲。讀寫請求能夠在短時間內處理。
- 讀寫延展性。讀寫的壓力可由多個節點均衡分擔。
- 容錯性。對于讀寫請求的處理不依賴于任何一個特定節點。
- 數據持久性。特定條件下的節點故障不會造成數據丟失。
- 一致性。一致性比前面幾個特性都要復雜得多，我們需要詳細討論一下幾種不同的觀點。 但是我們不會涉及過多的一致性理論和并發模型，因為這已經超出了本文的范疇，我只會使用一些簡單特點構成的精簡體系。
- 讀寫一致性。從讀寫的觀點來看，數據庫的基本目標是使副本趨同的時間盡可能短（即更新傳遞到所有副本的時間），保證最終一致性。除了這個較弱的保證，還有一些更強的一致性特點：
- 寫后讀一致性。在數據項X上寫操作的效果總是能夠被后續的X上的讀操作看見。
- 讀后讀一致性。在一次對數據項X的讀操作之后，后續對X的讀操作應該返回與第一次的返回值相同或是更加新的值。
- 寫一致性。分區的數據庫經常會發生寫沖突。數據庫應當能處理這種沖突并保證多個寫請求不會被不同的分區所處理。這方面數據庫提供了幾種不同的一致性模型：
- 原子寫。假如數據庫提供了API，一次寫操作只能是一個單獨的原子性的賦值，避免寫沖突的辦法是找出每個數據的“最新版本”。這使得所有的節點都能夠在更新結束時獲得同一版本，而與更新的順序無關，網絡故障和延遲經常造成各節點更新順序不一致。 數據版本可以用時間戳或是用戶指定的值來表示。Cassandra用的就是這種方法。
- 原子化的讀-改-寫。應用有時候需要進行 讀-改-寫 序列操作而非單獨的原子寫操作。假如有兩個客戶端讀取了同一版本的數據，修改并且把修改后的數據寫回，按照原子寫模型，時間上比較靠后的那一次更新將會覆蓋前一次。這種行為在某些情況下是不正確的（例如，兩個客戶端往同一個列表值中添加新值）。數據庫提供了至少兩種解決方法：
- 沖突預防。 讀-改-寫 可以被認為是一種特殊情況下的事務，所以分布式鎖或是 PAXOS這樣的一致協議都可以解決這種問題。這種技術支持原子讀改寫語義和任意隔離級別的事務。另一種方法是避免分布式的并發寫操作，將對特定數據項的所有寫操作路由到單個節點上（可以是全局主節點或者分區主節點）。為了避免沖突，數據庫必須犧牲網絡隔離情況下的可用性。這種方法常用于許多提供強一致性保證的系統（例如大多數關系數據庫，HBase，MongoDB）。
- 沖突檢測。數據庫跟蹤并發更新的沖突，并選擇回滾其中之一或是維持兩個版本交由客戶端解決。并發更新通常用向量時鐘 （這是一種樂觀鎖）來跟蹤，或者維護一個完整的版本歷史。這個方法用于 Riak, Voldemort, CouchDB.
現在讓我們仔細看看常用的復制技術，并按照描述的特點給他們分一下類。第一幅圖描繪了不同技術之間的邏輯關系和不同技術在系統的一致性、擴展性、可用性、延遲性之間的權衡坐標。 第二張圖詳細描繪了每個技術。
復本因子是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，因為寫操作對于兩個副本的更新是非事務的，在更新沒有完成的時候讀就可能讀到兩個都是舊值或者一新一舊：
- 對于某種讀延遲的要求，設置R和W的不同值可以調整寫延遲與持久性，反之亦然。
- 如果W<=N/2，并發的多個寫入會寫到不同的若干節點（如，寫操作A寫前N/2個，B寫后N/2個）。 設置 W>N/2 可以保證在符合回滾模型的原子讀改寫時及時檢測到沖突。
- 嚴格來講，這種模式雖然可以容忍個別節點的失效， 但是對于網絡隔離的容錯性并不好。在實踐中，常使用”近似數量通過“這樣的方法，通過犧牲一致性來提高某些情景下的可用性。
（F, 讀全部寫若干）讀一致性問題可以通過在讀數據的時候訪問所有副本（讀數據或者檢查摘要）來減輕。這確保了只要有至少一個節點上的數據更新新的數據就能被讀取者看到。但是在網絡隔離的情況下這種保證就不能起到作用了。
（G, 主從） 這種技術常被用來提供原子寫或者 沖突檢測持久級別的讀改寫。為了實現沖突預防級別，必須要用一種集中管理方式或者是鎖。最簡單的策略是用主從異步復制。對于特定數據項的寫操作全部被路由到一個中心節點，并在上面順序執行。這種情況下主節點會成為瓶頸，所以必須要將數據劃分成一個個獨立的片區（不同片有不同的master），這樣才能提供擴展性。
（H, Transactional Read Quorum Write Quorum and Read One Write All） ?更新多個副本的方法可以通過使用事務控制技術來避免寫沖突。 眾所周知的方法是使用兩階段提交協議。但兩階段提交并不是完全可靠的，因為協調者失效可能會造成資源阻塞。 PAXOS提交協議是更可靠的選擇，但會損失一點性能。 在這個基礎上再向前一小步就是讀一個副本寫所有副本，這種方法把所有副本的更新放在一個事務中，它提供了強容錯一致性但會損失掉一些性能和可用性。
上面分析中的一些權衡有必要再強調一下
- 一致性與可用性。 嚴密的權衡已經由CAP理論給出了。在網絡隔離的情況下，數據庫要么將數據集中，要么既要接受數據丟失的風險。
- 一致性與擴展性。 看得出即使讀寫一致性保證降低了副本集的擴展性，只有在原子寫模型中才可以以一種相對可擴展的方式處理寫沖突。原子讀改寫模型通過給數據加上臨時性的全局鎖來避免沖突。這表明， 數據或操作之間的依賴，即使是很小范圍內或很短時間的，也會損害擴展性。所以精心設計數據模型，將數據分片分開存放對于擴展性非常重要。
- 一致性與延遲。 如上所述，當數據庫需要提供強一致性或者持久性的時候應該偏向于讀寫所有副本技術。但是很明顯一致性與請求延遲成反比，所以使用若干副本技術會是比較中允的辦法。
- 故障轉移與一致性/擴展性/延遲。有趣的是容錯性與一致性、擴展性、延遲的取舍沖突并不劇烈。通過合理的放棄一些性能與一致性，集群可以容忍多達 up to 的節點失效。這種折中在兩階段提交與 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，而這是錯誤的。解決這個問題的方法是用一個類似于向量時鐘的數據結構為每個節點維護一對計數器：
[js] view plaincopyprint?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值更大的節點會勝出：
協調者競選過程會統計參與的節點數目并確保集群中至少一半的節點參與了競選。這確保了在網絡隔離的情況下只有一部分節點能選出協調者（假設網絡中網絡會被分割成多塊區域，之間互不聯通，協調者競選的結果必然會在節點數相對比較多的那個區域中選出協調者，當然前提是那個區域中的可用節點多于集群原有節點數的半數。如果集群被隔離成幾個區塊，而沒有一個區塊的節點數多于原有節點總數的一半，那就無法選舉出協調者，當然這樣的情況下也別指望集群能夠繼續提供服務了）。
原文地址：http://juliashine.com/distributed-algorithms-in-nosql-databases/
總結
以上是生活随笔為你收集整理的深入解析NoSQL数据库的分布式算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 史蒂夫·乔布斯很懂团队建设
- 下一篇： 深入探究递归神经网络：大牛级的训练和优化