上一篇聊了聊構(gòu)建分布式系統(tǒng)所面臨的困難，這篇將著重討論構(gòu)建容錯(cuò)分布式系統(tǒng)的算法與協(xié)議。構(gòu)建容錯(cuò)系統(tǒng)的最佳方法是使用通用抽象，允許應(yīng)用程序忽略分布式系統(tǒng)中的一些問(wèn)題。本篇我們先聊一聊線性一致性，以及與線性一致性有關(guān)的技術(shù)，后續(xù)需要了解的分布式協(xié)調(diào)服務(wù)，如：ZooKeeper等，都是基于分布式系統(tǒng)的線性一致性。

1.更強(qiáng)的一致性

大多數(shù)分布式數(shù)據(jù)庫(kù)至少提供了最終一致性，這意味著如果停止對(duì)數(shù)據(jù)庫(kù)的寫(xiě)操作并等待一段時(shí)間，最終所有讀請(qǐng)求將返回相同的值。但是，這是一個(gè)非常弱的一致性保證，所謂的一段時(shí)間并不確定。如果寫(xiě)入一個(gè)值，然后立即讀取它，就不能保證讀取到剛才寫(xiě)入的值。

最終一致性的模型對(duì)于應(yīng)用程序開(kāi)發(fā)人員來(lái)說(shuō)是個(gè)大煩惱，當(dāng)使用只提供弱一致性的數(shù)據(jù)庫(kù)時(shí)，開(kāi)發(fā)人員需要意識(shí)到它的問(wèn)題，數(shù)據(jù)庫(kù)可能會(huì)有很微妙的錯(cuò)誤，因?yàn)閼?yīng)用程序可能大部分時(shí)間都工作得很好。而當(dāng)系統(tǒng)中有故障（例如網(wǎng)絡(luò)中斷）或高并發(fā)性時(shí)，最終一致性的數(shù)據(jù)模型將會(huì)暴露很多問(wèn)題。所以數(shù)據(jù)系統(tǒng)可以選擇提供的更強(qiáng)的一致性模型,但是又會(huì)引入新的Trade-off:有更強(qiáng)一致性的系統(tǒng)雖然更容易正確使用，但是它可能比弱一致性的系統(tǒng)的性能更差或容錯(cuò)性更低，我們需要更好的理解它并且選擇最適合需求的數(shù)據(jù)模型。

線性一致性

線性一致性的思想很簡(jiǎn)單，我們用下面兩幅圖來(lái)說(shuō)明：

并發(fā)讀寫(xiě)引起的不確定性
線性一致性：任何一個(gè)讀取返回了新值之后，所有后續(xù)讀取也必須返回新值

在一個(gè)線性系統(tǒng)之中，一定會(huì)有某個(gè)時(shí)間點(diǎn)（開(kāi)始和結(jié)束的寫(xiě)操作之間），x的值從0變成了1。因此，如果一個(gè)客戶端的讀取x時(shí)返回了新值1，所有后續(xù)的讀取也必須返回新的值。

線性化與串行化

線性化與串行化不同，它不構(gòu)成事務(wù)。因此不能完全保證并發(fā)寫(xiě)的安全性。數(shù)據(jù)庫(kù)可以同時(shí)提供串行化和線性化，如兩階段鎖便是可以同時(shí)提供串行化與線性化，而序列化的快照隔離不是線性化的。

線性一致性可以解決什么問(wèn)題？

• 分布式鎖和Leader選舉
  單Leader的系統(tǒng)需要確保只有一個(gè)Leader，多個(gè)Leader會(huì)導(dǎo)致腦裂的發(fā)生。而Leader選舉的本質(zhì)是鎖的爭(zhēng)用，每個(gè)節(jié)點(diǎn)試圖獲取鎖，獲取成功的節(jié)點(diǎn)成為L(zhǎng)eader。而無(wú)論如何，這把鎖必須是線性化：所有節(jié)點(diǎn)都必須同意哪個(gè)節(jié)點(diǎn)擁有鎖，成為L(zhǎng)eader

• 唯一性約束
  唯一性約束在數(shù)據(jù)庫(kù)中很常見(jiàn)：例如，用戶名或電子郵件地址必須唯一地標(biāo)識(shí)一個(gè)用戶，而在文件存儲(chǔ)服務(wù)中，不能有兩個(gè)具有相同路徑和文件名的文件。如果你想為數(shù)據(jù)寫(xiě)入執(zhí)行這一約束（例如，如果兩人試圖同時(shí)創(chuàng)建一個(gè)用戶或一個(gè)具有相同名稱的文件，其中將返回一個(gè)錯(cuò)誤），你需要線性化。

如何實(shí)現(xiàn)線性化系統(tǒng)？

線性化意味著：如同一個(gè)單拷貝的數(shù)據(jù)，并對(duì)其所有的操作都是原子的。最簡(jiǎn)單的答案就是真的只使用一個(gè)單一的數(shù)據(jù)復(fù)制。這種方式顯然就失去了容錯(cuò)性，單一節(jié)點(diǎn)出現(xiàn)異常則系統(tǒng)將無(wú)法訪問(wèn)。而使系統(tǒng)容錯(cuò)的最常用方法是使用副本技術(shù)：

• 單Leader多Follower機(jī)制
  在單Leader多Follower機(jī)制之中，Leader擁有主副本，Follower在其他節(jié)點(diǎn)上維護(hù)數(shù)據(jù)的備份副本。可以選擇從Leader上讀，或同步更新的Follower，可以在這個(gè)基礎(chǔ)之上實(shí)現(xiàn)線性化系統(tǒng)。

• 一致性算法
  通過(guò)協(xié)商一致性協(xié)議算法可以防止腦裂和讀取過(guò)期數(shù)據(jù)，通過(guò)一致性算法可以實(shí)現(xiàn)核心數(shù)據(jù)線性化的安全存儲(chǔ)。這是ZooKeeper與Chubby等分布式協(xié)調(diào)服務(wù)的基礎(chǔ)算法。

CAP理論與一致性的代價(jià)

Eric Brewer在2000年提出CAP理論，簡(jiǎn)而言之便是：數(shù)據(jù)系統(tǒng)必須在一致性、可用性、分區(qū)容忍性的三角關(guān)系之中有所權(quán)衡，任何系統(tǒng)沒(méi)有辦法同時(shí)滿足三種特性。

所以使用線性化的一致性自然會(huì)需要在可用性上做一些妥協(xié)， 在單Leader多Follower機(jī)制之下，需要滿足線性化一致性的寫(xiě)入和讀取的客戶端必須連接到Leader。如果Leader產(chǎn)生中斷，仍然可以讀取Follower的數(shù)據(jù)，但此時(shí)就無(wú)法保證線性化的要求了。

2.全序廣播

上文已經(jīng)提到過(guò)，可以通過(guò)單Leader多Follower機(jī)制與一致性算法來(lái)實(shí)現(xiàn)一個(gè)線性化的系統(tǒng)，但是，這里還有一個(gè)很重要的內(nèi)容我們需要探討：全序廣播。
不過(guò)先不要著急，咱們先再聊一聊分布式系統(tǒng)之中的時(shí)序：

Lamport時(shí)間戳

Lamport時(shí)間戳是生成因果關(guān)系的序列號(hào)的一種方法，我們可以通過(guò)它理清分布式系統(tǒng)之中操作的順序，Leslie Lamport 在1978年提出。Lamport時(shí)間戳的實(shí)現(xiàn)很簡(jiǎn)單，每個(gè)節(jié)點(diǎn)有一個(gè)唯一計(jì)數(shù)器標(biāo)識(shí)符，并且每個(gè)節(jié)點(diǎn)都保存它的計(jì)數(shù)器。兩個(gè)節(jié)點(diǎn)有時(shí)可能具有相同的計(jì)數(shù)器值，但在計(jì)數(shù)器值之中都包含節(jié)點(diǎn)id，所以每個(gè)計(jì)數(shù)器值都可以認(rèn)為是唯一的時(shí)間戳。

Lamport時(shí)間戳沒(méi)有確切的物理時(shí)間，但它可以分布式系統(tǒng)之中的事件排序：存在兩個(gè)時(shí)間戳，一個(gè)更大計(jì)數(shù)器的時(shí)間戳是更新的值；如果計(jì)數(shù)器的值是相同的，一個(gè)更大的節(jié)點(diǎn)ID是更大的時(shí)間戳。下圖展示了Lamport時(shí)間戳的工作原理，它能夠符合分布式系統(tǒng)之中的因果關(guān)系：

Lamport時(shí)間戳排序能夠排序出因果關(guān)系

但是從Lamport時(shí)間戳的總順序來(lái)看，無(wú)法判斷兩個(gè)操作是并發(fā)的，還是它們是因果相關(guān)的。雖然Lamport時(shí)間戳能夠確認(rèn)操作的因果關(guān)系，但是在分布式系統(tǒng)之中仍然存在一些問(wèn)題：
請(qǐng)考慮一個(gè)系統(tǒng)，該系統(tǒng)需要確保用戶名唯一標(biāo)識(shí)用戶帳戶。如果兩個(gè)用戶同時(shí)嘗試創(chuàng)建具有相同用戶名的帳戶，則其中一個(gè)應(yīng)該成功，另一個(gè)應(yīng)該失敗。顯然，如果兩個(gè)相同的用戶名的賬戶創(chuàng)建，選擇具有較低的時(shí)間戳的操作成功，因?yàn)長(zhǎng)amport時(shí)間戳是完全有序的，這種比較是有效的。但是為了確保沒(méi)有其他節(jié)點(diǎn)在同時(shí)在較早的時(shí)間創(chuàng)建帳戶，所以節(jié)點(diǎn)不得不與其他每個(gè)節(jié)點(diǎn)通信進(jìn)行確認(rèn)。如果出現(xiàn)網(wǎng)絡(luò)問(wèn)題，其他節(jié)點(diǎn)中的一個(gè)已經(jīng)失效或無(wú)法到達(dá)，則系統(tǒng)也將失效。

Lamport時(shí)間戳的問(wèn)題在于：需要收集所有操作之后，操作的總順序才會(huì)出現(xiàn)。如果另一個(gè)節(jié)點(diǎn)有其他操作，在不知道的情況下，無(wú)法構(gòu)造操作的最終順序。

全序廣播

全序廣播的機(jī)制是使用：通過(guò)單Leader多Follower機(jī)制，在Leader節(jié)點(diǎn)上對(duì)所有操作進(jìn)行排序，從而決定了整個(gè)操作順序，并將操作順序進(jìn)行廣播。全序廣播可以保證全局知曉信息，而解決Lamport時(shí)間戳面臨的問(wèn)題。但是全序廣播同樣要解決這樣幾個(gè)問(wèn)題：如果吞吐量大于單Leader的處理量，那么如何擴(kuò)展系統(tǒng)，以及出現(xiàn)Leader失效的情況，如何進(jìn)行故障轉(zhuǎn)移。

全序廣播要求滿足如下兩個(gè)屬性總是被滿足：

• 可靠的交付,沒(méi)有消息丟失：如果消息被傳遞到一個(gè)節(jié)點(diǎn)，它將被傳遞給所有節(jié)點(diǎn)。
• 完全有序傳遞，消息以相同的順序傳遞給每個(gè)節(jié)點(diǎn)。

一個(gè)正確的全序廣播算法必須保證節(jié)點(diǎn)和網(wǎng)絡(luò)故障時(shí)的可靠性和有序性。一旦出現(xiàn)網(wǎng)路分化的現(xiàn)象，算法可以保持重試，仍然保持信息的有序性。全序廣播對(duì)于分布式系統(tǒng)來(lái)說(shuō)有十分重要的意義：如果每個(gè)消息表示對(duì)數(shù)據(jù)庫(kù)的寫(xiě)入，并且每個(gè)副本以相同的順序處理相同的寫(xiě)入，則副本將保持彼此一致，而各個(gè)節(jié)點(diǎn)的狀態(tài)機(jī)也能夠保持一致，可以通過(guò)這樣的方式來(lái)實(shí)現(xiàn)狀態(tài)機(jī)復(fù)制。

3.通過(guò)全序廣播實(shí)現(xiàn)線性化一致性

全序廣播是異步的：消息保證以固定的順序可靠地傳遞，但不能保證何時(shí)傳遞消息（因此存在節(jié)點(diǎn)可能落后于其他節(jié)點(diǎn)）。而線性化一致性能夠保證：每次讀操作能夠讀到最新值的寫(xiě)入。我們可以依托于全序廣播，在存儲(chǔ)上實(shí)現(xiàn)線性化一致性：

• 1.將消息append到日志中，添加要聲明的用戶名。

• 2.節(jié)點(diǎn)通過(guò)內(nèi)存之中的狀態(tài)機(jī)檢查，如果該用戶名的第一條消息，則用戶名寫(xiě)入成功。否則，終止該操作。

由于全序廣播保證了，消息是以相同的順序傳遞給所有節(jié)點(diǎn)，假設(shè)存在并發(fā)寫(xiě)入，所有節(jié)點(diǎn)都會(huì)達(dá)成共識(shí)，第一個(gè)寫(xiě)入用戶名的消息。雖然全序廣播可以保證程序的線性寫(xiě)入，但是假設(shè)進(jìn)行讀操作的節(jié)點(diǎn)卻不能保證線性讀取，因?yàn)橄鬟f的延遲性，所以讀操作的結(jié)果可能是過(guò)時(shí)的。

當(dāng)然這里可以通過(guò)返回最新日志消息的位置，通過(guò)查詢位置，等待所有條目需要讀取的條目被寫(xiě)入，再進(jìn)行讀操作，便能夠達(dá)到讀操作的線性一致性。（在ZooKeeper中通過(guò)sync()操作實(shí)現(xiàn)），或者可以通過(guò)強(qiáng)制讀取Leader節(jié)點(diǎn)的副，顯然Leader節(jié)點(diǎn)上的數(shù)據(jù)一定是最新的結(jié)果。

小結(jié)：

通過(guò)全序廣播的線性一致性，我們已經(jīng)可以實(shí)現(xiàn)一個(gè)分布式系統(tǒng)的的協(xié)調(diào)服務(wù)了。下一篇將聊一聊分布式系統(tǒng)之中的一致性協(xié)議，也是分布式系統(tǒng)最核心的概念，我們?cè)趺礃幽軌蜃尫植际降墓?jié)點(diǎn)達(dá)成一致性，難者不會(huì)，會(huì)者不難，我們下一篇見(jiàn)。

總結(jié)

以上是生活随笔為你收集整理的线性一致性与全序广播------《Designing Data-Intensive Applications》读书笔记12的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。