NoSQL數(shù)據(jù)庫中怎么實(shí)現(xiàn)一個(gè)分布式算法

NoSQL數(shù)據(jù)庫中怎么實(shí)現(xiàn)一個(gè)分布式算法，相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

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

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

• 可用性。在網(wǎng)絡(luò)隔離的情況下剩余部分仍然可以應(yīng)對讀寫請求。

• 讀寫延遲。讀寫請求能夠在短時(shí)間內(nèi)處理。

• 讀寫延展性。讀寫的壓力可由多個(gè)節(jié)點(diǎn)均衡分擔(dān)。

• 容錯(cuò)性。對于讀寫請求的處理不依賴于任何一個(gè)特定節(jié)點(diǎn)。

• 數(shù)據(jù)持久性。特定條件下的節(jié)點(diǎn)故障不會(huì)造成數(shù)據(jù)丟失。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

持久性保障較弱因?yàn)樾碌臄?shù)據(jù)最初只有單個(gè)副本。

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

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

假如某些節(jié)點(diǎn)因?yàn)榫W(wǎng)絡(luò)故障或是節(jié)點(diǎn)失效在當(dāng)時(shí)是不可用的，更新最終也會(huì)通過反熵傳播過程來傳遞到該節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

讓我們從以下場景開始：

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

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

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

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

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

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

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

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

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

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

Cassandra用類似的方法計(jì)數(shù)[11]。利用基于狀態(tài)的或是基于操作的復(fù)制理論也可以設(shè)計(jì)出更復(fù)雜的最終一致的數(shù)據(jù)結(jié)構(gòu)。例如，[1]中就提及了一系列這樣的數(shù)據(jù)結(jié)構(gòu)，包括：

• 計(jì)數(shù)器(加減操作)

• 集合(添加和移除操作)

• 圖(增加邊或頂點(diǎn)，移除邊或頂點(diǎn))

• 列表(插入某位置或者移除某位置)

最終一致數(shù)據(jù)類型的功能通常是有限的，還會(huì)帶來額外的性能開銷。

數(shù)據(jù)放置

這部分主要關(guān)注控制在分布式數(shù)據(jù)庫中放置數(shù)據(jù)的算法。這些算法負(fù)責(zé)把數(shù)據(jù)項(xiàng)映射到合適的物理節(jié)點(diǎn)上，在節(jié)點(diǎn)間遷移數(shù)據(jù)以及像內(nèi)存這樣的資源的全局調(diào)配。

均衡數(shù)據(jù)

我們還是從一個(gè)簡單的協(xié)議開始，它可以提供集群節(jié)點(diǎn)間無縫的數(shù)據(jù)遷移。這常發(fā)生于像集群擴(kuò)容(加入新節(jié)點(diǎn))，故障轉(zhuǎn)移(一些節(jié)點(diǎn)宕機(jī))或是均衡數(shù)據(jù)(數(shù)據(jù)在節(jié)點(diǎn)間的分布不均衡)這樣的場景。如下圖A中所描繪的場景 – 有三個(gè)節(jié)點(diǎn)，數(shù)據(jù)隨便分布在三個(gè)節(jié)點(diǎn)上(假設(shè)數(shù)據(jù)都是key-value型)。

如果數(shù)據(jù)庫不支持?jǐn)?shù)據(jù)內(nèi)部均衡，就要在每個(gè)節(jié)點(diǎn)上發(fā)布數(shù)據(jù)庫實(shí)例，如上面圖B所示。這需要手動(dòng)進(jìn)行集群擴(kuò)展，停掉要遷移的數(shù)據(jù)庫實(shí)例，把它轉(zhuǎn)移到新節(jié)點(diǎn)上，再在新節(jié)點(diǎn)上啟動(dòng)，如圖C所示。盡管數(shù)據(jù)庫能夠監(jiān)控到每一條記錄，包括MongoDB, Oracle Coherence, 和還在開發(fā)中的 Redis Cluster 在內(nèi)的許多系統(tǒng)仍然使用的是自動(dòng)均衡技術(shù)。也即，將數(shù)據(jù)分片并把每個(gè)數(shù)據(jù)分片作為遷移的最小單位，這是基于效率的考慮。很明顯分片數(shù)會(huì)比節(jié)點(diǎn)數(shù)多，數(shù)據(jù)分片可以在各節(jié)點(diǎn)間平均分布。按照一種簡單的協(xié)議即可實(shí)現(xiàn)無縫數(shù)據(jù)遷移，這個(gè)協(xié)議可以在遷移數(shù)據(jù)分片的時(shí)候重定向客戶的數(shù)據(jù)遷出節(jié)點(diǎn)和遷入節(jié)點(diǎn)。下圖描繪了一個(gè)Redis Cluster中實(shí)現(xiàn)的get(key)邏輯的狀態(tài)機(jī)。

假定每個(gè)節(jié)點(diǎn)都知道集群拓?fù)?，能夠把任意key映射到相應(yīng)的數(shù)據(jù)分片，把數(shù)據(jù)分片映射到節(jié)點(diǎn)。如果節(jié)點(diǎn)判斷被請求的key屬于本地分片，就會(huì)在本地查找(上圖中上面的方框)。假如節(jié)點(diǎn)判斷請求的key屬于另一個(gè)節(jié)點(diǎn)X，他會(huì)發(fā)送一個(gè)永久重定向命令給客戶端(上圖中下方的方框)。永久重定向意味著客戶端可以緩存分片和節(jié)點(diǎn)間的映射關(guān)系。如果分片遷移正在進(jìn)行，遷出節(jié)點(diǎn)和遷入節(jié)點(diǎn)會(huì)標(biāo)記相應(yīng)的分片并且將分片的數(shù)據(jù)加鎖逐條加鎖然后開始移動(dòng)。遷出節(jié)點(diǎn)首先會(huì)在本地查找key，如果沒有找到，重定向客戶端到遷入節(jié)點(diǎn)，假如key已經(jīng)遷移完畢的話。這種重定向是一次性的，并且不能被緩存。遷入節(jié)點(diǎn)在本地處理重定向，但定期查詢在遷移還沒完成前被永久重定向。

動(dòng)態(tài)環(huán)境中的數(shù)據(jù)分片和復(fù)制

我們關(guān)注的另一個(gè)問題是怎么把記錄映射到物理節(jié)點(diǎn)。比較直接的方法是用一張表來記錄每個(gè)范圍的key與節(jié)點(diǎn)的映射關(guān)系，一個(gè)范圍的key對應(yīng)到一個(gè)節(jié)點(diǎn)，或者用key的hash值與節(jié)點(diǎn)數(shù)取模得到的值作為節(jié)點(diǎn)ID。但是hash取模的方法在集群發(fā)生更改的情況下就不是很好用，因?yàn)樵黾踊蛘邷p少節(jié)點(diǎn)都會(huì)引起集群內(nèi)的數(shù)據(jù)徹底重排。導(dǎo)致很難進(jìn)行復(fù)制和故障恢復(fù)。

有許多方法在復(fù)制和故障恢復(fù)的角度進(jìn)行了增強(qiáng)。最著名的就是一致性hash。網(wǎng)上已經(jīng)有很多關(guān)于一致性hash的介紹了，所以在這里我只提供一個(gè)基本介紹，僅僅為了文章內(nèi)容的完整性。下圖描繪了一致性hash的基本原理：

一致性hash從根本上來講是一個(gè)鍵值映射結(jié)構(gòu) – 它把鍵(通常是hash過的)映射到物理節(jié)點(diǎn)。鍵經(jīng)過hash之后的取值空間是一個(gè)有序的定長二進(jìn)制字符串，很顯然每個(gè)在此范圍內(nèi)的鍵都會(huì)被映射到圖A中 A、B、C三個(gè)節(jié)點(diǎn)中的某一個(gè)。為了副本復(fù)制，將取值空間閉合成一個(gè)環(huán)，沿環(huán)順時(shí)針前行直到所有副本都被映射到合適的節(jié)點(diǎn)上，如圖B所示。換句話說，Y將被定位在節(jié)點(diǎn)B上，因?yàn)樗贐的范圍內(nèi)，第一個(gè)副本應(yīng)該放置在C，第二個(gè)副本放置在A，以此類推。

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

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

這張圖畫的是一個(gè)由16個(gè)節(jié)點(diǎn)組成的集群，描繪了節(jié)點(diǎn)A是如何查找放在節(jié)點(diǎn)D上的key的。 (A) 描繪了路由，(B) 描繪了環(huán)針對節(jié)點(diǎn)A、B、C的局部圖像。在參考資料[15]中有更多關(guān)于分散式系統(tǒng)中的數(shù)據(jù)復(fù)制的內(nèi)容。

按照多個(gè)屬性的數(shù)據(jù)分片

當(dāng)只需要通過主鍵來訪問數(shù)據(jù)的時(shí)候，一致性hash的數(shù)據(jù)放置策略很有效，但是當(dāng)需要按照多個(gè)屬性來查詢的時(shí)候事情就會(huì)復(fù)雜得多。一種簡單的做法(MongoDB使用的)是用主鍵來分布數(shù)據(jù)而不考慮其他屬性。這樣做的結(jié)果是依據(jù)主鍵的查詢可以被路由到接個(gè)合適的節(jié)點(diǎn)上，但是對其他查詢的處理就要遍歷集群的所有節(jié)點(diǎn)。查詢效率的不均衡造成下面的問題：

有一個(gè)數(shù)據(jù)集，其中的每條數(shù)據(jù)都有若干屬性和相應(yīng)的值。是否有一種數(shù)據(jù)分布策略能夠使得限定了任意多個(gè)屬性的查詢會(huì)被交予盡量少的幾個(gè)節(jié)點(diǎn)執(zhí)行?

HyperDex數(shù)據(jù)庫提供了一種解決方案。基本思想是把每個(gè)屬性視作多維空間中的一個(gè)軸，將空間中的區(qū)域映射到物理節(jié)點(diǎn)上。一次查詢會(huì)被對應(yīng)到一個(gè)由空間中多個(gè)相鄰區(qū)域組成的超平面，所以只有這些區(qū)域與該查詢有關(guān)。讓我們看看參考資料[6]中的一個(gè)例子：

每一條數(shù)據(jù)都是一條用戶信息，有三個(gè)屬性First Name 、Last Name 和Phone Number。這些屬性被視作一個(gè)三維空間，可行的數(shù)據(jù)分布策略是將每個(gè)象限映射到一個(gè)物理節(jié)點(diǎn)。像“First Name = John”這樣的查詢對應(yīng)到一個(gè)貫穿4個(gè)象限的平面，也即只有4個(gè)節(jié)點(diǎn)會(huì)參與處理此次查詢。有兩個(gè)屬性限制的查詢對應(yīng)于一條貫穿兩個(gè)象限的直線，如上圖所示，因此只有2個(gè)節(jié)點(diǎn)會(huì)參與處理。

這個(gè)方法的問題是空間象限會(huì)呈屬性數(shù)的指數(shù)函數(shù)增長。結(jié)果就會(huì)是，只有幾個(gè)屬性限制的查詢會(huì)投射到許多個(gè)空間區(qū)域，也即許多臺(tái)服務(wù)器。將一個(gè)屬性較多的數(shù)據(jù)項(xiàng)拆分成幾個(gè)屬性相對較少的子項(xiàng)，并將每個(gè)子項(xiàng)都映射到一個(gè)獨(dú)立的子空間，而不是將整條數(shù)據(jù)映射到一個(gè)多維空間，這樣可以一定程度上緩解這個(gè)問題：

這樣能夠提供更好的查詢到節(jié)點(diǎn)的映射，但是增加了集群協(xié)調(diào)的復(fù)雜度，因?yàn)檫@種情況下一條數(shù)據(jù)會(huì)散布在多個(gè)獨(dú)立的子空間，而每個(gè)子空間都對應(yīng)各自的若干個(gè)物理節(jié)點(diǎn)，數(shù)據(jù)更新時(shí)就必須考慮事務(wù)問題。參考資料 [6]有這種技術(shù)的更多介紹和實(shí)現(xiàn)細(xì)節(jié)。

鈍化副本

有的應(yīng)用有很強(qiáng)的隨機(jī)讀取要求，這就需要把所有數(shù)據(jù)放在內(nèi)存里。在這種情況下，將數(shù)據(jù)分片并把每個(gè)分片主從復(fù)制通常需要兩倍以上的內(nèi)存，因?yàn)槊總€(gè)數(shù)據(jù)都要在主節(jié)點(diǎn)和從節(jié)點(diǎn)上各有一份。為了在主節(jié)點(diǎn)失效的時(shí)候起到代替作用，從節(jié)點(diǎn)上的內(nèi)存大小應(yīng)該和主節(jié)點(diǎn)一樣。如果系統(tǒng)能夠容忍節(jié)點(diǎn)失效的時(shí)候出現(xiàn)短暫中斷或性能下降，也可以不要分片。

下面的圖描繪了4個(gè)節(jié)點(diǎn)上的16個(gè)分片，每個(gè)分片都有一份在內(nèi)存里，副本存在硬盤上：

灰色箭頭突出了節(jié)點(diǎn)2上的分片復(fù)制。其他節(jié)點(diǎn)上的分片也是同樣復(fù)制的。紅色箭頭描繪了在節(jié)點(diǎn)2失效的情況下副本怎樣加載進(jìn)內(nèi)存。集群內(nèi)副本的均勻分布使得只需要預(yù)留很少的內(nèi)存就可以存放節(jié)點(diǎn)失效情況下激活的副本。在上面的圖里，集群只預(yù)留了1/3的內(nèi)存就可以承受單個(gè)節(jié)點(diǎn)的失效。特別要指出的是副本的激活(從硬盤加載入內(nèi)存)會(huì)花費(fèi)一些時(shí)間，這會(huì)造成短時(shí)間的性能下降或者正在恢復(fù)中的那部分?jǐn)?shù)據(jù)服務(wù)中斷。

系統(tǒng)協(xié)調(diào)

在這部分我們將討論與系統(tǒng)協(xié)調(diào)相關(guān)的兩種技術(shù)。分布式協(xié)調(diào)是一個(gè)比較大的領(lǐng)域，數(shù)十年以來有很多人對此進(jìn)行了深入的研究。這篇文章里只涉及兩種已經(jīng)投入實(shí)用的技術(shù)。關(guān)于分布式鎖，consensus協(xié)議以及其他一些基礎(chǔ)技術(shù)的內(nèi)容可以在很多書或者網(wǎng)絡(luò)資源中找到，也可以去看參考資料[17, 18, 21]。

故障檢測

故障檢測是任何一個(gè)擁有容錯(cuò)性的分布式系統(tǒng)的基本功能。實(shí)際上所有的故障檢測協(xié)議都基于心跳通訊機(jī)制，原理很簡單，被監(jiān)控的組件定期發(fā)送心跳信息給監(jiān)控進(jìn)程(或者由監(jiān)控進(jìn)程輪詢被監(jiān)控組件)，如果有一段時(shí)間沒有收到心跳信息就被認(rèn)為失效了。除此之外，真正的分布式系統(tǒng)還要有另外一些功能要求：

自適應(yīng)。故障檢測應(yīng)該能夠應(yīng)對暫時(shí)的網(wǎng)絡(luò)故障和延遲，以及集群拓?fù)?、?fù)載和帶寬的變化。但這有很大難度，因?yàn)闆]有辦法去分辨一個(gè)長時(shí)間沒有響應(yīng)的進(jìn)程到底是不是真的失效了，因此，故障檢測需要權(quán)衡故障識別時(shí)間(花多長時(shí)間才能識別一個(gè)真正的故障，也即一個(gè)進(jìn)程失去響應(yīng)多久之后會(huì)被認(rèn)為是失效)和虛假警報(bào)率之間的輕重。這個(gè)權(quán)衡因子應(yīng)該能夠動(dòng)態(tài)自動(dòng)調(diào)整。

靈活性。乍看上去，故障檢測只需要輸出一個(gè)表明被監(jiān)控進(jìn)程是否處于工作狀態(tài)的布爾值，但在實(shí)際應(yīng)用中這是不夠的。我們來看參考資料[12]中的一個(gè)類似MapReduce的例子。有一個(gè)由一個(gè)主節(jié)點(diǎn)和若干工作節(jié)點(diǎn)組成的分布式應(yīng)用，主節(jié)點(diǎn)維護(hù)一個(gè)作業(yè)列表，并將列表中的作業(yè)分配給工作節(jié)點(diǎn)。主節(jié)點(diǎn)能夠區(qū)分不同程度的失敗。如果主節(jié)點(diǎn)懷疑某個(gè)工作節(jié)點(diǎn)掛了，他就不會(huì)再給這個(gè)節(jié)點(diǎn)分配作業(yè)。其次，隨著時(shí)間推移，如果沒有收到該節(jié)點(diǎn)的心跳信息，主節(jié)點(diǎn)就會(huì)把運(yùn)行在這個(gè)節(jié)點(diǎn)上的作業(yè)重新分配給別的節(jié)點(diǎn)。最后，主節(jié)點(diǎn)確認(rèn)這個(gè)節(jié)點(diǎn)已經(jīng)失效，并釋放所有相關(guān)資源。

可擴(kuò)展性和健壯性。失敗檢測作為一個(gè)系統(tǒng)功能應(yīng)該能夠隨著系統(tǒng)的擴(kuò)大而擴(kuò)展。他應(yīng)該是健壯和一致的，也即，即使在發(fā)生通訊故障的情況下，系統(tǒng)中的所有節(jié)點(diǎn)都應(yīng)該有一個(gè)一致的看法(即所有節(jié)點(diǎn)都應(yīng)該知道哪些節(jié)點(diǎn)是不可用的，那些節(jié)點(diǎn)是可用的，各節(jié)點(diǎn)對此的認(rèn)知不能發(fā)生沖突，不能出現(xiàn)一部分節(jié)點(diǎn)知道某節(jié)點(diǎn)A不可用，而另一部分節(jié)點(diǎn)不知道的情況)

所謂的累計(jì)失效檢測器[12]可以解決前兩個(gè)問題，Cassandra[16]對它進(jìn)行了一些修改并應(yīng)用在產(chǎn)品中。其基本工作流程如下：

對于每一個(gè)被監(jiān)控資源，檢測器記錄心跳信息到達(dá)時(shí)間Ti。

計(jì)算在統(tǒng)計(jì)預(yù)測范圍內(nèi)的到達(dá)時(shí)間的均值和方差。

假定到達(dá)時(shí)間的分布已知(下圖包括一個(gè)正態(tài)分布的公式)，我們可以計(jì)算心跳延遲(當(dāng)前時(shí)間t_now和上一次到達(dá)時(shí)間Tc之間的差值) 的概率，用這個(gè)概率來判斷是否發(fā)生故障。如參考資料[12]中所建議的，可以使用對數(shù)函數(shù)來調(diào)整它以提高可用性。在這種情況下，輸出1意味著判斷錯(cuò)誤(認(rèn)為節(jié)點(diǎn)失效)的概率是10%，2意味著1%，以此類推。

根據(jù)重要程度不同來分層次組織監(jiān)控區(qū)，各區(qū)域之間通過謠言傳播協(xié)議或者中央容錯(cuò)庫同步，這樣可以滿足擴(kuò)展性的要求，又可以防止心跳信息在網(wǎng)絡(luò)中泛濫[14]。如下圖所示(6個(gè)故障檢測器組成了兩個(gè)區(qū)域，互相之間通過謠言傳播協(xié)議或者像ZooKeeper這樣的健壯性庫來聯(lián)系)：

協(xié)調(diào)者競選

協(xié)調(diào)者競選是用于強(qiáng)一致性數(shù)據(jù)庫的一個(gè)重要技術(shù)。首先，它可以組織主從結(jié)構(gòu)的系統(tǒng)中主節(jié)點(diǎn)的故障恢復(fù)。其次，在網(wǎng)絡(luò)隔離的情況下，它可以斷開處于少數(shù)的那部分節(jié)點(diǎn)，以避免寫沖突。

Bully 算法是一種相對簡單的協(xié)調(diào)者競選算法。MongoDB 用了這個(gè)算法來決定副本集中主要的那一個(gè)。Bully 算法的主要思想是集群的每個(gè)成員都可以聲明它是協(xié)調(diào)者并通知其他節(jié)點(diǎn)。別的節(jié)點(diǎn)可以選擇接受這個(gè)聲稱或是拒絕并進(jìn)入?yún)f(xié)調(diào)者競爭。被其他所有節(jié)點(diǎn)接受的節(jié)點(diǎn)才能成為協(xié)調(diào)者。節(jié)點(diǎn)按照一些屬性來判斷誰應(yīng)該勝出。這個(gè)屬性可以是一個(gè)靜態(tài)ID，也可以是更新的度量像最近一次事務(wù)ID(最新的節(jié)點(diǎn)會(huì)勝出)。

下圖的例子展示了bully算法的執(zhí)行過程。使用靜態(tài)ID作為度量，ID值更大的節(jié)點(diǎn)會(huì)勝出：

1、最初集群有5個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)5是一個(gè)公認(rèn)的協(xié)調(diào)者。
2、假設(shè)節(jié)點(diǎn)5掛了，并且節(jié)點(diǎn)2和節(jié)點(diǎn)3同時(shí)發(fā)現(xiàn)了這一情況。兩個(gè)節(jié)點(diǎn)開始競選并發(fā)送競選消息給ID更大的節(jié)點(diǎn)。
3、節(jié)點(diǎn)4淘汰了節(jié)點(diǎn)2和3，節(jié)點(diǎn)3淘汰了節(jié)點(diǎn)2。
4、這時(shí)候節(jié)點(diǎn)1察覺了節(jié)點(diǎn)5失效并向所有ID更大的節(jié)點(diǎn)發(fā)送了競選信息。
5、節(jié)點(diǎn)2、3和4都淘汰了節(jié)點(diǎn)1。
6、節(jié)點(diǎn)4發(fā)送競選信息給節(jié)點(diǎn)5。
7、節(jié)點(diǎn)5沒有響應(yīng)，所以節(jié)點(diǎn)4宣布自己當(dāng)選并向其他節(jié)點(diǎn)通告了這一消息。

看完上述內(nèi)容，你們掌握NoSQL數(shù)據(jù)庫中怎么實(shí)現(xiàn)一個(gè)分布式算法的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！