NoSQL數(shù)據(jù)庫的分布式算法

1、NoSQL數(shù)據(jù)庫的分布式算法作者：nosqlfan on星期四，十一月22, 2012 評論本文【閱讀：10,489次】本文英文原文發(fā)表于知名技術(shù)博客Highly Scalable Blog，對NoSQL數(shù)據(jù)庫中 的分布式算法和思想進行了詳細的講解。文章很長，由juliashine進行翻譯投稿。感謝譯者的共享精神！譯者介紹：Juliashine是多年抓娃工程師，現(xiàn)工作方向是海量數(shù)據(jù)處理與分析，關(guān) 注Hadoop與NoSQL生態(tài)體系。英文原文： Distributed Algorithms in NoSQL Databases譯文地址：NoSQL數(shù)據(jù)庫的分布式算法系統(tǒng)的可擴展性是推動NoSQL運

2、動發(fā)展的的主要理由，包含了分布式系統(tǒng)協(xié)調(diào)， 故障轉(zhuǎn)移，資源管理和許多其他特性。這么講使得NoSQL聽起來像是一個大筐， 什么都能塞進去。盡管NoSQL運動并沒有給分布式數(shù)據(jù)處理帶來根本性的技術(shù)變 革，但是依然引發(fā)了鋪天蓋地的關(guān)于各種協(xié)議和算法的研究以及實踐。正是通過這 些嘗試逐漸總結(jié)出了一些行之有效的數(shù)據(jù)庫構(gòu)建方法。在這篇文章里，我將針對 NoSQL數(shù)據(jù)庫的分布式特點進行一些系統(tǒng)化的描述。接下來我們將研究一些分布式策略，比如故障檢測中的復(fù)制，這些策略用黑體字標 出，被分為三段：數(shù)據(jù)一致性。NoSQL需要在分布式系統(tǒng)的一致性，容錯性和性能，低延遲及高可用之 間作出權(quán)衡，一般來說，數(shù)據(jù)一致性是一個

3、必選項，所以這一節(jié)主要是關(guān)數(shù)據(jù)復(fù)制和 數(shù)據(jù)恢復(fù)。數(shù)據(jù)放置。一個數(shù)據(jù)庫產(chǎn)品應(yīng)該能夠應(yīng)對不同的數(shù)據(jù)分布，集群拓撲和硬件配置。在這 一節(jié)我們將討論如何分布以及調(diào)整數(shù)據(jù)分布才能夠能夠及時解決故障，提供持久化保證， 高效查詢和保證集群中的資源（如內(nèi)存和硬盤空間）得到均衡使用。對等系統(tǒng)。像l eader election這樣的的技術(shù)已經(jīng)被用于多個數(shù)據(jù)庫產(chǎn)品以實現(xiàn)容錯和 數(shù)據(jù)強一致性。然而，即使是分散的的數(shù)據(jù)庫（無中心）也要跟蹤它們的全局狀態(tài)，檢 測故障和拓撲變化。這一節(jié)將介紹幾種使系統(tǒng)保持一致狀態(tài)的技術(shù)。數(shù)據(jù)一致性眾所周知，分布式系統(tǒng)經(jīng)常會遇到網(wǎng)絡(luò)隔離或是延遲的情況，在這種情況下隔離的 部分是不可用的，因

4、此要保持高可用性而不犧牲一致性是不可能的。這一事實通常 被稱作“CAP理論”。然而，一致性在分布式系統(tǒng)中是一個非常昂貴的東西，所以經(jīng) 常需要在這上面做一些讓步，不只是針對可用性，還有多種權(quán)衡。為了研究這些權(quán) 衡，我們注意到分布式系統(tǒng)的一致性問題是由數(shù)據(jù)隔離和復(fù)制引起的，所以我們將 從研究復(fù)制的特點開始：可用性。在網(wǎng)絡(luò)隔離的情況下剩余部分仍然可以應(yīng)對讀寫請求。 讀寫延遲。讀寫請求能夠在短時間內(nèi)處理。讀寫延展性。讀寫的壓力可由多個節(jié)點均衡分擔。容錯性。對于讀寫請求的處理不依賴于任何一個特定節(jié)點。數(shù)據(jù)持久性。特定條件下的節(jié)點故障不會造成數(shù)據(jù)丟失。 一致性。一致性比前面幾個特性都要復(fù)雜得多，我們需要詳

5、細討論一下幾種不同的觀點。 但是我們不會涉及過多的一致性理論和并發(fā)模型，因為這已經(jīng)超出了本文的范疇，我只 會使用一些簡單特點構(gòu)成的精簡體系。o讀寫一致性。從讀寫的觀點來看，數(shù)據(jù)庫的基本目標是使副本趨同的時間盡可能 短（即更新傳遞到所有副本的時間），保證最終一致性。除了這個較弱的保證， 還有一些更強的一致性特點：-寫后讀一致性。在數(shù)據(jù)項X上寫操作的效果總是能夠被后續(xù)的X上的讀操 作看見。-讀后讀一致性。在一次對數(shù)據(jù)項X的讀操作之后，后續(xù)對X的讀操作應(yīng)該 返回與第一次的返回值相同或是更加新的值。o寫一致性。分區(qū)的數(shù)據(jù)庫經(jīng)常會發(fā)生寫沖突。數(shù)據(jù)庫應(yīng)當能處理這種沖突并保證 多個寫請求不會被不同的分區(qū)所處

6、理。這方面數(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ù)寫回，按照原子寫模型，時間上比較靠后的那一次更新將會覆蓋前一 次。這種行為在某些情況下是

7、不正確的（例如，兩個客戶端往同一個列表 值中添加新值）。數(shù)據(jù)庫提供了至少兩種解決方法：-沖突預(yù)防。讀-改-寫可以被認為是一種特殊情況下的事務(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ā)更新的沖突，并選擇回滾其中之一或是

8、維持兩個版本交由客戶端解決。并發(fā)更新通常用向量時鐘19（這 是一種樂觀鎖）來跟蹤，或者維護一個完整的版本歷史。這個方法 用于 Riak, Voldemort, CouchDB.現(xiàn)在讓我們仔細看看常用的復(fù)制技術(shù)，并按照描述的特點給他們分一下類。第一幅 圖描繪了不同技術(shù)之間的邏輯關(guān)系和不同技術(shù)在系統(tǒng)的一致性、擴展性、可用性、 延遲性之間的權(quán)衡坐標。第二張圖詳細描繪了每個技術(shù)。scalabilitydistributioncontentionADUu-txweouQ2S/CJAntrEntropyconvergence time heG沽3Re adO ne-WriteO nCAP Theorem：

9、 mo one can standi art both sides of、 this lineM = q_MReadQuorum-WriteQuorumZone offatency-糖任 IReadAlhWriteQuorumACIb zoneReadOne-WriteAM2PC/PAXOSwrite-write consistencyAtomic WritesConflict DetectionConflict PreventionPp%a-OA 4OLJ SCQ 土tirad p 2e3-04 S3J3-QcoordinatorUnalailablA ncde Anit-entrcpy -

10、 - Digest rad- Async read復(fù)本因子是4。讀寫協(xié)調(diào)者可以個外部客戶端或我們會依據(jù)一致性從弱到強把所有的技術(shù)過一遍:. New replicaO OldrepliWrite/read個內(nèi)部代理節(jié)點。（A,反熵）一致性最弱，基于策略如下。寫操作的時候選擇任意一個節(jié)點更新，在讀的時候如果新數(shù)據(jù)還沒有通過后臺的反熵協(xié)議傳遞到讀的那個節(jié)點，那么讀到的仍然是舊數(shù)據(jù)。（下一節(jié)會詳細介紹反熵協(xié)議）。這種方法的主要特點是:o過高的傳播延遲使它在數(shù)據(jù)同步方面不太好用，所以比較典型的用法是只作為輔 助性的功能來檢測和修復(fù)計劃外的不一致0 Cassandra就使用了反熵算法來在各 節(jié)點之間傳遞數(shù)

11、據(jù)庫拓撲和其他一些元數(shù)據(jù)信息。o 一致性保證較弱：即使在沒有發(fā)生故障的情況下，也會出現(xiàn)寫沖突與讀寫不一致。o在網(wǎng)絡(luò)隔離下的高可用和健壯性。用異步的批處理替代了逐個更新，這使得性能 表現(xiàn)優(yōu)異。o持久性保障較弱因為新的數(shù)據(jù)最初只有單個副本。（B）對上面模式的一個改進是在任意一個節(jié)點收到更新數(shù)據(jù)請求的同時異步的發(fā)送更 新給所有可用節(jié)點。這也被認為是定向的反熵。o與純粹的反熵相比，這種做法只用一點小小的性能犧牲就極大地提高了一致性。 然而，正式一致性和持久性保持不變。o假如某些節(jié)點因為網(wǎng)絡(luò)故障或是節(jié)點失效在當時是不可用的，更新最終也會通過 反熵傳播過程來傳遞到該節(jié)點。（C）在前一個模式中，使用提示移交

12、技術(shù)8可以更好地處理某個節(jié)點的操作失敗。 對于失效節(jié)點的預(yù)期更新被記錄在額外的代理節(jié)點上，并且標明一旦特點節(jié)點可用就要 將更新傳遞給該節(jié)點。這樣做提高了一致性，降低了復(fù)制收斂時間。（D, 一次性讀寫）因為提示移交的責任節(jié)點也有可能在將更新傳遞出去之前就已經(jīng)失 效，在這種情況下就有必要通過所謂的讀修復(fù)來保證一致性。每個讀操作都會啟動一個 異步過程，向存儲這條數(shù)據(jù)的所有節(jié)點請求一份數(shù)據(jù)摘要（像簽名或者hash），如果 發(fā)現(xiàn)各節(jié)點返回的摘要不一致則統(tǒng)一各節(jié)點上的數(shù)據(jù)版本。我們用一次性讀寫來命名組 合了 A、B、C、D的技術(shù)-他們都沒有提供嚴格的一致性保證，但是作為一個自備的方 法已經(jīng)可以用于實踐了。

13、（E,讀若干寫若干）上面的策略是降低了復(fù)制收斂時間的啟發(fā)式增強。為了保證更強 的一致性，必須犧牲可用性來保證一定的讀寫重疊。通常的做法是同時寫入W個副本 而不是一個，讀的時候也要讀R個副本。o 首先，可以配置寫副本數(shù)W1。o其次，因為R+WN，寫入的節(jié)點和讀取的節(jié)點之間必然會有重疊，所以讀取的 多個數(shù)據(jù)副本里至少會有一個是比較新的數(shù)據(jù)（上面的圖中W=2, R=3, N=4）。 這樣在讀寫請求依序進行的時候（寫執(zhí)行完再讀）能夠保證一致性（對于單個用 戶的讀寫一致性），但是不能保障全局的讀一致性。用下面圖示里的例子來看， R=2, W=2, N=3，因為寫操作對于兩個副本的更新是非事務(wù)的，在更新沒

14、有完 成的時候讀就可能讀到兩個都是舊值或者一新一舊：In-progressIn-progress- old- newDonewb- newo對于某種讀延遲的要求，設(shè)置R和W的不同值可以調(diào)整寫延遲與持久性，反之 亦然。如果WN/2可以保證在符合回滾模型的原子讀改寫時及時檢測到?jīng)_突。o嚴格來講，這種模式雖然可以容忍個別節(jié)點的失效，但是對于網(wǎng)絡(luò)隔離的容錯性 并不好。在實踐中，常使用”近似數(shù)量通過“這樣的方法，通過犧牲一致性來提高 某些情景下的可用性。（F,讀全部寫若干）讀一致性問題可以通過在讀數(shù)據(jù)的時候訪問所有副本（讀數(shù)據(jù)或 者檢查摘要）來減輕。這確保了只要有至少一個節(jié)點上的數(shù)據(jù)更新新的數(shù)據(jù)就能被讀

15、取 者看到。但是在網(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 AID 更新多個 副本的方法可以通過使用事務(wù)控制技術(shù)來避免寫沖突。眾所

16、周知的方法是使用兩階段提 交協(xié)議。但兩階段提交并不是完全可靠的，因為協(xié)調(diào)者失效可能會造成資源阻塞。PAXOS提交協(xié)議20, 21是更可靠的選擇，但會損失一點性能。在這個基礎(chǔ)上再向前 一小步就是讀一個副本寫所有副本，這種方法把所有副本的更新放在一個事務(wù)中，它提 供了強容錯一致性但會損失掉一些性能和可用性。上面分析中的一些權(quán)衡有必要再強調(diào)一下：一致性與可用性。嚴密的權(quán)衡已經(jīng)由CAP理論給出了。在網(wǎng)絡(luò)隔離的情況下，數(shù)據(jù)庫 要么將數(shù)據(jù)集中，要么既要接受數(shù)據(jù)丟失的風險。一致性與擴展性?？吹贸黾词棺x寫一致性保證降低了副本集的擴展性，只有在原子寫 模型中才可以以一種相對可擴展的方式處理寫沖突。原子讀改寫模型

17、通過給數(shù)據(jù)加上臨 時性的全局鎖來避免沖突。這表明，數(shù)據(jù)或操作之間的依賴，即使是很小范圍內(nèi)或很短 時間的，也會損害擴展性。所以精心設(shè)計數(shù)據(jù)模型，將數(shù)據(jù)分片分開存放對于擴展性非 常重要。一致性與延遲。如上所述，當數(shù)據(jù)庫需要提供強一致性或者持久性的時候應(yīng)該偏向于 讀寫所有副本技術(shù)。但是很明顯一致性與請求延遲成反比，所以使用若干副本技術(shù)會是 比較中允的辦法。故障轉(zhuǎn)移與一致性/擴展性/延遲。有趣的是容錯性與一致性、擴展性、延遲的取舍沖突 并不劇烈。通過合理的放棄一些性能與一致性，集群可以容忍多達up to的節(jié)點失效。 這種折中在兩階段提交與PAXOS協(xié)議的區(qū)別里體現(xiàn)得很明顯。這種折中的另一個例 子是增加

18、特定的一致性保障，比如使用嚴格會話進程的讀己所寫”，但這又增加了故障 轉(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)者可以解決這個問題，但是去中心

19、化的數(shù)據(jù)庫能夠提供更好的容錯性。去中心化的主要做法是利用精心設(shè)計的傳染協(xié) 議7，這種協(xié)議相對簡單，但是提供了很好的收斂時間，而且能夠容忍任何節(jié)點的 失效和網(wǎng)絡(luò)隔離。盡管有許多類型的傳染算法，我們只關(guān)注反熵協(xié)議，因為NoSQL 數(shù)據(jù)庫都在使用它。反熵協(xié)議假定同步會按照一個固定進度表執(zhí)行，每個節(jié)點定期隨機或是按照某種規(guī) 則選擇另外一個節(jié)點交換數(shù)據(jù)，消除差異。有三種反風格的反熵協(xié)議：推，拉和混 合。推協(xié)議的原理是簡單選取一個隨機節(jié)點然后把數(shù)據(jù)狀態(tài)發(fā)送過去。在真實應(yīng)用 中將全部數(shù)據(jù)都推送出去顯然是愚蠢的，所以節(jié)點一般按照下圖所示的方式工作。digest of Apullpush-pullupdate

20、A-B節(jié)點A作為同步發(fā)起者準備好一份數(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)系。00一9080F-60403020101 2 3 4 5 6 7 8 9 10 11 12 13 14 1fiIteration可以看到，拉方式的收斂性比推方式更好，這可以從理論上得到

21、證明7。而且推方 式還存在一個“收斂尾巴”的問題。在多次迭代之后，盡管幾乎遍歷到了所有的節(jié)點， 但還是有很少的一部分沒受到影響。與單純的推和拉方式相比，混合方式的效率更 高，所以實際應(yīng)用中通常使用這種方式。反熵是可擴展的，因為平均轉(zhuǎn)換時間以集 群規(guī)模的對數(shù)函數(shù)形式增長。盡管這些技術(shù)看起來很簡單，仍然有許多研究關(guān)注于不同約束條件下反熵協(xié)議的性 能表現(xiàn)。其中之一通過一種更有效的結(jié)構(gòu)使用網(wǎng)絡(luò)拓撲來取代隨機選取10。在 網(wǎng)絡(luò)帶寬有限的條件下調(diào)整傳輸率或使用先進的規(guī)則來選取要同步的數(shù)據(jù)9。摘要 計算也面臨挑戰(zhàn)，數(shù)據(jù)庫會維護一份最近更新的日志以有助于摘要計算。最終一致數(shù)據(jù)類型 Eventually Con

22、sistent 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,而這

23、是錯誤的。解決 這個問題的方法是用一個類似于向量時鐘19 的數(shù)據(jù)結(jié)構(gòu)為每個節(jié)點維護一對計數(shù) 器1： class Counter int plusint minusint NODE_IDincrement() plusNODE_ID+decrement() minusNODE_ID+get() return sum(plus) - sum(minus)merge(Counter other) fori in 1.MAX_ID plusi = max(plusi, other.plusi)minusi = max(minusi, other.minusi)Cassandra用類似的方法計數(shù)11。利

24、用基于狀態(tài)的或是基于操作的復(fù)制理論也可 以設(shè)計出更復(fù)雜的最終一致的數(shù)據(jù)結(jié)構(gòu)。例如，1中就提及了一系列這樣的數(shù)據(jù)結(jié) 構(gòu)，包括：計數(shù)器（加減操作）集合（添加和移除操作）圖（增加邊或頂點，移除邊或頂點）列表（插入某位置或者移除某位置）最終一致數(shù)據(jù)類型的功能通常是有限的，還會帶來額外的性能開銷。數(shù)據(jù)放置這部分主要關(guān)注控制在分布式數(shù)據(jù)庫中放置數(shù)據(jù)的算法。這些算法負責把數(shù)據(jù)項映 射到合適的物理節(jié)點上，在節(jié)點間遷移數(shù)據(jù)以及像內(nèi)存這樣的資源的全局調(diào)配。均衡數(shù)據(jù)我們還是從一個簡單的協(xié)議開始，它可以提供集群節(jié)點間無縫的數(shù)據(jù)遷移。這常發(fā) 生于像集群擴容（加入新節(jié)點），故障轉(zhuǎn)移（一些節(jié)點宕機）或是均衡數(shù)據(jù)（數(shù)據(jù) 在節(jié)

25、點間的分布不均衡）這樣的場景。如下圖A中所描繪的場景-有三個節(jié)點， 數(shù)據(jù)隨便分布在三個節(jié)點上（假設(shè)數(shù)據(jù)都是key-value型）。如果數(shù)據(jù)庫不支持數(shù)據(jù)內(nèi)部均衡，就要在每個節(jié)點上發(fā)布數(shù)據(jù)庫實例，如上面圖B 所示。這需要手動進行集群擴展，停掉要遷移的數(shù)據(jù)庫實例，把它轉(zhuǎn)移到新節(jié)點上， 再在新節(jié)點上啟動，如圖C所示。盡管數(shù)據(jù)庫能夠監(jiān)控到每一條記錄，包括MongoDB, Oracle Coherence,和還在開發(fā)中的Redis Cluster在內(nèi)的許多系統(tǒng)仍然使用的是 自動均衡技術(shù)。也即，將數(shù)據(jù)分片并把每個數(shù)據(jù)分片作為遷移的最小單位，這是基 于效率的考慮。很明顯分片數(shù)會比節(jié)點數(shù)多，數(shù)據(jù)分片可以在各節(jié)點

26、間平均分布。 按照一種簡單的協(xié)議即可實現(xiàn)無縫數(shù)據(jù)遷移，這個協(xié)議可以在遷移數(shù)據(jù)分片的時候 重定向客戶的數(shù)據(jù)遷出節(jié)點和遷入節(jié)點。下圖描繪了一個Redis Cluster中實現(xiàn)的 get（key）邏輯的狀態(tài)機。假定每個節(jié)點都知道集群拓撲，能夠把任意key映射到相應(yīng)的數(shù)據(jù)分片，把數(shù)據(jù)分 片映射到節(jié)點。如果節(jié)點判斷被請求的key屬于本地分片，就會在本地查找（上圖 中上面的方框）。假如節(jié)點判斷請求的key屬于另一個節(jié)點X，他會發(fā)送一個永久 重定向命令給客戶端（上圖中下方的方框）。永久重定向意味著客戶端可以緩存分 片和節(jié)點間的映射關(guān)系。如果分片遷移正在進行，遷出節(jié)點和遷入節(jié)點會標記相應(yīng) 的分片并且將分片的數(shù)

27、據(jù)加鎖逐條加鎖然后開始移動。遷出節(jié)點首先會在本地查找 key，如果沒有找到，重定向客戶端到遷入節(jié)點，假如key已經(jīng)遷移完畢的話。這種 重定向是一次性的，并且不能被緩存。遷入節(jié)點在本地處理重定向，但定期查詢在 遷移還沒完成前被永久重定向。動態(tài)環(huán)境中的數(shù)據(jù)分片和復(fù)制我們關(guān)注的另一個問題是怎么把記錄映射到物理節(jié)點。比較直接的方法是用一張表 來記錄每個范圍的key與節(jié)點的映射關(guān)系，一個范圍的key對應(yīng)到一個節(jié)點，或者 用key的hash值與節(jié)點數(shù)取模得到的值作為節(jié)點ID。但是hash取模的方法在集 群發(fā)生更改的情況下就不是很好用，因為增加或者減少節(jié)點都會引起集群內(nèi)的數(shù)據(jù) 徹底重排。導致很難進行復(fù)制和故

28、障恢復(fù)。有許多方法在復(fù)制和故障恢復(fù)的角度進行了增強。最著名的就是一致性hash。網(wǎng)上 已經(jīng)有很多關(guān)于一致性hash的介紹了，所以在這里我只提供一個基本介紹，僅僅 為了文章內(nèi)容的完整性。下圖描繪了一致性hash的基本原理：一致性hash從根本上來講是一個鍵值映射結(jié)構(gòu)-它把鍵（通常是hash過的）映 射到物理節(jié)點。鍵經(jīng)過hash之后的取值空間是一個有序的定長二進制字符串，很 顯然每個在此范圍內(nèi)的鍵都會被映射到圖A中A、B、C三個節(jié)點中的某一個。為 了副本復(fù)制，將取值空間閉合成一個環(huán)，沿環(huán)順時針前行直到所有副本都被映射到 合適的節(jié)點上，如圖B所示。換句話說，Y將被定位在節(jié)點B上，因為它在B的范 圍內(nèi)

29、，第一個副本應(yīng)該放置在C，第二個副本放置在A，以此類推。這種結(jié)構(gòu)的好處體現(xiàn)在增加或減少一個節(jié)點的時候，因為它只會引起臨接區(qū)域的數(shù) 據(jù)重新均衡。如圖C所示，節(jié)點D的加入只會對數(shù)據(jù)項X產(chǎn)生影響而對Y無影響。同樣，移除節(jié)點B （或者B失效）只會影響Y和X的副本，而不會對X自身造成影 響。但是，正如參考資料8 中所提到的，這種做法在帶來好處的同時也有弱點，那 就是重新均衡的負擔都由鄰節(jié)點承受了，它們將移動大量的數(shù)據(jù)。通過將每個節(jié)點 映射到多個范圍而不是一個范圍可以一定程度上減輕這個問題帶來的不利影響，如 圖D所示。這是一個折中，它避免了重新均衡數(shù)據(jù)時負載過于集中，但是與基于模 塊的映射相比，保持了總均

30、衡數(shù)量適當降低。給大規(guī)模的集群維護一個完整連貫的hash環(huán)很不容易。對于相對小一點的數(shù)據(jù)庫 集群就不會有問題，研究如何在對等網(wǎng)絡(luò)中將數(shù)據(jù)放置與網(wǎng)絡(luò)路由結(jié)合起來很有意 思。一個比較好的例子是Chord算法，它使環(huán)的完整性讓步于單個節(jié)點的查找效率。 Chord算法也使用了環(huán)映射鍵到節(jié)點的理念，在這方面和一致性hash很相似。不 同的是，一個特定節(jié)點維護一個短列表，列表中的節(jié)點在環(huán)上的邏輯位置是指數(shù)增 長的（如下圖）。這使得可以使用二分搜索只需要幾次網(wǎng)絡(luò)跳躍就可以定位一個鍵。這張圖畫的是一個由16個節(jié)點組成的集群，描繪了節(jié)點A是如何查找放在節(jié)點D 上的key的。（A）描繪了路由，（B）描繪了環(huán)針對節(jié)

31、點A、B、C的局部圖像。在 參考資料15 中有更多關(guān)于分散式系統(tǒng)中的數(shù)據(jù)復(fù)制的內(nèi)容。按照多個屬性的數(shù)據(jù)分片當只需要通過主鍵來訪問數(shù)據(jù)的時候，一致性hash的數(shù)據(jù)放置策略很有效，但是 當需要按照多個屬性來查詢的時候事情就會復(fù)雜得多。一種簡單的做法（MongoDB 使用的）是用主鍵來分布數(shù)據(jù)而不考慮其他屬性。這樣做的結(jié)果是依據(jù)主鍵的查詢 可以被路由到接個合適的節(jié)點上，但是對其他查詢的處理就要遍歷集群的所有節(jié)點。 查詢效率的不均衡造成下面的問題：有一個數(shù)據(jù)集，其中的每條數(shù)據(jù)都有若干屬性和相應(yīng)的值。是否有一種數(shù)據(jù)分布策 略能夠使得限定了任意多個屬性的查詢會被交予盡量少的幾個節(jié)點執(zhí)行？ HyperDex

32、數(shù)據(jù)庫提供了一種解決方案?；舅枷胧前衙總€屬性視作多維空間中的 一個軸，將空間中的區(qū)域映射到物理節(jié)點上。一次查詢會被對應(yīng)到一個由空間中多 個相鄰區(qū)域組成的超平面，所以只有這些區(qū)域與該查詢有關(guān)。讓我們看看參考資料 6中的一個例子：Phone Number First Name RMFirst NameLst NameIjst Name= SmithF irsi A NDLast Name = Smith每一條數(shù)據(jù)都是一條用戶信息，有三個屬性First Name、Last Name和PhoneNumber。這些屬性被視作一個三維空間，可行的數(shù)據(jù)分布策略是將每個象限映射到 一個物理節(jié)點。像“Firs

33、t Name = Joh這樣的查詢對應(yīng)到一個貫穿4個象限的平面， 也即只有4個節(jié)點會參與處理此次查詢。有兩個屬性限制的查詢對應(yīng)于一條貫穿兩 個象限的直線，如上圖所示，因此只有2個節(jié)點會參與處理。這個方法的問題是空間象限會呈屬性數(shù)的指數(shù)函數(shù)增長。結(jié)果就會是，只有幾個屬 性限制的查詢會投射到許多個空間區(qū)域，也即許多臺服務(wù)器。將一個屬性較多的數(shù)據(jù)項拆分成幾個屬性相對較少的子項，并將每個子項都映射到一個獨立的子空間， 而不是將整條數(shù)據(jù)映射到一個多維空間，這樣可以一定程度上緩解這個問題：subspacesk4:v4rk5 iv5rk9-i vQData item with9 attributeskl：v

34、lk3 : v3 k41 v4 k 5: v5 k 6 : v K7q k3 : v8 E9: v9這樣能夠提供更好的查詢到節(jié)點的映射，但是增加了集群協(xié)調(diào)的復(fù)雜度，因為這種 情況下一條數(shù)據(jù)會散布在多個獨立的子空間，而每個子空間都對應(yīng)各自的若干個物 理節(jié)點，數(shù)據(jù)更新時就必須考慮事務(wù)問題。參考資料6有這種技術(shù)的更多介紹和實 現(xiàn)細節(jié)。鈍化副本有的應(yīng)用有很強的隨機讀取要求，這就需要把所有數(shù)據(jù)放在內(nèi)存里。在這種情況下， 將數(shù)據(jù)分片并把每個分片主從復(fù)制通常需要兩倍以上的內(nèi)存，因為每個數(shù)據(jù)都要在 主節(jié)點和從節(jié)點上各有一份。為了在主節(jié)點失效的時候起到代替作用，從節(jié)點上的 內(nèi)存大小應(yīng)該和主節(jié)點一樣。如果系統(tǒng)能夠

35、容忍節(jié)點失效的時候出現(xiàn)短暫中斷或性 能下降，也可以不要分片。下面的圖描繪了 4個節(jié)點上的16個分片，每個分片都有一份在內(nèi)存里，副本存在 硬盤上：灰色箭頭突出了節(jié)點2上的分片復(fù)制。其他節(jié)點上的分片也是同樣復(fù)制的。紅色箭 頭描繪了在節(jié)點2失效的情況下副本怎樣加載進內(nèi)存。集群內(nèi)副本的均勻分布使得 只需要預(yù)留很少的內(nèi)存就可以存放節(jié)點失效情況下激活的副本。在上面的圖里，集 群只預(yù)留了 1/3的內(nèi)存就可以承受單個節(jié)點的失效。特別要指出的是副本的激活（從 硬盤加載入內(nèi)存）會花費一些時間，這會造成短時間的性能下降或者正在恢復(fù)中的 那部分數(shù)據(jù)服務(wù)中斷。系統(tǒng)協(xié)調(diào)在這部分我們將討論與系統(tǒng)協(xié)調(diào)相關(guān)的兩種技術(shù)。分布式協(xié)

36、調(diào)是一個比較大的領(lǐng)域， 數(shù)十年以來有很多人對此進行了深入的研究。這篇文章里只涉及兩種已經(jīng)投入實用 的技術(shù)。關(guān)于分布式鎖，consensus協(xié)議以及其他一些基礎(chǔ)技術(shù)的內(nèi)容可以在很多 書或者網(wǎng)絡(luò)資源中找到，也可以去看參考資料17, 18, 21。故障檢測故障檢測是任何一個擁有容錯性的分布式系統(tǒng)的基本功能。實際上所有的故障檢測 協(xié)議都基于心跳通訊機制，原理很簡單，被監(jiān)控的組件定期發(fā)送心跳信息給監(jiān)控進 程（或者由監(jiān)控進程輪詢被監(jiān)控組件），如果有一段時間沒有收到心跳信息就被認 為失效了。除此之外，真正的分布式系統(tǒng)還要有另外一些功能要求：自適應(yīng)。故障檢測應(yīng)該能夠應(yīng)對暫時的網(wǎng)絡(luò)故障和延遲，以及集群拓撲、負載

37、和帶寬的 變化。但這有很大難度，因為沒有辦法去分辨一個長時間沒有響應(yīng)的進程到底是不是真 的失效了，因此，故障檢測需要權(quán)衡故障識別時間（花多長時間才能識別一個真正的故障，也即一個進程失去響應(yīng)多久之后會被認為是失效）和虛假警報率之間的輕重。這個 權(quán)衡因子應(yīng)該能夠動態(tài)自動調(diào)整。靈活性。乍看上去，故障檢測只需要輸出一個表明被監(jiān)控進程是否處于工作狀態(tài)的布爾 值，但在實際應(yīng)用中這是不夠的。我們來看參考資料12中的一個類似MapReduce的 例子。有一個由一個主節(jié)點和若干工作節(jié)點組成的分布式應(yīng)用，主節(jié)點維護一個作業(yè)列 表，并將列表中的作業(yè)分配給工作節(jié)點。主節(jié)點能夠區(qū)分不同程度的失敗。如果主節(jié)點 懷疑某個工

38、作節(jié)點掛了，他就不會再給這個節(jié)點分配作業(yè)。其次，隨著時間推移，如果 沒有收到該節(jié)點的心跳信息，主節(jié)點就會把運行在這個節(jié)點上的作業(yè)重新分配給別的節(jié) 點。最后，主節(jié)點確認這個節(jié)點已經(jīng)失效，并釋放所有相關(guān)資源?？蓴U展性和健壯性。失敗檢測作為一個系統(tǒng)功能應(yīng)該能夠隨著系統(tǒng)的擴大而擴展。他應(yīng) 該是健壯和一致的，也即，即使在發(fā)生通訊故障的情況下，系統(tǒng)中的所有節(jié)點都應(yīng)該有 一個一致的看法（即所有節(jié)點都應(yīng)該知道哪些節(jié)點是不可用的，那些節(jié)點是可用的，各 節(jié)點對此的認知不能發(fā)生沖突，不能出現(xiàn)一部分節(jié)點知道某節(jié)點A不可用，而另一部分 節(jié)點不知道的情況）所謂的累計失效檢測器12可以解決前兩個問題，Cassandra16

39、對它進行了一些修 改并應(yīng)用在產(chǎn)品中。其基本工作流程如下： 對于每一個被監(jiān)控資源，檢測器記錄心跳信息到達時間Ti。計算在統(tǒng)計預(yù)測范圍內(nèi)的到達時間的均值和方差。假定到達時間的分布已知（下圖包括一個正態(tài)分布的公式），我們可以計算心跳延遲（當 前時間t_now和上一次到達時間Tc之間的差值）的概率，用這個概率來判斷是否發(fā)生 故障。如參考資料12 中所建議的，可以使用對數(shù)函數(shù)來調(diào)整它以提高可用性。在這種 情況下，輸出1意味著判斷錯誤（認為節(jié)點失效）的概率是10%，2意味著1%，以此 類推。Failure DetectorNodeMonitoring協(xié)調(diào)者競選協(xié)調(diào)者競選是用于強一致性數(shù)據(jù)庫的一個重要技術(shù)。

40、首先，它可以組織主從結(jié)構(gòu)的 系統(tǒng)中主節(jié)點的故障恢復(fù)。其次，在網(wǎng)絡(luò)隔離的情況下，它可以斷開處于少數(shù)的那 部分節(jié)點，以避免寫沖突。Bully算法是一種相對簡單的協(xié)調(diào)者競選算法。MongoDB用了這個算法來決定副本 集中主要的那一個。Bully算法的主要思想是集群的每個成員都可以聲明它是協(xié)調(diào) 者并通知其他節(jié)點。別的節(jié)點可以選擇接受這個聲稱或是拒絕并進入?yún)f(xié)調(diào)者競爭。 被其他所有節(jié)點接受的節(jié)點才能成為協(xié)調(diào)者。節(jié)點按照一些屬性來判斷誰應(yīng)該勝出。 這個屬性可以是一個靜態(tài)ID，也可以是更新的度量像最近一次事務(wù)ID （最新的節(jié)點 會勝出）。下圖的例子展示了 bully算法的執(zhí)行過程。使用靜態(tài)ID作為度量，ID值

41、更大的節(jié)點 會勝出：最初集群有5個節(jié)點，節(jié)點5是一個公認的協(xié)調(diào)者。假設(shè)節(jié)點5掛了，并且節(jié)點2和節(jié)點3同時發(fā)現(xiàn)了這一情況。兩個節(jié)點開始競選并發(fā)送 競選消息給ID更大的節(jié)點。節(jié)點4淘汰了節(jié)點2和3,節(jié)點3淘汰了節(jié)點2。這時候節(jié)點1察覺了節(jié)點5失效并向所有ID更大的節(jié)點發(fā)送了競選信息。節(jié)點2、3和4都淘汰了節(jié)點1。節(jié)點4發(fā)送競選信息給節(jié)點5。節(jié)點5沒有響應(yīng)，所以節(jié)點4宣布自己當選并向其他節(jié)點通告了這一消息。協(xié)調(diào)者競選過程會統(tǒng)計參與的節(jié)點數(shù)目并確保集群中至少一半的節(jié)點參與了競選。 這確保了在網(wǎng)絡(luò)隔離的情況下只有一部分節(jié)點能選出協(xié)調(diào)者（假設(shè)網(wǎng)絡(luò)中網(wǎng)絡(luò)會被 分割成多塊區(qū)域，之間互不聯(lián)通，協(xié)調(diào)者競選的結(jié)果必

42、然會在節(jié)點數(shù)相對比較多的 那個區(qū)域中選出協(xié)調(diào)者，當然前提是那個區(qū)域中的可用節(jié)點多于集群原有節(jié)點數(shù)的 半數(shù)。如果集群被隔離成幾個區(qū)塊，而沒有一個區(qū)塊的節(jié)點數(shù)多于原有節(jié)點總數(shù)的 一半，那就無法選舉出協(xié)調(diào)者，當然這樣的情況下也別指望集群能夠繼續(xù)提供服務(wù) 了）。參考資料M. Shapiro et al. A Comprehensive Study of Convergent and Commutative Replicated Data TypesI. Stoica et al. Chord: A Scalable Peer-to-peer Lookup Service for Internet ApplicationsR. J. Honicky, E.L.Miller. Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data DistributionG. Shah. Distributed Data Structures for Peer-to-Peer SystemsA. Montresor, Gossip Protocols for Large-Scale Distributed