解密存儲引擎 bitcask 的設計原理

Riak 是一個專注於分佈式存儲的公司，他們想打造一個新的存儲引擎，該引擎要能實現以下幾個目標：

• 讀寫數據時，延遲要低；

• 高吞吐量；

• 能夠在不降低性能的前提下，處理超過內存容量的數據集；

• 具備從崩潰中快速恢復的能力，並且不丟數據；

• 簡單的備份和恢復策略；

• 代碼結構和數據格式相對簡單且易於理解；

• 即使面臨大數據集，性能依舊不受影響；

• 擁有簡單的授權機制，能夠和 Riak 的其它系統輕鬆集成；

當時 Riak 團隊只能找到滿足部分條件的存儲引擎，而這不是 Riak 團隊想要的，於是他們從頭設計了一個存儲引擎，也就是 Bitcask。

Bitcask 在概念上非常簡單，一個 Bitcask 實例就是一個目錄，並且規定同一時刻只能有一個進程操作該目錄，因此你可以把操作該目錄的進程看作是數據庫服務器。

然後不管目錄中有多少文件，同一時刻只會有一個活躍文件用於服務器寫入。當該文件的大小達到指定的閾值，它會被關閉，然後創建一個新的活躍文件。注意：不管是文件寫滿了還是服務器（進程）退出了，一旦文件被關閉，它就成爲了舊的數據文件（不活躍）。而舊的數據文件是不可變的，不會再執行寫操作。

所以 Bitcask 實例目錄就是一個活躍文件和多箇舊的數據文件的集合。

服務器進程在寫入活動文件時採用了追加模式（Append Only），從而避免了多餘的磁盤尋址。因爲寫操作沒有太多的優化技巧，必須等數據落盤了纔算寫入成功，所以順序寫是最常見、且最有效的優化手段。雖然機械盤的隨機寫性能很差，但順序寫的效果還是不錯的，Kafka 已經證明了這一點，當然除了順序寫 Kafka 還用了很多其它優化手段。

那麼進程在追加寫的時候，寫入到文件的數據格式是怎樣的呢？

總共有如下字段：

• crc：基於其它字段生成的校驗和，用於驗證數據的完整性和準確性；

• tstamp：由 32 位整數表示的時間戳，內部使用，不對外暴露；

• ksz：key size，記錄了 key 的大小；

• value_sz：value size，記錄了 value 的大小；

• key：實際存儲的 key；

• value：實際存儲的 value；

服務器每次寫入，都是向活躍文件追加這樣一條記錄。另外刪除也是一次追加寫入，只不過寫入的是一個特殊的墓碑值（tombstone），用於標記一條記錄的刪除，所以 Bitcask 在刪除數據時屬於邏輯刪除。當下一次 merge 的時候，再執行物理刪除。

凡是採用追加寫模式的存儲引擎，基本都是這個設計，比如 HBase。如果每次刪除都直接採用物理刪除的話，那麼速度不可能快。

因此 Bitcask 數據文件裏面存儲的就是這些記錄的線性序列。

key 和 value 有大有小，但前 4 個字段的大小是固定的，而 ksz 和 value_sz 記錄了 key 和 value 的大小。

以上這些記錄要追加寫入到磁盤，但內存中同樣要維護一個數據結構，在 Bitcask 裏面叫 keydir。那麼 keydir 裏面存的都是什麼呢？

看到這種結構，我們首先想到 keydir 很可能是使用哈希表。沒錯，官方也推薦採用哈希表實現，但你選擇紅黑樹、跳錶也是可以的，如果你需要有序遍歷的話。

解釋一下這些字段的含義：

• key：寫入的 key；

• file_id：因爲數據文件可以有很多，所以要通過 file_id 來標識鍵值對在哪一個文件中；

• value_sz：value 的大小；

• value_pos：偏移量，注意這個偏移量不是 value 的偏移量，而是 value 所在的整條記錄的起始位置的偏移量；

• tstamp：32 位整數表示的時間戳；

當服務器向文件追加一條記錄時，在內存中就會向 keydir 新增一個鍵值對。那麼問題來了，如果 key 已經存在了怎麼辦？

很簡單，key 存在相當於修改，但對於數據文件而言，更新和刪除一樣，依舊是追加一條新的記錄。數據文件在磁盤上，不會直接修改，更新和刪除本質上都是寫入。只不過刪除時，會寫入一個特殊的墓碑值，而更新則是寫入一條新的普通記錄，但記錄中的 key 已存在。

記錄更新之後，還要維護內存中的 keydir。由於 key 已存在，此時相當於對 keydir 進行更新，會保存新數據的位置信息。

儘管舊數據和新數據都存在於磁盤上，但 keydir 裏面只會保存新數據的位置信息，因此任何讀取都會使用最新的可用版本，而舊數據則會在 merge 的時候被清理。

那麼整個讀取過程怎樣的呢？示意圖如下：

當基於 key 獲取 value 時，會先基於 key 在 keydir 中查找記錄的位置信息。通過 file_id 可以定位到數據文件，通過 value_pos 可以定位到記錄在數據文件中的偏移量。由於記錄的前 4 個字段的大小是固定的，key 的大小可以計算出來，所以 value 的偏移量也能確定，再通過 value_sz 即可將具體的 value 讀出來。

基於 key 獲取 value 偏移量是 O(1) 的複雜度，而知道偏移量和大小之後讀取 value 的複雜度也是常量級別，並且只需要一次 IO。

這裏你也許好奇，爲啥記錄中已經保存了 value_sz，在 keydir 中還要再保存一次？

答案是爲了減少磁盤 IO，如果 keydir 中不保存的話，那麼讀 value 之前要先把大小讀出來，這樣會有一次額外的磁盤 IO。由於記錄的前 4 個字段大小固定，key 是已知的，長度也可以計算，那麼 value 的偏移量就是已知的。如果 value 的大小再已知的話，那麼只用一次 IO 就能把 value 讀出來，所以 keydir 中也需要保存一份 value_sz。

所以整個過程還是很好理解的，但我們說了，更新數據和寫入數據是一樣的，都是往磁盤追加一條記錄。雖然內存中 keydir 只會保存新數據的元信息，但磁盤上的數據文件會將舊數據和新數據都保存起來。當然刪除也是同理，舊數據不刪除，追加一條新記錄（特殊的墓碑值）。

因此隨着時間的推移，Bitcask 佔用的空間一定會越來越大，因爲舊數據不會被刪除。所以 Bitcask 會定期執行 merge 操作，將無用數據給清理掉。

至於 merge 的過程也很簡單，就是遍歷所有的舊數據文件（注意是不可變的舊數據文件，活躍文件不會遍歷），然後將所有有效（沒有被刪除）的鍵的最新版本寫入到新的文件中，最後再將舊數據文件刪除。

雖然 merge 會創建一組新的文件，但這些文件依舊是舊數據文件，不會被寫入。此外 merge 是在後臺進行的，不會干擾正常的讀寫操作。

經過 merge 之後，新創建的數據文件裏面保存的都是有效的最新記錄，這裏的 merge data file 還表示舊的數據文件，只不過是 merge 之後的。然後我們看到 merge 之後，它還會爲每個數據文件生成一個 hint 文件，hint 文件裏面保存的是記錄的一些元信息，比如在數據文件中的位置、value 的大小。

Bitcask 進程重新啓動時要在內存中構建 keydir，如果是基於數據文件構建的話會很慢，而通過 hint 文件就可以快速構建了。因爲 hint 文件裏面不保存實際數據，它的容量會遠比數據文件要小。

所以到這裏我們可以看出，Bitcask 是純內存索引，在查找 value 時必須經過內存中的 keydir。因此有人發現了，這不就是將 key 放在內存中，將 value 放在了磁盤中嗎？

是的，Bitcask 將 key 和 value 分開存儲了：

• 在內存中對 key 創建索引；

• 磁盤文件存儲 value 數據；

keydir 保存 key 和 value 在磁盤上的位置信息，查找時要先通過 key 拿到位置信息，然後再基於位置信息拿到 value。所以這種設計就使得 Bitcask 必須滿足以下幾點，才能發揮出威力。

• value 的大小一定要比 key 大很多，否則還不如直接用哈希表。另外 value 也不能太大，因爲寫入是串行的；

• 所有記錄的 key 要能全部載入內存；

• 連續寫入，隨機讀取；

到目前爲止我們就說完了 Bitcask 到底是什麼，它是怎麼設計的，然後再來回顧一下 Riak 團隊給 Bitcask 設定的目標是否全部實現了。

1）讀寫低延遲

顯然是滿足的，因爲讀寫只有一次磁盤 IO。

2）高吞吐量

也是滿足的，因爲寫入數據是順序寫。

3）處理大於 RAM 的數據集且不影響性能

沒問題，因爲 value 都在磁盤上。但要保證 value 的大小要遠超過 key，否則用 Bitcask 沒有多大意義。

4）從崩潰中快速恢復

很多存儲在寫數據之前會先寫日誌，但在 Bitcask 中寫日誌和寫數據是一碼事，所以恢復非常簡單，無需進行重放。

5）簡單的備份和恢復

備份和恢復非常簡單，只需將整個目錄拷貝一份即可，因爲文件是不可變的，並且都在同一目錄下。

6）代碼結構和數據格式易於理解****

代碼結構取決於具體實現，但數據格式確實很好理解。

7）在大數據集下表現良好****

根據官方測試，在處理幾十 GB 的數據時表現很好，但即便數據量增大，表現也不會有明顯變化，只要 keydir 能夠完全適應 RAM。當然這個限制也是微不足道的，因爲即使有數百萬個 key，也用不了 1G 的內存。

當然還是那句話，Bitcask 的適用場景是 value 的大小要遠高於 key。

最後是 Bitcask 的一些 API：

bitcask.open(dir_name, mode) - 以指定模式打開一個新的或現有的 Bitcask 存儲。

bitcask.open(dir_name) - 以只讀模式打開一個新的或現有的 Bitcask 存儲。

bitcask.get(key) - 從 Bitcask 數據存儲中按 key 檢索 value。

bitcask.put(key, value) - 向 Bitcask 數據存儲中添加鍵值對。

bitcask.delete(key) - 從 Bitcask 數據存儲中刪除一個鍵值對。

bitcask.list_keys() - 列出 Bitcask 數據存儲中的所有鍵。

bitcask.fold(func) - 遍歷 Bitcask 數據存儲中的所有鍵值對。

bitcask.merge(dir_name) - 將 Bitcask 數據存儲中的數據文件合併成更緊湊的形式，同時生成 hint 文件，用於進程重啓時加速 keydir 的構建。

bitcask.sync() - 將寫入強制同步到磁盤。

bitcask.close() - 關閉 Bitcask 數據存儲，並將所有待處理的寫入（如果有）同步到磁盤。後續進程重啓時會創建新的活躍文件，並基於 hint 文件構建索引。

以上就是 Bitcask 的原理與相關細節，感興趣的話可以考慮使用自己擅長的語言實現一下。

本文來自於 Riak 官方論文：

• https://riak.com/assets/bitcask-intro.pdf

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