本文翻譯自《Tweaking the BookKeeper Protocol - Unbounded Ledgers》，作者 Jack Vanlightly，Apache BookKeeper Committer。StreamNative 校對並整理。

譯者簡介

朱哲，現就職於 Shopee Engineering Infra 團隊，初次接觸 Pulsar 開源社區 目前正在參與社區文檔的翻譯工作，期望早日全面瞭解社區並期待能貢獻代碼～

在上一篇文章 [1] 中，我描述了必要的協議更改用於確保關閉的 ledger 中所有的 entry 都能夠達到 Write Quorum (WQ)，即寫入的 ledger 超過 Ack Quorum，並且打開（OPEN）的 ledger 中除最後一個 fragment 之外的 entry 全部達到 Write Quorum。

在這篇文章中，我們將研究對協議的另一項調整，允許 ledger 無界，支持多個客戶端在其生命週期內對 ledger 寫入數據。

爲什麼選擇無界的 ledger

目前，ledger 是有界的。如果要創建無界日誌，則需要創建一組有界的 ledger 日誌（形成日誌的日誌）。例如，Pulsar Topic 實際上是一個有序的 ledger 流。核心的 BookKeeper 協議不支持開箱即用的無界日誌協議。如果想使用，必須在 BookKeeper 頂層封裝該邏輯，但這並非易事。

據我所知，log-of-ledgers 的實現由 Apache Pulsar 中的 Managed Ledger 模塊和 BookKeeper 倉庫中的一部分分佈式日誌庫（Distributed Log library）組成。這兩個模塊本身就相當複雜。

但是 ledger 是否需要有界？難道我們不能只允許單個 ledger 成爲無界流並使其包含在覈心協議中嗎（即使用單個 ledger 存儲所有消息）？UnboundedLedgerHandle（無界的 ledger 處理器）可能是比現有替代方案更簡單的流 API（極大地降低代碼量）。

日誌的日誌

使用 BookKeeper 進行日誌存儲的好處在於它的動態特性。例如，當橫向擴展 bookie 節點時，它們會很快開始自動負載均衡。原因之一是隨着新 ledger 的增加，新的 bookie 能用來託管這些 ledger。Ledger 是更大日誌中的日誌段，每個日誌段可以託管在一組不同的 bookie 上。

但是單個 ledger 已經是日誌段（即 fragment）的日誌。每次寫入失敗時，系統會給已有 ledger 追加新的 fragment，從而導致系統發生 ensemble change。每個 ledger 都包含一個或多個 fragment，每個 fragment 都共享同一個 bookie ensemble。出於這個原因，從日誌直接對應到 ledger 並不是獲得這種良好擴展能力的唯一方法。

在當前的協議下，Fragment 會在寫入失敗時新建。但對於無界的 ledger，我們還可以設置每個 fragment 的最大容量，一旦當前 fragment 達到該容量，將會觸發 ensemble change。

圖 1. 從 fragment 的角度看無界與有界 ledger 的對比

在無界 ledger 中，一個流（例如 Pulsar topic）是一個單獨的 ledger，由跨 bookie 集羣存儲的 fragment 日誌組成。

無界 ledger 的協議更改

將當前協議修改爲無界 ledger 所需的變動比較小，畢竟大部分協議及代碼已經存在。

更改此協議的核心是要將 ledger fencing 從 boolean 類型（即 “是否爲 fenced”） 改爲整數 term，當新客戶端接管數據寫入時此 term 的值會增加。

我們從一個 ledger 只能由創建它的客戶端寫入的模型轉變爲一個 ledger 可以被任意客戶端寫入，但一次只能由一個客戶端寫入的模型。就像在常規的 BookKeeper 協議中一樣，假設協議外部的客戶端存在 leader 選舉，那麼在正常情況下，應該只有一個客戶端嘗試寫入 ledger。即便有兩個或多個客戶端爭奪控制權，該協議仍然適用。

Fencing 保證了 BookKeeper 只有一個編寫器（Pulsar Broker）可以寫入 Ledger，此機制在協議修改後將會被 term 機制替代。當多個客戶端協調後將會選舉出一個寫入 ledger 的客戶端，同時會在元數據和最後一個 fragment 所在的 bookie 中記錄該 ledger。恢復流程會在 term 的開始執行，而非只在 ledger 關閉時。

圖 2. Ledger 的生命週期的狀態及 term

每個 fragment 都沒有綁定到任何特定的 term，term 只是一種 fencing 機制，防止之前的 leader 進行寫入操作，從而影響集羣數據。

所下圖所示，使用 term 機制時，元數據會新增一個字段。由於 ledger 長期存儲的特性，ensemble 列表（即 fragments）可能會變得非常大，所以現有的 ensemble 字段需要修改。爲了執行數據保留策略，使用 BookKeeper 的系統需要能夠刪除 fragment，而不是 ledger。

圖 3. 元數據獲新增了一個 item 字段。需要重新考慮數據過期的最小緯度，因爲 fragment 列表可能會變得非常大。

Term 機制與 fencing 機制非常相似。當一個新客戶端想要對 ledger 進行寫入時，首先會在 ledger 元數據中增加 term 的值（也就是前文協議中新增的字段），然後執行 ledger 恢復操作。客戶端像往常一樣將 LAC 請求發送到當前 fragment，但和之前不同的是使用新的 term 機制，而不是 fencing 標誌。

圖 4. Fencing 過程包含新的 term，而不是 fencing 標誌。

以下請求需要包含客戶端當前的 term 信息：

• • normal adds

• • recovery adds

• • recovery LAC reads

• • recovery reads

正常的讀取數據與 term 無關，唯一相關的仍然是 LAC (Last Add Confirmed)，即最後一個寫成功的消息 ID。

如果 bookie 的 ledger term 小於或等於請求的 ledger term，它會接受該請求並更新當前的 ledger term。如果 bookie 有更高的 ledger term，它會以 InvalidTerm 響應拒絕請求。

當客戶端收到 InvalidTerm 響應時，它應該退出，停止繼續寫入數據。它可以檢查它是否仍然是假定的 leader（存在於此協議外部），如果仍然是，則會先刷新其 ledger 元數據以重新接入。

對 ledger 恢復流程的一個額外修改是，恢復時必須刪除最後一個 fragment 中前一個 term 的所有髒數據（dirty entry），實現方法是在恢復期間寫回的最後一個 entry 中包含一個新的 “truncate”（截斷）標誌。我們必須保證最後一個 entry 被寫入最後一個 fragment 的所有 bookie，因此我們必須利用 “確保 Write Quorum” 中的一些邏輯來實現這一點。

Term 的使用範疇

到目前爲止，我想到了兩種主要的設計，每一種都以不同的方式使用 term。

僅將 term 用於 fencing

本文所談及的 term 並未將其作爲 entry 標識符或 fragment 標識符的一部分，它僅用於 fencing。然而準確來說，這裏所談到的 term 設計還至少需要以下二點：第一，上一篇文章 [2] 中詳述的 “確保 Write Quorum” 更改的一部分內容；第二，一個最終的截斷 no-op entry 作爲恢復期間要寫回的最後一條 entry。請查看以下內容以瞭解原因：

• • 客戶端 c1 寫入兩條 entry {Id: 0, value: A} 和 {Id: 1, value: B} 到 bookie b1、b2 和 b3。

• • entry0 成功寫入 b1、b2 和 b3，而 entry1 只成功寫入 b1。

• • 客戶端 c2 此時接管併成爲 leader。執行數據恢復時，檢測到最後一個可恢復的數據是 entry0，於是將 entry0 寫回 b1、b2 和 b3，並更新 ledger 狀態爲打開（OPEN），允許新數據寫入。

• • 客戶端 c2 寫入一條 entry {id: 1, value: C} 到 b1、b2 和 b3。

• • b2 和 b3 回覆 ack 確認成功寫入該消息，b1 此時暫無響應。由於已寫入 entry 的 bookie 數目超過 Ack Quorum，因此客戶端 c2 認爲寫入成功並忽略 b1 的超時。

• • 此時，日誌會產生差異，不同 bookie 上 entry1 所對應的值不同，即 {Id: 1, value: B} 和 {id: 1, value: C}。

要避免這種情況，可以添加一個帶有 “truncate”（截斷）標誌的 no-op entry 作爲要恢復的最後一個 entry。當 bookie 收到帶有 truncate 標誌的 entry 時，它會刪除所有具有更高 id 的 entry。藉助 truncate 標誌並確保達到 Write Quorum，可以確保最後一個 fragment 中的任何 bookie 都沒有截斷任何髒數據。這意味着 BookKeeper 客戶端需要知道這些 no-op entry 並丟棄它們。

這種方法的好處是 term 只是 ledger 元數據中的一個額外字段，並且 bookie 只需要將 term 存儲在 ledger 索引中，就像現在使用 fencing 一樣。term 不需要與每個具體的 entry 一起存儲。

缺點則是引入了 no-op entry。

在恢復寫入時，我們只需要確保 Write Quorum，因此正常寫入可以繼續使用現有行爲。

將 term 作爲 entry 標識符

另一種解決方案是使 term 更深入地集成在協議中，將 term 作爲 entry 標識符的一部分寫入，這可以防止上述日誌差異的情況。c1 寫入的未提交 entry 1 不會與 c2 寫入的 entry 1 混淆，因爲它們具有不同的 term。

此時元數據需要包括每個 term 的 entry 範圍，以便客戶端在讀取給定 entry 時可以包含正確的 term。

我們不需要 fragment 和 term 進行關聯，這樣做的原因是會使元數據更加緊湊。

這種方法的好處是我們不需要在恢復寫入時確保 Write Quorum，缺點則是 term 必須與每個 entry 一起存儲。

之後，我可能會構建一個無界 ledger 的設計，其中包括將 term 作爲 entry 標識符的一部分。

正式驗證

基於需要確保 Write Quorum 的規範，我已經通過 TLA+ 驗證了無界 ledger 協議的更改。

請參考我的 GitHub 倉庫 BookKeeper TLA+[3] 查看相關規範驗證。

最後的思考

目前上文提到的相關問題只是對於這種架構的預想，因爲 Splunk 現在沒有對無界 ledger 的迫切需求。但我確實認爲它可以在未來成爲對 BookKeeper 的重要補充，並且可能適用於新的場景。

從修改後的 LedgerHandle 接口中生成流 API 的協議更改不是太大，但實際上有許多次要影響，例如會影響自動恢復和垃圾收集。因此，協議的變更絕非無足輕重。

無論如何，探索協議的變化很有趣。它揭示了協議爲何如此的一些原因以及所做出的權衡決策，表明了 TLA+ 對這類系統的價值，因爲它讓我們能輕而易舉地驗證各種想法。

此外，還可能有一些不同的設計可供我們選擇與探索。

更新 1：我的原始設計不包括截斷（truncation）。當使用更大的模型時，TLA+ 規範發現了日誌差異的反例。爲了避免這種情況，在新 term 的恢復階段恢復的最後一個 entry 需要一個新的 “truncation” 標誌。

引用鏈接

[1] 上一篇文章: https://jack-vanlightly.com/blog/2021/12/7/tweaking-the-bookkeeper-protocol-guaranteeing-write-quorum
[2] 上一篇文章: https://jack-vanlightly.com/blog/2021/12/7/tweaking-the-bookkeeper-protocol-guaranteeing-write-quorum
[3] GitHub 倉庫 BookKeeper TLA+: https://github.com/Vanlightly/bookkeeper-tlaplus/blob/main/tweaks/ProtocolUnboundedLedgersAndGWQ.tla

ApachePulsar Apache 軟件基金會頂級項目，下一代雲原生分佈式消息流平臺，集消息、存儲、輕量化函數式計算爲一體，採用計算與存儲分離架構設計，支持多租戶、持久化存儲、多機房跨區域數據複製，具有強一致性、高吞吐、低延時及高可擴展性等流數據存儲特性。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/JSlObyqMsdZUtgFBfaeaBQ