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

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

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

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

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

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

圖片

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

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

圖片

總共有如下字段：

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

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

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

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

圖片

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

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

圖片

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

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

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

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

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

圖片

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

圖片

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

那么整個(gè)讀取過(guò)程怎樣的呢？示意圖如下：

圖片

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

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

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

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

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

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

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

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

圖片

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

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

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

是的，Bitcask 將 key 和 value 分開(kāi)存儲(chǔ)了：

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

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

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

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

1）讀寫低延遲

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

2）高吞吐量

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

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

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

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

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

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

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

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

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

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

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

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

最后是 Bitcask 的一些 API：

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

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

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

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

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

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

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

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

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

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

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

本文來(lái)自于 Riak 官方論文：

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