一個簡單的全序廣播（totally ordered broadcast）協(xié)議
摘要
這是一個關(guān)于 Zookeeper 使用的全序廣播協(xié)議的簡短概述，這個協(xié)議稱之為 Zab，它在概念上容易理解，易于實現(xiàn)，并具有高性能。在本文中，我們將介紹 Zookeeper 對 Zab 的需求，也會展示該協(xié)議的使用方式，并概述了該協(xié)議的工作原理。
1. 介紹
在 Yahoo，我們已經(jīng)開發(fā)了一款高性能、高可用的協(xié)調(diào)服務(wù) - Zookeeper，該服務(wù)允許大型應(yīng)用程序執(zhí)行諸如領(lǐng)導(dǎo)者選舉（Leader Election）、狀態(tài)傳播（Status Propagation）和會和（Rendezvous）等協(xié)調(diào)任務(wù)。此服務(wù)實現(xiàn)了一個層級的數(shù)據(jù)節(jié)點空間，稱之為 Znode，客戶端可以使用它來自定義協(xié)調(diào)任務(wù)。我們發(fā)現(xiàn)該服務(wù)相當(dāng)靈活，很容滿足我們應(yīng)用在生產(chǎn)需求中遇到的性能要求。Zookeeper 放棄使用鎖，而是實現(xiàn)了無需等待（wait-free）的共享數(shù)據(jù)對象，并保證了這些對象的操作順序?？蛻舳死眠@些保證來自定義協(xié)調(diào)任務(wù)。總體而言，Zookeeper 的主要前提之一是，對于應(yīng)用程序來說，更新操作順序比其他典型的協(xié)調(diào)技術(shù)（例如阻塞）更為重要。
Zookeeper 中集成的是一個全序廣播協(xié)議：Zab。當(dāng)保障客戶端實現(xiàn)時，有序的廣播至關(guān)重要，同時也需要在每個 Zookeeper 服務(wù)器上維護(hù) Zookeeper 狀態(tài)的副本，這些副本使用全序廣播協(xié)議來保持一致（如狀態(tài)機副本）。本文著重于 Zookeeper 對這種廣播協(xié)議的需求及其實現(xiàn)的概述。
Zookeeper 服務(wù)通常包含三到七臺機器，Zookeeper 實現(xiàn)可以支持更多的機器，但是三到七臺計算機可以提供足夠的性能和彈性?？蛻舳丝梢赃B接到提供服務(wù)的任一臺機器，并且始終可以獲取一致的 Zookeeper 狀態(tài)視圖。該服務(wù)最多可以容忍 2f+1 臺服務(wù)器 中 f 臺發(fā)生崩潰故障。
應(yīng)用程序中廣泛使用 Zookeeper，并且成千上萬的客戶端同時訪問它，因此我們需要高吞吐量。我們設(shè)計 Zookeeper 時采用了讀寫操作比高于 2:1 的工作場景，然而，我們發(fā)現(xiàn) Zookeeper 的高寫入吞吐量使其也適用于以寫入為主的工作場景。Zookeeper 通過從每個服務(wù)器上讀取 Zookeeper 狀態(tài)的本地副本來提高讀取吞吐量，這樣，在服務(wù)中添加服務(wù)器可以擴(kuò)展它的容器能力和提高讀取吞吐量。寫入吞吐量無法通過添加服務(wù)器來擴(kuò)展，相反，它受到廣播協(xié)議吞吐量的限制，因此，我們需要具有高吞吐量的廣播協(xié)議。
圖一顯示了 Zookeeper 服務(wù)的邏輯組成，讀取請求是從包含 Zookeeper 狀態(tài)的本地數(shù)據(jù)庫提供的，寫請求經(jīng)由 Zookeeper 請求轉(zhuǎn)換為冪等事務(wù)，并在生成響應(yīng)之前通過 Zab 發(fā)送。許多 Zookeeper 寫請求本質(zhì)上都是有條件的：
- 一個 Znode 節(jié)點僅在沒有任何子節(jié)點的情況下才能刪除；
- 創(chuàng)建 Znode 節(jié)點需要附加名稱和序列號；
- 更改數(shù)據(jù)需要匹配預(yù)期的版本；
- 甚至無條件（non-conditional）寫請求也以非冪等的方式修改元數(shù)據(jù)，例如版本號。
通過稱為領(lǐng)導(dǎo)者（leader）的單個服務(wù)器發(fā)送所有更新，我們將非冪等請求轉(zhuǎn)換為冪等事務(wù)。在本文中，我們使用事務(wù)（transaction）一詞來表示冪等的請求。領(lǐng)導(dǎo)者可以執(zhí)行轉(zhuǎn)換，因為它對數(shù)據(jù)庫副本的未來狀態(tài)有充分的了解，并且可以計算出新紀(jì)錄的狀態(tài)，冪等事務(wù)是此新狀態(tài)的一條記錄。Zookeeper在許多方面都使用了冪等事務(wù)，這超出了本文的范圍，但是事務(wù)的冪等性質(zhì)也使我們可以在恢復(fù)過程中放寬對廣播協(xié)議的順序要求。
2. 需求
我們假設(shè)有一組實現(xiàn)并使用了原子廣播協(xié)議的進(jìn)程集，為了確保在 Zookeeper 中可以正確地轉(zhuǎn)換冪等請求，在同一時間只能有一個領(lǐng)導(dǎo)者，因此我們實現(xiàn)協(xié)議時，強制規(guī)定只有這樣一條進(jìn)程，當(dāng)我們提供協(xié)議的更多細(xì)節(jié)時，會進(jìn)行更深入的討論，Zookeeper 對廣播協(xié)議提出以下需求：
- 可靠交付（Reliable delivery）：假設(shè)一條消息 m，在一臺服務(wù)器交付，最終它可以在所有正常的服務(wù)器交付；
- 完全有序（Total order）：假設(shè)一臺服務(wù)器先交付消息 a，再交付消息 b，那么最終所有的服務(wù)器都會按照順序交付消息 a 和消息 b
- 因果有序（Causal order）：假設(shè)消息 a 在因果關(guān)系上先于消息 b，那么在交付時，消息 a 必須在消息 b 之前；
為了正確起見，Zookeeper 還增加了前綴屬性 - 前綴屬性（Prefix property）：假設(shè)消息 m 是領(lǐng)導(dǎo)者 L 交付的最后一條消息，則必須交付 L 在 m 消息之前提議的任何消息。
注意，一條進(jìn)程可能會被多次選舉，然而，根據(jù)前綴屬性而言，每次都被視為不同的領(lǐng)導(dǎo)者。有了這三個保證，我們就可以維護(hù) Zookeeper 數(shù)據(jù)庫副本的正確定：
- 可靠性和全序性可以確保所有副本均具有一致的狀態(tài)；
- 因果有序性可以確保從使用 Zab 的應(yīng)用程序角度來看，副本都具有正確的狀態(tài)；
- 領(lǐng)導(dǎo)者根據(jù)收到的請求建議對數(shù)據(jù)庫進(jìn)行更新。
需要重點觀察 Zab 考慮了兩種因果關(guān)系：
- 如果兩個消息，a 和 b，是由同一臺服務(wù)器發(fā)送的，并且 a 在 b 之前提出，則我們說 a 的因果關(guān)系在 b 之前；
- Zab 假設(shè)在同一時間只有一個領(lǐng)導(dǎo)者可以提交提案（proposal），如果領(lǐng)導(dǎo)者發(fā)生了變更，則任何先前提議的消息在因果關(guān)系上都先于新領(lǐng)導(dǎo)者提出的消息。
因果沖突示例
為了顯示由于違反因果關(guān)系第2個維度而導(dǎo)致的問題，請考慮以下情形：
Zookeeper 客戶端 C1 請求將 znode /a 設(shè)置為1，先將其轉(zhuǎn)換為消息 w1("/a","1",1)，這個元組中包含路徑、值和 znode 的最終版本；
然后 C1 請求將 /a 設(shè)置為2，它轉(zhuǎn)換成消息 w2("/a","2",2)
L1 提議并提交 w1 消息，但它只能在失敗之前向其自身發(fā)送 w2 消息
新的領(lǐng)導(dǎo)者 L2 接任
客戶端 C2 請求根據(jù)版本1將 /a 設(shè)置為3，該版本將轉(zhuǎn)換為消息 w3("/a","3",2)
L2 提議并交付 w3
在這種情況下，客戶端收到 w1 消息的成功響應(yīng)，但是由于領(lǐng)導(dǎo)者失敗而導(dǎo)致 w2 消息出現(xiàn)錯誤。如果最終 L1 恢復(fù)，重新獲得領(lǐng)導(dǎo)權(quán)，并嘗試為 w2 交付提議，則將違反客戶端請求的因果順序，并且副本狀態(tài)將發(fā)生錯誤。
我們的故障模型是具有狀態(tài)恢復(fù)的崩潰失敗模型（crash-fail with stateful recovery），我們不需要時鐘同步，但是我們需要服務(wù)器感知時間的速率大致相同（我們使用超時來檢測故障）。組成 Zab 的進(jìn)程具有持久化狀態(tài)，因此進(jìn)程可以在故障后重新啟動并使用持久化狀態(tài)進(jìn)行恢復(fù)。這意味著進(jìn)程可能只有部分有效的狀態(tài)，例如丟失了最近的事務(wù)，更成問題的是，進(jìn)程中可能包含了之前更早的還未交付的，但現(xiàn)在必須丟棄的事務(wù)。
我們有能力處理 f 個故障，同時我們還需要處理相關(guān)的可恢復(fù)故障，例如斷電。為了從這些故障中恢復(fù)，我們要求在提交消息之前將消息記錄磁盤介質(zhì)上。
雖然我們假定不會發(fā)生拜占庭式故障（Byzantine failure），但我們還是使用摘要（digest）來檢測數(shù)據(jù)是否損壞，我們還將額外的元數(shù)據(jù)添加到協(xié)議數(shù)據(jù)包中，用于完整性檢查。如果檢測到數(shù)據(jù)損壞或完整性檢查失敗，我們將終止服務(wù)器進(jìn)程。
由于運行環(huán)境的獨立性以及協(xié)議本身等實際問題，使得對于我們的應(yīng)用來說，實現(xiàn)完全拜占庭容錯的系統(tǒng)（Byzantine tolerant system）是不切實際的。這也表明，實現(xiàn)真正可靠的獨立實現(xiàn)不僅需要編程資源，還需要更多其他資源。迄今為止，我們大多數(shù)生產(chǎn)問題都是由于實現(xiàn)問題影響到了所有副本，或者 Zab 實現(xiàn)范疇外的問題，但是同樣會影響到 Zab 功能，例如網(wǎng)絡(luò)配置錯誤。
Zookeeper 使用內(nèi)存數(shù)據(jù)庫，并將事務(wù)日志和定期快照存儲在磁盤上。Zab 的事務(wù)日志也兼做了數(shù)據(jù)庫寫前（write-head）事務(wù)日志，因此事務(wù)將只寫入磁盤一次。因為數(shù)據(jù)庫是在內(nèi)存中的，并且我們使用千兆網(wǎng)卡，因此寫操作的性能瓶頸是磁盤 I/O，為了緩解磁盤 I/O 瓶頸，我們采用批處理寫入事務(wù)，以便可以在一次寫入磁盤時記錄多個事務(wù)。這個批處理發(fā)生在副本實現(xiàn)層面而非協(xié)議層面，因此實現(xiàn)更接近于數(shù)據(jù)庫的分組提交（group commit），而非消息打包（message packing）。我們不選擇消息打包，這樣可以最大程度減少延遲，同時仍然可以通過批量磁盤 I/O 獲得打包操作的大部分好處。
除此之外我們還有其他操作需求：
- 低延遲（Low latency）：Zookeeper 被應(yīng)用程序廣泛使用，用戶期望響應(yīng)時間足夠短；
- 爆發(fā)性高吞吐量（Bursty high throughput）：使用 Zookeeper 的應(yīng)用程序通常具有以讀為主的工作負(fù)載，但有時需要重整數(shù)據(jù)，會導(dǎo)致大的寫吞吐量峰值；
- 平滑的故障處理（Smooth failure handling）：如果不是領(lǐng)導(dǎo)服務(wù)器發(fā)生故障，并且仍然有足夠數(shù)量的正確服務(wù)器，則不應(yīng)該發(fā)生服務(wù)中斷。
3. 為什么要選擇新的協(xié)議
可靠的廣播協(xié)議根據(jù)應(yīng)用程序要求不同呈現(xiàn)不同的語義。例如 Birman 和 Joseph 提出了兩個原語（primitives），ABCAST 和 CBCAST，它們分別滿足完全有序和因果有序。Zab 同時滿足了兩者的需求。
在我們的案例中，有一個很好的候選協(xié)議 Paxos。Paxos具有許多重要的屬性，比如當(dāng)存在進(jìn)程故障時仍能確保安全性；允許進(jìn)程崩潰和恢復(fù)，以及允許在現(xiàn)實情況下在三個通信步驟內(nèi)提交操作。我們看到有兩個假設(shè)可以使我們簡化 Paxos 并獲取高吞吐量。首先，Paxos 可以容忍消息丟失和消息重新排序，通過使用 TCP 在成對的服務(wù)器之間進(jìn)行通信，我們可以保證交付的消息都是以 FIFO 順序提交的，這使我們即使在服務(wù)器進(jìn)程中有多個未完成的提議消息時也能滿足每個提議者間的因果關(guān)系。但是，Paxos 并不直接保證因果關(guān)系，因為它不需要 FIFO 通道。
在 Paxos 中，提議者（Proposer）是可以提交提議的代理，為了保證進(jìn)度，只能有一個提議者提出提議，否則在特定情況下，提議者之間會永遠(yuǎn)保持競爭。處于激活狀態(tài)的提議者稱之為領(lǐng)導(dǎo)者，當(dāng) Paxos 從領(lǐng)導(dǎo)者故障中恢復(fù)后，新領(lǐng)導(dǎo)者將確保所有交付到一半的消息均已完全交付，然后從舊領(lǐng)導(dǎo)者遺留下來的實例序號恢復(fù)提議。由于多個領(lǐng)導(dǎo)者會為同一份實例提出提議，這會產(chǎn)生兩個問題。首先，提案可能會發(fā)生沖突，Paxos 使用選票來派發(fā)和解決有沖突的提案。其次，僅知道已經(jīng)提交的實例號還不夠，進(jìn)程還必須知道提交了哪個值。Zab 通過確保對一個給定的值只能有一條提議來避免這兩個問題，這消除了投票的需要，同時簡化了恢復(fù)過程，在 Paxos 中，如果服務(wù)器認(rèn)為自己是領(lǐng)導(dǎo)者，它將使用更高的選票從先前的領(lǐng)導(dǎo)者手中接管領(lǐng)導(dǎo)職務(wù)。但是在 Zab 中，新的領(lǐng)導(dǎo)者無法接任領(lǐng)導(dǎo)權(quán)，直到大量的服務(wù)器放棄了先前的領(lǐng)導(dǎo)者。
獲得高吞吐量的另一種方法是通過限制每個廣播消息的協(xié)議消息復(fù)雜度，例如使用固定序列環(huán)（FSR），F(xiàn)SR 不會隨著系統(tǒng)的增長而減少吞吐量，但是延遲會隨著進(jìn)程數(shù)量的增加而增加，這個不適用于我們的環(huán)境。虛擬同步（Virtual synchrony）在群組穩(wěn)定了足夠長時間后可以提供高吞吐量，但是，任一服務(wù)器故障都會導(dǎo)致服務(wù)重新配置，在重配置過程中會有短暫的服務(wù)中斷。另外，在這個系統(tǒng)里，故障監(jiān)視器（failure detector）需要監(jiān)視所有服務(wù)器，這樣，故障監(jiān)視器的可靠性對重新配置的穩(wěn)定性和速度顯得尤為關(guān)鍵。基于領(lǐng)導(dǎo)者（Leader-based）的協(xié)議同樣依賴故障監(jiān)視器來保持活性，這個故障監(jiān)視器一次只監(jiān)視一臺服務(wù)器，就是 Leader。在接下來章節(jié)的討論中，當(dāng)領(lǐng)導(dǎo)者沒有發(fā)生故障時，我們就不為寫入或者保持服務(wù)可用性使用固定數(shù)量的集群和群組。
根據(jù) Defago 等人的分類，我們的協(xié)議有固定的計數(shù)器（sequencer）就是領(lǐng)導(dǎo)者。這個領(lǐng)導(dǎo)者是通過領(lǐng)導(dǎo)者選舉算法選舉出來的，并與其他服務(wù)器，稱為追隨者（follower）保持同步。由于領(lǐng)導(dǎo)者必須管理發(fā)給所有追隨者的消息，所以使用固定計數(shù)器可能會造成系統(tǒng)的各個服務(wù)器之間負(fù)載不均衡。雖然如此，我們接受這個方法，主要有以下幾個原因：
- 客戶端可以連接到任何服務(wù)器，并且服務(wù)器必須在本地提供讀取操作，并維護(hù)有關(guān)客戶端會話的信息。追隨者進(jìn)程（而非領(lǐng)導(dǎo)者進(jìn)程）的額外負(fù)載會使負(fù)載分布更加均勻；
- 涉及的服務(wù)器數(shù)量很少，這意味著網(wǎng)絡(luò)通信開銷不會成為影響固定計數(shù)器協(xié)議的瓶頸；
- 無需實現(xiàn)更復(fù)雜的方法，這種簡單的方式可以提供足夠的性能。
例如，使用移動計數(shù)器會增加實現(xiàn)的復(fù)雜性，因為我們必須處理諸如令牌丟失之類的問題。另外我們選擇遠(yuǎn)離基于通信歷史記錄的模型，例如基于發(fā)送者（sender-based）的模型，以避免此類協(xié)議的二次消息復(fù)雜度（quadratic message complexity），最終一致性協(xié)議也有同樣的問題。
使用領(lǐng)導(dǎo)者，需要我們從領(lǐng)導(dǎo)者的失敗中恢復(fù)過來以保證進(jìn)度，我們使用與視圖變化相關(guān)的技術(shù)，例如 Keidar and Dolev 協(xié)議，與他們協(xié)議不同的是，我們不使用群組通信進(jìn)行操作。如果新服務(wù)器加入或退出（可能是崩潰），那么我們不會引發(fā)視圖變更，除非那是一個 Leader 崩潰的事件。
4. Zab協(xié)議
Zab 協(xié)議包括兩個模式：恢復(fù)（recovery）和廣播（broadcast）。服務(wù)啟動時，或者領(lǐng)導(dǎo)者發(fā)生故障之后，Zab 會過渡到恢復(fù)模式。當(dāng)領(lǐng)導(dǎo)者重新出現(xiàn)并且多數(shù)服務(wù)器與之進(jìn)行同步后，恢復(fù)模式結(jié)束。狀態(tài)同步保證領(lǐng)導(dǎo)者和新的服務(wù)器保持一致的狀態(tài)。
當(dāng)一個領(lǐng)導(dǎo)者有了多數(shù)同步的追隨者，它就可以開始廣播消息。就像我們在簡介中提到的，Zookeeper 服務(wù)使用一個領(lǐng)導(dǎo)者處理請求。領(lǐng)導(dǎo)者就是那個通過初試話廣播協(xié)議處理廣播的服務(wù)器，其他服務(wù)器要發(fā)送消息的話需要將消息先發(fā)送給領(lǐng)導(dǎo)者。通過從恢復(fù)模式選出來的領(lǐng)導(dǎo)者同時擔(dān)任處理寫請求和協(xié)調(diào)廣播協(xié)議的領(lǐng)導(dǎo)者，我們消除了從寫請求領(lǐng)導(dǎo)者到廣播協(xié)議領(lǐng)導(dǎo)者間的網(wǎng)絡(luò)延遲。
如果一個 Zab 服務(wù)器在領(lǐng)導(dǎo)者正在廣播的時候上線，這個服務(wù)器會以恢復(fù)模式啟動，并會尋找領(lǐng)導(dǎo)者并與之同步，然后開始參與消息廣播。服務(wù)會保持在廣播模式，直到領(lǐng)導(dǎo)者發(fā)生故障或者它不再具有多數(shù)集合的追隨者。任意多數(shù)集的追隨者對領(lǐng)導(dǎo)者都是足夠的，這樣服務(wù)就能維持激活狀態(tài)。比如一個 Zab 服務(wù)由三臺服務(wù)器組成，其中一臺是領(lǐng)導(dǎo)者，另外兩臺是追隨者，然后系統(tǒng)進(jìn)入廣播模式。如果其中一臺追隨者死亡，也不會造成服務(wù)中斷，因為領(lǐng)導(dǎo)者仍然具有一個多數(shù)集。如果這個追隨者恢復(fù)而另一個死亡，那樣也不會造成服務(wù)中斷。
4.1 廣播
在原子廣播協(xié)議運行時，我們使用的協(xié)議為廣播模式，類似一個簡單的二段式提交（two-phase commit）：領(lǐng)導(dǎo)者提出一個請求，收集投票，最后提交。圖二描述了我們協(xié)議的信息流。我們可以簡化二段式提交，因為我們沒有中斷（abort），追隨者要么接受這個領(lǐng)導(dǎo)者的提案，要么放棄這個領(lǐng)導(dǎo)者。沒有中斷意味著我們可以在多數(shù)服務(wù)器回應(yīng)（ack）時立即提交，而不用等到所有服務(wù)器響應(yīng)。在這個簡化的二段式提交中，系統(tǒng)不能自己處理領(lǐng)導(dǎo)者故障，所以我們添加了恢復(fù)模式去處理領(lǐng)導(dǎo)者故障。
這個廣播協(xié)議使用 FIFO（TCP）通道進(jìn)行所有通信，使用 FIFO 通道時，保證順序一致就非常簡單了，消息通過 FIFO 通道被順序派發(fā)，只要消息以它們接收到的順序被處理，順序就能得到保證。
領(lǐng)導(dǎo)者為需要交付的消息廣播一個提案，在發(fā)起提案之前，領(lǐng)導(dǎo)者會為它分配一個唯一的單調(diào)遞增的Id，稱為 zxid。因為 Zab 保證了因果有序，所以發(fā)送的消息也會根據(jù) zxid 排序。包含信息的提案會附加到每個追隨者的輸出隊列中，并通過 FIFO 通道發(fā)送給追隨者。當(dāng)追隨者收到提案時，會將它寫入磁盤，條件允許的話會批量寫入，當(dāng)提案寫入到磁盤后會立即發(fā)送一個回應(yīng)給領(lǐng)導(dǎo)者（acknowledgement）。當(dāng)領(lǐng)導(dǎo)者從多數(shù)追隨者哪里收到回應(yīng)后，它會廣播一條提交（commit）指令，然后在本地提交信息。當(dāng)追隨者從領(lǐng)導(dǎo)者那邊收到提交（commit）指令時也會提交信息。
注意，如果追隨者之間可以互相廣播 ACK 的話，領(lǐng)導(dǎo)者并不一定要發(fā)送 COMMIT 指令，這個改動不僅會提升網(wǎng)絡(luò)負(fù)載，它也需要比簡單星狀拓?fù)洌╯tart topology）結(jié)構(gòu)更完整的通信圖，星狀拓?fù)鋸?TCP 連接的角度來看更容器管理。假設(shè)采用之前設(shè)想的圖，并跟蹤 ACK 信息，對于我們現(xiàn)實中的實現(xiàn)來說，是不可接受的復(fù)雜度。
4.2 恢復(fù)
這個簡單的廣播協(xié)議在領(lǐng)導(dǎo)者發(fā)生故障或失去多數(shù)的追隨者前都能良好工作，為了保證進(jìn)度，可以選舉新領(lǐng)導(dǎo)者和使所有服務(wù)器都進(jìn)入正確狀態(tài)的恢復(fù)過程就顯得很有必要了。對于領(lǐng)導(dǎo)者選舉，我們需要一個高成功率的算法保障其處于激活態(tài)。這個領(lǐng)導(dǎo)者選舉協(xié)議不僅要讓領(lǐng)導(dǎo)者知道自己是領(lǐng)導(dǎo)者，也要讓多數(shù)服務(wù)器贊成這個決定。如果選舉在某個階段發(fā)生錯誤，那么服務(wù)器不會進(jìn)行下一步工作，它們最終會超時，然后重新開始領(lǐng)導(dǎo)者選舉。領(lǐng)導(dǎo)者選舉總共有兩種實現(xiàn)，在大多數(shù)服務(wù)運行正常的情況下，領(lǐng)導(dǎo)者選舉最快幾百毫秒就能完成。
在恢復(fù)階段完成的這段時間內(nèi)，會有一些提案被交付，提案個數(shù)的最大值可以配置，默認(rèn)值是1000，為了保證這個協(xié)議在領(lǐng)導(dǎo)者故障時也能正常工作，我們需要兩個確切的保證：我們不會忽略任何已提交的消息，也不會保留已經(jīng)丟棄的消息。
如果某條消息在一臺機器交付，那么就應(yīng)該在所有機器上都被交付，哪怕那臺機器出現(xiàn)故障。這種情況很容易出現(xiàn)，如果領(lǐng)導(dǎo)者在提交了一條消息后，在 COMMIT 指令達(dá)到其他機器前出現(xiàn)故障，如圖三所示，因為領(lǐng)導(dǎo)者已經(jīng)提交（commit）了這條消息，客戶端應(yīng)該能在這條消息中看到事務(wù)的結(jié)果，所以該事務(wù)最終要發(fā)送給所有其他服務(wù)器，這樣客戶端才能看到一個一致的視圖。
相反地，需要被丟棄的消息必須丟棄，同樣這種情況也很容易出現(xiàn)，如果領(lǐng)導(dǎo)者生成了一個提案，然后在任何其他其他機器看到這個提案之前就出現(xiàn)了故障，如圖三所示，沒有其他服務(wù)器看到編號為3的提案，所以在圖四中，當(dāng)服務(wù)器1重新上線并重新集成到系統(tǒng)中，它需要保證把編號為3的提案丟棄。如果服務(wù)器1成為新的領(lǐng)導(dǎo)者，并在消息P1和P2被提交后提交消息3，就違反了我們的順訊保證。
通過對領(lǐng)導(dǎo)者選舉協(xié)議的簡單調(diào)整就能解決記住已交付消息的問題，如果這個領(lǐng)導(dǎo)者選舉協(xié)議保證新的領(lǐng)導(dǎo)者具有多數(shù)服務(wù)器中最高的提案編號，那么新選出來的領(lǐng)導(dǎo)者就會擁有所有已提交的消息。在提出新提案消息之前，新選出來的領(lǐng)導(dǎo)者要保證所有記錄在它事務(wù)日志中的消息已經(jīng)被交付，并被多數(shù)服務(wù)器通過。注意到新的領(lǐng)導(dǎo)者是處理最高 zxid 的服務(wù)器進(jìn)程正好是一個優(yōu)化，這樣新選舉出來的領(lǐng)導(dǎo)者不需要從追隨者群組中去查找，哪個擁有最高的 zxid，并且去拉?。╢etch）丟失的事務(wù)。
所有正常運行的服務(wù)器要么是一個領(lǐng)導(dǎo)者，要么就是這個領(lǐng)導(dǎo)者的追隨者。領(lǐng)導(dǎo)者保證它的追隨者可以看到所有提案，并且所有已通過的提案都被交付。它通過把新連接的追隨者還沒看到的提案（PROPOSAL）指令放到隊列里，然后將從這些提案到最新提交信息的提交（COMMIT）指令記錄也放到隊列里來實現(xiàn)這個需求。當(dāng)所有這些消息都放到隊列中后，領(lǐng)導(dǎo)者將追隨者添加到以后的 PROPOSAL 和 ACK 廣播列表。
忽略那些被提出的，但是沒有被交付的消息同樣也很容易處理。在我們的實現(xiàn)中，zxid 是個64位數(shù)字，其中低32位當(dāng)做一個簡單的計數(shù)器，每一條提案都會增加那個計數(shù)。高32位代表輪次（epoch）。每次新的領(lǐng)導(dǎo)者選出，它會從它日志中最高的 zxid 中提取出輪次，增加輪次，并用新輪次和計數(shù)0組成新的 zxid。使用輪次去標(biāo)記領(lǐng)導(dǎo)者的變更，并且讓多數(shù)服務(wù)器可以感知到某臺服務(wù)器是當(dāng)前輪次的領(lǐng)導(dǎo)者，可以讓我們避免多個領(lǐng)導(dǎo)者使用同一個 zxid 提出不同提案的情況。使用這個模式的另一個好處是我們能忽略當(dāng)領(lǐng)導(dǎo)者故障時生產(chǎn)的實例，這樣可以加速并簡化恢復(fù)過程。如果一臺服務(wù)器重啟，并帶著一條沒被交付的上輪消息，它不能成為一個新的領(lǐng)導(dǎo)者，因為在任一多數(shù)服務(wù)集中，都有一個具有最新輪次的，即有最高 zxid 提案的服務(wù)器。當(dāng)這個服務(wù)器以追隨者的身份連接領(lǐng)導(dǎo)者時，領(lǐng)導(dǎo)者檢查追隨者的最大提案輪次中最后提交的消息，并讓追隨者清空它的事務(wù)日志直到當(dāng)前輪次。在圖四中，當(dāng)服務(wù)器1連接上領(lǐng)導(dǎo)者時，領(lǐng)導(dǎo)者會告訴它從事務(wù)日志中清除提案3。
結(jié)束語
我們可以快速地實現(xiàn)這個協(xié)議，并且在生產(chǎn)環(huán)境上證明了它的健壯性。更為重要的是，我們也實現(xiàn)了高吞吐量低延遲的目標(biāo)。在非飽和（non-saturated）系統(tǒng)中，延遲與服務(wù)器數(shù)量無關(guān)，是數(shù)據(jù)包傳輸延遲的4倍，通常情況以毫秒為單位。爆發(fā)性負(fù)載也得到了適當(dāng)?shù)奶幚?，因為提案收到多?shù)回應(yīng)時，消息就會被提交。遲緩的服務(wù)器不會影響爆發(fā)性吞吐量，因為速率較快的多數(shù)服務(wù)器可以在不包含慢速服務(wù)器的前提下整體響應(yīng)消息。最后，由于領(lǐng)導(dǎo)者收到多數(shù)追隨者回應(yīng)后就提交消息，所以只要大多數(shù)機器運行正常，追隨者的故障就不會影響性能和吞吐量。
由于該協(xié)議的高效實現(xiàn)，我們有一個系統(tǒng)已經(jīng)達(dá)到了每秒數(shù)萬次的操作，讀寫負(fù)載比例達(dá)到2:1，甚至更高。這個系統(tǒng)已經(jīng)在生產(chǎn)環(huán)境中使用，并且應(yīng)用于大型應(yīng)用，比如雅虎 crawler 和雅虎廣告系統(tǒng)。
