[TOC]
本篇文章主要聚焦于 BookKeeper 內(nèi)核的實現(xiàn)機(jī)制上，會從 BookKeeper 的基本概念、架構(gòu)、讀寫一致性實現(xiàn)、讀寫分離實現(xiàn)、容錯機(jī)制等方面來講述，因為我并沒有看過 BookKeeper 的源碼，所以這里的講述主要還是從原理、方案實現(xiàn)上來介紹，具體如何從解決方案落地到具體的代碼實現(xiàn)，有興趣的可以去看下 BookKeeper 的源碼實現(xiàn)。

BookKeeper 基礎(chǔ)

正如 Apache BookKeeper 官網(wǎng)介紹的一樣：A scalable, fault-tolerant, and low-latency storage service optimized for real-time workloads。BookKeeper 的定位是一個可用于實時場景下的高擴(kuò)展性、強(qiáng)容錯、低延遲的存儲服務(wù)。Pulsar-Cloud Native Messaging & Streaming - 示說網(wǎng) 中也做了一個簡單總結(jié)：

1. 低延遲多副本復(fù)制：Quorum Parallel Replication；
2. 持久化：所有操作保證在刷盤后才 ack；
3. 強(qiáng)一致性：可重復(fù)讀的一致性（Repeatable Read Consistency）;
4. 讀寫高可用；
5. 讀寫分離。

BookKeeper 基本概念

如下圖所示，一個 Log/Stream/Topic 可以由下面的部分組成（圖片來自 Pulsar-Cloud Native Messaging & Streaming）。

image.png

1. Ledger：它是 BK 的一個基本存儲單元（本質(zhì)上還是一種抽象），BK Client 的讀寫操作也都是以 Ledger 為粒度的；
2. Fragment：BK 的最小分布單元（實際上也是物理上的最小存儲單元），也是 Ledger 的組成單位，默認(rèn)情況下一個 Ledger 會對應(yīng)的一個 Fragment（一個 Ledger 也可能由多個 Fragment 組成）；
3. Entry：每條日志都是一個 Entry，它代表一個 record，每條 record 都會有一個對應(yīng)的 entry id；

關(guān)于 Fragment，它是 Ledger 的物理組成單元，也是最小的物理存儲單元，在以下兩種情況下會創(chuàng)建新的 Fragment：

1. 當(dāng)創(chuàng)建新的 Ledger 時；
2. 當(dāng)前 Fragment 使用的 Bookies 發(fā)生寫入錯誤或超時，系統(tǒng)會在剩下的 Bookie 中新建 Fragment，但這時并不會新建 Ledger，因為 Ledger 的創(chuàng)建和關(guān)閉是由 Client 控制的，這里只是新建了 Fragment（需要注意的是：這兩個 Fragment 對應(yīng)的 Ensemble Bookie 已經(jīng)不一樣了，但它們都屬于一個 Ledger，這里并不一定是一個 Ensemble Change 操作）。

BookKeeper 架構(gòu)設(shè)計

Apache BookKeeper 的架構(gòu)如下圖所示，它主要由三個組件構(gòu)成：客戶端 (client)、數(shù)據(jù)存儲節(jié)點(diǎn) (Bookie) 和元數(shù)據(jù)存儲 Service Discovery（ZooKeeper），Bookies 在啟動的時候向 ZooKeeper 注冊節(jié)點(diǎn)，Client 通過 ZooKeeper 發(fā)現(xiàn)可用的 Bookie。

image.png

這里，我們可以看到 BookKeeper 架構(gòu)屬于典型的 slave-slave 架構(gòu)，zk 存儲其集群的 meta 信息（zk 雖是單點(diǎn)，但 zk 目前的高可用還是很有保障的），這種模式的好處顯而易見，server 端變得非常簡單，所有節(jié)點(diǎn)都是一樣的角色和處理邏輯，能夠這樣設(shè)計的主要原因是其副本沒有 leader 和 follower 之分，這是它與一些常見 mq（如：kafka、RocketMQ）系統(tǒng)的典型區(qū)別，每種設(shè)計都有其 trade-off，BeekKeeper 從設(shè)計之初就是為了高可靠而設(shè)計。

BookKeeper 存儲層實現(xiàn)

Apache BookKeeper 是一個高可靠的分布式存儲系統(tǒng)，存儲層的實現(xiàn)是其核心，對一個存儲系統(tǒng)來說，關(guān)鍵的幾點(diǎn)實現(xiàn)，無非是：一致性如何保證、IO 如何優(yōu)化、高可用如何實現(xiàn)等，這小節(jié)就讓我們揭開其神秘面紗。

新建 Ledger

Ledger 是 BookKeeper 的基本存儲抽象單元，這里先看下一個 Ledger 是如何創(chuàng)建的，這里會介紹一些關(guān)于 Ledger 存儲層的一些重要概念（圖片來自 Pulsar-Cloud Native Messaging & Streaming）。

image.png

Ledger 是一組追加有序的記錄，它是由 Client 創(chuàng)建的，然后由其進(jìn)行追加寫操作。每個 Ledger 在創(chuàng)建時會被賦予全局唯一的 ID，其他的 Client 可以根據(jù) Ledger ID，對其進(jìn)行讀取操作。創(chuàng)建 Ledger 及 Entry 寫入的相關(guān)過程如下：

1. Client 在創(chuàng)建 Ledger 的時候，從 Bookie Pool 里面按照指定的數(shù)據(jù)放置策略挑選出一定數(shù)量的 Bookie，構(gòu)成一個 Ensemble；
2. 每條 Entry 會被并行地發(fā)送給 Ensemble 里面的部分 Bookies（每條 Entry 發(fā)送多少個 Bookie 是由 Write Quorum size 設(shè)置、具體發(fā)送哪些 Bookie 是由 Round Robin 算法來計算），并且所有 Entry 的發(fā)送以流水線的方式進(jìn)行，也就是意味著發(fā)送第 N + 1 條記錄的寫請求不需要等待發(fā)送第 N 條記錄的寫請求返回；
3. 對于每條 Entry 的寫操作而言，當(dāng)它收到 Ensemble 里面大多數(shù) Bookie 的確認(rèn)后（這個由 Ack Quorum size 來設(shè)置），Client 認(rèn)為這條記錄已經(jīng)持久化到這個 Ensemble 中，并且有大多數(shù)副本。

image.png

這里引入了三個重要的概念，它們也是 BookKeeper 一致性的基礎(chǔ)：

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

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

1. Ensemble：可以控制一個 Ledger 的讀寫帶寬；
2. Write Quorum：控制一條記錄的復(fù)本數(shù)；
3. Ack Quorum：寫每條記錄需要等待的 Ack 數(shù) ，控制時延；
4. 增加 Ensemble，可以增加讀寫帶寬（增加了可寫的機(jī)器數(shù)）；
5. 減少 Ack Quorum，可以減長尾時延。

一致性

對于分布式存儲系統(tǒng)，為了高可用，多副本是其通用的解決方案，但也帶來了一致性的問題，這里就看下 Apache BookKeeper 是如何解決其帶來的一致性問題的。

在介紹其讀寫一致性之前，先看下 BK 的一致性模型（圖片來自 Twitter高性能分布式日志系統(tǒng)架構(gòu)解析）。

image.png

對于 Write 操作而言，writer 不斷添加記錄，每條記錄會被 writer 賦予一個嚴(yán)格遞增的 id，所有的追加操作都是異步的，也就是說：第二條記錄不用等待第一條記錄返回結(jié)果。所有寫成功的操作都會按照 id 遞增順序返回 ack 給 writer。（圖片來自 Twitter高性能分布式日志系統(tǒng)架構(gòu)解析）。

image.png

伴隨著寫成功的 ack，writer 不斷地更新一個指針叫做 Last-Add-Confirm（LAC），所有 Entry id 小于等于 LAC 的記錄保證持久化并復(fù)制到大多數(shù)副本上，而 LAC 與 LAP（Last-Add-Pushed）之間的記錄就是已經(jīng)發(fā)送到 Bookie 上但還未被 ack 的數(shù)據(jù)。

讀的一致性

所有的 Reader 都可以安全讀取 Entry ID 小于或者等于 LAC 的記錄，從而保證 reader 不會讀取未確認(rèn)的數(shù)據(jù)，從而保證了 reader 之間的一致性（圖片來自 Twitter高性能分布式日志系統(tǒng)架構(gòu)解析）。

image.png

寫的一致性

從上面的介紹中，也可以看出，對于 BK 的多個副本，其并沒有 leader 和 follower 之分，因此，BK 并不會進(jìn)行相應(yīng)的選主（leader election）操作，并且限制每個 Ledger 只能被一個 Writer 寫，BK 通過 Fencing 機(jī)制來防止出現(xiàn)多個 Writer 的狀態(tài)，從而保證寫的一致性。

讀寫分離

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

image.png

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

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

上面是論文中關(guān)于 BK 讀寫分離機(jī)制實現(xiàn)的介紹，我當(dāng)時在看完上面的記錄之后，腦海中有以下疑問：

1. 一個寫請求是怎么處理？什么時候數(shù)據(jù)被認(rèn)為是 ack 了；
2. 數(shù)據(jù)肯定先寫到 Journal Device 中的，那么數(shù)據(jù)是如何到 Ledger Device 中的？
3. Ledger Device 中的順序?qū)懜S機(jī)讀是什么意思？難道跟 RocketMQ 的存儲結(jié)構(gòu)一樣？
4. Ledger Device 底層是怎么切分實際的物理文件的？
5. 數(shù)據(jù)在什么時候才能可見？
6. 在從 Ledger Device 讀數(shù)據(jù)時，它是通過什么機(jī)制提高查詢速度的？

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

image.png

Journal Device 分析：

• 處理寫入請求時，如果 Journal 是在專用的磁盤上，由于是順序?qū)懭胨⒈P，性能會很高；

Ledger Device 的實現(xiàn)：

• Bookie 最初的設(shè)計方案是每個 Ledger 對應(yīng)一個物理文件，但這樣會極大消耗寫性能，所以 Bookie 當(dāng)前的設(shè)計方案是所有 Ledger 都寫一個單獨(dú)的文件中，這個文件又叫 entry log；
• 寫入時，不但會寫入到 Journal 中還會寫入到緩存（memtable）中，定期會做刷盤（刷盤前會做排序，通過 聚合+排序 優(yōu)化讀取性能）；
• 優(yōu)化查找：Ledger Device 中會維護(hù)一個索引結(jié)構(gòu)，存儲在 RocksDB 中，它會將 (LedgerId，EntryId) 映射到(EntryLogId，文件中的偏移量)。

讀寫流程

了解完 BK 的一致性模型和讀寫分離機(jī)制之后，這里來看下 BK 的讀寫流程。

Entry 寫入流程

了解完 BK 的一致性模型和讀寫分離機(jī)制之后，這里來看下 BK 的讀寫流程。

Entry 寫入流程
這里以一個例子來說明，假設(shè) E 是3，Qw 和 Qa 是2，那么 Entry 寫入如下圖（圖片來自 Durability with BookKeeper）：

image.png

• Writer 會先分配對應(yīng)的 id，然后按照 round-robin 算法從3個 Bookie 中選取2個 Bookie；
• Writer 會向兩個 Bookie 發(fā)送寫入請求，因為 Qa 設(shè)置為2，只有收到兩個 ack 響應(yīng)后，才會認(rèn)為這條 Entry 寫入成功；

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

1. 那么只能向另外2臺 Bookie 寫入數(shù)據(jù)；
2. 這時候這個 Ledger 會新建一個 Fragment，假設(shè)掛的是A，之前 Ensemble 是 A、B、C，現(xiàn)在的是 B、C；
3. 這個變化會更新到 zk 中這個 Ledger 的 meta 中。

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

1. Ensemble 里面的存活的 Bookies 不能滿足 Qw 的要求；
2. Client 會進(jìn)行一個 Ensemble Change 操作；
3. Ensemble Change 將從 Bookie Pool 中根據(jù)數(shù)據(jù)放置策略挑選出額外的 Bookie 用來取代那些不存活的 Bookie 。

Entry 讀取流程

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

image.png

如何想要讀取 id 為1的那條 Entry 應(yīng)該怎么做？

• 在讀取會選擇最優(yōu)的 Bookie，有了 Entry 的 id 和 Ledger 的 Ensemble 就可以根據(jù) round-robin 計算出其所在 Bookie 信息，會選擇向其中一個 Bookie 發(fā)送讀請求。

這種機(jī)制會導(dǎo)致，讀取數(shù)據(jù)時可能需要從多個 Bookie 獲取數(shù)據(jù)，需要并發(fā)訪問多個 Bookie，性能會變差，極端情況會有這個問題。

• BK 有一個優(yōu)化策略：讀取時一般是選擇讀一段數(shù)據(jù)，如果 entries 在同一臺機(jī)器上，會從同一個 Bookie 把這批 Entry 全部讀取。

BK 怎么處理長尾效應(yīng)的問題（長尾效應(yīng)指的是某臺機(jī)器上某段或者某條數(shù)據(jù)讀取得比較慢，進(jìn)而影響了整體的效率）？

• Client 可以向任意一個副本讀取相應(yīng)的 Entry，但為了保證低延時，這里使用了一個叫 Speculative Read 的機(jī)制。讀請求首先發(fā)送給第一個副本后，如果在指定的時間內(nèi)沒有收到 reponse，則發(fā)送讀請求給第二個副本，然后同時等待第一個和第二個副本。誰第一個返回，即讀取成功。通過有效的 Speculative read，可以很大程度減少長尾效應(yīng)。

BookKeeper 容錯機(jī)制

Fencing 機(jī)制

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

Fencing 怎么觸發(fā)呢？

• 如果一個 Writer 打開一個 Ledger，發(fā)現(xiàn)這個 Ledger 存在，并且沒有 close，這種情況下，就會觸發(fā) Fencing 策略，并且觸發(fā) Ledger Recovery。

Log Recovery 機(jī)制

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

由于 Writer 掛了（Ledger 未正常關(guān)閉），導(dǎo)致部分?jǐn)?shù)據(jù)寫入成功，實際上這個條消息并不滿足 Qw（可能滿足了 Qa），會導(dǎo)致不同 Reader 讀取的結(jié)果不一致！如下圖所示：

image.png

解決方案就是： Log Recovery，正常關(guān)閉這個 Ledger，并將 The Last Entry 及狀態(tài)更新到 metadata 中。

Log Recovery 怎么實現(xiàn)呢？通常有兩種方案：

1. 遍歷這個 Ledger 所有 Entry 進(jìn)行恢復(fù)；
2. 利用 LAC 機(jī)制可以加速 recovery：恢復(fù)前，先獲取每個 Ledger 的 LAC 信息，然后從 LAC 開始恢復(fù)；

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

Bookie 容錯

當(dāng)一個 Bookie 故障時：

• 所有在這個 Bookie 上的 Ledgers 都處于 under-replica 狀態(tài)，恢復(fù)就是復(fù)制 Fragment （Ledger 的組成單位）的過程，以確保每個 Ledger 維護(hù)的副本數(shù)打到 Qw。

Bk 提供自動和手動兩種方式：兩種方式的復(fù)制協(xié)議是一樣的；自動恢復(fù)是 BK 內(nèi)部自動觸發(fā)，手動過程需要手動干預(yù)，這里重點(diǎn)介紹自動過程：

• 自動恢復(fù)是在 Bookie 上運(yùn)行 AutoRecoveryMain 線程來實現(xiàn)，它會首先通過 zk 選舉一個 Auditor；
• Auditor 的作用是檢查不可用的 Bookie，然后做下面的操作：讀取 zk 上完整的 Ledgers 信息，找到失敗的 Ledgers（副本不滿足條件的）；然后在 zk 的 /underreplicated znode 節(jié)點(diǎn)創(chuàng)建重新復(fù)制任務(wù)；

• AutoRecoveryMain 還有 Replicator Worker 線程會復(fù)制相應(yīng)的 Fragment 到自己的 Ledger 上，如果復(fù)制后滿足 Fully Replicated，那么就從 zk 的節(jié)點(diǎn)中刪除這個任務(wù)；

  
  
  image.png

每個 Bookie 在發(fā)現(xiàn)任務(wù)時會嘗試鎖定，如果無法鎖定就會執(zhí)行后面的任務(wù)。如果獲得鎖，那么：

1. 掃描 Ledgers，查找不屬于當(dāng)前 Bookie 的 Fragment；
2. 對于每個匹配的 Fragment，它將另一個 Bookie 的數(shù)據(jù)復(fù)制到它自己的 Bookie，用新的集合更新 Zookeeper 并將 Fragment 標(biāo)識為 Fully Replicated。

如果 Ledgers 仍然存在副本數(shù)不足的 Fragment，則釋放鎖。如果所有 Fragment 都已經(jīng)Fully Replicated，則從 /underreplicated 刪除重復(fù)復(fù)制任務(wù)。

寫一致性：Fencing機(jī)制

簡單來說，F(xiàn)encing機(jī)制用于防止有多個writer（pulsar中即為broker）同時寫同一個topic/partition

什么時候會出現(xiàn)多個writer同時寫同一個topic呢？在pulsar中，當(dāng)zk檢測到有一個broker1掛掉了，那么會把該broker1擁有的topic所有權(quán)轉(zhuǎn)移到另一個broker2。如果broker1實際上沒掛掉（類似出現(xiàn)腦裂的情況），那么會出現(xiàn)broker1、broker2同時寫同一個topic，對于broker1寫入完成的數(shù)據(jù)，由于topic已經(jīng)給broker2接管了，在broker2看來并不知道broker1寫入了數(shù)據(jù)，就會出現(xiàn)寫入數(shù)據(jù)的不一致。

Broker Recovery：Fencing

Broker crash，或 Broker 與 ZK 出現(xiàn)網(wǎng)絡(luò)分區(qū)導(dǎo)致腦裂，需進(jìn)行 partition ownership 轉(zhuǎn)移。

• Broker1 心跳超時后，ZK 將 topic partition 的 ownership 轉(zhuǎn)移到 Broker2
• Broker2 向 Ensemble 發(fā)起 Fencing ledger_X 請求，Bookies 紛紛將 ledger_X 置為 Fencing 不可寫狀態(tài)。
• Broker1 寫數(shù)據(jù)失敗收到 FenceException，說明該 partition 已被 Broker 接管，主動放棄 ownership
• Client 收到異常后與 Broker1 斷開連接，進(jìn)行 Topic Lookup 與 Broker2 建立長連接。
• 同時，Broker2 對 ledger_X LAC1 之后的 entry log 依次逐一進(jìn)行 Forwarding Recovery（若 unknow 狀態(tài)的 entry 副本數(shù)實際上已達(dá)到 WQ，則認(rèn)為該 entry 寫成功，LAC1 自增為 LAC2）

• Broker2 更新 ledger_X 的 metadata，將其置為 CLOSE 狀態(tài)，再創(chuàng)建新 ledger，繼續(xù)處理 Client 的寫請求。

  
  
  image.png