BookKeeper 基礎

正如 Apache BookKeeper 官網介紹的一樣：A scalable, fault-tolerant, and low-latency storage service optimized for real-time workloads。BookKeeper 的定位是一個可用於實時場景下的高擴充套件性、強容錯、低延遲的儲存服務。Pulsar-Cloud Native Messaging & Streaming – 示說網 中也做了一個簡單總結：

低延遲多副本複製：Quorum Parallel Replication；持久化：所有操作保證在刷盤後才 ack；強一致性：可重複讀的一致性（Repeatable Read Consistency）;讀寫高可用；讀寫分離。BookKeeper 基本概念

BookKeeper 簡介 部分已經對 BookKeeper 的基本概念做了一些講解，這裡再重新回顧一下，只有明白這些概念之後才能對更好地理解後面的內容，如下圖所示，一個 Log/Stream/Topic 可以由下面的部分組成（圖片來自 Pulsar-Cloud Native Messaging & Streaming）。

BookKeeper 中的基本概念

其中：

Ledger：它是 BK 的一個基本儲存單元（本質上還是一種抽象），BK Client 的讀寫操作也都是以 Ledger 為粒度的；Fragment：BK 的最小分佈單元（實際上也是物理上的最小儲存單元），也是 Ledger 的組成單位，預設情況下一個 Ledger 會對應的一個 Fragment（一個 Ledger 也可能由多個 Fragment 組成）；Entry：每條日誌都是一個 Entry，它代表一個 record，每條 record 都會有一個對應的 entry id；

關於 Fragment，它是 Ledger 的物理組成單元，也是最小的物理儲存單元，在以下兩種情況下會建立新的 Fragment：

當建立新的 Ledger 時；當前 Fragment 使用的 Bookies 發生寫入錯誤或超時，系統會在剩下的 Bookie 中新建 Fragment，但這時並不會新建 Ledger，因為 Ledger 的建立和關閉是由 Client 控制的，這裡只是新建了 Fragment（需要注意的是：這兩個 Fragment 對應的 Ensemble Bookie 已經不一樣了，但它們都屬於一個 Ledger，這裡並不一定是一個 Ensemble Change 操作）。BookKeeper 架構設計

Apache BookKeeper 的架構如下圖所示，它主要由三個元件構成：客戶端 (client)、資料儲存節點 (Bookie) 和元資料儲存 Service Discovery（ZooKeeper），Bookies 在啟動的時候向 ZooKeeper 註冊節點，Client 透過 ZooKeeper 發現可用的 Bookie。

Apache BookKeeper 架構

這裡，我們可以看到 BookKeeper 架構屬於典型的 slave-slave 架構，zk 儲存其叢集的 meta 資訊（zk 雖是單點，但 zk 目前的高可用還是很有保障的），這種模式的好處顯而易見，server 端變得非常簡單，所有節點都是一樣的角色和處理邏輯，能夠這樣設計的主要原因是其副本沒有 leader 和 follower 之分，這是它與一些常見 mq（如：kafka、RocketMQ）系統的典型區別，每種設計都有其 trade-off，BeekKeeper 從設計之初就是為了高可靠而設計。

BookKeeper 儲存層實現

Apache BookKeeper 是一個高可靠的分散式儲存系統，儲存層的實現是其核心，對一個儲存系統來說，關鍵的幾點實現，無非是：一致性如何保證、IO 如何最佳化、高可用如何實現等，這小節就讓我們揭開其神秘面紗。

新建 Ledger

Ledger 是 BookKeeper 的基本儲存抽象單元，這裡先看下一個 Ledger 是如何建立的，這裡會介紹一些關於 Ledger 儲存層的一些重要概念（圖片來自 Pulsar-Cloud Native Messaging & Streaming）。

BookKeeper Ledger 的建立

Ledger 是一組追加有序的記錄，它是由 Client 建立的，然後由其進行追加寫操作。每個 Ledger 在建立時會被賦予全域性唯一的 ID，其他的 Client 可以根據 Ledger ID，對其進行讀取操作。建立 Ledger 及 Entry 寫入的相關過程如下：

Client 在建立 Ledger 的時候，從 Bookie Pool 裡面按照指定的資料放置策略挑選出一定數量的 Bookie，構成一個 Ensemble；每條 Entry 會被並行地傳送給 Ensemble 裡面的部分 Bookies（每條 Entry 傳送多少個 Bookie 是由 Write Quorum size 設定、具體傳送哪些 Bookie 是由 Round Robin 演算法來計算），並且所有 Entry 的傳送以流水線的方式進行，也就是意味著傳送第 N + 1 條記錄的寫請求不需要等待發送第 N 條記錄的寫請求返回；對於每條 Entry 的寫操作而言，當它收到 Ensemble 裡面大多數 Bookie 的確認後（這個由 Ack Quorum size 來設定），Client 認為這條記錄已經持久化到這個 Ensemble 中，並且有大多數副本。

BookKeeper Ledger 多副本複製

這裡引入了三個重要的概念，它們也是 BookKeeper 一致性的基礎：

Ensemble size(E)：Set of Bookies across which a ledger is striped，一個 Ledger 所涉及的 Bookie 集合；Write Quorum Size（Qw）：Number of replicas，副本數；Ack Quorum Size（Qa）：Number of responses needed before client’s write is satisfied。

從上面 Ensemble、Qw、Qa 的概念可以得到以下這些推論：

Ensemble：可以控制一個 Ledger 的讀寫頻寬；Write Quorum：控制一條記錄的複本數；Ack Quorum：寫每條記錄需要等待的 Ack 數 ，控制時延；增加 Ensemble，可以增加讀寫頻寬（增加了可寫的機器數）；減少 Ack Quorum，可以減長尾時延。一致性

對於分散式儲存系統，為了高可用，多副本是其通用的解決方案，但也帶來了一致性的問題，這裡就看下 Apache BookKeeper 是如何解決其帶來的一致性問題的。

一致性模型

在介紹其讀寫一致性之前，先看下 BK 的一致性模型（圖片來自 Twitter高效能分散式日誌系統架構解析）。

BookKeeper 一致性模型-開始時的狀態

對於 Write 操作而言，writer 不斷新增記錄，每條記錄會被 writer 賦予一個嚴格遞增的 id，所有的追加操作都是非同步的，也就是說：第二條記錄不用等待第一條記錄返回結果。所有寫成功的操作都會按照 id 遞增順序返回 ack 給 writer。（圖片來自 Twitter高效能分散式日誌系統架構解析）。

BookKeeper 一致性模型-追加資料時的中間狀態

伴隨著寫成功的 ack，writer 不斷地更新一個指標叫做 Last-Add-Confirm（LAC），所有 Entry id 小於等於 LAC 的記錄保證持久化並複製到大多數副本上，而 LAC 與 LAP（Last-Add-Pushed）之間的記錄就是已經發送到 Bookie 上但還未被 ack 的資料。

讀的一致性

所有的 Reader 都可以安全讀取 Entry ID 小於或者等於 LAC 的記錄，從而保證 reader 不會讀取未確認的資料，從而保證了 reader 之間的一致性（圖片來自 Twitter高效能分散式日誌系統架構解析）。

BookKeeper 一致性模型-讀的一致性

寫的一致性

從上面的介紹中，也可以看出，對於 BK 的多個副本，其並沒有 leader 和 follower 之分，因此，BK 並不會進行相應的選主（leader election）操作，並且限制每個 Ledger 只能被一個 Writer 寫，BK 透過 Fencing 機制來防止出現多個 Writer 的狀態，從而保證寫的一致性。

讀寫分離

下面來看下 BK 儲存層一個很重要的設計，那就是讀寫分離機制。在論文 Durability with BookKeeper 中，關於讀寫分離機制的介紹如下所示（圖片來自 Durability with BookKeeper）：

BookKeeper 讀寫分離

A bookie uses two devices, ideally in separate physical disks:

The journal device is a write-ahead log and stores synchronously and sequentially all updates the bookie executes.The ledger device contains an indexed copy of a ledger fragment, which a bookie uses to respond to read requests.

上面是論文中關於 BK 讀寫分離機制實現的介紹，我當時在看完上面的記錄之後，腦海中有以下疑問：

一個寫請求是怎麼處理？什麼時候資料被認為是 ack 了；資料肯定先寫到 Journal Device 中的，那麼資料是如何到 Ledger Device 中的？Ledger Device 中的順序寫跟隨機讀是什麼意思？難道跟 RocketMQ 的儲存結構一樣？Ledger Device 底層是怎麼切分實際的物理檔案的？資料在什麼時候才能可見？在從 Ledger Device 讀資料時，它是透過什麼機制提高查詢速度的？

帶著這些疑問，接下來來分析其實現（圖片來自 Pulsar-Cloud Native Messaging & Streaming）：

BookKeeper 讀寫分離

Journal Device 分析：

處理寫入請求時，如果 Journal 是在專用的磁碟上，由於是順序寫入刷盤，效能會很高；

Ledger Device 的實現：

Bookie 最初的設計方案是每個 Ledger 對應一個物理檔案，但這樣會極大消耗寫效能，所以 Bookie 當前的設計方案是所有 Ledger 都寫一個單獨的檔案中，這個檔案又叫 entry log；寫入時，不但會寫入到 Journal 中還會寫入到快取（memtable）中，定期會做刷盤（刷盤前會做排序，透過 聚合+排序 最佳化讀取效能）；最佳化查詢：Ledger Device 中會維護一個索引結構，儲存在 RocksDB 中，它會將 (LedgerId，EntryId) 對映到(EntryLogId，檔案中的偏移量)。讀寫流程

瞭解完 BK 的一致性模型和讀寫分離機制之後，這裡來看下 BK 的讀寫流程。

Entry 寫入流程

這裡以一個例子來說明，假設 E 是3，Qw 和 Qa 是2，那麼 Entry 寫入如下圖（圖片來自 Durability with BookKeeper）：

BookKeeper Entry 寫入流程

Writer 會先分配對應的 id，然後按照 round-robin 演算法從3個 Bookie 中選取2個 Bookie；Writer 會向兩個 Bookie 傳送寫入請求，因為 Qa 設定為2，只有收到兩個 ack 響應後，才會認為這條 Entry 寫入成功；

如果寫入過程中有一臺 Bookie 掛了怎麼辦？

那麼只能向另外2臺 Bookie 寫入資料；這時候這個 Ledger 會新建一個 Fragment，假設掛的是A，之前 Ensemble 是 A、B、C，現在的是 B、C；這個變化會更新到 zk 中這個 Ledger 的 meta 中。

如果寫入過程中有兩個 Bookie 掛了怎麼辦？

Ensemble 裡面的存活的 Bookies 不能滿足 Qw 的要求；Client 會進行一個 Ensemble Change 操作；Ensemble Change 將從 Bookie Pool 中根據資料放置策略挑選出額外的 Bookie 用來取代那些不存活的 Bookie 。Entry 讀取流程

這裡依然以一個例子做說明，例子是緊接著上面的示例，如下圖所示（圖片來自 Durability with BookKeeper）：

BookKeeper Entry 讀取流程

如何想要讀取 id 為1的那條 Entry 應該怎麼做？

在讀取會選擇最優的 Bookie，有了 Entry 的 id 和 Ledger 的 Ensemble 就可以根據 round-robin 計算出其所在 Bookie 資訊，會選擇向其中一個 Bookie 傳送讀請求。

這種機制會導致，讀取資料時可能需要從多個 Bookie 獲取資料，需要併發訪問多個 Bookie，效能會變差，極端情況會有這個問題。

BK 有一個最佳化策略：讀取時一般是選擇讀一段資料，如果 entries 在同一臺機器上，會從同一個 Bookie 把這批 Entry 全部讀取。

BK 怎麼處理長尾效應的問題（長尾效應指的是某臺機器上某段或者某條資料讀取得比較慢，進而影響了整體的效率）？

Client 可以向任意一個副本讀取相應的 Entry，但為了保證低延時，這裡使用了一個叫 Speculative Read 的機制。讀請求首先發送給第一個副本後，如果在指定的時間內沒有收到 reponse，則傳送讀請求給第二個副本，然後同時等待第一個和第二個副本。誰第一個返回，即讀取成功。透過有效的 Speculative read，可以很大程度減少長尾效應。BookKeeper 容錯機制

這裡來簡單來看下 BookKeeper 容錯機制的實現。

Fencing 機制

Fencing 機制在前面已經簡單介紹過了，它目的主要是為了保證寫的一致性，嚴格保證一個 Ledger 只能被一個 Writer 來寫。

Fencing 怎麼觸發呢？

如果一個 Writer 開啟一個 Ledger，發現這個 Ledger 存在，並且沒有 close，這種情況下，就會觸發 Fencing 策略，並且觸發 Ledger Recovery。Log Recovery 機制

一個 Ledger 正常關閉後，會在其 Metadata 中儲存 the last entry 的資訊，所以正常關閉一個 Ledger 是非常重要的（Ledger 一旦關閉，其就是不可變的，讀取的時候可以從任意一個 Bookie 上讀取，而不需要再取 care 這個 Ledger 的 LAC 資訊），否則可能會出現這樣一種情況：

由於 Writer 掛了（Ledger 未正常關閉），導致部分資料寫入成功，實際上這個條訊息並不滿足 Qw（可能滿足了 Qa），會導致不同 Reader 讀取的結果不一致！如下圖所示：

不同 Reader 讀取不一致的情況

解決方案就是： Log Recovery，正常關閉這個 Ledger，並將 The Last Entry 及狀態更新到 metadata 中。

Log Recovery 怎麼實現呢？通常有兩種方案：

遍歷這個 Ledger 所有 Entry 進行恢復；利用 LAC 機制可以加速 recovery：恢復前，先獲取每個 Ledger 的 LAC 資訊，然後從 LAC 開始恢復；

很明顯，第二種方案是比較合理的恢復速度更快。

Bookie 容錯

當一個 Bookie 故障時：

所有在這個 Bookie 上的 Ledgers 都處於 under-replica 狀態，恢復就是複製 Fragment （Ledger 的組成單位）的過程，以確保每個 Ledger 維護的副本數打到 Qw。

Bk 提供自動和手動兩種方式：兩種方式的複製協議是一樣的；自動恢復是 BK 內部自動觸發，手動過程需要手動干預，這裡重點介紹自動過程：

/underreplicated

Bookie 容錯機制

每個 Bookie 在發現任務時會嘗試鎖定，如果無法鎖定就會執行後面的任務。如果獲得鎖，那麼：

掃描 Ledgers，查詢不屬於當前 Bookie 的 Fragment；對於每個匹配的 Fragment，它將另一個 Bookie 的資料複製到它自己的 Bookie，用新的集合更新 Zookeeper 並將 Fragment 標識為 Fully Replicated。

如果 Ledgers 仍然存在副本數不足的 Fragment，則釋放鎖。如果所有 Fragment 都已經Fully Replicated，則從 /underreplicated 刪除重複複製任務。

BookKeeper介紹

BookKeeper帶有多個讀寫日誌的server，稱為 bookies。每一個bookie是一個BookKeeper的儲存服務，儲存了寫到BookKeeper上的write-ahead日誌，及其資料內容。寫入的log流(稱它為流是因為BookKeeper記錄的是byte[])稱為 ledgers，一個ledger是一個日誌檔案，每個日誌單元叫 ledger entry，也就是bookies是存ledgers的。ledger只支援append操作，而且同時只能有一個單執行緒來寫。ZK充當BookKeeper的元資料儲存服務，在zk中會儲存ledger相關的元資料，包括當前可用的bookies，ledger分佈的位置等。

BookKeeper透過讀寫多個儲存節點達到高可用性，同時為了恢復由於異常造成的多節點資料不一致性，引入了資料一致性演算法。BookKeeper的可用性還體現在只要有足夠多的bookies可用，整個服務就可用。實際上，一份entry的寫入需要確保N份日誌冗餘在N個bookie上寫成功，而我們需要>N個bookie提供服務。在啟動BookKeeper的時候，需要指定一個ensemble值，即bookie可用的最小節點數量，還需要指定一個quorums值，即日誌寫入BookKeeper服務端的冗餘份數。BookKeeper的可擴充套件性體現在可以增加bookie數目，增加bookies可以提升讀寫吞吐量。

下面這張圖，展示了序列化日誌怎樣寫入到Bookie上。

Ledger記錄首先寫入到Journal，然後再寫入到Indexes和Entry Log。寫入到Journal是同步落盤持久化的。寫入到Entry Log的是先快取在Page Cache中，非同步刷盤。一般建議Journal與日誌實體（Entry Log/Ledger Indexes）分開儲存，避免寫入IO競爭。另外，為了寫入的高效能，Journal選擇SSD儲存；日誌實體可以儲存在通用的硬碟裝置上，比如JBOD。

由於不同Ledgers的記錄都是匯聚到一起寫入Entry Log的，即Bookies是順序寫，隨機讀的。為了提升讀取效能，Bookies給每個Ledger維護了一個Ledger Indexes。這個索引對映日誌實體（entries）位置與Ledger的關係（即entry log上哪個位置開始到哪個位置結束的資料屬於哪個Ledger）。

參考：

Durability with BookKeeper;Pulsar-Cloud Native Messaging & Streaming；Apache BookKeeper Documentation;Introduction to Apache BookKeeper;Why Apache BookKeeper? Part 1: consistency, durability, availability;Why Apache Bookkeeper? Part 2；Understanding How Apache Pulsar Works；How to Lose Messages on a RabbitMQ Cluster；Pulsar-Cloud Native Messaging & Streaming – 示說網；Twitter高效能分散式日誌系統架構解析；