作者：仕祿

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

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

1. 簡介

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

在分布式系統中，數據通常需要被分散在多臺機器上，主要為了達到以下目的：

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

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

圖1 常見數據分布

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

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

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

1.2 文章系列概述

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

2. 數據復制模式

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

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

簡介

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

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

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

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

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

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

a.在某一個時間點產生一個一致性的快照。 

b.將快照拷貝到從節點。 

c.從節點連接到主節點請求所有快照點后發生的改變日志。 

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

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

處理節點失效

從節點失效——追趕式恢復

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

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

主節點失效——節點切換

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

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

問題

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

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

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

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

2.2 多主節點復制

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

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

圖3 多主節點復制

使用場景

a. 多數據中心部署

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

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

b. 離線客戶端操作

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

圖4 Notion界面

c. 協同編輯

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

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

沖突解決

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

a. 沖突實例

圖5 沖突實例

在圖中，由于多主節點采用異步復制，用戶將數據寫入到自己的網頁就返回成功了，但當嘗試把數據復制到另一個主節點時就會出問題，這里我們如果假設主節點更新時采用類似CAS的更新方式時更新時，都會由于預期值不符合從而拒絕更新。針對這樣的沖突，書中給出了幾種常見的解決思路。

b. 解決思路

1. 避免沖突

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

2. 收斂于一致狀態

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

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

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

3. 用戶自行處理

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

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

c. 處理細節介紹

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

1. 直接指定事件順序

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

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

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

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

圖6 違背因果關系示例

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

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

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

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

圖7 掃碼點餐示例

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

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

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

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

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

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

2.3 無主節點復制

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

處理節點失效

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

圖8 Quorum寫入處理節點失效

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

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

讀寫Quorum

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

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

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

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

• 在實際實現中，一般數據會發送或讀取所有節點，w和r決定了我們需要等待幾個節點的寫入或讀取確認。

Quorum一致性的局限性

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

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

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

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

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

如果某些副本寫入成功，其他副本寫入失敗（磁盤空間滿）且總的成功數少于w，那些成功的副本數據并不會回滾，這意味著及時寫入失敗，后續還是可能讀到新值。

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

2.4 本章小結

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

3. 分布式系統的挑戰

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

3.1 部分失效

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

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

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

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

3.2 分布式系統特有的故障

不可靠的網絡

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

圖9 不可靠的網絡

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

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

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

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

應對之道

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

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

a. 負載均衡需要避免往失效的節點上發數據（服務發現模塊中的健康檢查功能）。 

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

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

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

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

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

3.2 不可靠的時鐘

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

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

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

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

圖10 不可靠的時鐘

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

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

如何在這艱難的環境中設計系統

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

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

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

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

1. 同步模型

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

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

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

3. 異步模型

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

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

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

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

Safety and Liveness

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

4. 總結

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

5. 作者簡介

仕祿，美團基礎研發平臺/數據科學與平臺部工程師。