05丨Paxos算法（一）：如何在多個節點間確定某變量的值?

提到分布式算法，就不得不提 Paxos 算法，在過去幾十年里，它基本上是分布式共識的代名詞，因為當前最常用的一批共識算法都是基于它改進的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法、ZAB 協議等等。而很多同學都會在準確和系統理解 Paxos 算法上踩坑，比如，只知道它可以用來達成共識，但不知道它是如何達成共識的。

蘭伯特提出的Paxos算法包含2個部分：

1. 一個是Basic Paxos算法，描述的多節點之間如何就某個值（提案Value）達成共識；
2. 另一個是 Multi-Paxos 思想，描述的是執行多個 Basic Paxos 實例，就一系列值達成共識。

可因為蘭伯特提到的 Multi-Paxos 思想，缺少代碼實現的必要細節（比如怎么選舉領導者），所以在理解上比較難。

為了讓你理解 Paxos 算法，分別以Basic Paxos 和 Multi-Paxos 為核心，帶你了解 Basic Paxos 如何達成共識，以及針對 Basic Paxos 的局限性 Multi-Paxos 又是如何改進的。

在我看來，Basic Paxos 是 Multi-Paxos 思想的核心，說白了，MultiPaxos 就是多執行幾次 Basic Paxos。所以掌握它之后，你能更好地理解后幾講基于 Multi-Paxos 思想的共識算法（比如 Raft 算法），還能掌握分布式共識算法的最核心內容，當現在的算法不能滿足業務需求，進行權衡折中，設計自己的算法。

來看一道思考題

假設我們要實現一個分布式集群，這個集群是由節點A、B、C組成，提供只讀KV存儲服務。你應該知道，創建只讀變量的時候，必須要對它進行賦值，而且這個值后續沒辦法修改。因此一個節點創建只讀變量后就不能再修改它了，所以所有節點必須要先對只讀變量的值達成共識，然后所有節點再一起創建這個只讀變量。

那么，當有多個客戶端（比如客戶端1、2）訪問這個系統，試圖創建同一個只讀變量（比如X），客戶端1試圖創建值為3的X，客戶端2試圖創建值為7的X，這樣要如何達成共識，實現各節點上X值的一致呢？帶著這個問題，我們進入今天的學習。

在一些經典的算法中，你會看到一些既形象又獨有的概念（比如二階段提交協議中的協調者），Basic Paxos算法也不例外。為了幫助人們更好地理解Basic Paxos算法，蘭伯特在講解時，也使用了一些獨有而且比較重要的概念，提案、準備（Prepare）請求、接受（Accept）請求、角色等等，其中最重要的就是“角色”。因為角色是對 Basic Paxos 中最核心的三個功能的抽象，比如，由接受者（Acceptor）對提議的值進行投票，并存儲接受的值。

你需要了解的三種角色

在Basic Paxos中，有提議者（Proposer）、接受者（Accetor）、學習者（Learner）三種角色，它們之間的關系如下：

看著是不是有些復雜，其實并不難理解：

1. 提議者（Proposer）：提議一個值，用于投票表決。為了方便演示，你可以把客戶端 1 和 2 看作是提議者。但在絕大多數場景中，集群中收到客戶端請求的節點，才是提議者。這樣做的好處是，對業務代碼沒有入侵性，也就是說，我們不需要在業務代碼中實現算法邏輯，就可以像使用數據庫一樣訪問后端的數據。
2. 接受者（Acceptor）：對每個提議的值進行投票，并存儲接受的值，比如 A、B、C 三個節點。 一般來說，集群中的所有節點都在扮演接受者的角色，參與共識協商，并接受和存儲數據。
3. 學習者（Learner）：被告知投票的結果，接受達成共識的值，存儲保存，不參與投票的過程。一般來說，學習者是數據備份節點，比如“Master-Slave”模型中的 Slave，被動地接受數據，容災備份。

講到這兒，你可能會有疑惑：前面不是說接收客戶端請求的節點是提議者嗎？這里怎么又是接受者呢？這是因為一個節點（或進程）可以身兼多個角色。想象一下，一個 3 節點的集群，1 個節點收到了請求，那么該節點將作為提議者發起二階段提交，然后這個節點和另外2 個節點一起作為接受者進行共識協商，就像下圖的樣子：

其實，這三個角色，在本質上代表的是三種功能：

1. 提議者代表的是接入和協調功能，收到客戶端請求后，發起二階段提交，進行共識協商；
2. 接受者代表投票協商和存儲數據，對提議的值進行投票，并接受達成共識的值，存儲保存；
3. 學習者代表存儲數據，不參與共識協商，只接受達成共識的值，存值保存。

因為一個完整的算法過程是由這三個角色對應的功能組成的，所以理解這三種角色，是你理解Basic Paxos如何就提議的值達成共識的基礎。那么接下來，咱們看看如何使用Basic Paxos達成共識，解決開篇提到的那道思考題。

如何達成共識？

想象這樣一個場景，現在疫情這么嚴重，每個村的路都封得差不多了，就你的村委會不作為，遲遲沒有什么防疫的措施。你決定給村委會提交個提案，提一些防疫的建議，除了建議之外，為了和其他村民的提案做區分，你的提案還得包含一個提案編號，來起到唯一標識的作用。

與你的做法類似，在 Basic Paxos 中，蘭伯特也使用提案代表一個提議。不過在提案中，除了提案編號，還包含了提議值。為了方便演示，我使用[n, v]表示一個提案，其中 n 為提案編號，v 為提議值。

要強調一下，整個共識協商是分2個階段進行的（也就是二階段提交），那么具體要如何協商呢？

我們假設客戶端1的提案編號為1，客戶端2的提案編號為5，并假設節點A、B先收到來自客戶端1的準備請求，節點C先收到來自客戶端2的準備請求。

準備（Prepare）階段

先來看第一個階段，首先客戶端 1、2 作為提議者，分別向所有接受者發送包含提案編號的準備請求：

你要注意，在準備請求中是不需要指定提議的值的，只需要攜帶提案編號就可以了，這是很多同學容易產生誤解的地方。

接著，當節點A、B收到的提案編號為1的準備請求，節點C收到提案編號為5的準備請求后，將進行這樣的處理：

1. 由于之前沒有通過任何提案，所以節點A、B將返回一個“尚無提案”的響應。也就是說節點A和B在告訴提議者，我之前沒有通過任何提案呢，并承諾以后不再響應提案編號小于等于1的準備請求，不會通過編號小于1的提案。
2. 節點C也是如此，它將返回一個“尚無提案”的響應，并承諾以后不再響應提案編號小于等于 5 的準備請求，不會通過編號小于 5 的提案。

另外，當節點A、B收到編號為5的準備請求，和節點C收到提案編號為1的準備請求的時候，將進行這樣的處理過程：

1. 當節點A、B收到提案編號為5的準備請求的時候，因為提案編號5大于它們之前響應的準備請求的提案編號1，而且兩個節點都沒有通過任何提案，所以它將返回一個“尚無提案”的響應，并承諾以后不再響應提案小于等于5的準備請求，不會通過編號小于 5 的提案。
2. 當節點C收到提案編號為1的準備請求的時候，由于提案編號1小于它之前響應的準備請求的提案編號5，所以丟棄該準備請求，不做響應。

接受（Accept）階段

第二個階段也就是接受階段，首先客戶端1、2在收到大多數節點的準備響應之后，會分別發送接收請求：

1. 當客戶端1收到大多數的接受者（節點A、B）的準備響應后，根據響應中提案編號最大的提案的值，設置接受請求中的值。因為該值在來自節點A、B的準備響應中都為空（也就是“尚無提案”），所以就把自己的提議值3作為提案的值，發送接受請求[1, 3]。
2. 當客戶端3收到大多數的接受者的準備響應后（節點A、B和節點C），根據響應中提案編號最大的提案的值，來設置接受請求中的值。因為該值來自節點A、B、C的準備響應中都為空（也就是“尚無提案”），所以就把自己的提議值7作為提案的值，發送接受請求[5, 7]。

當三個節點收到2個客戶端的接受請求時，會進行這樣的處理：

1. 當節點A、B、C收到接受請求[1, 3]的時候，由于提案的提案編號1小于三個節點承諾能通過的提案的最小提案編號5，所以提案[1, 3]將被拒絕。
2. 當節點 A、B、C 收到接受請求[5, 7]的時候，由于提案的提案編號5 不小于三個節點承諾能通過的提案的最小提案編號 5，所以就通過提案[5, 7]，也就是接受了值 7，三個節點就 X 值為 7 達成了共識。

講到這兒我想補充一下，如果集群中有學習者，當接受者通過了一個提案時，就通知給所有的學習者。當學習者發現大多數的接受者都通過了某個提案，那么它也通過該提案，接受該提案的值。

通過上面的演示過程，你可以看到，最終各節點就 X 的值達成了共識。那么在這里我還想強調一下，Basic Paxos 的容錯能力，源自“大多數”的約定，你可以這么理解：當少于一半的節點出現故障的時候，共識協商仍然在正常工作。

內容小結

本節課我主要帶你了解了 Basic Paxos 的原理和一些特點，我希望你明確這樣幾個重點。

1. 你可以看到，Basic Paxos 是通過二階段提交的方式來達成共識的。二階段提交是達成共識的常用方式，如果你需要設計新的共識算法的時候，也可以考慮這個方式。
2. 除了共識，Basic Paxos 還實現了容錯，在少于一半的節點出現故障時，集群也能工作。它不像分布式事務算法那樣，必須要所有節點都同意后才提交操作，因為“所有節點都同意”這個原則，在出現節點故障的時候會導致整個集群不可用。也就是說，“大多數節點都同意”的原則，賦予了 Basic Paxos 容錯的能力，讓它能夠容忍
   少于一半的節點的故障。
3. 本質上而言，提案編號的大小代表著優先級，你可以這么理解，根據提案編號的大小，接受者保證三個承諾，具體來說：如果準備請求的提案編號，小于等于接受者已經響應的準備請求的提案編號，那么接受者將承諾不響應這個準備請求；如果接受請求中的提案的提案編號，小于接受者已經響應的準備請求的提案編號，那么接受者將承諾不通過這個提案；如果接受者之前有通過提案，那么接受者將承諾，會在準備請求的響應中，包含已經通過的最大編號的提案信息。

課堂思考

在示例中，如果節點 A、B 已經通過了提案[5, 7]，節點 C 未通過任何提案，那么當客戶端 3 提案編號為 9 時，通過 Basic Paxos 執行“SET X = 6”，最終三個節點上 X 值是多少呢？為什么呢？

節點A、B、C上的X值都是7。

原因：在Prepare階段，提議者（客戶端3）發現已有大多數節點（A和B）接受了提案[5,7]（值7），因此必須選擇值7（而不是6）進行提交，最終所有節點接受提案[9,7]。

06丨Paxos算法（二）：Multi-Paxos不是一個算法，而是統稱

Basic Paxos 只能就單個值（Value）達成共識，一旦遇到為一系列的值實現共識的時候，它就不管用了。雖然蘭伯特提到可以通過多次執行 Basic Paxos 實例（比如
每接收到一個值時，就執行一次 Basic Paxos 算法）實現一系列值的共識。但是，很多同學讀完論文后，應該還是兩眼摸黑，雖然每個英文單詞都能讀懂，但還是不理解蘭伯特提到的 Multi-Paxos，為什么Multi-Paxos 這么難理解呢？

在我看來，蘭伯特并沒有把 Multi-Paxos 講清楚，只是介紹了大概的思想，缺少算法過程的細節和編程所必須的細節（比如缺少選舉領導者的細節）。這也就導致每個人實現的 Multi-Paxos 都不一樣。不過從本質上看，大家都是在蘭伯特提到的 Multi-Paxos 思想上補充細節，設計自己的 Multi-Paxos 算法，然后實現它（比如 Chubby 的
Multi-Paxos 實現、Raft 算法、ZAB 協議等）。

所以在這里，我補充一下：蘭伯特提到的Multi-Paxos是一種思想，不是算法。而Multi-Paxos算法是一個統稱，它是指基于Multi-Paxos思想，通過多個Basic Paxos實例實現一系列指的共識的算法（比如Chubby的Multi-Paxos實現、Raft算法等）。這一點尤其需要你注意。

為了幫你掌握 Multi-Paxos 思想，我會先帶你了解，對于 Multi-Paxos 蘭伯特是如何思考的，也就是說，如何解決 Basic Paxos 的痛點問題；然后我再以 Chubby 的 Multi-Paxos 實現為例，具體講解一下。為啥選它呢？因為 Chubby 的 Multi-Paxos 實現，代表了 Multi-Paxos 思想在生產環境中的真正落地，它將一種思想變成了代碼實現。

蘭伯特關于 Multi-Paxos 的思考

熟悉 Basic Paxos 的同學可能還記得，Basic Paxos 是通過二階段提交來達成共識的。在第一階段，也就是準備階段，接收到大多數準備響應的提議者，才能發起接受請求進入第二階段（也就是接受階段）：

而如果我們直接通過多次執行Basic Paxos實例，來實現一系列指的共識，就會存在幾個問題：

1. 如果多個提議者同時提交提案，可能出現因為提案沖突，在準備階段沒有提議者接收到大多數準備響應，協商失敗，需要重新協商。你想象一下，一個 5 節點的集群，如果 3 個節點作為提議者同時提案，就可能發生因為沒有提議者接收大多數響應（比如 1 個提議者接收到 1 個準備響應，另外 2 個提議者分別接收到 2 個準備響應）而準備失敗，需要重新協商。
2. 2輪RPC通訊（準備階段和接受階段）往返消息多、耗性能、延遲大。你要知道，分布式系統的運行是建立在 RPC 通訊的基礎之上的，因此，延遲一直是分布式系統的痛點，是需要我們在開發分布式系統時認真考慮和優化的。

那么如何解決上面的2個問題呢？可以通過引入領導者和優化Basic Paxos執行來解決，咱們首先聊一聊領導者。

領導者（Leader）

我們可以通過引入領導者節點，也就是說，領導者節點作為唯一提議者，這樣就不存在多個提議者同時提交提案的情況，也就不存在提案沖突的情況了：

在這里，我補充一點：在論文中，蘭伯特沒有說如何選舉領導者，需要我們在實現 Multi-Paxos 算法的時候自己實現。 比如在 Chubby 中，主節點（也就是領導者節點）是通過執行 Basic Paxos 算法，進行投票選舉產生的。

那么，如何解決第二個問題，也就是如何優化 Basic Paxos 執行呢？

優化Basic Paxos執行

我們可以采用“當領導者處于穩定狀態時，省掉準備階段，直接進入接受階段”這個優化機制，優化Basic Paxos執行。也就是說，領導者節點上，序列中的命令是最新的，不再需要通過準備請求來發現之前被大多數節點通過的提案，領導者可以獨立指定提案中的值。這時，領導者在提交命令時，可以省掉準備階段，直接進入到接受階段：

你看，和重復執行Basic Paxos相比，Multi-Paxos引入領導者節點之后，因為只有領導者節點一個提議者，只有它說了算，所以就不存在提案沖突。另外，當主節點處于穩定狀態時，就省掉準備階段，直接進入接受階段，所以在很大程度上減少了往返的消息數，提升了性能，降低了延遲。

Chubby的Multi-Paxos實現

既然蘭伯特只是大概的介紹了 Multi-Paxos 思想，那么 Chubby 是如何補充細節，實現 Multi-Paxos 算法的呢？

首先，它通過引入主節點，實現了蘭伯特提到的領導者（Leader）節點的特性。也就是說，主節點作為唯一提議者，這樣就不存在多個提議者同時提交提案的情況，也就不存在提案沖突的情況了。

另外，在 Chubby 中，主節點是通過執行 Basic Paxos 算法，進行投票選舉產生的，并且在運行過程中，主節點會通過不斷續租的方式來延長租期（Lease）。比如在實際場景中，幾天內都是同一個節點作為主節點。如果主節點故障了，那么其他的節點又會投票選舉出新的主節點，也就是說主節點是一直存在的，而且是唯一的。

其次，在 Chubby 中實現了蘭伯特提到的，“當領導者處于穩定狀態時，省掉準備階段，直接進入接受階段”這個優化機制。

最后，在 Chubby 中，實現了成員變更（Group membership），以此保證節點變更的時候集群的平穩運行。

在Chubby中，為了實現強一致性，讀操作也只能在主節點上執行。 也就是說，只要數據寫入成功，之后所有的客戶端讀到的數據都是一致的。具體的過程，就是下面的樣子。

所有的讀請求和寫請求都由主節點來處理。當主節點從客戶端接收到寫請求后，作為提議者，執行Basic Paxos實例，將數據發送給所有的節點，并且在大多數的服務器接受了這個寫請求之后，再響應給客戶端成功：

當主節點接收到讀請求后，處理就比較簡單了，主節點只需要查詢本地數據，然后返回給客戶端就可以了：

Chubby 的 Multi-Paxos 實現，盡管是一個閉源的實現，但這是 MultiPaxos 思想在實際場景中的真正落地，Chubby 團隊不僅編程實現了理論，還探索了如何補充細節。其中的思考和設計非常具有參考價值，不僅能幫助我們理解 Multi-Paxos 思想，還能幫助我們理解其他的 Multi-Paxos 算法（比如 Raft 算法）。

內容小結

本節課我主要帶你了解了 Basic Paxos 的局限，以及 Chubby 的Multi-Paxos 實現。我希望你明確的重點如下：

1. 蘭伯特提到的 Multi-Paxos 是一種思想，不是算法，而且還缺少算法過程的細節和編程所必須的細節，比如如何選舉領導者等，這也就導致了每個人實現的 Multi-Paxos 都不一樣。而 Multi-Paxos 算法是一個統稱，它是指基于 Multi-Paxos 思想，通過多個 Basic Paxos 實例實現一系列數據的共識的算法（比如 Chubby 的Multi Paxos 實現、Raft 算法等）。
2. Chubby 實現了主節點（也就是蘭伯特提到的領導者），也實現了蘭伯特提到的 “當領導者處于穩定狀態時，省掉準備階段，直接進入接受階段” 這個優化機制，省掉 Basic Paxos 的準備階段，提升了數據的提交效率，但是所有寫請求都在主節點處理，限制了集群處理寫請求的并發能力，約等于單機。
3. 因為在 Chubby 的 Multi-Paxos 實現中，也約定了“大多數原則”，也就是說，只要大多數節點正常運行時，集群就能正常工作，所以Chubby 能容錯（n - 1）/2 個節點的故障。
4. 本質上而言，“當領導者處于穩定狀態時，省掉準備階段，直接進入接受階段”這個優化機制，是通過減少非必須的協商步驟來提升性能的。這種方法非常常用，也很有效。比如，Google 設計的QUIC 協議，是通過減少 TCP、TLS 的協商步驟，優化 HTTPS 性能。我希望你能掌握這種性能優化思路，后續在需要時，可以通過
   減少非必須的步驟，優化系統性能。

最后，我想說的是，我個人比較喜歡 Paxos 算法（蘭伯特的 Basic Paxos 和 Multi-Paxos），雖然 Multi-Paxos 缺失算法細節，但這反而給我們提供了思考空間，讓我們可以反復思考和考據缺失的細節，比如在 Multi-Paxos 中到底需不需要選舉領導者，再比如如何實現提案
編號等等。

但我想強調，Basic Paxos 是經過證明的，而 Multi-Paxos 是一種思想，缺失實現算法的必須編程細節，這就導致，Multi-Paxos 的最終算法實現，是建立在一個未經證明的基礎之上的，正確性是個問號。

與此同時，實現 Multi-Paxos 算法，最大的挑戰是如何證明它是正確的。 比如 Chubby 的作者做了大量的測試，和運行一致性檢測腳本，驗證和觀察系統的健壯性。在實際使用時，我不推薦你設計和實現新的 Multi-Paxos 算法，而是建議優先考慮 Raft 算法，因為 Raft 的正確性是經過證明的。當 Raft 算法不能滿足需求時，你再考慮實現和優化 Multi-Paxos 算法。

課堂思考

既然，我提了 Chubby 只能在主節點上執行讀操作，那么在最后，我給你留了一個思考題，這個設計有什么局限呢？

07丨Raf算法（一）：如何選舉領導者？

Raft 算法屬于 Multi-Paxos 算法，它是在蘭伯特 Multi-Paxos 思想的基礎上，做了一些簡化和限制，比如增加了日志必須是連續的，只支持領導者、跟隨者和候選人三種狀態，在理解和算法實現上都相對容易許多。

除此之外，Raft算法是現在分布式系統開發首選的共識算法。絕大多數選用 Paxos 算法的系統（比如 Cubby、Spanner）都是在 Raft 算法發布前開發的，當時沒得選；而全新的系統大多選擇了 Raft 算法（比如 Etcd、Consul、CockroachDB）。

對你來說，掌握這個算法，可以的心應手地處理絕大部分場景的容錯和一致性需求，比如分布式配置系統、分布式NoSQL存儲等等，輕松突破系統的單機限制。

如果要用一句話概括 Raft 算法，我覺得是這樣的：從本質上說，Raft算法是通過一切以領導者為準的方式，實現一系列值的共識和各節點日志的一致。這句話比較抽象，我來做個比喻，領導者就是 Raft 算法中的霸道總裁，通過霸道的“一切以我為準”的方式，決定了日志中命令的值，也實現了各節點日志的一致。

會用三講的時間，分別以領導者選舉、日志復制、成員變更為核心，講解 Raft 算法的原理，在實戰篇中，會帶你進一步剖析 Raft 算法的實現，介紹基于 Raft 算法的分布式系統開發實戰。那么我希望從原理到實戰，在幫助你掌握分布式系統架構設計技巧和開發實戰能力的同時，加深你對 Raft 算法的理解。

在課程開始之前，我們先來看一道思考題。

既然要選舉領導者，那要從哪些成員中選舉呢？除了領導者，Raft 算法還支持哪些成員身份呢？這部分內容是你需要掌握的，最基礎的背景知識。

有哪些成員身份？

成員身份，又叫做服務器節點狀態，Raft 算法支持領導者
（Leader）、跟隨者（Follower）和候選人（Candidate） 3 種狀態。為了方便講解，我們使用不同的圖形表示不同的狀態。在任何時候，每一個服務器節點都處于這 3 個狀態中的 1 個。

1. 跟隨者：就相當于普通群眾，默默地接收和處理來自領導者的消息，當等待領導者心跳信息超時的時候，就主動站出來，推薦自己當候選人。
2. 候選人：候選人將向其他節點發送請求投票（RequestVote）RPC消息，通知其他節點來投票，如果贏得了大多數選票，就晉升當領導者。
3. 領導者：蠻不講理的霸道總裁，一切以我為準，平常的主要工作內容就是 3 部分，處理寫請求、管理日志復制和不斷地發送心跳信息，通知其他節點“我是領導者，我還活著，你們現在不要發起新的選舉，找個新領導者來替代我。”

需要你注意的是，Raft 算法是強領導者模型，集群中只能有一個“霸道總裁”。

選舉領導者的過程

那么這三個成員是怎么選出來領導者的呢？為了方便你理解，我以圖例的形式演示一個典型的領導者選舉過程。
首先，在初始狀態下，集群中所有的節點都是跟隨者的狀態。

Raft 算法實現了隨機超時時間的特性。也就是說，每個節點等待領導者節點心跳信息的超時時間間隔是隨機的。通過上面的圖片你可以看到，集群中沒有領導者，而節點 A 的等待超時時間最小（150ms），它會最先因為沒有等到領導者的心跳信息，發生超時。

這個時候，節點 A 就增加自己的任期編號，并推舉自己為候選人，先給自己投上一張選票，然后向其他節點發送請求投票 RPC 消息，請它們選舉自己為領導者。

如果其他節點接收到候選人 A 的請求投票 RPC 消息，在編號為 1 的這屆任期內，也還沒有進行過投票，那么它將把選票投給節點 A，并增加自己的任期編號。
如果候選人在選舉超時時間內贏得了大多數的選票，那么它就會成為本屆任期內新的領導者。

節點 A 當選領導者后，他將周期性地發送心跳消息，通知其他服務器我是領導者，阻止跟隨者發起新的選舉，篡權。

講到這兒，你是不是發現領導者選舉很容易理解？與現實中的議會選舉也蠻類似？當然，你可能還是對一些細節產生一些疑問：

1. 節點間是如何通訊的呢？
2. 什么是任期呢？
3. 選舉有哪些規則？
4. 隨機超時時間又是什么？

選舉過程四連問

節點間如何通訊？

在 Raft 算法中，服務器節點間的溝通聯絡采用的是遠程過程調用（RPC），在領導者選舉中，需要用到這樣兩類的 RPC：

1. 請求投票（Request Vote） RPC，是由候選人在選舉期間發起，通知各節點進行投票；
2. 日志復制（Append Entries）RPC，是由領導者發起，用來復制日志和提供心跳消息。

我想強調的是，日志復制 RPC 只能由領導者發起，這是實現強領導者模型的關鍵之一，希望你能注意這一點，后續能更好地理解日志復制，理解日志的一致是怎么實現的。

什么是任期？

我們知道，議會選舉中的領導者是有任期的，領導者任命到期后，要重新開會再次選舉。Raft 算法中的領導者也是有任期的，每個任期由單調遞增的數字（任期編號）標識，比如節點 A 的任期編號是 1。任期編號是隨著選舉的舉行而變化的，這是在說下面幾點。

1. 跟隨者在等待領導者心跳信息超時后，推薦自己為候選人時，回增加自己的任期號，比如節點A的當前任期編號為0，那么在推薦自己為候選人時，會將自己的任期編號增加為 1。
2. 如果一個服務器節點，發現自己的任期編號比其他節點小，那么它會更新自己的編號到較大的編號值。比如節點 B 的任期編號是0，當收到來自節點 A 的請求投票 RPC 消息時，因為消息中包含了節點 A 的任期編號，且編號為 1，那么節點 B 將把自己的任期編號更新為 1。

我想強調的是，與現實議會選舉中的領導者的任期不同，Raft 算法中的任期不只是時間段，而且任期編號的大小，會影響領導者選舉和請求的處理。

1. 在Raft算法中約定，如果一個候選人或者領導者，發現自己的任期編號比其他節點小，那么它會立即恢復成跟隨者狀態。比如分區錯誤恢復后，任期編號為 3 的領導者節點 B，收到來自新領導者的，包含任期編號為 4 的心跳消息，那么節點 B 將立即恢復成跟隨者狀態。
2. 還約定如果一個節點接收到一個包含較小的任期編號值的請求，那么它會直接拒絕這個請求。比如節點 C 的任期編號為 4，收到包含任期編號為 3 的請求投票 RPC 消息，那么它將拒絕這個消息。

在這里，你可以看到，Raft 算法中的任期比議會選舉中的任期要復雜。同樣，在 Raft 算法中，選舉規則的內容也會比較多。

選舉有哪些規則

在議會選舉中，比成員的身份、領導者的任期還要重要的就是選舉的規則，比如一人一票、彈劾制度等。“無規矩不成方圓”，在Raft算法中，也約定了選舉規則，主要有這樣幾點。

1. 領導者周期性地向所有跟隨者發送心跳消息（即不包含日志項的日志復制 RPC 消息），通知大家我是領導者，阻止跟隨者發起新的選舉。
2. 如果在指定時間內，跟隨者沒有接收到來自領導者的消息，那么它就認為當前沒有領導者，推舉自己為候選人，發起領導者選舉。
3. 在一次選舉中，贏得大多數選票的候選人，將晉升為領導者。
4. 在一個任期內，領導者一直都會是領導者，直到它自身出現問題（比如宕機），或者因為網絡延遲，其他節點發起一輪新的選舉。
5. 在一次選舉中，每一個服務器節點最多會對一個任期編號投出一張選票，并且按照“先來先服務”的原則進行投票。比如節點 C 的任期編號為 3，先收到了 1 個包含任期編號為 4 的投票請求（來自節點 A），然后又收到了 1 個包含任期編號為 4 的投票請求（來自節點 B）。那么節點 C 將會把唯一一張選票投給節點 A，當再收到節點 B 的投票請求 RPC 消息時，對于編號為 4 的任期，已沒有選票可投了。

6. 當任期編號相同時，日志完整性高的跟隨者（也就是最后一條日志項對應的任期編號值更大，索引號更大），拒絕投票給日志完整性低的候選人。比如節點 B、C 的任期編號都是 3，節點 B 的最后一條日志項對應的任期編號為 3，而節點 C 為 2，那么當節點 C 請求節點 B 投票給自己時，節點 B 將拒絕投票。

我想強調的是，選舉是跟隨者發起的，推舉自己為候選人；大多數選票是指集群成員半數以上的選票；大多數選票規則的目標，是為了保證在一個給定的任期內最多只有一個領導者。

其實在選舉中，除了選舉規則外，我們還需要避免一些會導致選舉失敗的情況，比如同一任期內，多個候選人同時發起選舉，導致選票被瓜分，選舉失敗。那么在 Raft 算法中，如何避免這個問題呢？答案就是隨機超時時間。

如何理解隨機超時時間

在議會選舉中，常出現未達到指定票數，選舉無效，需要重新選舉的情況。在 Raft 算法的選舉中，也存在類似的問題，那它是如何處理選舉無效的問題呢？

其實，Raft 算法巧妙地使用隨機選舉超時時間的方法，把超時時間都分散開來，在大多數情況下只有一個服務器節點先發起選舉，而不是同時發起選舉，這樣就能減少因選票瓜分導致選舉失敗的情況。

我想強調的是，在 Raft 算法中，隨機超時時間是有 2 種含義的，這里是很多同學容易理解出錯的地方，需要你注意一下：

1. 跟隨者等待領導者心跳信息超時的時間間隔，是隨機的；
2. 當沒有候選人贏得過半票數，選舉無效了，這時需要等待一個隨機時間間隔，也就是說，等待選舉超時的時間間隔，是隨機的。

內容小結

本節課我主要帶你了解了 Raft 算法的
特點、領導者選舉等。我希望你明確這樣幾個重點。

1. Raft 算法和蘭伯特的 Multi-Paxos 不同之處，主要有 2 點。首先，在 Raft 中，不是所有節點都能當選領導者，只有日志最完整的節點，才能當選領導者；其次，在 Raft 中，日志必須是連續的。
2. Raft 算法通過任期、領導者心跳消息、隨機選舉超時時間、先來先服務的投票原則、大多數選票原則等，保證了一個任期只有一位領導，也極大地減少了選舉失敗的情況。
3. 本質上，Raft 算法以領導者為中心，選舉出的領導者，以“一切以我為準”的方式，達成值的共識，和實現各節點日志的一致。

在本講，我們使用 Raft 算法在集群中選出了領導者節點 A，那么選完領導者之后，領導者需要處理來自客戶的寫請求，并通過日志復制實現各節點日志的一致（下節課我會重點帶你了解這一部分內容）。

課堂思考

Raft 算法實現了“一切以我為準”的強領導者模型，那么你不妨思考，這個設計有什么限制和局限呢？

08丨Raf算法（二）：如何復制日志?

在Raft算法中，副本數據是以日志的形式存在的，領導者接收到來自客戶端寫請求后，處理寫請求的過程就是一個復制和提交日志項的過程。

那Raft是如何復制日志的呢？又如何實現日志的一致的呢？這些內容是Raft中非常核心的內容，也就是今天講解的重點。

如何理解日志？

剛剛我提到，副本數據是以日志的形式存在的，日志是由日志項組成，日志項究竟是什么樣子呢？

其實，日志項是一種數據格式，它主要包含用戶指定的數據，也就是指令（Command），還包含一些附加信息，比如索引值（Log index）、任期編號（Term）。那你該怎么理解這些信息呢？

1. 指令：一條由客戶端請求指定的、狀態機需要執行的指令。你可以將指令理解成客戶端指定的數據。
2. 索引值：日志項對應的整數索引值。它其實就是用來標識日志項的，是一個連續的、單調遞增的整數號碼。
3. 任期編號：創建這條日志項的領導者的任期編號。

從圖中你可以看到，一屆領導者任期，往往有多條日志項。而且日志項的索引值是連續的，這一點你需要注意。

講到這兒你可能會問：不是說Raft實現了各節點間日志的一致嗎？那為什么圖中4個跟隨者的日志都不一樣呢？日志是怎么復制的呢？又該如何實現日志的一致呢？

如何復制日志？

你可以把Raft的日志復制理解成一個優化后的二階段提交（將二階段優化成了一階段），減少了一半的往返消息，也就是降低了一半的消息延遲。那日志復制的具體過程是什么呢？

首先，領導者進入第一階段，通過日志復制（Append Entries） RPC消息，將日志項復制到集群其他階段上。

接著，如果領導者接收到大多數的“復制成功”響應后，它將日志項提交到它的狀態機，并返回成功給客戶端。如果領導者沒有接收到大多數的“復制成功”響應，那么就返回錯誤給客戶端。

學到這里，有同學可能有這樣的疑問了，領導者將日志項提交到它的狀態機，怎么沒通知跟隨者提交日志項呢？

這是Raft中的一個優化，領導者不直接發送消息通知其他節點提交指定日志項。因為領導者的日志復制RPC消息或心跳消息，包含了當前最大的，將會被提交的日志項索引值。所以通過日志復制RPC消息或心跳消息，跟隨者就可以直到領導者的日志提交位置信息。

因此，當其他節點接受領導者的心跳消息，或者新的日志復制RPC消息后，就會將這條日志項提交到它的狀態機。而這個優化，降低了處理客戶端請求的延遲，將二階段提交優化為了一段提交，降低了一半的消息延遲。

為了幫你理解，我畫了一張過程圖，然后再帶你走一遍這個過程，這樣你可以更加全面地掌握日志復制。

1. 接收到客戶端請求后，領導者基于客戶端請求中的指令，創建一個新日志項，并附加到本地日志中。
2. 領導者通過日志復制RPC，將新的日志項復制到其他的服務器。
3. 當領導者將日志項，成功復制到大多數的服務器上的時候，領導者會將這條日志項提交到它的狀態機中。
4. 領導者將執行的結果返回給客戶端。
5. 當跟隨者接收到心跳信息，或者新的日志復制RPC消息后，如果跟隨者發現領導者已經提交了某條日志項，而它還沒提交，那么跟隨者就將這條日志項提交到本地的狀態機中。

不過，這是一個理想狀態下的日志復制過程。在實際環境中，復制日志的時候，你可能會遇到進程崩潰、服務器宕機等問題，這些問題會導致日志不一致。那么在這種情況下，Raft 算法是如何處理不一致日志，實現日志的一致的呢？

如何實現日志的一致？

在 Raft 算法中，領導者通過強制跟隨者直接復制自己的日志項，處理不一致日志。也就是說，Raft 是通過以領導者的日志為準，來實現各節點日志的一致的。具體有 2 個步驟。

1. 首先，領導者通過日志復制RPC的一致性檢查，找到跟隨者節點上，與自己相同日志項的最大索引值。也就是說，這個索引值之前的日志，領導者和跟隨者是一致的，之后的日志是不一致的了。
2. 然后，領導者強制跟隨者更新覆蓋的不一致日志項，實現日志的一致。

我帶你詳細地走一遍這個過程（為了方便演示，我們引入 2 個新變量）。

1. PrevLogEntry：表示當前要復制的日志項，前面一條日志項的索引值。比如在圖中，如果領導者將索引值為8的日志項發送給跟隨者，那么此時PrevLogEntey的值為7。
2. PrevLogTerm：表示當前要復制的日志項，前面一條日志項的任期編號，比如在圖中，如果領導者將索引值為 8 的日志項發送給跟隨者，那么此時 PrevLogTerm 值為 4。

1. 領導者通過日志復制 RPC信息，發送當前最新日志項到跟隨者（為了演示方便，假設當前需要復制的日志項是最新的），這個消息的 PrevLogEntry 值為 7，PrevLogTerm 值為 4。
2. 如果跟隨者在它的日志中，找不到與PrevLogEntry值為7、PrevLogTerm值為4的日志項，也就是說它的日志和領導者的不一致了，那么跟隨者就會拒絕接收新的日志項，并返回失敗信息給領導者。
3. 這時，領導者會遞減要復制的日志項的索引值，并發送新的日志項到跟隨者，這個消息的 PrevLogEntry 值為 6，PrevLogTerm 值為3。
4. 如果跟隨者在它的日志中，找到了 PrevLogEntry 值為 6、
   PrevLogTerm 值為 3 的日志項，那么日志復制 RPC 返回成功，這樣一來，領導者就知道在 PrevLogEntry 值為 6、PrevLogTerm 值為 3 的位置，跟隨者的日志項與自己相同。
5. 領導者通過日志復制 RPC，復制并更新覆蓋該索引值之后的日志項（也就是不一致的日志項），最終實現了集群各節點日志的一致。

從上面步驟中你可以看到，領導者通過日志復制 RPC 一致性檢查，找到跟隨者節點上與自己相同日志項的最大索引值，然后復制并更新覆蓋該索引值之后的日志項，實現了各節點日志的一致。需要你注意的是，跟隨者中的不一致日志項會被領導者的日志覆蓋，而且領導者從來不會覆蓋或者刪除自己的日志。

內容小結

本節課我主要帶你了解了在 Raft 中什么是日志、如何復制日志、以及如何處理不一致日志等內容。我希望你明確這樣幾個重點。

1. 在 Raft 中，副本數據是以日志的形式存在的，其中日志項中的指令表示用戶指定的數據。
2. 蘭伯特的 Multi-Paxos 不要求日志是連續的，但在 Raft 中日志必須是連續的。而且在 Raft 中，日志不僅是數據的載體，日志的完整性還影響領導者選舉的結果。也就是說，日志完整性最高的節點才能當選領導者。
3. Raft 是通過以領導者的日志為準，來實現日志的一致的。

課堂思考

領導者接收到大多數的“復制成功”響應后，就會將日志提交到它自己的狀態機，然后返回“成功”響應客戶端。如果此時有個節點不在“大多數”中，也就是說它接收日志項失敗，那么在這種情況下，Raft 會如何處理實現日志的一致呢？

09」Raf算法（三）：如何解決成員變更的問題?

在日常工作中，你可能會遇到服務器故障的情況，這時你就需要替換集群中的服務器。如果遇到需要改變數據副本數的情況，則需要增加或移除集群中的服務器。總的來說，在日常工作中，集群中的服務器數量是會發生變化的。

在開始今天內容之前，我先介紹一下“配置”這個詞兒。因為常聽到有同學說，自己不理解配置（Configuration）的含義，從而不知道如何理解論文中的成員變更。

的確，配置是成員變更中一個非常重要的概念，我建議你這么理解：
它就是在說集群是哪些節點組成的，是集群各節點地址信息的集合。比如節點 A、B、C 組成的集群，那么集群的配置就是[A, B, C]集合。

理解了這一點之后，咱們先來看一道思考題。

假設我們有一個由節點 A、B、C 組成的 Raft 集群，現在我們需要增加數據副本數，增加 2 個副本（也就是增加 2 臺服務器），擴展為由節點 A、B、C、D、E， 5 個節點組成的新集群：

那么 Raft 算法是如何保障在集群配置變更時，集群能穩定運行，不出現 2 個領導者呢？帶著這個問題，我們正式進入今天的學習。

成員變更的問題

在我看來，在集群中進行成員變更的最大風險是，可能會同時出現2個領導者。比如在進行成員變更時，節點A、B和C之間發生了分區錯誤，節點A、B組成舊配置中的“大多數”，也就是變更前的3節點集群中的“大多數”，那么這時的領導者（節點A）依舊是領導者。

另一方面，節點C和新節點D、E組成了新配置的“大多數”，也就是變更后的5節點中的“大多數”，它們可能會選舉出新的領導者（比如節點C）。那么這時，就出現了同時存在2個領導者的情況。

如果出現了3個領導者，那么就違背“領導者的唯一性”的原則，進而影響到集群的穩定運行。你要如何解決這個問題呢？也許有的同學想到了一個解決方法。

因為我們在啟動集群時，配置是固定的，不存在成員變更，在這種情況下，Raft 的領導者選舉能保證只有一個領導者。也就是說，這時不會出現多個領導者的問題，那我可以先將集群關閉再啟動新集群啊。也就是先把節點 A、B、C 組成的集群關閉，然后再啟動節點 A、B、C、D、E 組成的新集群。

在我看來，這個方法不可行。 為什么呢？因為你每次變更都要重啟集群，意味著在集群變更期間服務不可用，肯定不行啊，太影響用戶體驗了。想象一下，你正在玩王者榮耀，時不時彈出一個對話框通知你：系統升級，游戲暫停 3 分鐘。這體驗糟糕不糟糕？

既然這種方法影響用戶體驗，根本行不通，那到底怎樣解決成員變更的問題呢？最常用的方法就是單節點變更。

如何通過單節點變更解決成員變更的問題？

單節點變更，就是通過一次變更一個節點實現成員變更。如果需要變更多個節點，那你需要執行多次單節點變更。比如將 3 節點集群擴容為 5 節點集群，這時你需要執行 2 次單節點變更，先將 3 節點集群變更為 4 節點集群，然后再將 4 節點集群變更為 5 節點集群，就像下圖的樣子。

現在，讓我們回到開篇的思考題，看看如何用單節點變更的方法，解決這個問題。為了演示方便，我們假設節點 A 是領導者：

目前的集群配置為[A, B, C]，我們先向集群中加入節點 D，這意味著新配置為[A, B, C, D]。成員變更，是通過這么兩步實現的：

1. 第一步，領導者（節點A）向新節點（節點D）同步數據；
2. 第二步，領導者（節點A）將新配置[A, B, C, D]作為一個日志項，復制到新配置中所有節點（節點 A、B、C、D）上，然后將新配置的日志項提交到本地狀態機，完成單節點變更。
   
   在變更完成后，現在的集群配置就是[A, B, C, D]，我們再向集群中加入節點 E，也就是說，新配置為[A, B, C, D, E]。成員變更的步驟和上面類似：
3. 第一步，領導者（節點 A）向新節點（節點 E）同步數據；
4. 第二步，領導者（節點 A）將新配置[A, B, C, D, E]作為一個日志項，復制到新配置中的所有節點（A、B、C、D、E）上，然后再將新配置的日志項提交到本地狀態機，完成單節點變更。

這樣一來，我們就通過一次變更一個節點的方式，完成了成員變更，保證了集群中始終只有一個領導者，而且集群也在穩定運行，持續提供服務。

我想說的是，在正常情況下，不管舊的集群配置是怎么組成的，舊配置的“大多數”和新配置的“大多數”都會有一個節點是重疊的。 也就是說，不會同時存在舊配置和新配置 2 個“大多數”：


從上圖中你可以看到，不管集群是偶數節點，還是奇數節點，不管是增加節點，還是移除節點，新舊配置的“大多數”都會存在重疊（圖中的橙色節點）。

需要你注意的是，在分區錯誤、節點故障等情況下，如果我們并發執行單節點變更，那么就可能出現一次單節點變更尚未完成，新的單節點變更又在執行，導致集群出現 2 個領導者的情況。

如果你遇到這種情況，可以在領導者啟動時，創建一個 NO_OP 日志項（也就是空日志項），只有當領導者將 NO_OP 日志項提交后，再執行成員變更請求。這個解決辦法，你記住就可以了，可以自己在課后試著研究下。具體的實現，可參考 Hashicorp Raft 的源碼，也就是runLeader() 函數中：

noop := &logFuture{log: Log{Type: LogNoop,},
}
r.dispatchLogs([]*logFuture{noop})

當然，有的同學會好奇“聯合共識”，在我看來，因為它難以實現，很少被 Raft 實現采用。比如，除了 Logcabin 外，未見到其他常用 Raft實現采用了它，所以這里我就不多說了。

內容小結

本節課我主要帶你了解了成員變更的問題和單節點變更的方法，我希望你明確這樣幾個重點。

1. 成員變更的問題，主要在于進行成員變更時，可能存在新舊配置的2 個“大多數”，導致集群中同時出現兩個領導者，破壞了 Raft 的領導者的唯一性原則，影響了集群的穩定運行。
2. 單節點變更是利用“一次變更一個節點，不會同時存在舊配置和新配置 2 個‘大多數’”的特性，實現成員變更。
3. 因為聯合共識實現起來復雜，不好實現，所以絕大多數 Raft 算法的實現，采用的都是單節點變更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 單節點變更的實現，是由 Raft 算法的作者迭戈·安加羅（Diego Ongaro）設計的，很有參考價值。

除此之外，考慮到本節課是 Raft 算法的最后一講，所以在這里，我想多說幾句，幫助你更好地理解 Raft 算法。
有很多同學把 Raft 當成一致性算法，其實 Raft 不是一致性算法而是共識算法，是一個 Multi-Paxos 算法，實現的是如何就一系列值達成共識。并且，Raft 能容忍少數節點的故障。雖然 Raft 算法能實現強一致性，也就是線性一致性（Linearizability），但需要客戶端協議的配合。在實際場景中，我們一般需要根據場景特點，在一致性強度和實現復雜度之間進行權衡。比如 Consul 實現了三種一致性模型。

1. default：客戶端訪問領導者節點執行讀操作，領導者確認自己處于穩定狀態時（在 leader leasing 時間內），返回本地數據給客戶端，否則返回錯誤給客戶端。在這種情況下，客戶端是可能讀到舊數據的，比如此時發生了網絡分區錯誤，新領導者已經更新過數據，但因為網絡故障，舊領導者未更新數據也未退位，仍處于穩定狀態。
2. consistent：客戶端訪問領導者節點執行讀操作，領導者在和大多數節點確認自己仍是領導者之后返回本地數據給客戶端，否則返回錯誤給客戶端。在這種情況下，客戶端讀到的都是最新數據。
3. stale：從任意節點讀數據，不局限于領導者節點，客戶端可能會讀到舊數據。

一般而言，在實際工程中，Consul 的 consistent 就夠用了，可以不用線性一致性，只要能保證寫操作完成后，每次讀都能讀到最新值就可以了。比如為了實現冥等操作，我們使用一個編號 (ID) 來唯一標記一個操作，并使用一個狀態字段（nil/done）來標記操作是否已經執行，
那么只要我們能保證設置了 ID 對應狀態值為 done 后，能立即和一直讀到最新狀態值就可以了，也就通過防止操作的重復執行，實現了冥等性。

總的來說，Raft 算法能很好地處理絕大部分場景的一致性問題，我推薦你在設計分布式系統時，優先考慮 Raft 算法，當 Raft 算法不能滿足現有場景需求時，再去調研其他共識算法。

比如我負責過多個 QQ 后臺的海量服務分布式系統，其中配置中心、名字服務以及時序數據庫的 META 節點，采用了 Raft 算法。在設計時序數據庫的 DATA 節點一致性時，基于水平擴展、性能和數據完整性等考慮，就沒采用 Raft 算法，而是采用了 Quorum NWR、失敗重傳、反熵等機制。這樣安排不僅滿足了業務的需求，還通過盡可能采用最終一致性方案的方式，實現系統的高性能，降低了成本。

一致性算法和共識算法是分布式系統中兩個密切相關但有區別的概念。

一致性算法：關注如何在分布式系統中保持多個節點數據狀態的一致，確保所有節點的數據副本最終達到相同的狀態。
共識算法：關注如何使分布式系統中的多個節點就某個提案或狀態達成一致，確保所有節點對同一狀態的確認。

課程思考

強領導者模型會限制集群的寫性能，那你想想看，有什么辦法能突破 Raft 集群的寫性能瓶頸呢？

10丨一致哈希算法：如何分群，突破集群的"領導者"限制?

如果我們通過 Raft 算法實現了 KV 存儲，雖然領導者模型簡化了算法實現和共識協商，但寫請求只能限制在領導者節點上處理，導致了集群的接入性能約等于單機，那么隨著業務發展，集群的性能可能就扛不住了，會造成系統過載和服務不可用，這時該怎么辦呢？

其實這是一個非常常見的問題。在我看來，這時我們就要通過分集群，突破單集群的性能限制了。

說到這兒，有同學可能會說了，分集群還不簡單嗎？加個 Proxy 層，由 Proxy 層處理來自客戶端的讀寫請求，接收到讀寫請求后，通過對Key 做哈希找到對應的集群就可以了啊。

是的，哈希算法的確是個辦法，但它有個明顯的缺點：當需要變更集群數時（比如從 2 個集群擴展為 3 個集群），這時大部分的數據都需要遷移，重新映射，數據的遷移成本是非常高的。那么如何解決哈希算法，數據遷移成本高的痛點呢？答案就是一致哈希（Consistent Hashing）。

在正式開始學習之前，我們先看一道思考題。
假設我們有一個由 A、B、C 三個節點組成（為了方便演示，我使用節點來替代集群）的 KV 服務，每個節點存放不同的 KV 數據：

那么，使用哈希算法實現哈希尋址時，到底有哪些問題呢？帶著這個問題，讓我們開始今天的內容吧。

使用哈希算法有什么問題？

使用哈希算法，當節點數量發生變更時，遷移成本是非常高昂的，這在實際生產環境中也是無法想象的。

如何使用一致哈希實現哈希尋址？

一致哈希算法也用了取模運算，但與哈希算法不同的是，哈希算法是對節點的數量進行取模運算，而一致哈希算法是對 $2^{32}$ 進行取模運算。你可以想象下，一致哈希算法，將整個哈希值空間組織成一個虛擬的圓環，也就是哈希環：

從圖中你可以看到，哈希環的空間是按順時針方向組織的，圓環的正上方的點代表 0，0 點右側的第一個點代表 1，以此類推，2、3、4、5、6……直到 $2^{32}?1$，也就是說 0 點左側的第一個點代表 $2^{32}?1$。在一致哈希中，你可以通過執行哈希算法（為了演示方便，假設哈希算法函數為“c-hash()”），將節點映射到哈希環上，比如選擇節點的主機名作為參數執行 c-hash()，那么每個節點就能確定其在哈希環上的位置了：

當需要對指定 key 的值進行讀寫的時候，你可以通過下面 2 步進行尋址：

1. 首先，將key作為參數執行c - hash()計算哈希值，并確定此key在環上的位置；
2. 然后，從這個位置沿著哈希環順時針“行走”，遇到的第一個節點就是key對應的節點。

為了幫助你更好地理解如何通過一致哈希進行尋址，我舉個例子。假設 key-01、key-02、key-03 三個 key，經過哈希算法 c-hash() 計算后，在哈希環上的位置就像下圖的樣子：

那么根據一致哈希算法，key-01 將尋址到節點 A，key-02 將尋址到節點 B，key-03 將尋址到節點 C。講到這兒，你可能會問：“那一致哈希是如何避免哈希算法的問題呢？”

別著急，接下來我分別以增加節點和移除節點為例，具體說一說一致哈希是如何避免上面的問題的。假設，現在有一個節點故障了（比如節點 C）：

你可以看到，key-01和key-02不會受到影響，只有key-03的尋址被重定位到A。一般來說，在一致哈希算法中，如果某個節點宕機不可用了，那么受影響的數據僅僅是，會尋址到此節點和前一節點之間的數據。比如當節點 C 宕機了，受影響的數據是會尋址到節點 B 和節點C 之間的數據（例如 key-03），尋址到其他哈希環空間的數據（例如key-01），不會受到影響。

那如果此時集群不能滿足業務的需求，需要擴容一個節點（也就是增加一個節點，比如 D）：

你可以看到，key-01、key-02 不受影響，只有 key-03 的尋址被重定位到新節點 D。一般而言，在一致哈希算法中，如果增加一個節點，受影響的數據僅僅是，會尋址到新節點和前一節點之間的數據，其它數據也不會受到影響。

讓我們一起來看一個例子。使用一致哈希的話，對于 1000 萬 key 的3 節點 KV 存儲，如果我們增加 1 個節點，變為 4 節點集群，只需要遷移 24.3% 的數據。

你看，使用了一致哈希后，我們需要遷移的數據量僅為使用哈希算法時的三分之一，是不是大大提升效率了呢？

總的來說，使用了一致哈希算法后，擴容或縮容的時候，都只需要重定位環空間中的一小部分數據。也就是說，一致哈希算法具有較好的容錯性和可擴展性。

需要你注意的是，在哈希尋址中常出現這樣的問題：客戶端訪問請求集中在少數的節點上，出現了有些機器高負載，有些機器低負載的情況，那么在一致哈希中，有什么辦法能讓數據訪問分布的比較均勻呢？答案就是虛擬節點。

在一致哈希中，如果節點太少，容易因為節點分布不均勻造成數據訪問的冷熱不均，也就是說大多數訪問請求都會集中少量幾個節點上：

你能從圖中看到，雖然有 3 個節點，但訪問請求主要集中的節點 A上。那如何通過虛擬節點解決冷熱不均的問題呢？

其實，就是對每一個服務器節點計算多個哈希值，在每個計算結果位置上，都放置一個虛擬節點，并將虛擬節點映射到實際節點。比如，可以在主機名的后面增加編號，分別計算 “Node-A-01”“Node-A02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值，于是形成 6 個虛擬節點：

你可以從圖中看到，增加了節點后，節點在哈希環上的分布就相對均勻了。這時，如果有訪問請求尋址到“Node-A-01”這個虛擬節點，將被重定位到節點 A。你看，這樣我們就解決了冷熱不均的問題。最后我想說的是，可能有同學已經發現了，當節點數越多的時候，使用哈希算法時，需要遷移的數據就越多，使用一致哈希時，需要遷移的數據就越少。

當我們向 10 個節點集群中增加節點時，如果使用了哈希算法，需要遷移高達 90.91% 的數據，使用一致哈希的話，只需要遷移 6.48% 的數據。

我希望你能注意到這個規律，使用一致哈希實現哈希尋址時，可以通過增加節點數降低節點宕機對整個集群的影響，以及故障恢復時需要遷移的數據量。后續在需要時，你可以通過增加節點數來提升系統的容災能力和故障恢復效率。

課堂思考

Raft 集群具有容錯能力，能容忍少數的節點故障，那么在多個 Raft 集群組成的 KV 系統中，如何設計一致哈希，實現當某個集群的節點出現了故障時，整個系統還能穩定運行呢？

11丨Gossip協議：流言語，原來也可以實現一致性

有一部分同學的業務在可用性上比較敏感，比如監控主機和業務運行的告警系統。這個時候，相信你希望自己的系統能在極端情況下（比如集群中只有一個節點在運行）也能運行。回憶了二階段提交協議和Raft 算法之后，你發現它們都需要全部節點或者大多數節點正常運行，才能穩定運行，那么它們就不適合了。而根據 Base 理論，你需要實現最終一致性，怎么樣才能實現最終一致性呢？

在我看來，你可以通過 Gossip 協議實現這個目標。

Gossip 協議，顧名思義，就像流言蜚語一樣，利用一種隨機、帶有傳染性的方式，將信息傳播到整個網絡中，并在一定時間內，使得系統內的所有節點數據一致。對你來說，掌握這個協議不僅能很好地理解這種最常用的，實現最終一致性的算法，也能在后續工作中得心應手地實現數據的最終一致性。

Gossip的三板斧

Gossip的三板斧分別是：直接郵寄（Direct Mail）、反熵（Antientropy）和謠言傳播（Rumor mongering）。

直接郵寄：就是直接發送更新數據，當數據發送失敗時，將數據緩存下來，然后重傳。從圖中你可以看到，節點A直接將更新數據發送給了節點B、D。

直接郵寄雖然實現起來比較容易，數據同步也很及時，但可能會因為緩存隊列滿了而丟數據。也就是說，只采用直接郵寄是無法實現最終一致性的，這一點我希望你能注意到。

那如何實現最終一致性呢？答案就是反熵。本質上，反熵是一種通過異步修復實現最終一致性的方法（關于異步修復，你可以回顧一下04講）。常見的最終一致性系統（比如 Cassandra），都實現了反熵功能。

反熵指的是集群中的節點，每隔段時間就隨機選擇某個其他節點，然后通過互相交換自己的所有數據來消除兩者之間的差異，實現數據的最終一致性：

從圖中可以看到，節點 A 通過反熵的方式，修復了節點 D 中缺失的數據。那具體怎么實現的呢？

其實，在實現反熵的時候，主要有推、拉和推拉三種方式。我將以修復下圖中，2 個數據副本的不一致為例，具體帶你了解一下。

推方式，就是將自己的所有副本數據，推給對方，修復對方副本中的熵：

拉方式，就是拉取對方的所有副本數據，修復自己副本中的熵：

理解了推和拉之后，推拉這個方式就很好理解了，這個方式就是同時修復自己副本和對方副本中的熵：

因為反熵需要節點兩兩交換和比對自己所有的數據，執行反熵時通訊成本會很高，所以我不建議你在實際場景中頻繁執行反熵，并且可以通過引入校驗和（Checksum）等機制，降低需要對比的數據量和通訊消息等。

雖然反熵很實用，但是執行反熵時，相關的節點都是已知的，而且節點數量不能太多，如果是一個動態變化或節點數比較多的分布式環境（比如在 DevOps 環境中檢測節點故障，并動態維護集群節點狀態），這時反熵就不適用了。那么當你面臨這個情況要怎樣實現最終一致性呢？答案就是謠言傳播。

謠言傳播，廣泛地散播謠言，它指的是當一個節點有了新數據后，這個節點變成活躍狀態，并周期性地聯系其他節點向其發送新數據，直到所有的節點都存儲了該新數據：

從圖中你可以看到，節點 A 向節點 B、D 發送新數據，節點 B 收到新數據后，變成活躍節點，然后節點 B 向節點 C、D 發送新數據。其實，謠言傳播非常具有傳染性，它適合動態變化的分布式系統。

如何使用Anti-entropy實現最終一致

在分布式存儲系統中，實現數據副本最終一致性，最常用的方法就是反熵了。為了幫你徹底理解和掌握在實際環境中實現反熵的方法，我想以自研 InfluxDB 的反熵實現為例，具體帶你了解一下。

在自研 InfluxDB 中，一份數據副本是由多個分片組成的，也就是實現了數據分片，三節點三副本的集群，就像下圖的樣子：

反熵的目標是確保每個 DATA 節點擁有元信息指定的分片，而且不同節點上，同一分片組中的分片都沒有差異。比如說，節點 A 要擁有分片 Shard1 和 Shard2，而且，節點 A 的 Shard1 和 Shard2，與節點B、C 中的 Shard1 和 Shard2，是一樣的。

那么，在 DATA 節點上，存在哪些數據缺失的情況呢？也就說，我們需要解決哪些問題呢？
我們將數據缺失，分為這樣 2 種情況。

1. 缺失分片：也就是說，在某個節點上整個分片都丟失了。
2. 節點之間的分片不一致：也就是說，節點上分片都存在，但里面的數據不一樣，有數據丟失的情況發生。

第一種情況修復起來不復雜，我們只需要將分片數據，通過 RPC通訊，從其他節點上拷貝過來就可以了：

第二種情況修復起來要復雜一些。我們需要設計一個閉環的流程，按照一個順序修復，執行完流程后，也就是實現了一致性了。具體是怎么設計的呢？

它是按照一定順序來修復節點的數據差異，先隨機選擇一個節點，然后循環修復，每個節點生成自己節點有、下一個節點沒有的差異數據，發送給下一個節點，進行修復（為了方便演示，假設 Shard1、Shard2 在各節點上是不一致的）：

從圖中可以看到，數據修復的起始節點為節點 A，數據修復是按照順時針順序，循環修復的。需要你注意的是，最后節點 A 又對節點 B 的數據執行了一次數據修復操作，因為只有這樣，節點 C 有、節點 B 缺失的差異數據，才會同步到節點 B 上。

學到這里你可以看到，在實現反熵時，實現細節和最初算法的約定有些不同。比如，不是一個節點不斷隨機選擇另一個節點，來修復副本上的熵，而是設計了一個閉環的流程，一次修復所有節點的副本數據不一致。

為什么這么設計呢？因為我們希望能在一個確定的時間范圍內實現數據副本的最終一致性，而不是基于隨機性的概率，在一個不確定的時間范圍內實現數據副本的最終一致性。

這樣做能減少數據不一致對監控視圖影響的時長。而我希望你能注意到，技術是要活學活用的，要能根據場景特點權衡妥協，設計出最適合這個場景的系統功能。最后需要你注意的是，因為反熵需要做一致性對比，很消耗系統性能，所以建議你將是否啟用反熵功能、執行一致性檢測的時間間隔等，做成可配置的，能在不同場景中按需使用。

內容總結

本節課我主要帶你了解了 Gossip 協議、如何在實際系統中實現反熵等。我希望你明確這樣幾個重點：

1. 作為一種異步修復、實現最終一致性的協議，反熵在存儲組件中應用廣泛，比如 Dynamo、InfluxDB、Cassandra，我希望你能徹底掌握反熵的實現方法，在后續工作中，需要實現最終一致性時，優先考慮反熵。
2. 因為謠言傳播具有傳染性，一個節點傳給了另一個節點，另一個節點又將充當傳播者，傳染給其他節點，所以非常適合動態變化的分布式系統，比如 Cassandra 采用這種方式動態管理集群節點狀態。

在實際場景中，實現數據副本的最終一致性時，一般而言，直接郵寄的方式是一定要實現的，因為不需要做一致性對比，只是通過發送更新數據或緩存重傳，來修復數據的不一致，性能損耗低。在存儲組件中，節點都是已知的，一般采用反熵修復數據副本的一致性。當集群節點是變化的，或者集群節點數比較多時，這時要采用謠言傳播的方式，同步更新數據，實現最終一致。

課堂思考

既然使用反熵實現最終一致性時，需要通過一致性檢測發現數據副本的差異，如果每次做一致性檢測時都做數據對比的話，肯定是比較消耗性能的，那有什么辦法降低一致性檢測時的性能消耗呢？

12丨Quorum NWR算法：想要靈活地自定義一致性，沒問題！

你開發實現了一套 AP 型的分布式系統，實現了最終一致性。業務也接入了，運行正常，一起看起來都那么美好。
可是，突然有同事說，我們要拉這幾個業務的數據做實時分析，希望數據寫入成功后，就能立即讀取到新數據，也就是要實現強一致性（Werner Vogels 提出的客戶端側一致性模型，不是指線性一致性），數據更改后，要保證用戶能立即查詢到。這時你該怎么辦呢？

首先你要明確最終一致性和強一致性有什么區別。

1. 強一致性能保證寫操作完成后，任何后續訪問都能讀到更新后的值；
2. 最終一致性只能保證如果對某個對象沒有新的寫操作了，最終所有后續訪問都能讀到相同的最近更新的值。也就是說，寫操作完成后，后續訪問可能會讀到舊數據。

其實，在我看來，為了一個臨時的需求，我們重新開發一套系統，或者遷移數據到新系統，肯定是不合適的。因為工作量比較大，而且耗時也長，而我建議你通過 Quorum NWR 解決這個問題。
也就是說，在原有系統上開發實現一個新功能，就可以滿足業務同學的需求了。因為通過 Quorum NWR，你可以自定義一致性級別，通過臨時調整寫入或者查詢的方式，當 W + R > N 時，就可以實現強一致性了。

其實，在 AP 型分布式系統中（比如 Dynamo、Cassandra、InfluxDB 企業版的 DATA 節點集群），Quorum NWR 是通常都會實現的一個功能，很常用。對你來說，掌握 Quorum NWR，不僅是掌握一種常用的實現一致性的方法，更重要的是，后續用戶可以根據業務的特點，靈活地指定一致性級別。

為了幫你掌握 Quorum NWR，除了帶你了解它的原理外，我還會以InfluxDB 企業版的實現為例，帶你看一下它在實際場景中的實現，這樣你可以在理解原理的基礎上，掌握 Quorum NWR 的實戰技巧。
首先，你需要了解 Quorum NWR 中的三個要素，N、W、R。因為它們是 Quorum NWR 的核心內容，我們就是通過組合這三個要素，實現自定義一致性級別的。

Quorum NWR的三要素

N 表示副本數，又叫做復制因子（Replication Factor）。也就是說，N 表示集群中同一份數據有多少個副本，就像下圖的樣子：

從圖中你可以看到，在這個三節點的集群中，DATA-1 有 2 個副本，DATA-2 有 3 個副本，DATA-3 有 1 個副本。也就是說，副本數可以不等于節點數，不同的數據可以有不同的副本數。

需要你注意的是，在實現 Quorum NWR 的時候，你需要實現自定義副本的功能。也就是說，用戶可以自定義指定數據的副本數，比如，用戶可以指定 DATA-1 具有 2 個副本，DATA-2 具有 3 個副本，就像圖中的樣子。

當我們指定了副本后，就可以對副本數據進行讀寫操作了。那么這么多副本，你要如何執行讀寫操作呢？先來看一看寫操作，也就是 W。

W，又稱寫一致性級別（Write Consistency Level），表示成功完成 W 個副本更新，才完成寫操作：

從圖中你可以看到，DATA-2 的寫副本數為 2，也就說，對 DATA-2 執行寫操作時，完成了 2 個副本的更新（比如節點 A、C），才完成寫操作。

那么有的同學會問了，DATA-2 有 3 個數據副本，完成了 2 副本的更新，就完成了寫操作，那么如何實現強一致性呢？如果讀到了第三個數據副本（比如節點 B），不就可能無法讀到更新后的值了嗎？別急，我講完如何執行讀操作后，你就明白了。

R，又稱讀一致性級別（Read Consistency Level），表示讀取一個數據對象時需要讀 R 個副本。你可以這么理解，讀取指定數據時，要讀 R 副本，然后返回 R 個副本中最新的那份數據：

從圖中你可以看到，DATA-2 的讀副本數為 2。也就是說，客戶端讀取DATA-2 的數據時，需要讀取 2 個副本中的數據，然后返回最新的那份數據。

這里需要你注意的是，無論客戶端如何執行讀操作，哪怕它訪問的是寫操作未強制更新副本數據的節點（比如節點 B），但因為 W(2) + R(2) > N(3)，也就是說，訪問節點 B，執行讀操作時，因為要讀 2 份數據副本，所以除了節點 B 上的 DATA-2，還會讀取節點 A 或節點 C 上的 DATA-2，就像上圖的樣子（比如節點 C 上的 DATA-2），而節點 A 和節點 C 的 DATA-2 數據副本是強制更新成功的。這個時候，返回給客戶端肯定是最新的那份數據。

你看，通過設置 R 為 2，即使讀到前面問題中的第三份副本數據（比如節點 B），也能返回更新后的那份數據，實現強一致性了。

除此之外，關于 NWR 需要你注意的是，N、W、R 值的不同組合，會產生不同的一致性效果，具體來說，有這么兩種效果：

1. 當 W + R > N 的時候，對于客戶端來講，整個系統能保證強一致性，一定能返回更新后的那份數據。
2. 當 W + R < N 的時候，對于客戶端來講，整個系統只能保證最終一致性，可能會返回舊數據。

你可以看到，Quorum NWR 的原理并不復雜，也相對比較容易理解，但在這里，我想強調一下，掌握它的關鍵在于如何根據不同的場景特點靈活地實現 Quorum NWR，所以接下來，我帶你具體問題具體分析，以 InfluxDB 企業版為例講解一下。

如何實現 Quorum NWR？

在 InfluxDB 企業版中，可以在創建保留策略時，設置指定數據庫（Database）對應的副本數，具體的命令，就像下面的樣子：

1. create retention policy “rp_one_day” on “telegraf” duration 1d replication 3

通過 replication 參數，指定了數據庫 telegraf 對應的副本數為 3。

需要你注意的，在 InfluxDB 企業版中，副本數不能超過節點數據。你可以這么理解，多副本的意義在于冗余備份，如果副本數超過節點數，就意味著在一個節點上會存在多個副本，那么這時冗余備份的意義就不大了。比如機器故障時，節點上的多個副本是同時被影響的。

InfluxDB 企業版，支持“any、one、quorum、all”4 種寫一致性級別，具體的含義是這樣的。

1. any：任何一個節點寫入成功后，或者接收節點已將數據寫入Hinted-handoff 緩存（也就是寫其他節點失敗后，本地節點上緩存寫失敗數據的隊列）后，就會返回成功給客戶端。
2. one：任何一個節點寫入成功后，立即返回成功給客戶端，不包括成功寫入到 Hinted-handoff 緩存。
3. quorum：當大多數節點寫入成功后，就會返回成功給客戶端。此選項僅在副本數大于 2 時才有意義，否則等效于 all。
4. all：僅在所有節點都寫入成功后，返回成功。

對時序數據庫而言，讀操作常會拉取大量數據，查詢性能是挑戰，是必須要考慮優化的，因此，在 InfluxDB 企業版中，不支持讀一致性級別，只支持寫一致性級別。另外，我們可以通過設置寫一致性級別為 all，來實現強一致性。

你看，如果我們像 InfluxDB 企業版這樣，實現了 Quorum NWR，那么在業務臨時需要實現強一致性時，就可以通過設置寫一致性級別為 all，來實現了。

內容小結

明確這樣幾個重點。

1. 一般而言，不推薦副本數超過當前的節點數，因為當副本數據超過節點數時，就會出現同一個節點存在多個副本的情況。當這個節點故障時，上面的多個副本就都受到影響了。
2. 當 W + R > N 時，可以實現強一致性。另外，如何設置 N、W、R 值，取決于我們想優化哪方面的性能。比如，N 決定了副本的冗余備份能力；如果設置 W = N，讀性能比較好；如果設置 R = N，寫性能比較好；如果設置 W = (N + 1) / 2、R = (N + 1) / 2，容錯能力比較好，能容忍少數節點（也就是 (N - 1) / 2）的故障。

最后，我想說的是，Quorum NWR 是非常實用的一個算法，能有效彌補 AP 型系統缺乏強一致性的痛點，給業務提供了按需選擇一致性級別的靈活度，建議你的開發實現 AP 型系統時，也實現 Quorum NWR。

課堂思考

提到實現 Quorum NWR 時，需要實現自定義副本的能力，那么，一般設置幾個副本就可以了，為什么呢？

13丨PBFT算法：有人作惡，如何達成共識?

口信消息型拜占庭問題之解在實際項目中是如何落地的呢？

不過事實上，它很難在實際項目落地，因為口信消息型拜占庭問題之解是一個非常理論化的算法，沒有和實際場景結合，也沒有考慮如何在實際場景中落地和實現。

比如，它實現的是在拜占庭錯誤場景下，忠將們如何在叛徒干擾時，就一致行動達成共識。但是它并不關心結果是什么，這會出現一種情況：現在適合進攻，但將軍們達成的最終共識卻是撤退。

很顯然，這不是我們想要的結果。因為在實際場景中，我們需要就提議的一系列值（而不是單值），即使在拜占庭錯誤發生的時候也能被達成共識。那你要怎么做呢？答案就是掌握 PBFT 算法。

PBFT 算法非常實用，是一種能在實際場景中落地的拜占庭容錯算法，它在區塊鏈中應用廣泛（比如 Hyperledger Sawtooth、Zilliqa）。為了幫助你更好地理解 PBFT 算法，在今天的內容中，我除了帶你了解 PBFT 達成共識的原理之外，還會介紹口信消息型拜占庭問題之解的局限。相信學習完本講內容后，你不僅能理解 PBFT 達成共識的基本原理，還能理解算法背后的演化和改進。

在開始今天的學習之前，咱們先看一道思考題：假設蘇秦再一次帶隊抗秦，這一天，蘇秦和 4 個國家的 4 位將軍趙、
魏、韓、楚商量軍機要事，結果剛商量完沒多久蘇秦就接到了情報，情報上寫道：聯軍中可能存在一個叛徒。這時，蘇秦要如何下發作戰指令，保證忠將們正確、一致地執行下發的作戰指令，而不是被叛徒干擾呢？

帶著這個問題，我們正式進入今天的學習。

首先，咱們先來研究一下，為什么口信消息型拜占庭問題之解很難在實際場景中落地，除了我在開篇提到的非常理論化，沒有和實際的需求結合之外，還有其他的原因么？

其實，這些問題是后續眾多拜占庭容錯算法在努力改進和解決的，理解了這些問題，能幫助你更好地理解后來的拜占庭容錯算法（包括 PBFT 算法）。

口信消息型拜占庭問題之解的局限

我想說的是，這個算法有個非常致命的缺陷。如果將軍數為 n、叛將數為 f，那么算法需要遞歸協商 f+1 輪，消息復雜度為 O(n ^ (f + 1))，消息數量指數級暴增。你可以想象一下，如果叛將數為 64，消息數已經遠遠超過 int64 所能表示的了，這是無法想象的，肯定不行啊。

另外，盡管對于簽名消息，不管叛將數（比如 f）是多少，經過 f + 1 輪的協商，忠將們都能達成一致的作戰指令，但是這個算法同樣存在“理論化”和“消息數指數級暴增”的痛點。

講到這兒，你肯定明白為什么這個算法很難在實際場景中落地了。可技術是不斷發展的，算法也是在解決實際場景問題中不斷改進的。那么 PBFT 算法的原理是什么呢？為什么它能在實際場景中落地呢？

PBFT 是如何達成共識的？

我們先來看看如何通過 PBFT 算法，解決蘇秦面臨的共識問題。先假設蘇秦制定的作戰指令是進攻，而楚是叛徒（為了演示方便）：

需要你注意的是，所有的消息都是簽名消息，也就是說，消息發送者的身份和消息內容都是無法偽造和篡改的（比如，楚無法偽造一個假裝來自趙的消息）。
首先，蘇秦聯系趙，向趙發送包含作戰指令“進攻”的請求（就像下圖的樣子）。

當趙接收到蘇秦的請求之后，會執行三階段協議（Three-phase protocol）。

1. 趙將進入預準備（Pre-prepare）階段，構造包含作戰指令的預準備消息，并廣播給其他將軍（魏、韓、楚）。
   
   那么在這里，我想問你一個問題：魏、韓、楚，收到消息后，能直接執行指令嗎？

答案是不能，因為他們不能確認自己接收到指令和其他人接收到的指令是相同的。比如，趙可能是叛徒，趙收到了 2 個指令，分別是“進攻”和“準備 30 天的糧草”，然后他給魏發送的是“進攻”，給韓、楚發送的是“準備 30 天糧草”，這樣就會出現無法一致行動的情況。那么他們具體怎么辦呢？我接著說一下。
2. 接收到預準備消息之后，魏、韓、楚將進入準備（Prepare）階段，并分別廣播包含作戰指令的準備消息給其他將軍。比如，魏廣播準備消息給趙、韓、楚（如圖所示）。為了方便演示，我們假設叛徒楚想通過不發送消息，來干擾共識協商（你能看到，圖中的楚是沒有發送消息的）。

然后，當某個將軍收到 2f 個一致的包含作戰指令的準備消息后，會進入提交（Commit）階段（這里的 2f 包括自己，其中 f 為叛徒數，在我的演示中是 1）。在這里，我也給你提一個問題：這個時候該將軍（比如魏）可以直接執行指令嗎？

答案還是不能，因為魏不能確認趙、韓、楚是否收到了 2f 個一致的包含作戰指令的準備消息。也就是說，魏這時無法確認趙、韓、楚是否準備好了執行作戰指令。那么怎么辦呢？別著急，咱們繼續往下看。

1. 進入提交階段后，各將軍分別廣播提交消息給其他將軍，也就是告訴其他將軍，我已經準備好了，可以執行指令了。

2. 最后，當某個將軍收到 2f + 1 個驗證通過的提交消息后（包括自己，其中 f 為叛徒數，在我的演示中為 1），也就是說，大部分的將軍們已經達成共識，這時可以執行作戰指令了，那么該將軍將執行蘇秦的作戰指令，執行完畢后發送執行成功的消息給蘇秦。

最后，當蘇秦收到 f+1 個相同的響應（Reply）消息時，說明各位將軍們已經就作戰指令達成了共識，并執行了作戰指令（其中 f 為叛徒數，在我的演示中為 1）。你看，經過了三輪協商，是不是就指定的作戰指令達成了共識，并執行了作戰指令了呢？

在這里，蘇秦采用的就是簡化版的 PBFT 算法。在這個算法中：

1. 你可以將趙、魏、韓、楚理解為分布式系統的四個節點，其中趙是主節點（Primary node），魏、韓、楚是從節點（Secondary node）；
2. 將蘇秦理解為業務，也就是客戶端；
3. 將消息理解為網絡消息；
4. 將作戰指令“進攻”，理解成客戶端提議的值，也就是希望被各節點達成共識，并提交給狀態機的值。

在這里我想說的是， PBFT 算法是通過簽名（或消息認證碼 MAC）約束惡意節點的行為，也就是說，每個節點都可以通過驗證消息簽名確認消息的發送來源，一個節點無法偽造另外一個節點的消息。最終，基于大多數原則（2f + 1）實現共識的。

需要你注意的是，最終的共識是否達成，客戶端是會做判斷的，如果客戶端在指定時間內未收到請求對應的 f + 1 相同響應，就認為集群出故障了，共識未達成，客戶端會重新發送請求。

另外需要你注意的是，PBFT 算法通過視圖變更（View Change）的方式，來處理主節點作惡，當發現主節點在作惡時，會以“輪流上崗”方式，推舉新的主節點。

最后我想說的是，盡管 PBFT 算法相比口信消息型拜占庭之解已經有了很大的優化，將消息復雜度從 O(n ^ (f + 1)) 降低為 O(n ^ 2)，能在實際場景中落地，并解決實際的共識問題。但 PBFT 還是需要比較多的消息。比如在 13 節點集群中（f 為 4）。

1. 請求消息：1
2. 預準備消息：3f = 12
3. 準備消息：3f * (3f - f) = 96
4. 提交消息：(3f - f + 1) * (3f + 1)= 117
5. 回復消息：3f - 1 = 11

也就是說，一次共識協商需要 237 個消息，你看，消息數還是蠻多的，所以我推薦你，在中小型分布式系統中使用 PBFT 算法。

內容小結

以上就是本節課的全部內容了，本節課我主要帶你了解了口信消息型
拜占庭問題之解的局限和 PBFT 的原理，我希望你明確這樣幾個重
點。

1. 不管口信消息型拜占庭問題之解，還是簽名消息型拜占庭問題之解，都是非常理論化的，未考慮實際場景的需求，而且協商成本非常高，指數級的消息復雜度是很難在實際場景中落地，和解決實際場景問題的。
2. PBFT 算法是通過簽名（或消息認證碼 MAC）約束惡意節點的行為，采用三階段協議，基于大多數原則達成共識的。另外，與口信消息型拜占庭問題之解（以及簽名消息型拜占庭問題之解）不同的是，PBFT 算法實現的是一系列值的共識，而不是單值的共識。

最后，我想說的是，相比 Raft 算法完全不適應有人作惡的場景，PBFT 算法能容忍 (n - 1)/3 個惡意節點 (也可以是故障節點)。另外，相比 PoW 算法，PBFT 的優點是不消耗算力，所以在日常實踐中，PBFT 比較適用于相對“可信”的場景中，比如聯盟鏈。

需要你注意的是，PBFT 算法與 Raft 算法類似，也存在一個“領導者”（就是主節點），同樣，集群的性能也受限于“領導者”。另外，O(n ^ 2) 的消息復雜度，以及隨著消息數的增加，網絡時延對系統運行的影響也會越大，這些都限制了運行 PBFT 算法的分布式系統的規模，也決定了 PBFT 算法適用于中小型分布式系統。

課堂思考

當客戶端在收到了 f + 1 個結果，就認為共識達成了，那么為什么這個值不能小于 f + 1 呢？

14丨PoW算法：有辦法黑比特幣嗎?

談起比特幣，你應該再熟悉不過了，比特幣是基于區塊鏈實現的，而區塊鏈運行在因特網上，這就存在有人試圖作惡的情況。口信消息型拜占庭問題之解、PBFT 算法雖然能防止壞人作惡，但只能防止少數的壞人作惡，也就是 (n - 1) / 3 個壞人 (其中 n 為節點數)。可如果區塊鏈也只能防止一定比例的壞人作惡，那就麻煩了，因為壞人可以不斷增加節點數，輕松突破 (n - 1) / 3 的限制。

那區塊鏈是如何改進這個問題的呢？答案就是 PoW 算法。

在我看來，區塊鏈通過工作量證明（Proof of Work）增加了壞人作惡的成本，以此防止壞人作惡。比如，如果壞人要發起 51% 攻擊，需要控制現網 51% 的算力，成本是非常高昂的。為啥呢？因為根據Cryptoslate 估算，對比特幣進行 51% 算力攻擊需要上百億人民幣！

那么為了幫你更好地理解和掌握 PoW 算法，我會詳細講解它的原理和 51% 攻擊的本質。希望讓你在理解 PoW 算法的同時，也了解 PoW 算法的局限。

首先我來說說 PoW 的原理，換句話說，就是 PoW 是如何運行的。

如何理解工作量證明？

什么是工作量證明 (Proof Of Work，簡稱 PoW) 呢？你可以這么理解：就是一份證明，用來確認你做過一定量的工作。比如，你的大學畢業證書就是一份工作量證明，證明你通過 4 年的努力完成了相關課程的學習。

那么回到計算機世界，具體來說就是，客戶端需要做一定難度的工作才能得出一個結果，驗證方卻很容易通過結果來檢查出客戶端是不是做了相應的工作。

比如小李來 BAT 面試，說自己的編程能力很強，那么他需要做一定難度的工作（比如做個編程題）。根據做題結果，面試官可以判斷他是否適合這個崗位。你看，小李做個編程題，面試官核驗做題結果，這就是一個現實版的工作量證明。

具體的工作量證明過程，就像下圖中的樣子：

請求方做了一些運算，解決了某個問題，然后把運算結果發送給驗證方，進行核驗，驗證方根據運算結果，就能判斷請求方是否做了相關的工作。

需要你注意的是，這個算法具有不對稱性，也就是說，工作對于請求方是有難度的，對于驗證方則是比較簡單的，易于驗證的。

既然工作量證明是通過指定的結果，來證明自己做過了一定量的工作。那么在區塊鏈的 PoW 算法中需要做哪些工作呢？答案是哈希運算。區塊鏈是通過執行哈希運算，然后通過運算后的結果值，證明自己做過了相關工作。為了幫你更好地理解哈希運算，在介紹哈希運算之前，咱們先來聊一聊哈希函數。

哈希函數（Hash Function），也叫散列函數。就是說，你輸入一個任意長度的字符串，哈希函數會計算出一個長度相同的哈希值。假設我們對任意長度字符串（比如"geektime"）執行 SHA256 哈希運算，就會得到一個 32 字節的哈希值。

那我們如何通過哈希函數進行哈希運算，從而證明工作量呢？為了幫你理解這部分內容，我舉個具體的例子。

我們給出的工作量要求是，基于一個基本的字符串（比
如"geektime"），你可以在這個字符串后面添加一個整數值，然后對變更后（添加整數值) 的字符串進行 SHA256 哈希運算，如果運算后得到的哈希值（16 進制形式）是以"0000"開頭的，就驗證通過。為了達到這個工作量證明的目標，我們需要不停地遞增整數值，一個一個試，對得到的新字符串進行 SHA256 哈希運算。

按照這個規則，我們需要經過 35024 次計算，才能找到恰好前 4 位為 0 的哈希值。

"geektime0" => 01f28c5df06ef0a575fd0e529be9a6f73b1
"geektime1" => a2567c06fdb5775cb1e3ce17b72754cf146
...
"geektime35022" =>
8afc85049a9e92fe0b6c98b02b27c09fb869fbfe273d0ab84a
"geektime35023" =>
0000ec5927ba10ea45a6822dcc205050ae74ae1ad2d9d41e97

通過這個示例你可以看到，工作量證明是通過執行哈希運算，經過一段時間的計算后，得到符合條件的哈希值。也就是說，可以通過這個哈希值，來證明我們的工作量。

關于這個規則，我也想多說幾句，這個規則不是固定的，在實際場景中，你可以根據場景特點，制定不同的規則，比如，你可以試試分別運行多少次，才能找到恰好前 3 位和前 5 位為 0 的哈希值。

現在，你對工作量證明的原理應該有一定的了解了，那么有同學肯定好奇了，在區塊鏈中是如何實現工作量證明的呢？

區塊鏈如何實現 PoW 算法的？

區塊鏈也是通過 SHA256 來執行哈希運算的，通過計算出符合指定條件的哈希值，來證明工作量的。因為在區塊鏈中，PoW 算法是基于區塊鏈中的區塊信息，進行哈希運算的，所以我先帶你回顧一下區塊鏈的相關知識。

區塊鏈的區塊，是由區塊頭、區塊體 2 部分組成的，就像下圖中的樣子。

1. 區塊頭（Block Head）：區塊頭主要由上一個區塊的哈希值、區塊體的哈希值、4 字節的隨機數（nonce）等組成的。
2. 區塊體（Block Body）：區塊包含的交易數據，其中的第一筆交易是 Coinbase 交易，這是一筆激勵礦工的特殊交易。

我想說的是，擁有 80 字節固定長度的區塊頭，就是用于區塊鏈工作量證明的哈希運算中輸入字符串，而且通過雙重 SHA256 哈希運算（也就是對 SHA256 哈希運算的結果，再執行一次哈希運算），計算出的哈希值，只有小于目標值（target），才是有效的，否則哈希值是無效的，必須重算。

學到這兒你可以看到，在區塊鏈中是通過對區塊頭執行 SHA256 哈希運算，得到小于目標值的哈希值，來證明自己的工作量的。

計算出符合條件的哈希值后，礦工就會把這個信息廣播給集群中所有其他節點，其他節點驗證通過后，會將這個區塊加入到自己的區塊鏈中，最終形成一串區塊鏈，就像下圖的樣子：

最后，我想說的是，算力越強，系統大概率會越先計算出這個哈希值。這也就意味著，如果壞人們掌握了 51% 的算力，就可以發起 51% 攻擊，比如，實現雙花（Double Spending），也就是說，同一份錢花 2 次。

具體說的話，就是攻擊者掌握了較多的算力，能挖掘一條比原鏈更長的攻擊鏈，并將攻擊鏈向全網廣播，這時呢，按照約定，節點將接受更長的鏈，也就是攻擊鏈，丟棄原鏈。就像下圖的樣子：

需要你注意的是，即使攻擊者只有 30% 的算力，他也有可能連續計算出多個區塊的哈希值，挖掘出更長的攻擊鏈，發動攻擊； 另外，即使攻擊者擁有 51% 的算力，他也有可能半天無法計算出一個區塊的哈希值，也就是攻擊失敗。也就是說，能否計算出符合條件的哈希值，有一定的概率性，但長久來看，攻擊者攻擊成功的概率等同于攻擊者算力的權重。

內容小結

以上就是本節課的全部內容了，本節課我主要帶你了解了 PoW 算法的原理，和 51% 攻擊，我希望你明確這樣幾個重點。

1. 在比特幣的區塊鏈中，PoW 算法，是通過 SHA256 進行哈希運算，計算出符合指定條件的哈希值，來證明工作量的。
2. 51% 攻擊，本質是因為比特幣的區塊鏈約定了“最長鏈勝出，其它節點在這條鏈基礎上擴展”，攻擊者可以通過優勢算力實現對最長鏈的爭奪。
3. 除了通過 PoW 算法，增加壞人作惡的成本，比特幣還通過“挖礦得幣”獎勵好人，最終保持了整個系統的運行穩定。

因為本講是拜占庭容錯算法的最后一講，我想多說幾句：學完了 01 講的同學，應該還記得，我們提到 Raft 算法是非拜占庭容錯算法。那么如果我們把 Raft 算法用于拜占庭場景中，會怎么樣呢？

比如，在比特幣中，我們采用了 Raft 算法實現共識，而不是基于 PoW 算法的區塊鏈，那么，就會出現這樣的情況，當惡意節點當選為領導者后，他可以不斷地告訴其他節點，這些比特幣都是我的，按照 Raft 的約定，其他節點也就只能接受這種情況，誰讓惡意節點是領導者呢？最終就會出現，所有的比特幣都被惡意節點盜走的情況，完全亂套了。

另外我想說的是，因為拜占庭容錯算法（比如 PoW 算法、PBFT 算法），能容忍一定比例的作惡行為，所以它在相對開放的場景中應用廣泛，比如公鏈、聯盟鏈。非拜占庭容錯算法（比如 Raft）無法對作惡行為進行容錯，主要用于封閉、絕對可信的場景中，比如私鏈、公司內網的 DevOps 環境。我希望你能準確理解 2 類算法之間的差異，根據場景特點，選擇合適的算法，保障業務高效、穩定的運行。

課堂思考

既然，我提了如何通過計算得到"0000"開頭的哈希值，來做實現工作量證明，那么你不妨思考下，如果約定是更多“0”開頭的哈希值，比如“00000000”，工作量是增加了還是減少了，為什么呢？

15丨ZAB協議：如何實現操作的順序性?

很多同學應該使用過 ZooKeeper，它是一個開源的分布式協調服務，比如你可以使用它進行配置管理、名字服務等等。在 ZooKeeper 中，數據是以節點的形式存儲的。如果你要用 ZooKeeper 做配置管理，那么就需要在里面創建指定配置，假設創建節點"/geekbang"和"/geekbang/time"，步驟如下：

[zk: localhost:2181(CONNECTED) 7] create /geekbang
Created /geekbang
[zk: localhost:2181(CONNECTED) 8] create /geekbang
Created /geekbang/time

我們分別創建了配置"/geekbang" 和"/geekbang/time"，對應的值分別為 123 和 456。那么在這里我提個問題：你覺得在 ZooKeeper 中，能用蘭伯特的 Multi-Paxos 實現各節點數據的共識和一致嗎？

當然不行。因為蘭伯特的 Multi-Paxos，雖然能保證達成共識后的值不再改變，但它不管關心達成共識的值是什么，也無法保證各值（也就是操作）的順序性。這是為什么呢？這個問題是 ZAB 協議著力解決的，也是理解 ZAB 協議的關鍵。

不過，雖然大家都在提 ZAB 協議，但是在我看來，ZAB 協議和ZooKeeper 代碼耦合在一起，也就是說，你是無法單獨使用 ZAB 協議的，所以一般而言，只需要理解 ZAB 協議的架構和基礎原理就可以了，不需要對代碼和細節做太多的深究。所以，我會從 ZAB 協議的最核心設計目標（如何實現操作的順序性）出發，帶你了解它的基礎原理。

為什么 Multi-Paxos 無法實現操作順序性？

蘭伯特的 Multi-Paxos 解決的是一系列值如何達成共識的問題，它關心的是，對于指定序號的位置，最多只有一個指令（Command）會被選定，但它不關心選定的是哪個指令，也就是說，它不關心指令的順序性（也就是操作的順序性）。

這么說可能比較抽象，為了方便你理解，我舉個具體的例子演示一下（一個 3 節點的 Multi-Paxos 集群），為了演示方便，我們假設當前所有節點被選定的指令的最大序號為 100，也就是說，新提議的指令對應的序號將為 101。

首先節點 A 是領導者，提議了指令 X、Y，但是因為網絡故障，指令只成功復制到了節點 A。

假設這時節點 A 故障了，新當選的領導者為節點 B。節點 B 當選領導者后，需要先作為學習者了解目前已被選定的指令。節點 B 學習之后，發現當前被選定指令的最大序號為 100（因為節點 A 故障了，它被選定指令的最大序號 102，無法被節點 B 發現），那么它可以從序號 101 開始提議新的指令。這時它接收到客戶端請求，并提議了指令 Z，指令 Z 被成功復制到節點 B、C。

這時節點 B 故障了，節點 A 恢復了，選舉出領導者 C 后，節點 B 故障也恢復了。節點 C 當選領導者后，需要先作為學習者，了解目前已被選定的指令，這時它執行 Basic Paxos 的準備階段，就會發現之前選定的值（比如 Z、Y），然后發送接受請求，最終在序號 101、102處達成共識的指令是 Z、Y。就像下圖的樣子。

在這里，你可以看到，原本預期的指令是 X、Y，最后變成了 Z、Y，也就是說，雖然 Multi-Paxos 能就一系列值達成共識，但它不關心達成共識后的值是什么，這顯然不是我們想要的結果。

比如，假設在 ZooKeeper 中直接使用了蘭伯特的 Multi-Paxos，這時咱們創建節點"/geekbang"和"/geekbang/time"，那么就可能出現，系統先創建了節點"/geekbang/time"，這樣肯定就出錯了：

[zk: localhost:2181(CONNECTED) 6] create /geekbang
Node does not exist: /geekbang/time

因為創建節點"/geekbang/time"時，找不到節點"/geekbang"，所以就會創建失敗。

在這里我多說幾句，蘭伯特有很多關于分布式的理論，這些理論都很經典（比如拜占庭將軍問題、Paxos），但也因為太早了，與實際場景結合的不多，所以后續的眾多算法是在這個基礎之上做了大量的改進（比如，PBFT、Raft 等）。

另外我還想補充一下，在我看來，在ZAB 論文中，關于 Paxos 問題的分析是有爭議的。因為 ZooKeeper 當時應該考慮的是 Multi-Paxos，而不是有多個提議者的 Basic Paxos。對于 Multi-Paxos而言，領導者作為唯一提議者，不存在同時多個提議者的情況。也就是說，Multi-Paxos 無法保證操作的順序性的問題是存在的，但原因不是文中演示的原因，本質上是因為 Multi-Paxos 實現的是一系列值的共識，不關心最終達成共識的值是什么，不關心各值的順序。

既然 Multi-Paxos 不行，ZooKeeper 怎么實現操作的順序性的呢? 答案是它實現了 ZAB 協議。

你可能會說了：Multi-Paxos 無法實現操作的順序性，但 Raft 可以啊，為什么 ZooKeeper 不用 Raft 呢？這個問題其實比較簡單，因為 Raft 出來的比較晚，直到 2013 年才正式提出，在 2007 年開發 ZooKeeper 的時候，還沒有 Raft 呢。

ZAB 是如何保證操作的順序性的？

與蘭伯特的 Multi-Paxos 不同，ZAB 不是共識算法，不基于狀態機，而是基于主備模式的原子廣播協議，最終實現了操作的順序性。

這里我說的主備，就是 Master-Slave 模型，一個主節點和多個備份節點，所有副本的數據都以主節點為準，主節點采用二階段提交，向備份節點同步數據，如果主節點發生故障，數據最完備的節點將當選主節點。而原子廣播協議，你可以理解成廣播一組消息，消息的順序是固定的。

需要你注意的是，ZAB 在這里做了個優化，為了實現分區容錯能力，將數據復制到大多數節點后（也就是如果大多數節點準備好了），領導者就會進入提交執行階段，通知備份節點執行提交操作。在這一點上，Raft 和 ZAB 是類似的，我建議你可以對比著 Raft 算法來理解ZAB。

講到這兒我再多說一句，前面幾講的留言中有同學問狀態機的事情：在 Multi-Paxos、Raft 中為什么需要狀態機？這是一個很棒的問題，為你的深入思考點個贊！所以咱們先來看一下這個問題。

什么是狀態機？

本質上來說，狀態機指的是有限狀態機，它是一個數學模型。你可以這么理解：狀態機是一個功能模塊，用來處理一系列請求，最大的特點就是確定性，也就是說，對于相同的輸入，不管重復運行多少次，最終的內部狀態和輸出都是相同的。

就像你敲擊鍵盤，在 Word 文檔上打字一樣，你敲擊鍵盤的順序決定了 Word 文檔上的文字，你按照相同的順序敲擊鍵盤，一定能敲出相同的文字，這就是一個現實版的狀態機。那么為什么在 Multi-Paxos、Raft 中需要狀態機呢？

你想一下，Multi-Paxos、Raft 都是共識算法，而共識算法是就一系列值達成共識的，達成共識后，這個值就不能改了。但有時候我們是需要更改數據的值的，比如 KV 存儲，我們肯定需要更改指定 key（比如 X）對應的值，這時我們就可以通過狀態機來解決這個問題。比如，如果你想把 X 的值改為 7，那你可以提議一個新的指令“SET X = 7”，當這個指令被達成共識并提交到狀態機后，你查詢到的值就是 7 了，也就成功修改了 X 的值。

講到這兒，你應該理解什么是狀態機，為什共識算法需要狀態機了吧？在解決這個問題之后，咱們說回剛剛的話題：ZAB 協議如何保證操作的順序性？

如何實現操作的順序性？

首先，ZAB 實現了主備模式，也就是所有的數據都以主節點為準：

其次，ZAB 實現了 FIFO 隊列，保證消息處理的順序性。

另外，ZAB 還實現了當主節點崩潰后，只有日志最完備的節點才能當選主節點，因為日志最完備的節點包含了所有已經提交的日志，所以這樣就能保證提交的日志不會再改變。

你看，ZAB 協議通過這幾個特性就能保證后來的操作不會比當前的操作先執行，也就能保證節點"/geekbang"會在節點"/geekbang/time"之前創建。

學到這里，想必你已經發現了，這些特性好像和 Raft 很像。是的，因為在前面幾講，我們已經學習了 Raft 算法，所以你可以類比 Raft 來理解，在 Raft 中：

1. 所有日志以領導者的為準；
2. 領導者接收到客戶端請求后，會基于請求中的指令，創建日志項，并將日志項緩存在本地，然后按照順序，復制到其他節點和提交 ;
3. 在 Raft 中，也是日志最完備的節點才能當選領導者。

內容小結

本節課我主要帶你了解了狀態機、為什么 Multi-Paxos 無法實現操作的順序性，以及 ZAB 協議如何保證操作的順序性。我希望你明確這樣幾個重點。

1. 狀態機最大的特點是確定性，對于相同的輸入不管運行多少次，最終的內部狀態和輸出都是相同的。需要你注意的是，在共識算法中，我們可以通過提議新的指令，達成共識后，提交給狀態機執行，來達到修改指定內容的效果，比如修改 KV 存儲中指定 key 對應的值。
2. ZAB 是通過“一切以領導者為準”的強領導者模型和嚴格按照順序提交日志，來實現操作的順序性的，這一點和 Raft 是一樣的。

最后我想說的是，蘭伯特的 Multi-Paxos 只考慮了如何實現共識，也就是，如何就一系列值達成共識，未考慮如何實現各值（也就是操作）的順序性。最終 ZooKeeper 實現了基于主備模式的原子廣播協議，保證了操作的順序性，而且，ZAB 協議的實現，影響到了后來的共識算法，也就是 Raft 算法，Raft 除了能就一些值達成共識，還能保證各值的順序性。

學習完本講內容后，你可以看到，Raft 算法和 ZAB 協議很類似，比如主備模式（也就是領導者、跟隨者模型）、日志必須是連續的、以領導者的日志為準是日志一致等等。你可以想一下，那為什么它們會比較類似呢？

我的看法是，“英雄所見略同”。比如 ZAB 協議要實現操作的順序性，而 Raft 的設計目標，不僅僅是操作的順序性，而是線性一致性，這兩個目標，都決定了它們不能允許日志不連續，要按照順序提交日志，那么，它們就要通過上面的方法實現日志的順序性，并保證達成共識（也就是提交）后的日志不會再改變。

課堂思考

我提到在 ZAB 中，寫操作必須在主節點上執行，主節點是通過簡化版的二階段提交向備份節點同步數據。那么如果讀操作訪問的是備份節點，能保證每次都能讀到最新的數據嗎？為什么呢？