Riak 是一個專注于分布式存儲的公司，他們想打造一個新的存儲引擎，該引擎要能實(shí)現(xiàn)以下幾個目標(biāo)：

• 讀寫數(shù)據(jù)時，延遲要低；
• 高吞吐量；
• 能夠在不降低性能的前提下，處理超過內(nèi)存容量的數(shù)據(jù)集；
• 具備從崩潰中快速恢復(fù)的能力，并且不丟數(shù)據(jù)；
• 簡單的備份和恢復(fù)策略；
• 代碼結(jié)構(gòu)和數(shù)據(jù)格式相對簡單且易于理解；
• 即使面臨大數(shù)據(jù)集，性能依舊不受影響；
• 擁有簡單的授權(quán)機(jī)制，能夠和 Riak 的其它系統(tǒng)輕松集成；

當(dāng)時 Riak 團(tuán)隊只能找到滿足部分條件的存儲引擎，而這不是 Riak 團(tuán)隊想要的，于是他們從頭設(shè)計了一個存儲引擎，也就是 Bitcask。

Bitcask 在概念上非常簡單，一個 Bitcask 實(shí)例就是一個目錄，并且規(guī)定同一時刻只能有一個進(jìn)程操作該目錄，因此你可以把操作該目錄的進(jìn)程看作是數(shù)據(jù)庫服務(wù)器。

然后不管目錄中有多少文件，同一時刻只會有一個活躍文件用于服務(wù)器寫入。當(dāng)該文件的大小達(dá)到指定的閾值，它會被關(guān)閉，然后創(chuàng)建一個新的活躍文件。注意：不管是文件寫滿了還是服務(wù)器（進(jìn)程）退出了，一旦文件被關(guān)閉，它就成為了舊的數(shù)據(jù)文件（不活躍）。而舊的數(shù)據(jù)文件是不可變的，不會再執(zhí)行寫操作。

所以 Bitcask 實(shí)例目錄就是一個活躍文件和多個舊的數(shù)據(jù)文件的集合。

圖片

服務(wù)器進(jìn)程在寫入活動文件時采用了追加模式（Append Only），從而避免了多余的磁盤尋址。因?yàn)閷懖僮鳑]有太多的優(yōu)化技巧，必須等數(shù)據(jù)落盤了才算寫入成功，所以順序?qū)懯亲畛Ｒ?、且最有效的?yōu)化手段。雖然機(jī)械盤的隨機(jī)寫性能很差，但順序?qū)懙男Ч€是不錯的，Kafka 已經(jīng)證明了這一點(diǎn)，當(dāng)然除了順序?qū)?Kafka 還用了很多其它優(yōu)化手段。

那么進(jìn)程在追加寫的時候，寫入到文件的數(shù)據(jù)格式是怎樣的呢？

圖片

總共有如下字段：

• crc：基于其它字段生成的校驗(yàn)和，用于驗(yàn)證數(shù)據(jù)的完整性和準(zhǔn)確性；
• tstamp：由 32 位整數(shù)表示的時間戳，內(nèi)部使用，不對外暴露；
• ksz：key size，記錄了 key 的大??；
• value_sz：value size，記錄了 value 的大??；
• key：實(shí)際存儲的 key；
• value：實(shí)際存儲的 value；

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

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

因此 Bitcask 數(shù)據(jù)文件里面存儲的就是這些記錄的線性序列。

圖片

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

以上這些記錄要追加寫入到磁盤，但內(nèi)存中同樣要維護(hù)一個數(shù)據(jù)結(jié)構(gòu)，在 Bitcask 里面叫 keydir。那么 keydir 里面存的都是什么呢？

圖片

看到這種結(jié)構(gòu)，我們首先想到 keydir 很可能是使用哈希表。沒錯，官方也推薦采用哈希表實(shí)現(xiàn)，但你選擇紅黑樹、跳表也是可以的，如果你需要有序遍歷的話。

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

• key：寫入的 key；
• file_id：因?yàn)閿?shù)據(jù)文件可以有很多，所以要通過 file_id 來標(biāo)識鍵值對在哪一個文件中；
• value_sz：value 的大??；
• value_pos：偏移量，注意這個偏移量不是 value 的偏移量，而是 value 所在的整條記錄的起始位置的偏移量；
• tstamp：32 位整數(shù)表示的時間戳；

當(dāng)服務(wù)器向文件追加一條記錄時，在內(nèi)存中就會向 keydir 新增一個鍵值對。那么問題來了，如果 key 已經(jīng)存在了怎么辦？

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

圖片

記錄更新之后，還要維護(hù)內(nèi)存中的 keydir。由于 key 已存在，此時相當(dāng)于對 keydir 進(jìn)行更新，會保存新數(shù)據(jù)的位置信息。

圖片

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

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

圖片

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

基于 key 獲取 value 偏移量是 O(1) 的復(fù)雜度，而知道偏移量和大小之后讀取 value 的復(fù)雜度也是常量級別，并且只需要一次 IO。

這里你也許好奇，為啥記錄中已經(jīng)保存了 value_sz，在 keydir 中還要再保存一次？

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

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

因此隨著時間的推移，Bitcask 占用的空間一定會越來越大，因?yàn)榕f數(shù)據(jù)不會被刪除。所以 Bitcask 會定期執(zhí)行 merge 操作，將無用數(shù)據(jù)給清理掉。

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

雖然 merge 會創(chuàng)建一組新的文件，但這些文件依舊是舊數(shù)據(jù)文件，不會被寫入。此外 merge 是在后臺進(jìn)行的，不會干擾正常的讀寫操作。

圖片

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

Bitcask 進(jìn)程重新啟動時要在內(nèi)存中構(gòu)建 keydir，如果是基于數(shù)據(jù)文件構(gòu)建的話會很慢，而通過 hint 文件就可以快速構(gòu)建了。因?yàn)?hint 文件里面不保存實(shí)際數(shù)據(jù)，它的容量會遠(yuǎn)比數(shù)據(jù)文件要小。

所以到這里我們可以看出，Bitcask 是純內(nèi)存索引，在查找 value 時必須經(jīng)過內(nèi)存中的 keydir。因此有人發(fā)現(xiàn)了，這不就是將 key 放在內(nèi)存中，將 value 放在了磁盤中嗎？

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

• 在內(nèi)存中對 key 創(chuàng)建索引；
• 磁盤文件存儲 value 數(shù)據(jù)；

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

• value 的大小一定要比 key 大很多，否則還不如直接用哈希表。另外 value 也不能太大，因?yàn)閷懭胧谴械模?/li>
• 所有記錄的 key 要能全部載入內(nèi)存；
• 連續(xù)寫入，隨機(jī)讀取；

到目前為止我們就說完了 Bitcask 到底是什么，它是怎么設(shè)計的，然后再來回顧一下 Riak 團(tuán)隊給 Bitcask 設(shè)定的目標(biāo)是否全部實(shí)現(xiàn)了。

1）讀寫低延遲

顯然是滿足的，因?yàn)樽x寫只有一次磁盤 IO。

2）高吞吐量

也是滿足的，因?yàn)閷懭霐?shù)據(jù)是順序?qū)憽?/p>

3）處理大于 RAM 的數(shù)據(jù)集且不影響性能

沒問題，因?yàn)?value 都在磁盤上。但要保證 value 的大小要遠(yuǎn)超過 key，否則用 Bitcask 沒有多大意義。

4）從崩潰中快速恢復(fù)

很多存儲在寫數(shù)據(jù)之前會先寫日志，但在 Bitcask 中寫日志和寫數(shù)據(jù)是一碼事，所以恢復(fù)非常簡單，無需進(jìn)行重放。

5）簡單的備份和恢復(fù)

備份和恢復(fù)非常簡單，只需將整個目錄拷貝一份即可，因?yàn)槲募遣豢勺兊?，并且都在同一目錄下?/p>

6）代碼結(jié)構(gòu)和數(shù)據(jù)格式易于理解

代碼結(jié)構(gòu)取決于具體實(shí)現(xiàn)，但數(shù)據(jù)格式確實(shí)很好理解。

7）在大數(shù)據(jù)集下表現(xiàn)良好

根據(jù)官方測試，在處理幾十 GB 的數(shù)據(jù)時表現(xiàn)很好，但即便數(shù)據(jù)量增大，表現(xiàn)也不會有明顯變化，只要 keydir 能夠完全適應(yīng) RAM。當(dāng)然這個限制也是微不足道的，因?yàn)榧词褂袛?shù)百萬個 key，也用不了 1G 的內(nèi)存。

當(dāng)然還是那句話，Bitcask 的適用場景是 value 的大小要遠(yuǎn)高于 key。

最后是 Bitcask 的一些 API：

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

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

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

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

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

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

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

bitcask.merge(dir_name) - 將 Bitcask 數(shù)據(jù)存儲中的數(shù)據(jù)文件合并成更緊湊的形式，同時生成 hint 文件，用于進(jìn)程重啟時加速 keydir 的構(gòu)建。

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

bitcask.close() - 關(guān)閉 Bitcask 數(shù)據(jù)存儲，并將所有待處理的寫入（如果有）同步到磁盤。后續(xù)進(jìn)程重啟時會創(chuàng)建新的活躍文件，并基于 hint 文件構(gòu)建索引。

以上就是 Bitcask 的原理與相關(guān)細(xì)節(jié)，感興趣的話可以考慮使用自己擅長的語言實(shí)現(xiàn)一下。

本文來自于 Riak 官方論文：

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