bitcask 論文詳解

論文地址：https://riak.com/assets/bitcask-intro.pdf

bitcask 最初是由一個做分佈式存儲系統的商業化公司 riak 提出來的。

Riak 有很多產品，其中就包括一個分佈式 KV 存儲系統 Riak KV，他們的產品具有可插拔的存儲引擎，可以獨立於整個系統，單獨開發和測試新的存儲引擎。

基於此，它們想打造一個全新的存儲引擎，在最理想的情況下，滿足下面的這些條件：

• 讀寫低延遲

• 高吞吐，特別是對大量的隨機寫入

• 能夠處理超過內存容量的數據

• 崩潰恢復友好，能夠保證快速恢復，儘量不丟數據

• 簡單的備份和恢復策略

• 相對簡單、易懂的代碼結構和數據存儲格式

• 在大數據量下，性能有保障

• 能夠有自由的授權使用在 Riak 的系統中

現有的存儲引擎，沒有一個能夠很好的滿足這些條件，於是 Riak 團隊重新設計了一個簡單的存儲引擎 bitcask。

一個 bitcask 實例就是系統上的一個目錄，並且限制同一時刻只能有一個進程打開這個目錄。目錄中有多個文件，同一時刻只有一個活躍的文件用於寫入。

當活躍文件寫到滿足一個閾值之後，就會被關閉，成爲舊的數據文件，並且打開一個新的文件用於寫入。

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

當前活躍文件的寫入是追加的（append only），這意味着可以利用順序 IO，不會有多餘的磁盤尋址，最大限度保證了吞吐。

寫入到文件的數據，具有固定的格式，大致有這些字段：

• crc：數據校驗，防止數據被破壞、篡改等

• timestamp：寫入數據的時間戳

• ksz：key size，key 的大小

• value_sz：value size，value 的大小

• key：用戶實際存儲的 key

• value：用戶實際存儲的 value

每次寫入都是追加寫到活躍文件當中，刪除操作實際上也是一次追加寫入，只不過寫入的是一個特殊的墓碑值，用於標記一條記錄的刪除，也就是說不會實際去刪除某條數據。

當下次 merge 的時候，纔會將這種無效的數據清理掉。

所以一個文件中的數據，實際上就是多個相同格式的數據集合的排列：

在追加寫入磁盤文件完成後，然後更新內存中的數據結構，叫做 keydir，實際上就是全部 key 的一個集合，存儲的是 key 到一條磁盤文件數據的位置。

這裏論文中說的是使用一個哈希表來存儲，實際上這裏的選擇比較靈活，選用任意內存中的數據結構都是可以的，可以根據自己的需求來設計。

例如哈希表，可以更高效的獲取數據，但是無法遍歷數據，如果想要數據有序遍歷，可以選擇 B 樹、跳錶等結構。

keydir 一定會存儲一條數據在磁盤中最新的位置，舊的數據仍然存在，等待 merge 的時候被清理。

所以讀取數據就會變得很簡單，首先根據 key 從內存中找到對應的記錄，這個記錄存儲的是數據在磁盤中的位置，然後根據這個位置，找到磁盤上對應的數據文件，以及文件中的具體偏移，這樣就能夠獲取到完整的數據了。

由於舊的數據實際上一直存在於磁盤文件中，因爲我們並沒有將舊的數據刪掉，而是新追加了一條標識其被刪除的記錄。

所以隨着 bitcask 存儲的數據越來越多，舊的數據也可能會越來越多。論文中提出了一個 merge 的過程來清理所有無效的數據。

merge 會遍歷所有不可變的舊數據文件，將所有有效的數據重新寫到新的數據文件中，並且將舊的數據文件刪除掉。

merge 完成後，還會爲每個數據文件生成一個 hint 文件，hint 文件可以看做是全部數據的索引，它和數據文件唯一的區別是，它不會存儲實際的 value。

它的作用是在 bitcask 啓動的時候，直接加載 hint 文件中的數據，快速構建索引，而不用去全部重新加載數據文件，換句話說，就是在啓動的時候加載更少的數據，因爲 hint 文件不存儲 value，它的容量會比數據文件小。

好了，bitcask 總體的設計完成了，我們再回過頭來看看，bitcask 是否滿足了設計之初的那些要點：

• 首先，bitcask 很快，查詢和寫入都很快，因爲讀寫都只有一次磁盤 IO

• 並且寫入數據還是順序 IO，保證了高吞吐

• 內存中不會存儲實際的 value，因此在 value 較大的情況下，能夠處理超過內存容量的數據

• 提交日誌和數據文件實際上就是同一個文件，數據的崩潰恢復能夠得到保證

• 備份和恢復非常簡單，只需要拷貝整個數據目錄即可

• 設計簡潔，數據文件格式易懂、易管理

總體來說，bitcask 基本滿足了設計的要求，是一個簡潔優雅、高效的存儲引擎。

最後再來看看 bitcask 的一些面向用戶的 API 操作接口，這可以幫助我們在實現的時候提供一些參考。

bitcask::Open(Directory Name);
// 打開一個 bitcask 數據庫實例，使用傳入的目錄路徑
// 需要保證進程對該目錄具有可讀可寫權限

bitcask::Get(Key);
// 通過 Key 獲取存儲的 value

bitcask::Put(Key, Value);
// 存儲 key 和 value

bitcask::Delete(Key);
// 刪除一個 key

bitcask::list_keys();
// 獲取全部的 key

bitcask::Fold(Fun);
// 遍歷所有的數據，執行函數 Fun

bitcask::Merge(Directory Name);
// 執行 merge，清理無效數據

bitcask::Sync();
// 刷盤，將所有緩衝區的寫入持久化到磁盤中

bitcask::Close();
// 關閉數據庫

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