從在校大二開始到如今參加工作，接觸了不少關(guān)于分布式的東西。但總是感覺分布式基礎(chǔ)理論知識很含糊，不清晰。打算在這一周里梳理下相關(guān)的知識線路。

CAP理論

CAP理論又稱CAP定理，指的是在一個分布式系統(tǒng)中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分區(qū)容錯性），三者不可得兼。

CAP

三個特性進(jìn)行了如下歸納：

• 一致性（C）：在分布式系統(tǒng)中的所有數(shù)據(jù)備份，在同一時刻是否同樣的值。等同于所有節(jié)點(diǎn)訪問同一份最新的數(shù)據(jù)副本。
• 可用性（A）：在集群中一部分節(jié)點(diǎn)故障后，集群整體是否還能響應(yīng)客戶端的讀寫請求。對數(shù)據(jù)更新具備高可用性。
• 可擴(kuò)展性/分區(qū)容忍性（P）：以實(shí)際效果而言，分區(qū)相當(dāng)于對通信的時限要求。系統(tǒng)如果不能在時限內(nèi)達(dá)成數(shù)據(jù)一致性，就意味著發(fā)生了分區(qū)的情況，必須就當(dāng)前操作在C和A之間做出選擇。

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

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

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

BASE理論

BASE是Basically Available（基本可用）、Soft state（軟狀態(tài)）和Eventually consistent（最終一致性）三個短語的簡寫，BASE是對CAP中一致性和可用性權(quán)衡的結(jié)果，其來源于對大規(guī)?；ヂ?lián)網(wǎng)系統(tǒng)分布式實(shí)踐的結(jié)論，是基于CAP定理逐步演化而來的，其核心思想是即使無法做到強(qiáng)一致性（Strong consistency），但每個應(yīng)用都可以根據(jù)自身的業(yè)務(wù)特點(diǎn)，采用適當(dāng)?shù)姆绞絹硎瓜到y(tǒng)達(dá)到最終一致性（Eventual consistency）。

• 基本可用:基本可用是指分布式系統(tǒng)在出現(xiàn)不可預(yù)知故障的時候，允許損失部分可用性——但請注意，這絕不等價(jià)于系統(tǒng)不可用,舉個例子：
  • 響應(yīng)時間上的損失：正常情況下，一個在線搜索引擎需要0.5秒內(nèi)返回給用戶相應(yīng)的查詢結(jié)果，但由于出現(xiàn)異常（比如系統(tǒng)部分機(jī)房發(fā)生斷電或斷網(wǎng)故障），查詢結(jié)果的響應(yīng)時間增加到了1~2秒。
  • 功能上的損失：正常情況下，在一個電子商務(wù)網(wǎng)站上進(jìn)行購物，消費(fèi)者幾乎能夠順利地完成每一筆訂單，但是在一些節(jié)日大促購物高峰的時候，由于消費(fèi)者的購物行為激增，為了保護(hù)購物系統(tǒng)的穩(wěn)定性，部分消費(fèi)者可能會被引導(dǎo)到一個降級頁面。
• 弱狀態(tài)：也稱為軟狀態(tài)，和硬狀態(tài)相對，是指允許系統(tǒng)中的數(shù)據(jù)存在中間狀態(tài)，并認(rèn)為該中間狀態(tài)的存在不會影響系統(tǒng)的整體可用性，即允許系統(tǒng)在不同節(jié)點(diǎn)的數(shù)據(jù)副本之間進(jìn)行數(shù)據(jù)同步的過程存在延時。
• 最終一致性：是系統(tǒng)中所有的數(shù)據(jù)副本，在經(jīng)過一段時間的同步后，最終能夠達(dá)到一個一致的狀態(tài)。因此，最終一致性的本質(zhì)是需要系統(tǒng)保證最終數(shù)據(jù)能夠達(dá)到一致，而不需要實(shí)時保證系統(tǒng)數(shù)據(jù)的強(qiáng)一致性

一致性模型

數(shù)據(jù)一致性來說，簡單說有三種類型，當(dāng)然，如果細(xì)分的話，還有很多一致性模型，如：順序一致性，F(xiàn)IFO一致性，會話一致性，單讀一致性，單寫一致性等。下面介紹主要的三種一致性模型：

• Strong Consistency 強(qiáng)一致性：新的數(shù)據(jù)一旦寫入，在任意副本任意時刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強(qiáng)一致性的。
• Eventually 最終一致性：當(dāng)你寫入一個新值后，有可能讀不出來，但在某個時間窗口之后保證最終能讀出來。比如：DNS，電子郵件、Amazon S3，Google搜索引擎這樣的系統(tǒng)。
• Weak 弱一致性：當(dāng)你寫入一個新值后，讀操作在數(shù)據(jù)副本上可能讀出來，也可能讀不出來。比如：某些cache系統(tǒng)，網(wǎng)絡(luò)游戲其它玩家的數(shù)據(jù)和你沒什么關(guān)系，VOIP這樣的系統(tǒng)。

從這三種一致型的模型上來說，我們可以看到，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ù)操作都會讀取到最新值。但是其它用戶可能要過一會才可以看到。Facebook的數(shù)據(jù)同步就是采用這種原則。
• Session Consistency（會話一致性）：一次會話內(nèi)一旦讀到某個值，不會讀到更舊的值。
• Monotonic Read Consistency（單調(diào)一致性）：一個用戶一旦讀到某個值，不會讀到比這個值更舊的值，其他用戶不一定。

Quorum W+R>N和vector clock

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

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

配置的時候要求W+R > N。 因?yàn)閃+R > N， 所以 R > N-W 這個是什么意思呢？就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的備份的差值要大。

對于一個分布式系統(tǒng)來說，N通常都大于3，也就說同一份數(shù)據(jù)需要保存在三個以上不同的節(jié)點(diǎn)上，以防止單點(diǎn)故障。W是成功寫操作的最小節(jié)點(diǎn)數(shù)，這里的寫成功可以理解為“同步”寫，比如N=3，W=1，那么只要寫成功一個節(jié)點(diǎn)就可以了，另外的兩份數(shù)據(jù)是通過異步的方式復(fù)制的。R是成功讀操作的最小節(jié)點(diǎn)數(shù)，讀操作為什么要讀多份數(shù)據(jù)呢？在分布式系統(tǒng)中，數(shù)據(jù)在不同的節(jié)點(diǎn)上可能存在著不一致的情況，繼續(xù)往下看。

NWR模型的一些設(shè)置會造成臟數(shù)據(jù)的問題，因?yàn)檫@很明顯不是像Paxos一樣是一個強(qiáng)一致的東西，所以，可能每次的讀寫操作都不在同一個結(jié)點(diǎn)上，于是會出現(xiàn)一些結(jié)點(diǎn)上的數(shù)據(jù)并不是最新版本，但卻進(jìn)行了最新的操作。也就是說，如果你讀出來數(shù)據(jù)的版本是v1，當(dāng)你計(jì)算完成后要回填數(shù)據(jù)后，卻發(fā)現(xiàn)數(shù)據(jù)的版本號已經(jīng)被人更新成了v2，那么服務(wù)器就會拒絕你，這就是版本沖突問題。

于是，Amazon的Dynamo引入了Vector Clock（矢量鐘）這個設(shè)計(jì)。這個設(shè)計(jì)讓每個結(jié)點(diǎn)各自記錄自己的版本信息，也就是說，對于同一個數(shù)據(jù)，需要記錄兩個事：1、誰更新的我，2、我的版本號是什么

看一個操作序列：

1. 對節(jié)點(diǎn)A的D數(shù)據(jù)進(jìn)行寫操作。數(shù)據(jù)D會增加一個版本信息(A，1)。我們把這個時候的數(shù)據(jù)記做D1(A，1）。

2. 然后繼續(xù)對數(shù)據(jù)節(jié)點(diǎn)A的D數(shù)據(jù)進(jìn)行寫操作處，于是對節(jié)點(diǎn)A的D數(shù)據(jù)記錄為D2(A，2)。這個時候，D2是可以覆蓋D1的，不會有沖突產(chǎn)生。

3. 現(xiàn)在我們假設(shè)D2傳播到了所有節(jié)點(diǎn)(B和C)，B和C收到的數(shù)據(jù)不是從客戶產(chǎn)生的，而是別人復(fù)制給他們的，所以他們不產(chǎn)生新的版本信息，所以現(xiàn)在B和C所持有的數(shù)據(jù)還是D2(A，2)。于是A，B，C上的數(shù)據(jù)及其版本號都是一樣的。

4. 如果我們有一個新的寫請求到了B結(jié)點(diǎn)上，于是B結(jié)點(diǎn)生成數(shù)據(jù)D3(A,2; B,1)，意思是：數(shù)據(jù)D全局版本號為3，A升了兩新，B升了一次。這就是所謂的代碼版本的log

5. 如果D3沒有傳播到C的時候又一個請求被C處理了，于是，以C結(jié)點(diǎn)上的數(shù)據(jù)是D4(A,2; C,1)

6. 最精彩的事情來了：如果這個時候來了一個讀請求，我們要記得，我們的W=1 那么R=N=3，所以R會從所有三個節(jié)點(diǎn)上讀，此時，他會讀到三個版本：

   • A結(jié)點(diǎn)：D2(A,2)
   • B結(jié)點(diǎn)：D3(A,2; B,1);
   • C結(jié)點(diǎn)：D4(A,2; C,1)

7. 這個時候可以判斷出，D2已經(jīng)是舊版本（已經(jīng)包含在D3/D4中），可以舍棄。

8. 但是D3和D4是明顯的版本沖突。于是，交給調(diào)用方自己去做版本沖突處理。就像源代碼版本管理一樣。

Dynamo的配置用的是CAP里的A和P。Vector Clock(Version Vector)只能用于發(fā)現(xiàn)數(shù)據(jù)沖突，但是想要解決數(shù)據(jù)沖突還要留給用戶去定奪（就好比git commit出現(xiàn)conflicts，需要手工解決一樣），當(dāng)然也可以設(shè)置某種策略來直接解決沖突（保留最新或集群內(nèi)多數(shù)表決）。

lease機(jī)制

一般描述如下：

• Lease 是由授權(quán)者授予的在一段時間內(nèi)的承諾。
• 授權(quán)者一旦發(fā)出 lease，則無論接受方是否收到，也無論后續(xù)接收方處于何種狀態(tài)，只要 lease 不過期，授權(quán)者一定遵守承諾，按承諾的時間、內(nèi)容執(zhí)行。
• 接收方在有效期內(nèi)可以使用頒發(fā)者的承諾，只要 lease 過期，接收方放棄授權(quán)，不再繼續(xù)執(zhí)行，要重新申請Lease。
• 可以通過版本號、時間周期，或者到某個固定時間點(diǎn)認(rèn)為Lease證書失效

通俗解釋一下：

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

即Lease是一種帶期限的契約，在此期限內(nèi)擁有Lease的節(jié)點(diǎn)有權(quán)利操作一些預(yù)設(shè)好的對象。從更深 層次上來看，Lease就是一把帶有超時機(jī)制的分布式鎖，如果沒有Lease，分布式環(huán)境中的鎖可能會因?yàn)殒i擁有者的失敗而導(dǎo)致死鎖，有了lease死鎖會被控制在超時時間之內(nèi)。

一般的應(yīng)用：

雙主問題

如果有3副本A、B、C，并通過中心結(jié)點(diǎn)M來管理。A B C互主副本。其中A節(jié)點(diǎn)為primary,且同一時刻只能有一個primary節(jié)點(diǎn)處理方法是在每個副本與中心節(jié)點(diǎn)M中維護(hù)一個心跳，期望通過心跳是否存在而判斷對方是否依舊存活。心跳方法其實(shí)根本無法解決分布式下的這個問題。考慮如下場景：

• M在某時刻未能預(yù)期收到主節(jié)點(diǎn)A的心跳，M認(rèn)為A已經(jīng)異常，于是從B、C中選取一個B作為主節(jié)點(diǎn)。但實(shí)際上A并未異常，而是由于網(wǎng)絡(luò)瞬時阻塞、或是M本身出現(xiàn)異常使A這消息暫時未收到。這時，系統(tǒng)中出現(xiàn)A、B兩個都是主節(jié)點(diǎn)的情況，稱“雙主”問題，從節(jié)點(diǎn)C可能同時從這兩個主節(jié)點(diǎn)同步數(shù)據(jù)，這會引發(fā)很嚴(yán)重的數(shù)據(jù)錯誤。

lease（租期、承諾）機(jī)制就是用來解決這類問題的：

由中心節(jié)點(diǎn)向M其他節(jié)點(diǎn)發(fā)送lease,若某個節(jié)點(diǎn)持有有效的lease,則認(rèn)為該節(jié)點(diǎn)正?？梢蕴峁┓?wù)。節(jié)點(diǎn) A、B、C 依然周期性的發(fā)送heart beat報(bào)告自身狀態(tài),節(jié)點(diǎn)M收到heart beat后發(fā)送一個lease,表示節(jié)點(diǎn)M確認(rèn)了節(jié)點(diǎn) A、B、C 的狀態(tài),并允許節(jié)點(diǎn)在 lease 有效期內(nèi)正常工作。節(jié)點(diǎn)M可以給 primary節(jié)點(diǎn)一個特殊的lease,表示節(jié)點(diǎn)可以作為primary工作。一旦節(jié)點(diǎn)M希望切換新的primary,則只需等前一個primary的lease過期,則就可以安全的頒發(fā)新的lease給新的primary節(jié)點(diǎn),從而不會出現(xiàn)“雙主”問題。實(shí)際工程實(shí)現(xiàn)時要考慮primary的lease過期的時間。

在實(shí)際系統(tǒng)中,若用一個中心節(jié)點(diǎn)發(fā)送lease也有很大的風(fēng)險(xiǎn),一旦該中心節(jié)點(diǎn)宕機(jī)或網(wǎng)絡(luò)異常,則所有的節(jié)點(diǎn)沒有l(wèi)ease,從而造成系統(tǒng)高度不可用。為此,實(shí)際系統(tǒng)總是使用多個中心節(jié)點(diǎn)互為副本,成為一個小的集群,該小集群具有高可用性,對外頒發(fā)lease的功能。

讀鎖/寫鎖（分布式鎖）

master和slave模型緩存系統(tǒng)中，其中master負(fù)責(zé)少量的讀、所有的寫和同步操作，slave負(fù)責(zé)讀操作，如何保證讀到緩存的一致性？ps(這種情況不適用于強(qiáng)一致性的應(yīng)用)

當(dāng)讀請求到來時，m節(jié)點(diǎn)在向各s節(jié)點(diǎn)發(fā)送數(shù)據(jù)時同時向節(jié)點(diǎn)頒發(fā)一個lease,一旦真實(shí)時間超過這個時間點(diǎn),則lease過期失效。在lease的有效期內(nèi),s保證不會修改對應(yīng)數(shù)據(jù)的值。因此,節(jié)點(diǎn)收到數(shù)據(jù)和lease后,將數(shù)據(jù)加入本地Cache,一旦對應(yīng)的lease超時,節(jié)點(diǎn)將對應(yīng)的本地cache數(shù)據(jù)刪除。m在修改數(shù)據(jù)時,首先阻塞所有寫的讀請求,并等待之前為該數(shù)據(jù)發(fā)出的所有l(wèi)ease超時過期,然后修改數(shù)據(jù)的值。之后重復(fù)上面的工作。

上述等lease失效的過程中，可能有新的請求請求到達(dá)，這時s又會繼續(xù)頒發(fā)新的lease，使得lease一直不結(jié)束，形成“活鎖”，即修改請求等待lease失效，而又源源不斷頒發(fā)新lease而一直無法完成。此問題形成了“活鎖”

• 解決活鎖的辦法：當(dāng)有修改請求在等待著lease失效時，如果后續(xù)有讀請求，則只返回請求數(shù)據(jù)而不頒發(fā)新lease，或者是只頒發(fā)目前最長的lease。

一致性哈希

傳統(tǒng)hash(x) % N算法的弊端：不利于架構(gòu)的伸縮性，我們?yōu)槊總€節(jié)點(diǎn)都增加一個備用節(jié)點(diǎn)，當(dāng)某個節(jié)點(diǎn)失效時，就自動切換到備用節(jié)點(diǎn)上，類似于數(shù)據(jù)庫的master和slave。但是依然無法解決增加或刪除節(jié)點(diǎn)后，需要做hash重分布的問題，也就是無法動態(tài)增刪節(jié)點(diǎn)。

這時就引入了一致性hash的概念 ，將所有的節(jié)點(diǎn)分布到一個hash環(huán)上，每個請求都落在這個hash環(huán)上的某個位置，只需要按照順時針方向找到的第一個節(jié)點(diǎn)，就是自己需要的服務(wù)節(jié)點(diǎn)。當(dāng)某個節(jié)點(diǎn)發(fā)生故障時，只需要在環(huán)上找到下一個可用節(jié)點(diǎn)即可。

Hash 環(huán)

虛擬節(jié)點(diǎn):每個虛擬節(jié)點(diǎn)都有一個對應(yīng)的物理節(jié)點(diǎn)，而每個物理節(jié)點(diǎn)可以對應(yīng)若干個虛擬節(jié)點(diǎn)。并且這些虛擬節(jié)點(diǎn)連續(xù)的分配在環(huán)上，這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時的緩存重新分布。

一篇不錯的一致性哈希文章

敬請期待系列文章

• 2PC/3PC：分布式事務(wù)
• Paxos：強(qiáng)一致性協(xié)議
• Gossip協(xié)議：節(jié)點(diǎn)管理
• Raft
• 拜占庭將軍問題
• ZAB協(xié)議
• MVCC
• 區(qū)塊鏈