作者：仕祿

分布式系統(tǒng)設計是一項十分復雜且具有挑戰(zhàn)性的事情。其中，數(shù)據(jù)復制與一致性更是其中十分重要的一環(huán)。數(shù)據(jù)復制領域概念龐雜、理論性強，如果對應的算法沒有理論驗證大概率會出錯。如果在設計過程中，不了解對應理論所解決的問題以及不同理論之間的聯(lián)系，勢必無法設計出一個合理的分布式系統(tǒng)。

本系列文章分上下兩篇，以《數(shù)據(jù)密集型應用系統(tǒng)設計（DDIA）》（下文簡稱《DDIA》）為主線，文中的核心理論講解與圖片來自于此書。在此基礎上，加入了日常工作中對這些概念的理解與個性化的思考，并將它們映射到Kafka中，跟大家分享一下如何將具體的理論應用于實際生產(chǎn)環(huán)境中。

1. 簡介

1.1 簡介——使用復制的目的

在分布式系統(tǒng)中，數(shù)據(jù)通常需要被分散在多臺機器上，主要為了達到以下目的：

1. 擴展性，數(shù)據(jù)量因讀寫負載巨大，一臺機器無法承載，數(shù)據(jù)分散在多臺機器上可以有效地進行負載均衡，達到靈活的橫向擴展。
2. 容錯、高可用，在分布式系統(tǒng)中，單機故障是常態(tài)，在單機故障下仍然希望系統(tǒng)能夠正常工作，這時候就需要數(shù)據(jù)在多臺機器上做冗余，在遇到單機故障時其他機器就可以及時接管。
3. 統(tǒng)一的用戶體驗，如果系統(tǒng)客戶端分布在多個地域，通常考慮在多個地域部署服務，以方便用戶能夠就近訪問到他們所需要的數(shù)據(jù)，獲得統(tǒng)一的用戶體驗。

數(shù)據(jù)的多機分布的方式主要有兩種，一種是將數(shù)據(jù)分片保存，每個機器保存數(shù)據(jù)的部分分片（Kafka中稱為Partition，其他部分系統(tǒng)稱為Shard），另一種則是完全的冗余，其中每一份數(shù)據(jù)叫做一個副本（Kafka中稱為Replica），通過數(shù)據(jù)復制技術實現(xiàn)。在分布式系統(tǒng)中，兩種方式通常會共同使用，最后的數(shù)據(jù)分布往往是下圖的樣子，一臺機器上會保存不同數(shù)據(jù)分片的若干個副本。本系列博文主要介紹的是數(shù)據(jù)如何做復制，分區(qū)則是另一個主題，不在本文的討論范疇。

圖1 常見數(shù)據(jù)分布

復制的目標需要保證若干個副本上的數(shù)據(jù)是一致的，這里的“一致”是一個十分不確定的詞，既可以是不同副本上的數(shù)據(jù)在任何時刻都保持完全一致，也可以是不同客戶端不同時刻訪問到的數(shù)據(jù)保持一致。一致性的強弱也會不同，有可能需要任何時候不同客端都能訪問到相同的新的數(shù)據(jù)，也有可能是不同客戶端某一時刻訪問的數(shù)據(jù)不相同，但在一段時間后可以訪問到相同的數(shù)據(jù)。因此，“一致性”是一個值得單獨抽出來細說的詞。在下一篇文章中，我們將重點介紹這個詞在不同上下文之間的含義。

此時，大家可能會有疑問，直接讓所有副本在任意時刻都保持一致不就行了，為啥還要有各種不同的一致性呢？我們認為有兩個考量點，第一是性能，第二則是復雜性。

性能比較好理解，因為冗余的目的不完全是為了高可用，還有延遲和負載均衡這類提升性能的目的，如果只一味地為了地強調(diào)數(shù)據(jù)一致，可能得不償失。復雜性是因為分布式系統(tǒng)中，有著比單機系統(tǒng)更加復雜的不確定性，節(jié)點之間由于采用不大可靠的網(wǎng)絡進行傳輸，并且不能共享統(tǒng)一的一套系統(tǒng)時間和內(nèi)存地址（后文會詳細進行說明），這使得原本在一些單機系統(tǒng)上很簡單的事情，在轉到分布式系統(tǒng)上以后就變得異常復雜。這種復雜性和不確定性甚至會讓我們懷疑，這些副本上的數(shù)據(jù)真的能達成一致嗎？下一篇文章會專門詳細分析如何設計算法來應對這種復雜和不確定性。

1.2 文章系列概述

本系列博文將分為上下兩篇，第一篇將主要介紹幾種常見的數(shù)據(jù)復制模型，然后介紹分布式系統(tǒng)的挑戰(zhàn)，讓大家對分布式系統(tǒng)一些稀奇古怪的故障有一些感性的認識。第二篇文章將針對本篇中提到的問題，分別介紹事務、分布式共識算法和一致性，以及三者的內(nèi)在聯(lián)系，再分享如何在分布式系統(tǒng)中保證數(shù)據(jù)的一致性，進而讓大家對數(shù)據(jù)復制技術有一個較為全面的認識。此外，本系列還將介紹業(yè)界驗證分布式算法正確性的一些工具和框架。接下來，讓我們一起開始數(shù)據(jù)復制之旅吧！

2. 數(shù)據(jù)復制模式

總體而言，最常見的復制模式有三種，分別為主從模式、多主節(jié)點模式、無主節(jié)點模式，下面分別進行介紹。

2.1 最簡單的復制模式——主從模式

簡介

對復制而言，最直觀的方法就是將副本賦予不同的角色，其中有一個主副本，主副本將數(shù)據(jù)存儲在本地后，將數(shù)據(jù)更改作為日志，或者以更改流的方式發(fā)到各個從副本（后文也會稱節(jié)點）中。在這種模式下，所有寫請求就全部會寫入到主節(jié)點上，讀請求既可以由主副本承擔也可以由從副本承擔，這樣對于讀請求而言就具備了擴展性，并進行了負載均衡。但這里面存在一個權衡點，就是客戶端視角看到的一致性問題。這個權衡點存在的核心在于，數(shù)據(jù)傳輸是通過網(wǎng)絡傳遞的，數(shù)據(jù)在網(wǎng)絡中傳輸?shù)臅r間是不能忽略的。

圖2 同步復制與異步復制如上圖所示，在這個時間窗口中，任何情況都有可能發(fā)生。在這種情況下，客戶端何時算寫入完成，會決定其他客戶端讀到數(shù)據(jù)的可能性。這里我們假設這份數(shù)據(jù)有一個主副本和一個從副本，如果主副本保存后即向客戶端返回成功，這樣叫做異步復制（1）。而如果等到數(shù)據(jù)傳送到從副本1，并得到確認之后再返回客戶端成功，稱為同步復制（2）。這里我們先假設系統(tǒng)正常運行，在異步同步下，如果從副本承擔讀請求，假設reader1和reader2同時在客戶端收到寫入成功后發(fā)出讀請求，兩個reader就可能讀到不一樣的值。

為了避免這種情況，實際上有兩種角度的做法，第一種角度是讓客戶端只從主副本讀取數(shù)據(jù)，這樣，在正常情況下，所有客戶端讀到的數(shù)據(jù)一定是一致的（Kafka當前的做法）；另一種角度則是采用同步復制，假設使用純的同步復制，當有多個副本時，任何一個副本所在的節(jié)點發(fā)生故障，都會使寫請求阻塞，同時每次寫請求都需要等待所有節(jié)點確認，如果副本過多會極大影響吞吐量。而如果僅采用異步復制并由主副本承擔讀請求，當主節(jié)點故障發(fā)生切換時，一樣會發(fā)生數(shù)據(jù)不一致的問題。

很多系統(tǒng)會把這個決策權交給用戶，這里我們以Kafka為例，首先提供了同步與異步復制的語義（通過客戶端的acks參數(shù)確定），另外提供了ISR機制，而只需要ISR中的副本確認即可，系統(tǒng)可以容忍部分節(jié)點因為各種故障而脫離ISR，那樣客戶端將不用等待其確認，增加了系統(tǒng)的容錯性。當前Kafka未提供讓從節(jié)點承擔讀請求的設計，但在高版本中已經(jīng)有了這個Feature。這種方式使系統(tǒng)有了更大的靈活性，用戶可以根據(jù)場景自由權衡一致性和可用性。

主從模式下需要的一些能力

增加新的從副本（節(jié)點）1. 在Kafka中，我們所采取的的方式是通過新建副本分配的方式，以追趕的方式從主副本中同步數(shù)據(jù)。2. 數(shù)據(jù)庫所采用的的方式是通過快照+增量的方式實現(xiàn)。

a.在某一個時間點產(chǎn)生一個一致性的快照。 

b.將快照拷貝到從節(jié)點。 

c.從節(jié)點連接到主節(jié)點請求所有快照點后發(fā)生的改變?nèi)罩尽?nbsp;

d.獲取到日志后，應用日志到自己的副本中，稱之為追趕。  

e.可能重復多輪a-d。

處理節(jié)點失效

從節(jié)點失效——追趕式恢復

針對從節(jié)點失效，恢復手段較為簡單，一般采用追趕式恢復。而對于數(shù)據(jù)庫而言，從節(jié)點可以知道在崩潰前所執(zhí)行的最后一個事務，然后連接主節(jié)點，從該節(jié)點將拉取所有的事件變更，將這些變更應用到本地記錄即可完成追趕。

對于Kafka而言，恢復也是類似的，Kafka在運行過程中，會定期項磁盤文件中寫入checkpoint，共包含兩個文件，一個是recovery-point-offset-checkpoint，記錄已經(jīng)寫到磁盤的offset，另一個則是replication-offset-checkpoint，用來記錄高水位（下文簡稱HW），由ReplicaManager寫入，下一次恢復時，Broker將讀取兩個文件的內(nèi)容，可能有些被記錄到本地磁盤上的日志沒有提交，這時就會先截斷（Truncate）到HW對應的offset上，然后從這個offset開始從Leader副本拉取數(shù)據(jù)，直到認追上Leader，被加入到ISR集合中

主節(jié)點失效——節(jié)點切換

主節(jié)點失效則會稍稍復雜一些，需要經(jīng)歷三個步驟來完成節(jié)點的切換。

1. 確認主節(jié)點失效，由于失效的原因有多種多樣，大多數(shù)系統(tǒng)會采用超時來判定節(jié)點失效。一般都是采用節(jié)點間互發(fā)心跳的方式，如果發(fā)現(xiàn)某個節(jié)點在較長時間內(nèi)無響應，則會認定為節(jié)點失效。具體到Kafka中，它是通過和Zookeeper（下文簡稱ZK）間的會話來保持心跳的，在啟動時Kafka會在ZK上注冊臨時節(jié)點，此后會和ZK間維持會話，假設Kafka節(jié)點出現(xiàn)故障（這里指被動的掉線，不包含主動執(zhí)行停服的操作），當會話心跳超時時，ZK上的臨時節(jié)點會掉線，這時會有專門的組件（Controller）監(jiān)聽到這一信息，并認定節(jié)點失效。
2. 選舉新的主節(jié)點。這里可以通過通過選舉的方式（民主協(xié)商投票，通常使用共識算法），或由某個特定的組件指定某個節(jié)點作為新的節(jié)點（Kafka的Controller）。在選舉或指定時，需要盡可能地讓新主與原主的差距最小，這樣會最小化數(shù)據(jù)丟失的風險（讓所有節(jié)點都認可新的主節(jié)點是典型的共識問題）--這里所謂共識，就是讓一個小組的節(jié)點就某一個議題達成一致，下一篇文章會重點進行介紹。
3. 重新配置系統(tǒng)是新的主節(jié)點生效，這一階段基本可以理解為對集群的元數(shù)據(jù)進行修改，讓所有外界知道新主節(jié)點的存在（Kafka中Controller通過元數(shù)據(jù)廣播實現(xiàn)），后續(xù)及時舊的節(jié)點啟動，也需要確保它不能再認為自己是主節(jié)點，從而承擔寫請求。

問題

雖然上述三個步驟較為清晰，但在實際發(fā)生時，還會存在一些問題：

1. 假設采用異步復制，在失效前，新的主節(jié)點與原主節(jié)點的數(shù)據(jù)存在Gap，選舉完成后，原主節(jié)點很快重新上線加入到集群，這時新的主節(jié)點可能會收到?jīng)_突的寫請求，此時還未完全執(zhí)行上述步驟的第三步，也就是原主節(jié)點沒有意識到自己的角色發(fā)生變化，還會嘗試向新主節(jié)點同步數(shù)據(jù)。這時，一般的做法是，將原主節(jié)點上未完成復制的寫請求丟掉，但這又可能會發(fā)生數(shù)據(jù)丟失或不一致，假設我們每條數(shù)據(jù)采用MySQL的自增ID作為主鍵，并且使用Redis作為緩存，假設發(fā)生了MySQL的主從切換，從節(jié)點的計數(shù)器落后于主節(jié)點，那樣可能出現(xiàn)應用獲取到舊的自增ID，這樣就會與Redis上對應ID取到的數(shù)據(jù)不一致，出現(xiàn)數(shù)據(jù)泄露或丟失。
2. 假設上面的問題，原主節(jié)點因為一些故障永遠不知道自己角色已經(jīng)變更，則可能發(fā)生“腦裂”，兩個節(jié)點同時操作數(shù)據(jù)，又沒有相應解決沖突（沒有設計這一模塊），就有可能對數(shù)據(jù)造成破壞。
3. 此外，對于超時時間的設定也是個十分復雜的問題，過長會導致服務不可用，設置過短則會導致節(jié)點頻繁切換，假設本身系統(tǒng)處于高負載狀態(tài)，頻繁角色切換會讓負載進一步加重（團隊內(nèi)部對Kafka僵尸節(jié)點的處理邏輯）。

異步復制面臨的主要問題——復制滯后

如前文所述，如果我們使用純的同步復制，任何一臺機器發(fā)生故障都會導致服務不可寫入，并且在數(shù)較多的情況下，吞吐和可用性都會受到比較大的影響。很多系統(tǒng)都會采用半步復制或異步復制來在可用性和一致性之間做權衡。在異步復制中，由于寫請求寫到主副本就返回成功，在數(shù)據(jù)復制到其他副本的過程中，如果客戶端進行讀取，在不同副本讀取到的數(shù)據(jù)可能會不一致，《DDIA》將這個種現(xiàn)象稱為復制滯后（Replication Lag），存在這種問題的復制行為所形成的數(shù)據(jù)一致性統(tǒng)稱為最終一致性。未來還會重點介紹一下一致性和共識，但在本文不做過多的介紹，感興趣的同學可以提前閱讀《Problems with Replication Lag》這一章節(jié)。

2.2 多主節(jié)點復制

前文介紹的主從復制模型中存在一個比較嚴重的弊端，就是所有寫請求都需要經(jīng)過主節(jié)點，因為只存在一個主節(jié)點，就很容易出現(xiàn)性能問題。雖然有從節(jié)點作為冗余應對容錯，但對于寫入請求實際上這種復制方式是不具備擴展性的。

此外，如果客戶端來源于多個地域，不同客戶端所感知到的服務相應時間差距會非常大。因此，有些系統(tǒng)順著傳統(tǒng)主從復制進行延伸，采用多個主節(jié)點同時承擔寫請求，主節(jié)點接到寫入請求之后將數(shù)據(jù)同步到從節(jié)點，不同的是，這個主節(jié)點可能還是其他節(jié)點的從節(jié)點。復制模式如下圖所示，可以看到兩個主節(jié)點在接到寫請求后，將數(shù)據(jù)同步到同一個數(shù)據(jù)中心的從節(jié)點。此外，該主節(jié)點還將不斷同步在另一數(shù)據(jù)中心節(jié)點上的數(shù)據(jù)，由于每個主節(jié)點同時處理其他主節(jié)點的數(shù)據(jù)和客戶端寫入的數(shù)據(jù)，因此需要模型中增加一個沖突處理模塊，最后寫到主節(jié)點的數(shù)據(jù)需要解決沖突。

圖3 多主節(jié)點復制

使用場景

a. 多數(shù)據(jù)中心部署

一般采用多主節(jié)點復制，都是為了做多數(shù)據(jù)中心容災或讓客戶端就近訪問（用一個高大上的名詞叫做異地多活），在同一個地域使用多主節(jié)點意義不大，在多個地域或者數(shù)據(jù)中心部署相比主從復制模型有如下的優(yōu)勢：

• 性能提升：性能提升主要表現(xiàn)在兩個核心指標上，首先從吞吐方面，傳統(tǒng)的主從模型所有寫請求都會經(jīng)過主節(jié)點，主節(jié)點如果無法采用數(shù)據(jù)分區(qū)的方式進行負載均衡，可能存在性能瓶頸，采用多主節(jié)點復制模式下，同一份數(shù)據(jù)就可以進行負載均衡，可以有效地提升吞吐。另外，由于多個主節(jié)點分布在多個地域，處于不同地域的客戶端可以就近將請求發(fā)送到對應數(shù)據(jù)中心的主節(jié)點，可以最大程度地保證不同地域的客戶端能夠以相似的延遲讀寫數(shù)據(jù)，提升用戶的使用體驗。
• 容忍數(shù)據(jù)中心失效：對于主從模式，假設主節(jié)點所在的數(shù)據(jù)中心發(fā)生網(wǎng)絡故障，需要發(fā)生一次節(jié)點切換才可將流量全部切換到另一個數(shù)據(jù)中心，而采用多主節(jié)點模式，則可無縫切換到新的數(shù)據(jù)中心，提升整體服務的可用性。

b. 離線客戶端操作

除了解決多個地域容錯和就近訪問的問題，還有一些有趣的場景，其中一個場景則是在網(wǎng)絡離線的情況下還能繼續(xù)工作，例如我們筆記本電腦上的筆記或備忘錄，我們不能因為網(wǎng)絡離線就禁止使用該程序，我們依然可以在本地愉快的編輯內(nèi)容（圖中標記為Offline狀態(tài)），當我們連上網(wǎng)之后，這些內(nèi)容又會同步到遠程的節(jié)點上，這里面我們把本地的App也當做其中的一個副本，那么就可以承擔用戶在本地的變更請求。聯(lián)網(wǎng)之后，再同步到遠程的主節(jié)點上。

圖4 Notion界面

c. 協(xié)同編輯

這里我們對離線客戶端操作進行擴展，假設我們所有人同時編輯一個文檔，每個人通過Web客戶端編輯的文檔都可以看做一個主節(jié)點。這里我們拿美團內(nèi)部的學城（內(nèi)部的Wiki系統(tǒng)）舉例，當我們正在編輯一份文檔的時候，基本上都會發(fā)現(xiàn)右上角會出現(xiàn)“xxx也在協(xié)同編輯文檔”的字樣，當我們保存的時候，系統(tǒng)就會自動將數(shù)據(jù)保存到本地并復制到其他主節(jié)點上，各自處理各自端上的沖突。

另外，當文檔出現(xiàn)了更新時，學城會通知我們有更新，需要我們手動點擊更新，來更新我們本地主節(jié)點的數(shù)據(jù)。書中說明，雖然不能將協(xié)同編輯完全等同于數(shù)據(jù)庫復制，但卻是有很多相似之處，也需要處理沖突問題。

沖突解決

通過上面的分析，我們了解到多主復制模型最大挑戰(zhàn)就是解決沖突，下面我們簡單看下《DDIA》中給出的通用解法，在介紹之前，我們先來看一個典型的沖突。

a. 沖突實例

圖5 沖突實例

在圖中，由于多主節(jié)點采用異步復制，用戶將數(shù)據(jù)寫入到自己的網(wǎng)頁就返回成功了，但當嘗試把數(shù)據(jù)復制到另一個主節(jié)點時就會出問題，這里我們?nèi)绻僭O主節(jié)點更新時采用類似CAS的更新方式時更新時，都會由于預期值不符合從而拒絕更新。針對這樣的沖突，書中給出了幾種常見的解決思路。

b. 解決思路

1. 避免沖突

所謂解決問題最根本的方式則是盡可能不讓它發(fā)生，如果能夠在應用層保證對特定數(shù)據(jù)的請求只發(fā)生在一個節(jié)點上，這樣就沒有所謂的“寫沖突”了。繼續(xù)拿上面的協(xié)同編輯文檔舉例，如果我們把每個人的都在填有自己姓名表格的一行里面進行編輯，這樣就可以最大程度地保證每個人的修改范圍不會有重疊，沖突也就迎刃而解了

2. 收斂于一致狀態(tài)

然而，對更新標題這種情況而言，沖突是沒法避免的，但還是需要有方法解決。對于單主節(jié)點模式而言，如果同一個字段有多次寫入，那么最后寫入的一定是最新的。ZK、KafkaController、KafkaReplica都有類似Epoch的方式去屏蔽過期的寫操作，由于所有的寫請求都經(jīng)過同一個節(jié)點，順序是絕對的，但對于多主節(jié)點而言，由于沒有絕對順序的保證，就只能試圖用一些方式來決策相對順序，使沖突最終收斂，這里提到了幾種方法：

給每個寫請求分配Uniq-ID，例如一個時間戳，一個隨機數(shù)，一個UUID或Hash值，最終取最高的ID作為最新的寫入。如果基于時間戳，則稱作最后寫入者獲勝（LWW），這種方式看上去非常直接且簡單，并且非常流行。但很遺憾，文章一開始也提到了，分布式系統(tǒng)沒有辦法在機器間共享一套統(tǒng)一的系統(tǒng)時間，所以這個方案很有可能因為這個問題導致數(shù)據(jù)丟失（時鐘漂移）。

每個副本分配一個唯一的ID，ID高的更新優(yōu)先級高于地域低的，這顯然也會丟失數(shù)據(jù)。當然，我們可以用某種方式做拼接，或利用預先定義的格式保留沖突相關信息，然后由用戶自行解決。

3. 用戶自行處理

其實，把這個操作直接交給用戶，讓用戶自己在讀取或寫入前進行沖突解決，這種例子也是屢見不鮮，Github采用就是這種方式。

這里只是簡單舉了一些沖突的例子，其實沖突的定義是一個很微妙的概念?！禗DIA》第七章介紹了更多關于沖突的概念，感興趣同學可以先自行閱讀，在下一篇文章中也會提到這個問題。

c. 處理細節(jié)介紹

此外，在書中將要結束《復制》這一章時，也詳細介紹了如何進行沖突的處理，這里也簡單進行介紹。這里我們可以思考一個問題，為什么會發(fā)生沖突？通過閱讀具體的處理手段后，我們可以嘗試這樣理解，正是因為我們對事件發(fā)生的先后順序不確定，但這些事件的處理主體都有重疊（比如都有設置某個數(shù)據(jù)的值）。通過我們對沖突的理解，加上我們的常識推測，會有這樣幾種方式可以幫我們來判斷事件的先后順序。

1. 直接指定事件順序

對于事件發(fā)生的先后順序，我們一個最直觀的想法就是，兩個請求誰新要誰的，那這里定義“最新”是個問題，一個很簡單的方式是使用時間戳，這種算法叫做最后寫入者獲勝LWW。

但分布式系統(tǒng)中沒有統(tǒng)一的系統(tǒng)時鐘，不同機器上的時間戳無法保證精確同步，那就可能存在數(shù)據(jù)丟失的風險，并且由于數(shù)據(jù)是覆蓋寫，可能不會保留中間值，那么最終可能也不是一致的狀態(tài)，或出現(xiàn)數(shù)據(jù)丟失。如果是一些緩存系統(tǒng)，覆蓋寫看上去也是可以的，這種簡單粗暴的算法是非常好的收斂沖突的方式，但如果我們對數(shù)據(jù)一致性要求較高，則這種方式就會引入風險，除非數(shù)據(jù)寫入一次后就不會發(fā)生改變。

2. 從事件本身推斷因果關系和并發(fā)

上面直接簡單粗暴的制定很明顯過于武斷，那么有沒有可能時間里面就存在一些因果關系呢，如果有我們很顯然可以通過因果關系知道到底需要怎樣的順序，如果不行再通過指定的方式呢？例如：

圖6 違背因果關系示例

這里是書中一個多主節(jié)點復制的例子，這里ClientA首先向Leader1增加一條數(shù)據(jù)x=1，然Leader1采用異步復制的方式，將變更日志發(fā)送到其他的Leader上。在復制過程中，ClientB向Leader3發(fā)送了更新請求，內(nèi)容則是更新Key為x的Value，使Value=Value+1。

原圖中想表達的是，update的日志發(fā)送到Leader2的時間早于insert日志發(fā)送到Leader2的時間，會導致更新的Key不存在。但是，這種所謂的事件關系本身就不是完全不相干的，書中稱這種關系為依賴或者Happens-before。

我們可能在JVM的內(nèi)存模型（JMM）中聽到過這個詞，在JMM中，表達的也是多個線程操作的先后順序關系。這里，如果我們把線程或者請求理解為對數(shù)據(jù)的操作（區(qū)別在于一個是對本地內(nèi)存數(shù)據(jù)，另一個是對遠程的某處內(nèi)存進行修改），線程或客戶端都是一種執(zhí)行者（區(qū)別在于是否需要使用網(wǎng)絡），那這兩種Happens-before也就可以在本質上進行統(tǒng)一了，都是為了描述事件的先后順序而生。

書中給出了檢測這類事件的一種算法，并舉了一個購物車的例子，如圖所示（以餐廳掃碼點餐的場景為例）：

圖7 掃碼點餐示例

圖中兩個客戶端同時向購物車里放東西，事例中的數(shù)據(jù)庫假設只有一個副本。

1. 首先Client1向購物車中添加牛奶，此時購物車為空，返回版本1，Value為[牛奶]。
2. 此時Client2向其中添加雞蛋，其并不知道Client1添加了牛奶，但服務器可以知道，因此分配版本號為2，并且將雞蛋和牛奶存成兩個單獨的值，最后將兩個值和版本號2返回給客戶端。此時服務端存儲了[雞蛋] 2 [牛奶]1。
3. 同理，Client1添加面粉，這時候Client1只認為添加了[牛奶]，因此將面粉與牛奶合并發(fā)送給服務端[牛奶，面粉]，同時還附帶了之前收到的版本號1，此時服務端知道，新值[牛奶，面粉]可以替換同一個版本號中的舊值[牛奶]，但[雞蛋]是并發(fā)事件，分配版本號3，返回值[牛奶，面粉] 3 [雞蛋]2。
4. 同理，Client2向購物車添加[火腿]，但在之前的請求中，返回了[雞蛋][牛奶]，因此和火腿合并發(fā)送給服務端[雞蛋，牛奶，火腿]，同時附帶了版本號2，服務端直接將新值覆蓋之前版本2的值[雞蛋]，但[牛奶，面粉]是并發(fā)事件，因此存儲值為[牛奶，面粉] 3 [雞蛋，牛奶，火腿] 4并分配版本號4。
5. 最后一次Client添加培根，通過之前返回的值里，知道有[牛奶，面粉，雞蛋]，Client將值合并[牛奶，面粉，雞蛋，培根]聯(lián)通之前的版本號一起發(fā)送給服務端，服務端判斷[牛奶，面粉，雞蛋，培根]可以覆蓋之前的[牛奶，面粉]但[雞蛋，牛奶，火腿]是并發(fā)值，加以保留。

通過上面的例子，我們看到了一個根據(jù)事件本身進行因果關系的確定。書中給出了進一步的抽象流程：

• 服務端為每個主鍵維護一個版本號，每當主鍵新值寫入時遞增版本號，并將新版本號和寫入值一起保存。
• 客戶端寫主鍵，寫請求比包含之前讀到的版本號，發(fā)送的值為之前請求讀到的值和新值的組合，寫請求的相應也會返回對當前所有的值，這樣就可以一步步進行拼接。
• 當服務器收到有特定版本號的寫入時，覆蓋該版本號或更低版本號的所有值，保留高于請求中版本號的新值（與當前寫操作屬于并發(fā)）。

有了這套算法，我們就可以檢測出事件中有因果關系的事件與并發(fā)的事件，而對于并發(fā)的事件，仍然像上文提到的那樣，需要依據(jù)一定的原則進行合并，如果使用LWW，依然可能存在數(shù)據(jù)丟失的情況。因此，需要在服務端程序的合并邏輯中需要額外做些事情。

在購物車這個例子中，比較合理的是合并新值和舊值，即最后的值是[牛奶，雞蛋，面粉，火腿，培根]，但這樣也會導致一個問題，假設其中的一個用戶刪除了一項商品，但是union完還是會出現(xiàn)在最終的結果中，這顯然不符合預期。因此可以用一個類似的標記位，標記記錄的刪除，這樣在合并時可以將這個商品踢出，這個標記在書中被稱為墓碑（Tombstone）。

2.3 無主節(jié)點復制

之前介紹的復制模式都是存在明確的主節(jié)點，從節(jié)點的角色劃分的，主節(jié)點需要將數(shù)據(jù)復制到從節(jié)點，所有寫入的順序由主節(jié)點控制。但有些系統(tǒng)干脆放棄了這個思路，去掉了主節(jié)點，任何副本都能直接接受來自客戶端的寫請求，或者再有一些系統(tǒng)中，會給到一個協(xié)調(diào)者代表客戶端進行寫入（以Group Commit為例，由一個線程積攢所有客戶端的請求統(tǒng)一發(fā)送），與多主模式不同，協(xié)調(diào)者不負責控制寫入順序，這個限制的不同會直接影響系統(tǒng)的使用方式。

處理節(jié)點失效

假設一個數(shù)據(jù)系統(tǒng)擁有三個副本，當其中一個副本不可用時，在主從模式中，如果恰好是主節(jié)點，則需要進行節(jié)點切換才能繼續(xù)對外提供服務，但在無主模式下，并不存在這一步驟，如下圖所示：

圖8 Quorum寫入處理節(jié)點失效

這里的Replica3在某一時刻無法提供服務，此時用戶可以收到兩個Replica的寫入成功的確認，即可認為寫入成功，而完全可以忽略那個無法提供服務的副本。當失效的節(jié)點恢復時，會重新提供讀寫服務，此時如果客戶端向這個副本讀取數(shù)據(jù)，就會請求到過期值。為了解決這個問題，這里客戶端就不是簡單向一個節(jié)點請求數(shù)據(jù)了，而是向所有三個副本請求，這時可能會收到不同的響應，這時可以通過類似版本號來區(qū)分數(shù)據(jù)的新舊（類似上文中并發(fā)寫入的檢測方式）。這里可能有一個問題，副本恢復之后難道就一直讓自己落后于其他副本嗎？這肯定不行，這會打破一致性的語義，因此需要一個機制。有兩種思路：

1. 客戶端讀取時對副本做修復，如果客戶端通過并行讀取多個副本時，讀到了過期的數(shù)據(jù)，可以將數(shù)據(jù)寫入到舊副本中，以便追趕上新副本。
2. 反熵查詢，一些系統(tǒng)在副本啟動后，后臺會不斷查找副本之間的數(shù)據(jù)diff，將diff寫到自己的副本中，與主從復制模式不同的是，此過程不保證寫入的順序，并可能引發(fā)明顯的復制滯后。

讀寫Quorum

上文中的實例我們可以看出，這種復制模式下，要想保證讀到的是寫入的新值，每次只從一個副本讀取顯然是有問題的，那么需要每次寫幾個副本呢，又需要讀取幾個副本呢？這里的一個核心點就是讓寫入的副本和讀取的副本有交集，那么我們就能夠保證讀到新值了。

直接上公式： 。其中N為副本的數(shù)量，w為每次并行寫入的節(jié)點數(shù)，r為每次同時讀取的節(jié)點數(shù)，這個公式非常容易理解，就不做過多贅述。不過這里的公式雖然看著比較直白也簡單，里面卻蘊含了一些系統(tǒng)設計思考：

• 一般配置方法，取
• w，r與N的關系決定了能夠容忍多少的節(jié)點失效

• 假設N=3, w=2, r=2，可以容忍1個節(jié)點故障。
• 假設N=5，w=3, r=3 可以容忍2個節(jié)點故障。
• N個節(jié)點可以容忍可以容忍個節(jié)點故障。

• 在實際實現(xiàn)中，一般數(shù)據(jù)會發(fā)送或讀取所有節(jié)點，w和r決定了我們需要等待幾個節(jié)點的寫入或讀取確認。

Quorum一致性的局限性

看上去這個簡單的公式就可以實現(xiàn)很強大的功能，但這里有一些問題值得注意：

• 首先，Quorum并不是一定要求多數(shù)，重要的是讀取的副本和寫入副本有重合即可，可以按照讀寫的可用性要求酌情考慮配置。
• 另外，對于一些沒有很強一致性要求的系統(tǒng)，可以配置w+r <= N，這樣可以等待更少的節(jié)點即可返回，這樣雖然有可能讀取到一個舊值，但這種配置可以很大提升系統(tǒng)的可用性，當網(wǎng)絡大規(guī)模故障時更有概率讓系統(tǒng)繼續(xù)運行而不是由于沒有達到Quorum限制而返回錯誤。
• 假設在w+r>N的情況下，實際上也存在邊界問題導致一些一致性問題：

首先假設是Sloppy Quorum（一個更為寬松的Quorum算法），寫入的w和讀取的r可能完全不相交，因此不能保證數(shù)據(jù)一定是新的。

如果兩個寫操作同時發(fā)生，那么還是存在沖突，在合并時，如果基于LWW，仍然可能導致數(shù)據(jù)丟失。

如果寫讀同時發(fā)生，也不能保證讀請求一定就能取到新值，因為復制具有滯后性（上文的復制窗口）。

如果某些副本寫入成功，其他副本寫入失?。?span style="color: #888888;">磁盤空間滿）且總的成功數(shù)少于w，那些成功的副本數(shù)據(jù)并不會回滾，這意味著及時寫入失敗，后續(xù)還是可能讀到新值。

雖然，看上去Quorum復制模式可以保證獲取到新值，但實際情況并不是我們想象的樣子，這個協(xié)議到最后可能也只能達到一個最終的一致性，并且依然需要共識算法的加持。

2.4 本章小結

以上我們介紹了所有常見的復制模式，我們可以看到，每種模式都有一定的應用場景和優(yōu)缺點，但是很明顯，光有復制模式遠遠達不到數(shù)據(jù)的一致性，因為分布式系統(tǒng)中擁有太多的不確定性，需要后面各種事務、共識算法的幫忙才能去真正對抗那些“稀奇古怪”的問題。到這里，可能會有同學就會問，到底都是些什么稀奇古怪的問題呢？相比單機系統(tǒng)又有那些獨特的問題呢？下面本文先來介紹分布式系統(tǒng)中的幾個最典型的挑戰(zhàn)（Trouble），讓一些同學小小地“絕望”一下，然后我們會下一篇文章中再揭曉答案。

3. 分布式系統(tǒng)的挑戰(zhàn)

這部分存在的意義主要想讓大家理解，為什么一些看似簡單的問題到了分布式系統(tǒng)中就會變得異常復雜。順便說一聲，這一章都是一些“奇葩”現(xiàn)象，并沒有過于復雜的推理和證明，希望大家能夠較為輕松愉悅地看完這些內(nèi)容。

3.1 部分失效

這是分布式系統(tǒng)中特有的一個名詞，這里先看一個現(xiàn)實當中的例子。假設老板想要處理一批文件，如果讓一個人做，需要十天。但老板覺得有點慢，于是他靈機一動，想到可以找十個人來搞定這件事，然后自己把工作安排好，認為這十個人一天正好干完，于是向他的上級信誓旦旦地承諾一天搞定這件事。他把這十個人叫過來，把任務分配給了他們，他們彼此建了個微信群，約定每個小時在群里匯報自己手上的工作進度，并強調(diào)在晚上5點前需要通過郵件提交最后的結果。于是老版就去愉快的喝茶去了，但是現(xiàn)實卻讓他大跌眼鏡。

首先，有個同學家里信號特別差，報告進度的時候只成功報告了3個小時的，然后老板在微信里問，也收不到任何回復，最后結果也沒法提交。另一個同學家的表由于長期沒換電池，停在了下午四點，結果那人看了兩次表都是四點，所以一點都沒著急，中間還看了個電影，慢慢悠悠做完交上去了，他還以為老板會表揚他，提前了一小時交，結果實際上已經(jīng)是晚上八點了。還有一個同學因為前一天沒睡好，效率極低，而且也沒辦法再去高強度的工作了。結果到了晚上5點，只有7個人完成了自己手頭上的工作。

這個例子可能看起來并不是非常恰當，但基本可以描述分布式系統(tǒng)特有的問題了。在分布式的系統(tǒng)中，我們會遇到各種“稀奇古怪”的故障，例如家里沒信號（網(wǎng)絡故障)，不管怎么叫都不理你，或者斷斷續(xù)續(xù)的理你。另外，因為每個人都是通過自己家的表看時間的，所謂的5點需要提交結果，在一定程度上舊失去了參考的絕對價值。因此，作為上面例子中的“老板”，不能那么自信的認為一個人干工作需要10天，就可以放心交給10個人，讓他們一天搞定。

我們需要有各種措施來應對分派任務帶來的不確定性，回到分布式系統(tǒng)中，部分失效是分布式系統(tǒng)一定會出現(xiàn)的情況。作為系統(tǒng)本身的設計人員，我們所設計的系統(tǒng)需要能夠容忍這種問題，相對單機系統(tǒng)來說，這就帶來了特有的復雜性。

3.2 分布式系統(tǒng)特有的故障

不可靠的網(wǎng)絡

對于一個純的分布式系統(tǒng)而言，它的架構大多為Share Nothing架構，即使是存算分離這種看似的Share Storage，它的底層存儲一樣是需要解決Share Nothing的。所謂Nothing，這里更傾向于叫Nothing but Network，網(wǎng)絡是不同節(jié)點間共享信息的唯一途徑，數(shù)據(jù)的傳輸主要通過以太網(wǎng)進行傳輸，這是一種異步網(wǎng)絡，也就是網(wǎng)絡本身并不保證發(fā)出去的數(shù)據(jù)包一定能被接到或是何時被收到。這里可能發(fā)生各種錯誤，如下圖所示：

圖9 不可靠的網(wǎng)絡

1. 請求丟失
2. 請求正在某個隊列中等待
3. 遠程節(jié)點已經(jīng)失效
4. 遠程節(jié)點無法響應
5. 遠程節(jié)點已經(jīng)處理完請求，但在ack的時候丟包
6. 遠程接收節(jié)點已經(jīng)處理完請求，但回復處理很慢

本文認為，造成網(wǎng)絡不可靠的原因不光是以太網(wǎng)和IP包本身，其實應用本身有時候異常也是造成網(wǎng)絡不可靠的一個誘因。因為，我們所采用的節(jié)點間傳輸協(xié)議大多是TCP，TCP是個端到端的協(xié)議，是需要發(fā)送端和接收端兩端內(nèi)核中明確維護數(shù)據(jù)結構來維持連接的，如果應用層發(fā)生了下面的問題，那么網(wǎng)絡包就會在內(nèi)核的Socket Buffer中排隊得不到處理，或響應得不到處理。

1. 應用程序GC。
2. 處理節(jié)點在進行重的磁盤I/O，導致CPU無法從中斷中恢復從而無法處理網(wǎng)絡請求。
3. 由于內(nèi)存換頁導致的顛簸。

這些問題和網(wǎng)絡本身的不穩(wěn)定性相疊加，使得外界認為的網(wǎng)絡不靠譜的程度更加嚴重。因此這些不靠譜，會極大地加重上一章中的 復制滯后性，進而帶來各種各樣的一致性問題。

應對之道

網(wǎng)絡異常相比其他單機上的錯誤而言，可能多了一種不確定的返回狀態(tài)，即延遲，而且延遲的時間完全無法預估。這會讓我們寫起程序來異常頭疼，對于上一章中的問題，我們可能無從知曉節(jié)點是否失效，因為你發(fā)的請求壓根可能不會有人響應你。因此，我們需要把上面的“不確定”變成一種確定的形式，那就是利用“超時”機制。這里引申出兩個問題：

1.  假設能夠檢測出失效，我們應該如何應對？

a. 負載均衡需要避免往失效的節(jié)點上發(fā)數(shù)據(jù)（服務發(fā)現(xiàn)模塊中的健康檢查功能）。 

b. 如果在主從復制中，如果主節(jié)點失效，需要出發(fā)選舉機制（Kafka中的臨時節(jié)點掉線，Controller監(jiān)聽到變更觸發(fā)新的選舉，Controller本身的選舉機制）。 

c. 如果服務進程崩潰，但操作系統(tǒng)運行正常，可以通過腳本通知其他節(jié)點，以便新的節(jié)點來接替（Kafka的僵尸節(jié)點檢測，會觸發(fā)強制的臨時節(jié)點掉線）。 

d. 如果路由器已經(jīng)確認目標節(jié)點不可訪問，則會返回ICMP不可達（ping不通走下線）。

2. 如何設置超時時間是合理的？

很遺憾地告訴大家，這里面實際上是個權衡的問題，短的超時時間會更快地發(fā)現(xiàn)故障，但同時增加了誤判的風險。這里假設網(wǎng)絡正常，那么如果端到端的ping時間為d，處理時間為r，那么基本上請求會在2d+r的時間完成。但在現(xiàn)實中，我們無法假設異步網(wǎng)絡的具體延遲，實際情況可能會更復雜。因此這是一個十分靠經(jīng)驗的工作。

3.2 不可靠的時鐘

說完了“信號”的問題，下面就要說說每家的“鐘表”——時鐘了，它主要用來做兩件事：

1. 描述當前的絕對時間
2. 描述某件事情的持續(xù)時間

在DDIA中，對于這兩類用途給出了兩種時間，一類成為墻上時鐘，它們會返回當前的日期和時間，例如clock_gettime(CLOCK_REALTIME) 或者System.currentTimeMills，但這類反應精確時間的API，由于時鐘同步的問題，可能會出現(xiàn)回撥的情況。因此，作為持續(xù)時間的測量通常采用單調(diào)時鐘，例如clock_gettime(CLOCK_MONOTONIC) 或者System.nanoTime。高版本的Kafka中把請求的相應延遲計算全部換成了這個API實現(xiàn)，應該也是這個原因。

這里時鐘同步的具體原理，以及如何會出現(xiàn)不準確的問題，這里就不再詳細介紹了，感興趣的同學可以自行閱讀書籍。下面將介紹一下如何使用時間戳來描述事件順序的案例，并展示如何因時鐘問題導致事件順序判斷異常的：

圖10 不可靠的時鐘

這里我們發(fā)現(xiàn)，Node1的時鐘比Node3快，當兩個節(jié)點在處理完本地請求準備寫Node2時發(fā)生了問題，原本ClientB的寫入明顯晚于ClientA的寫入，但最終的結果，卻由于Node1的時間戳更大而丟棄了本該保留的x+=1，這樣，如果我們使用LWW，一定會出現(xiàn)數(shù)據(jù)不符合預期的問題。

由于時鐘不準確，這里就引入了統(tǒng)計學中的置信區(qū)間的概念，也就是這個時間到底在一個什么樣的范圍里，一般的API是無法返回類似這樣的信息的。不過，Google的TrueTime API則恰恰能夠返回這種信息，其調(diào)用結果是一個區(qū)間，有了這樣的API，確實就可以用來做一些對其有依賴的事情了，例如Google自家的Spanner，就是使用TrueTime實現(xiàn)快照隔離。

如何在這艱難的環(huán)境中設計系統(tǒng)

上面介紹的問題是不是挺“令人絕望”的？你可能發(fā)現(xiàn)，現(xiàn)在時間可能是錯的，測量可能是不準的，你的請求可能得不到任何響應，你可能不知道它是不是還活著......這種環(huán)境真的讓設計分布式系統(tǒng)變得異常艱難，就像是你在100個人組成的大部門里面協(xié)調(diào)一些工作一樣，工作量異常的巨大且復雜。

但好在我們并不是什么都做不了，以協(xié)調(diào)這件事為例，我們肯定不是武斷地聽取一個人的意見，讓我們回到學生時代。我們需要評選一位班長，肯定我們都經(jīng)歷過投票、唱票的環(huán)節(jié)，最終得票最多的那個人當選，有時可能還需要設置一個前提，需要得票超過半數(shù)。

映射到分布式系統(tǒng)中也是如此，我們不能輕易地相信任何一臺節(jié)點的信息，因為它有太多的不確定，因此更多的情況下，在分布式系統(tǒng)中如果我們需要就某個事情達成一致，也可以采取像競選或議會一樣，大家協(xié)商、投票、仲裁決定一項提議達成一致，真相由多數(shù)人商議決定，從而達到大家的一致和統(tǒng)一，這也就是后面要介紹的分布式共識協(xié)議。這個協(xié)議能夠容忍一些節(jié)點的部分失效，或者莫名其妙的故障帶來的問題，讓系統(tǒng)能夠正常地運行下去，確保請求到的數(shù)據(jù)是可信的。

下面給出一些實際分布式算法的理論模型，根據(jù)對于延遲的假設不同，這里介紹三種系統(tǒng)模型。

1. 同步模型

該模型主要假設網(wǎng)絡延遲是有界的，我們可以清楚地知道這個延遲的上下界，不管出現(xiàn)任何情況，它都不會超出這個界限。

2. 半同步模型（大部分模型都是基于這個假設）

半同步模型認為大部分情況下，網(wǎng)絡和延遲都是正常的，如果出現(xiàn)違背的情況，偏差可能會非常大。

3. 異步模型

對延遲不作任何假設，沒有任何超時機制。而對于節(jié)點失效的處理，也存在三種模型，這里我們忽略惡意謊言的拜占庭模型，就剩下兩種。

1.崩潰-終止模型（Crash-Stop）：該模型中假設一個節(jié)點只能以一種方式發(fā)生故障，即崩潰，可能它會在任意時刻停止響應，然后永遠無法恢復。

2.崩潰-恢復模型：節(jié)點可能在任何時刻發(fā)生崩潰，可能會在一段時間后恢復，并再次響應，在該模型中假設，在持久化存儲中的數(shù)據(jù)將得以保存，而內(nèi)存中的數(shù)據(jù)會丟失。

而多數(shù)的算法都是基于半同步模型+崩潰-恢復模型來進行設計的。

Safety and Liveness

這兩個詞在分布式算法設計時起著十分關鍵的作用，其中安全性（Safety）表示沒有意外發(fā)生，假設違反了安全性原則，我們一定能夠指出它發(fā)生的時間點，并且安全性一旦違反，無法撤銷。而活性（Liveness）則表示“預期的事情最終一定會發(fā)生”，可能我們無法明確具體的時間點，但我們期望它在未來某個時間能夠滿足要求。在進行分布式算法設計時，通常需要必須滿足安全性，而活性的滿足需要具備一定的前提。

4. 總結

以上就是第一篇文章的內(nèi)容，簡單做下回顧，本文首先介紹了復制的三種常見模型，分別是主從復制、多主復制和無主復制，然后分別介紹了這三種模型的特點、適用場景以及優(yōu)缺點。接下來，我們用了一個現(xiàn)實生活中的例子，向大家展示了分布式系統(tǒng)中常見的兩個特有問題，分別是節(jié)點的部分失效以及無法共享系統(tǒng)時鐘的問題，這兩個問題為我們設計分布式系統(tǒng)帶來了比較大的挑戰(zhàn)。如果沒有一些設計特定的措施，我們所設計的分布式系統(tǒng)將無法很好地滿足設計的初衷，用戶也無法通過分布式系統(tǒng)來完成自己想要的工作。以上這些問題，我們會下篇文章《Replication（下）：事務，一致性與共識》中逐一進行解決，而事務、一致性、共識這三個關鍵詞，會為我們在設計分布式系統(tǒng)時保駕護航。

5. 作者簡介

仕祿，美團基礎研發(fā)平臺/數(shù)據(jù)科學與平臺部工程師。