[[349357]]

 分布式系統(tǒng)比起單機系統(tǒng)存在哪些難點呢?

0x01：網(wǎng)絡(luò)因素

由于服務(wù)和數(shù)據(jù)分布在不同的機器上，每次交互都需要跨機器運行，這帶來如下幾個問題：

網(wǎng)絡(luò)延遲：性能、超時

同機房的網(wǎng)絡(luò)IO還是比較塊的，但是跨機房，尤其是跨IDC，網(wǎng)絡(luò)IO就成為不可忽視的性能瓶頸了。并且，延遲不是帶寬，帶寬可以隨便增加，千兆網(wǎng)卡換成萬兆，只是成本的問題，但延遲是物理限制，基本不可能降低。

這帶來的問題就是系統(tǒng)整體性能的降低，會帶來一系列的問題，比如資源的鎖住，所以系統(tǒng)調(diào)用一般都要設(shè)置一個超時時間進(jìn)行自我保護(hù)，但是過度的延遲就會帶來系統(tǒng)的RPC調(diào)用超時，引發(fā)一個令人頭疼的問題：分布式系統(tǒng)調(diào)用的三態(tài)結(jié)果：成功、失敗、超時。不要小看這個第三態(tài)，這幾乎是所有分布式系統(tǒng)復(fù)雜性的根源。

針對這個問題有一些相應(yīng)的解決方案：異步化，失敗重試。而對于跨IDC數(shù)據(jù)分布帶來的巨大網(wǎng)絡(luò)因素影響，則一般會采用數(shù)據(jù)同步，代理專線等處理方式。

網(wǎng)絡(luò)故障：丟包、亂序、抖動。

這個可以通過將服務(wù)建立在可靠的傳輸協(xié)議上來解決，比如TCP協(xié)議。不過帶來的是更多的網(wǎng)絡(luò)交互。因此是性能和流量的一個trade off。這個在移動互聯(lián)網(wǎng)中更需要考慮。

0x02：魚與熊掌不可兼得——CAP定律

• CAP理論是由Eric Brewer提出的分布式系統(tǒng)中最為重要的理論之一：
• Consistency：一致性，事務(wù)保障，ACID模型。
• Availiablity：[高]可用性，冗余以避免單點，至少做到柔性可用(服務(wù)降級)。
• Partition tolerance：[高]可擴展性(分區(qū)容忍性)：一般要求系統(tǒng)能夠自動按需擴展，比如HBase。

CAP原理告訴我們，這三個因素最多只能滿足兩個，不可能三者兼顧。對于分布式系統(tǒng)來說，分區(qū)容錯是基本要求，所以必然要放棄一致性。對于大型網(wǎng)站來說，分區(qū)容錯和可用性的要求更高，所以一般都會選擇適當(dāng)放棄一致性。對應(yīng)CAP理論，NoSQL追求的是AP，而傳統(tǒng)數(shù)據(jù)庫追求的是CA，這也可以解釋為什么傳統(tǒng)數(shù)據(jù)庫的擴展能力有限的原因。

在CAP三者中，“可擴展性”是分布式系統(tǒng)的特有性質(zhì)。分布式系統(tǒng)的設(shè)計初衷就是利用集群多機的能力處理單機無法解決的問題。當(dāng)需要擴展系統(tǒng)性能時，一種做法是優(yōu)化系統(tǒng)的性能或者升級硬件(scale up)，一種做法就是“簡單”的增加機器來擴展系統(tǒng)的規(guī)模(scale out)。好的分布式系統(tǒng)總在追求”線性擴展性”，即性能可以隨集群數(shù)量增長而線性增長。

可用性和可擴展性一般是相關(guān)聯(lián)的，可擴展性好的系統(tǒng)，其可用性一般會比較高，因為有多個服務(wù)(數(shù)據(jù))節(jié)點，不是整體的單點。所以分布式系統(tǒng)的所有問題，基本都是在一致性與可用性和可擴展性這兩者之間的一個協(xié)調(diào)和平衡。對于沒有狀態(tài)的系統(tǒng)，不存在一致性問題，根據(jù)CAP原理，它們的可用性和分區(qū)容忍性都是很高，簡單的添加機器就可以實現(xiàn)線性擴展。而對于有狀態(tài)的系統(tǒng)，則需要根據(jù)業(yè)務(wù)需求和特性在CAP三者中犧牲其中的一者。一般來說，交易系統(tǒng)類的業(yè)務(wù)對一致性的要求比較高，一般會采用ACID模型來保證數(shù)據(jù)的強一致性，所以其可用性和擴展性就比較差。而其他大多數(shù)業(yè)務(wù)系統(tǒng)一般不需要保證強一致性，只要最終一致就可以了，它們一般采用BASE模型，用最終一致性的思想來設(shè)計分布式系統(tǒng)，從而使得系統(tǒng)可以達(dá)到很高的可用性和擴展性。

CAP定律其實也是衡量分布式系統(tǒng)的重要指標(biāo)，另一個重要的指標(biāo)是性能。

一致性模型

主要有三種：

• Strong Consistency(強一致性)：新的數(shù)據(jù)一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強一致性的。
• Week Consistency(弱一致性)：不同副本上的值有新有舊，需要應(yīng)用方做更多的工作獲取最新值。比如Dynamo。
• Evantual Consistency(最終一致性)：一旦更新成功，各副本的數(shù)據(jù)最終將達(dá)到一致。

從這三種一致型的模型上來說，我們可以看到，Weak和Eventually一般來說是異步冗余的，而Strong一般來說是同步冗余的(多寫)，異步的通常意味著更好的性能，但也意味著更復(fù)雜的狀態(tài)控制。同步意味著簡單，但也意味著性能下降。

以及其他變體：

• Causal Consistency(因果一致性)：如果Process A通知Process B它已經(jīng)更新了數(shù)據(jù)，那么Process B的后續(xù)讀取操作則讀取A寫入的最新值，而與A沒有因果關(guān)系的C則可以最終一致性。
• Read-your-writes Consistency(讀你所寫一致性)：如果Process A寫入了最新的值，那么 Process A的后續(xù)操作都會讀取到最新值。但是其它用戶可能要過一會才可以看到。
• Session Consistency(會話一致性)：一次會話內(nèi)一旦讀到某個值，不會讀到更舊的值。
• Monotonic Read Consistency(單調(diào)一致性)：一個用戶一旦讀到某個值，不會讀到比這個值更舊的值，其他用戶不一定。

其中最重要的變體是第二條：Read-your-Writes Consistency。特別適用于數(shù)據(jù)的更新同步，用戶的修改馬上對自己可見，但是其他用戶可以看到他老的版本。Facebook的數(shù)據(jù)同步就是采用這種原則。

0x03：分布式系統(tǒng)常用技術(shù)和應(yīng)用場景

• consistent hashing [with virtual node]：一致性哈希，數(shù)據(jù)分布
• vector clock：時鐘向量，多版本數(shù)據(jù)修改
• Quorum W+R>N [with vector clock]：抽屜原理，數(shù)據(jù)一致性的另一種解決方案。時鐘向量，多版本數(shù)據(jù)修改。
• Merkle tree [with anti-entropy]：數(shù)據(jù)復(fù)制
• MVCC：copy-on-write與snapshot
• 2PC/3PC：分布式事務(wù)
• Paxos：強一致性協(xié)議
• Symmetry and Decentralization：對稱性和去中心化。對稱性(symmetry)簡化了系統(tǒng)的配置和維護(hù)。去中心化是對對稱性的延伸，可以避免master單點，同時方便集群scale out。
• Map-Reduce：分而治之;移動數(shù)據(jù)不如移動計算。將計算盡量調(diào)度到與存儲節(jié)點在同一臺物理機器上的計算節(jié)點上進(jìn)行，這稱之為本地化計算。本地化計算是計算調(diào)度的一種重要優(yōu)化。
• Gossip協(xié)議：節(jié)點管理
• Lease機制：

consistent hashing：一致性哈希，解決數(shù)據(jù)均衡分布問題

我們通常使用的hash算法是hash() mod n，但是如果發(fā)生某個節(jié)點失效時，無法快速切換到其他節(jié)點。為了解決單點故障的問題，我們?yōu)槊總€節(jié)點都增加一個備用節(jié)點，當(dāng)某個節(jié)點失效時，就自動切換到備用節(jié)點上，類似于數(shù)據(jù)庫的master和slave。但是依然無法解決增加或刪除節(jié)點后，需要做hash重分布的問題，也就是無法動態(tài)增刪節(jié)點。這時就引入了一致性hash的概念 ，將所有的節(jié)點分布到一個hash環(huán)上，每個請求都落在這個hash環(huán)上的某個位置，只需要按照順時針方向找到的第一個節(jié)點，就是自己需要的服務(wù)節(jié)點。當(dāng)某個節(jié)點發(fā)生故障時，只需要在環(huán)上找到下一個可用節(jié)點即可。

一致性hash算法最常用于分布式cache中，比如注意的memcached。Dynamo也用其作為數(shù)據(jù)分布算法，并且對一致性算法進(jìn)行了改進(jìn)，提出了基于虛擬節(jié)點的改進(jìn)算法，其核心思路是引入虛擬節(jié)點，每個虛擬節(jié)點都有一個對應(yīng)的物理節(jié)點，而每個物理節(jié)點可以對應(yīng)若干個虛擬節(jié)點。

關(guān)于一致性hash的更多內(nèi)容，可以參考筆者另一篇博文：Memcached的分布式算法學(xué)習(xí)。

這篇文章也可以看看：某分布式應(yīng)用實踐一致性哈希的一些問題

virtual node

前面說過，有的Consistent Hashing的實現(xiàn)方法采用了虛擬節(jié)點的思想。使用一般的hash函數(shù)的話，服務(wù)器的映射地點的分布非常不均勻。因此，使用虛擬節(jié)點的思想，為每個物理節(jié)點(服務(wù)器)在continuum上分配100～200個點。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時的緩存重新分布。

Quorum W+R>N：抽屜原理，數(shù)據(jù)一致性的另一種解決方案

N: 復(fù)制的節(jié)點數(shù)，即一份數(shù)據(jù)被保存的份數(shù)。R: 成功讀操作的最小節(jié)點數(shù)，即每次讀取成功需要的份數(shù)。W: 成功寫操作的最小節(jié)點數(shù) ，即每次寫成功需要的份數(shù)。

所以 W+R>N的意思是：對于有N份拷貝的分布式系統(tǒng)，寫到W(W<=N)份成功算寫成功，讀R(R<=N)份數(shù)據(jù)算讀成功。

這三個因素決定了可用性，一致性和分區(qū)容錯性。W+R>N可以保證數(shù)據(jù)的一致性(C)，W越大數(shù)據(jù)一致性越高。這個NWR模型把CAP的選擇權(quán)交給了用戶，讓用戶自己在功能，性能和成本效益之間進(jìn)行權(quán)衡。

對于一個分布式系統(tǒng)來說，N通常都大于3，也就說同一份數(shù)據(jù)需要保存在三個以上不同的節(jié)點上，以防止單點故障。W是成功寫操作的最小節(jié)點數(shù)，這里的寫成功可以理解為“同步”寫，比如N=3，W=1，那么只要寫成功一個節(jié)點就可以了，另外的兩份數(shù)據(jù)是通過異步的方式復(fù)制的。R是成功讀操作的最小節(jié)點數(shù)，讀操作為什么要讀多份數(shù)據(jù)呢?在分布式系統(tǒng)中，數(shù)據(jù)在不同的節(jié)點上可能存在著不一致的情況，我們可以選擇讀取多個節(jié)點上的不同版本，來達(dá)到增強一致性的目的。

NWR模型的一些設(shè)置會造成臟數(shù)據(jù)和版本沖突問題，所以一般要引入vector clock算法來解決這個問題。

需要保證系統(tǒng)中有max(N-W+1,N-R+1)個節(jié)點可用。

關(guān)于NWR模型，建議閱讀 分布式系統(tǒng)的事務(wù)處理，寫的很通俗易懂。

vector clock：時鐘向量，多版本數(shù)據(jù)修改

參見 分布式系統(tǒng)的事務(wù)處理，寫的很通俗易懂。

lease機制

chubby、zookeeper 獲得lease(租約)的節(jié)點得到系統(tǒng)的承諾：在有效期內(nèi)數(shù)據(jù)/節(jié)點角色等是有效的，不會變化的。

lease機制的特點：

• lease頒發(fā)過程只需要網(wǎng)絡(luò)可以單向通信，同一個lease可以被頒發(fā)者不斷重復(fù)向接受方發(fā)送。即使頒發(fā)者偶爾發(fā)送lease失敗，頒發(fā)者也可以簡單的通過重發(fā)的辦法解決。
• 機器宕機對lease機制的影響不大。如果頒發(fā)者宕機，則宕機的頒發(fā)者通常無法改變之前的承諾，不會影響lease的正確性。在頒發(fā)者機恢復(fù)后，如果頒發(fā)者恢復(fù)出了之前的lease 信息，頒發(fā)者可以繼續(xù)遵守lease的承諾。如果頒發(fā)者無法恢復(fù)lease信息，則只需等待一個最大的lease超時時間就可以使得所有的lease都失效，從而不破壞lease機制。
• lease機制依賴于有效期，這就要求頒發(fā)者和接收者的時鐘是同步的。(1)如果頒發(fā)者的時鐘比接收者的時鐘慢，則當(dāng)接收者認(rèn)為lease已經(jīng)過期的時候，頒發(fā)者依舊認(rèn)為lease有效。接收者可以用在lease到期前申請新的lease的方式解決這個問題。(2)如果頒發(fā)者的時鐘比接收者的時鐘快，則當(dāng)頒發(fā)者認(rèn)為lease已經(jīng)過期的時候，可能將lease頒發(fā)給其他節(jié)點，造成承諾失效，影響系統(tǒng)的正確性。對于這種時鐘不同步，實踐中的通常做法是將頒發(fā)者的有效期設(shè)置得比接收者的略大，只需大過時鐘誤差就可以避免對lease的有效性的影響。

工程中，常選擇的lease時長是10秒級別，這是一個經(jīng)過驗證的經(jīng)驗值，實踐中可以作為參考并綜合選擇合適的時長。

雙主問題(腦裂問題)

lease機制可以解決網(wǎng)絡(luò)分區(qū)問題造成的“雙主”問題，即所謂的“腦裂”現(xiàn)象。配置中心為一個節(jié)點發(fā)放lease，表示該節(jié)點可以作為primary節(jié)點工作。當(dāng)配置中心發(fā)現(xiàn)primary有問題時，只需要等到前一個primary的lease過期，就可以安全地頒發(fā)新的lease給新的primary節(jié)點，而不會出現(xiàn)“雙主”問題。在實際系統(tǒng)中，若用一個中心節(jié)點作為配置中心發(fā)送lease也有很大的風(fēng)險。實際系統(tǒng)總是使用多個中心節(jié)點互為副本，成為一個小的集群，該小集群具有高可用性，對外提供頒發(fā)lease的功能。chubby和zookeeper都是基于這樣的設(shè)計。

chubby一般有五臺機器組成一個集群，可以部署成兩地三機房。chubby內(nèi)部的五臺機器需要通過Paxos協(xié)議選取一個chubby master機器，其它機器是chubby slave，同一時刻只有一個chubby master。chubby相關(guān)的數(shù)據(jù)，比如鎖信息，客戶端的session信息等都需要同步到整個集群，采用半同步的做法，超過一半的機器成功就可以回復(fù)客戶端。最后可以確保只有一個和原有的chubby master保持完全同步的chubby slave被選取為新的chubby master。

Gossip協(xié)議

Gossip用于P2P系統(tǒng)中自治節(jié)點獲悉對集群認(rèn)識(如集群的節(jié)點狀態(tài)，負(fù)載情況等)。系統(tǒng)中的節(jié)點定期互相八卦，很快八卦就在整個系統(tǒng)傳開了。A、B兩個節(jié)點八卦的方式主要是：A告訴B知道哪些人的什么八卦;B告訴A這些八卦里B知道哪些更新了;B更新A告訴他的八卦...... 說是自治系統(tǒng)，其實節(jié)點中還有一些種子節(jié)點。種子節(jié)點的作用主要是在有新節(jié)點加入系統(tǒng)時體現(xiàn)。新節(jié)點加入系統(tǒng)中，先與種子節(jié)點八卦，新節(jié)點獲得系統(tǒng)信息，種子節(jié)點知道系統(tǒng)中多了新節(jié)點。其他節(jié)點定期與種子節(jié)點八卦的時候就知道有新節(jié)點加入了。各個節(jié)點互相八卦的過程中，如果發(fā)現(xiàn)某個節(jié)點的狀態(tài)很長時間都沒更新，就認(rèn)為該節(jié)點已經(jīng)宕機了。

Dynamo使用了Gossip協(xié)議來做會員和故障檢測。

2PC、3PC、Paxos協(xié)議: 分布式事務(wù)的解決方案

分布式事務(wù)很難做，所以除非必要，一般來說都是采用最終一致性來規(guī)避分布式事務(wù)。

目前底層NoSQL存儲系統(tǒng)實現(xiàn)分布式事務(wù)的只有Google的系統(tǒng)，它在Bigtable之上用Java語言開發(fā)了一個系統(tǒng) Megastore，實現(xiàn)了兩階段鎖，并通過Chubby來避免兩階段鎖協(xié)調(diào)者宕機帶來的問題。Megastore實現(xiàn)目前只有簡單介紹，還沒有相關(guān)論文。

2PC

實現(xiàn)簡單，但是效率低，所有參與者需要block，throughput低;無容錯，一個節(jié)點失敗整個事務(wù)失敗。如果第一階段完成后，參與者在第二階沒有收到?jīng)Q策，那么數(shù)據(jù)結(jié)點會進(jìn)入“不知所措”的狀態(tài)，這個狀態(tài)會block住整個事務(wù)。

3PC

改進(jìn)版的2PC，把2PC的第一個段break成了兩段: 詢問，然后再鎖資源，最后真正提交。3PC的核心理念是：在詢問的時候并不鎖定資源，除非所有人都同意了，才開始鎖資源。

3PC比2PC的好處是，如果結(jié)點處在P狀態(tài)(PreCommit)的時候發(fā)生了Fail/Timeout的問題，3PC可以繼續(xù)直接把狀態(tài)變成C狀態(tài)(Commit)，而2PC則不知所措。

不過3PC實現(xiàn)比較困難，而且無法處理網(wǎng)絡(luò)分離問題。如果preCommit消息發(fā)送后兩個機房斷開，這時候coordinator所在的機房會abort，剩余的participant會commit。

Paxos

Paxos的目的是讓整個集群的結(jié)點對某個值的變更達(dá)成一致。Paxos算法是一種基于消息傳遞的一致性算法。Paxos算法基本上來說是個民主選舉的算法——大多數(shù)的決定會成個整個集群的統(tǒng)一決定。

任何一個點都可以提出要修改某個數(shù)據(jù)的提案，是否通過這個提案取決于這個集群中是否有超過半數(shù)的結(jié)點同意(所以Paxos算法需要集群中的結(jié)點是單數(shù))。這個是Paxos相對于2PC和3PC最大的區(qū)別，在2f+1個節(jié)點的集群中，允許有f個節(jié)點不可用。

Paxos的分布式民主選舉方式，除了保證數(shù)據(jù)變更的一致性之外，還常用于單點切換，比如Master選舉。

Paxos協(xié)議的特點就是難，both 理解 and 實現(xiàn) :(

關(guān)于2PC，3PC和Paxos，強烈推薦閱讀 分布式系統(tǒng)的事務(wù)處理。

目前大部分支付系統(tǒng)其實還是在2PC的基礎(chǔ)上進(jìn)行自我改進(jìn)的。一般是引入一個差錯處理器，進(jìn)行差錯協(xié)調(diào)(回滾或者失敗處理)。

MVCC：多版本并發(fā)控制

這個是很多RDMS存儲引擎實現(xiàn)高并發(fā)修改的一個重要實現(xiàn)機制。具體可以參考：

1. 多版本并發(fā)控制(MVCC)在分布式系統(tǒng)中的應(yīng)用

2. MVCC (Oracle, Innodb, Postgres).pdf

Map-Reduce思想

1. 分而治之

2. 移動數(shù)據(jù)不如移動計算

如果計算節(jié)點和存儲節(jié)點位于不同的物理機器則計算的數(shù)據(jù)需要通過網(wǎng)絡(luò)傳輸，此種方式的開銷很大。另一種思路是，將計算盡量調(diào)度到與存儲節(jié)點在同一臺物理機器上的計算節(jié)點上進(jìn)行，這稱之為本地化計算。本地化計算是計算調(diào)度的一種重要優(yōu)化。

經(jīng)典論文和分布式系統(tǒng)學(xué)習(xí)

Dynamo

HBase

LSM Tree

• LSM(Log Structured Merge Trees)是B+ Tree一種改進(jìn)
• 犧牲了部分讀性能，用來大幅提高寫性能
• 思路：拆分樹(1)首先寫WAL，然后記錄數(shù)據(jù)到內(nèi)存中，構(gòu)建一顆有序子樹(memstore)(2)隨著子樹越來越大，內(nèi)存的子樹會flush到磁盤上(storefile)(3)讀取數(shù)據(jù)：必須遍歷所有的有序子樹(不知數(shù)據(jù)在哪棵子樹) (4) Compact：后臺線程對磁盤中的子樹進(jìn)行歸并，變成大樹(子樹多了讀得慢)

事實上，lucene的索引機制也類似HBase的LSM樹。也是寫的時候分別寫在單獨的segment，后臺進(jìn)行segement合并。