Bitcask 是什么?

Bitcask 是一種很有趣的存儲(chǔ)模型的設(shè)計(jì)，這是一種底層格式為日志模樣的 kv 存儲(chǔ)。Bitcask 起源于 Riak 分布式數(shù)據(jù)庫，Bitcask 論文 詳細(xì)介紹了它的由來。

Bitcask 解決哪些的問題?

簡單梳理了下 Bitcask 論文中提到的架構(gòu)設(shè)計(jì)目標(biāo)：

• 讀寫的低時(shí)延;
• 高吞吐，在隨機(jī)寫入的場景;
• 數(shù)據(jù)量級(jí)要比 RAM 大;
• 持久化后的存儲(chǔ)，故障恢復(fù)也要方便;
• 也要方便備份，方便恢復(fù);

符合這些目標(biāo)的會(huì)是哪些場景呢?下面一步步看一下。

Bitcask 架構(gòu)設(shè)計(jì)

1 聊聊整體設(shè)計(jì)

要點(diǎn)一：基于文件系統(tǒng)，而非裸盤

這樣管理空間就方便了，而且可以把一些功能交給內(nèi)核文件系統(tǒng)，比如讀 cache，寫 buffer 等。

要點(diǎn)二：一個(gè)磁盤只有一個(gè)寫入點(diǎn)

換句話說只有一個(gè)可寫的文件。這個(gè)文件叫做 active data file，其他的為只讀文件。active data file 寫到一個(gè)預(yù)定的閾值大小之后，就可以輪轉(zhuǎn)成只讀的文件。

比如，active data file 寫到 10 G 大小就不寫了，切成只讀模式，新建一個(gè)文件來寫。這個(gè)新文件就變成 active data file 。

要點(diǎn)三：active data file 只有 append 寫入

日志文件的標(biāo)配嘛，永遠(yuǎn) append ，這樣才能保證最大程度的順序 IO ，壓榨出機(jī)械硬盤的順序性能。

要點(diǎn)四：刪除也是寫入

這個(gè)其實(shí)承接上面的。也是日志類型文件采用的手段，外面看來的原有對(duì)象的更新其實(shí)是操作日志的記錄，這樣才能最大限度的保持順序 IO 。

要點(diǎn)五：日志式文件本質(zhì)是無序文件，依靠內(nèi)存索引

在 LSM 的架構(gòu)中也提供，日志文件只做 append ，從用戶內(nèi)容來看是無序的(寫入時(shí)間上看是有序的)，所以為了解決讀的問題，必須要靠各種索引結(jié)構(gòu)來解決，在 LSM 里就是通過構(gòu)建內(nèi)存的跳表來解決索引的問題。

在 Bitcask 也是如此，Bitcask 在內(nèi)存中構(gòu)建所有 key 的 hash 表解決這個(gè)問題。

要點(diǎn)六：空間的回收叫做 merge ，其實(shí)就是 compact

Bitcask 內(nèi)部的回收流程叫做 merge ，其實(shí)就是 compact ，原理很簡單：遍歷文件，讀舊寫新，遇到標(biāo)記刪除了的內(nèi)容丟掉即可。

要點(diǎn)七：文件 merge 之后，順帶生成一份 “hint file”

Bitcask 的索引全構(gòu)建在內(nèi)存，換句話說，就是在進(jìn)程啟動(dòng)的時(shí)候要解析所有的底層日志文件。那這時(shí)候底層文件的大小、內(nèi)部對(duì)象數(shù)量的多少就決定了你構(gòu)建的快慢，Bitcask 為了加速構(gòu)建，所以提前把一些元數(shù)據(jù)信息放到尾端。這樣進(jìn)程啟動(dòng)的時(shí)候，就能直接讀 “hint file” 來獲取元數(shù)據(jù)了。

2 看看架構(gòu)圖

Bitcask 是基于文件系統(tǒng)的：

Bitcask 只有一個(gè)可寫的文件。可寫的文件叫做 active file，只讀的叫做非 active：

Bitcask 它的文件是有格式的：

Bitcask 它內(nèi)存的索引大概是這樣的：

3 寫入

寫入的過程很簡單，Bitcask 先寫文件，持久化落盤之后更新內(nèi)存 hash 表。

總結(jié)下寫的流程

寫日志文件，返回 file_id, offset, length 等關(guān)鍵信息;

更新內(nèi)存 hash 表內(nèi)容，把用戶 key 和上面的位置信息關(guān)聯(lián)起來;

思考兩點(diǎn)：

從 IO 次數(shù)來看，磁盤 IO 只需要整體落一次就夠了，不需要單獨(dú)寫索引;

從 IO 模型來看，寫永遠(yuǎn)都是順序 IO，對(duì)機(jī)械盤來講，性能最優(yōu);

4 讀取

讀取的過程很簡單，先在內(nèi)存 hash 表中查找用戶 key ，從而獲取到用戶 value 在日志文件的位置。

file_id: 標(biāo)示在哪個(gè)文件； 
offset: 標(biāo)示在文件的開始位置； 
length: 標(biāo)示值的長短（結(jié)束位置）； 

通過以上三個(gè)信息，就能找到對(duì)應(yīng)的文件取回?cái)?shù)據(jù)了。

總結(jié)下讀的流程：

在內(nèi)存 hash 表中找到 key 的值的文件位置;

下盤讀數(shù)據(jù);

思考兩點(diǎn)：

• 從 IO 次數(shù)來看，這里性能應(yīng)該還是不錯(cuò)的，因?yàn)橹挥凶x數(shù)據(jù)的時(shí)候才需要磁盤 IO ;
• 從 IO 模型來考慮，讀是非常大概率導(dǎo)致隨機(jī) IO 的，但這個(gè)可以依賴于文件系統(tǒng)的緩存，讀過的數(shù)據(jù)將可以加速訪問;

5 回收

Bitcask 回收的流程叫做 merge，其實(shí)很簡單，在日志文件中刪除的標(biāo)記已經(jīng)打上了，內(nèi)存里又有全部索引，那只需要把有效的數(shù)據(jù)讀出來寫到新文件，然后把舊文件一刪，就完成了空間的釋放。

但簡單的東西往往有內(nèi)涵，在前面我們提到，用戶的寫入為了順序化采用了日志的格式，但是 merge 這個(gè)是后端程序有時(shí)候會(huì)和前段的寫入并發(fā)執(zhí)行的，但底下磁盤只有一塊，兩個(gè)都是順序 IO ，但并發(fā)起來就成隨機(jī) IO 了。所以它的精細(xì)之處就在于 merge 的時(shí)機(jī)選擇和速率，這個(gè)也是它的含金量之一。

前面提到，Bitcask 為了索引 key/value 的位置，在內(nèi)存中構(gòu)建了全部的索引關(guān)系。這個(gè)構(gòu)建在初始化的時(shí)候可能會(huì)非常耗時(shí)，因?yàn)橐闅v全部的日志文件。怎么解決這個(gè)問題呢?

干脆直接把這個(gè)索引關(guān)系在合適的時(shí)機(jī)準(zhǔn)備好，進(jìn)程啟動(dòng)加載的時(shí)候，直接讀這部分?jǐn)?shù)據(jù)就行了。

最合適的時(shí)機(jī)不就是 merge 過程嘛。merge 過程無論怎樣都要遍歷了一次文件，生成一份索引關(guān)系歸檔起來就是順手的事情。這份歸檔的索引關(guān)系在 Bitcask 里叫做 “hint file” 。

劃重點(diǎn)：內(nèi)存的索引內(nèi)容和文件的 “hint file” 是對(duì)應(yīng)的。

不一樣的思考

每一種設(shè)計(jì)都有它針對(duì)的場景，通用的東西往往是平庸的。Bitcask 它也是如此，它不適用于所有場景，那它適用哪些場景呢?

Bitcask 主要是持久化日志型文件加上易失的內(nèi)存 hash 表組成。

這里有很多可以思考的關(guān)鍵點(diǎn)：

• 內(nèi)存 hash 表到底有多大?
• Bitcask 它適合存儲(chǔ)多大的數(shù)據(jù)?
• Bitcask 它適合存儲(chǔ)大對(duì)象還是小對(duì)象?

為了回答上面幾個(gè)問題，需要假定一些數(shù)據(jù)結(jié)構(gòu)：

日志結(jié)構(gòu)：

|crc|timestamp|key size|value size|key|value| 

我們假設(shè)前面頭部元數(shù)據(jù)用 4+4+4+4 個(gè)字節(jié)。

hash 表的結(jié)構(gòu)：

key -> |file_id| record size | record offset | timestamp | 

假定是 4+4+4+4 個(gè)字節(jié)(注意，由于這里用 offset 用 4 個(gè)字節(jié)表示，所以日志文件尋址范圍在 0-4G 之間)。

進(jìn)一步假設(shè)用戶 key 的平均大小為 32 字節(jié)。

1 內(nèi)存 hash 表到底有多大?

一個(gè) key/value 在內(nèi)存中最少占用 32+16 字節(jié)，假設(shè) 32 GiB 的內(nèi)存，那么可以存儲(chǔ) 32 GiB/ 48 Byte = 715,827,882 個(gè)索引。

7 億個(gè)健值對(duì)?

貌似還挺多，但也不一定。很多人對(duì)這個(gè)沒什么概念，我們?cè)偻七M(jìn)一個(gè)假設(shè)，假設(shè)用戶 value 平均大小是 8 KiB，那么就能算得的總空間是 ( 715,827,882 * 8 * 1024 ) / ( 1024 * 1024 * 1024 * 1024 ) = 5.3 TiB 。

5.3 TiB ?

實(shí)話實(shí)說，貌似不太大。現(xiàn)在一個(gè)機(jī)械盤 16 TiB 的都很普遍了。

現(xiàn)在反過來推算下，假設(shè)現(xiàn)在有一個(gè) 16 TiB 的盤，用戶 key 平均 32 字節(jié)，value 平均 8 KiB，如果寫滿的話，需要多少內(nèi)存?

算一下，( 16 TiB / (16+32+8KiB) ) * 48 Byte = 95 GiB ，一個(gè) 16 TiB 的盤寫滿的話需要 95 GiB 內(nèi)存來存儲(chǔ)它的索引。這其實(shí)是很大的開銷，因?yàn)橐慌_(tái)機(jī)器可能 64 塊盤。。。。

95 GiB * N 的內(nèi)存消耗能抗的住嗎?

不一定，看你公司的機(jī)型嘍。這都是錢嘛，畢竟內(nèi)存是很貴的。

索引全內(nèi)存構(gòu)建，這個(gè)構(gòu)建時(shí)間你能接受嗎?

不一定，如果說滿載的數(shù)據(jù)構(gòu)建要 1 個(gè)小時(shí)，你還會(huì)接受嗎?當(dāng)然不。

2 Bitcask 它適合存儲(chǔ)多大的數(shù)據(jù)?

那到底 Bitcask 適合存儲(chǔ)多少數(shù)據(jù)呢?

這個(gè)沒有標(biāo)準(zhǔn)答案，還是要看場景分析。就拿我上面舉的例子來講，對(duì)于 60 盤( 單盤 16 TiB )的場景來講，原生的Bitcask 可能就不大適合。

對(duì)于某些動(dòng)輒就說 Bitcask 適合存儲(chǔ)海量小對(duì)象而不加任何前提的說法，奇伢覺得還是不夠嚴(yán)謹(jǐn)。

在 這篇Bitcask 論文[1] 中其實(shí)有這么一段話

The tests mentioned above used a dataset of more than 10×RAM on the system in question, and showed no sign of changed behavior at that point. This is consistent with our expectations given the design of Bitcask.

它這里的基本目標(biāo)好像是 10 倍的 RAM ?

假設(shè)內(nèi)存 32 GiB，那換算下就是 320 GiB 的磁盤空間。這，似乎是內(nèi)存+ SSD 盤更適合 Bitcask 的場景，而不是真正超大容量 HDD 磁盤存儲(chǔ)的場景。

3 Bitcask 它適合存儲(chǔ)大對(duì)象還是小對(duì)象?

這個(gè)就很有意思了，Bitcask 能不能存儲(chǔ)海量數(shù)據(jù)相信通過的計(jì)算讀者已經(jīng)有數(shù)了。但是它適合的是大對(duì)象還是小對(duì)象呢?

這個(gè)其實(shí)還是比較明顯的，Bitcask 無疑是適合小對(duì)象的。理由很簡單，它從設(shè)計(jì)上就規(guī)定了只有一個(gè)寫入點(diǎn)( active file )，也就是說用戶的寫入是串行的，那么如果說用戶的 value 特別大，比如 100 M，那么系統(tǒng)吞吐會(huì)非常差(比如說，這個(gè)時(shí)候來了個(gè) 1K 的對(duì)象，卻只能排隊(duì))。而如果都是些小對(duì)象，那么完全可以聚合很多 key/value ，一次性落盤。這樣既滿足了順序 IO ，又提供了很好的系統(tǒng)的吞吐能力。

所以這里很重要的一點(diǎn)是：對(duì)象的大小。架構(gòu)的設(shè)計(jì)受此影響頗深。

拋出一個(gè)思考的問題：你認(rèn)為什么樣的才是小對(duì)象?

奇伢認(rèn)為，大小不夠一筆 IO 的都可以認(rèn)為是小對(duì)象。比如說某系統(tǒng) IO 落盤以 1M 為單位，那么 1M 以內(nèi)的都可認(rèn)為是小的對(duì)象，這樣就可以很好的做到 IO 的聚合，這也是 Bitcask 非常適合的場景。這樣就能做到：即使底下是串行的寫入也能提供用戶并發(fā)的性能。當(dāng)然這個(gè)并不嚴(yán)謹(jǐn)，實(shí)際情況要具體分析。

項(xiàng)目實(shí)現(xiàn)

Riak 是以 Erlang 編寫的一個(gè)高度可擴(kuò)展的分布式數(shù)據(jù)存儲(chǔ)，是一個(gè)很出名的 nosql 的數(shù)據(jù)庫 , Bitcask 的誕生和它關(guān)系密切 。

總結(jié)

Bitcask 展示了一個(gè)極富思考的存儲(chǔ)架構(gòu)，它簡單有效，并且可以有很多變形;

Bitcask 并不是一個(gè)最快的存儲(chǔ)系統(tǒng)，但是它性能足夠，并且簡單、穩(wěn)定;

估算的能力很重要，結(jié)合自己的場景，估算的數(shù)據(jù)能指導(dǎo)架構(gòu)設(shè)計(jì);

Bitcask 無疑是適合小對(duì)象的。小對(duì)象的定義?奇伢淺顯的認(rèn)為一次 IO 能裝的下的都可以認(rèn)為是小對(duì)象;

Bitcask 雖然只有一個(gè)可寫文件，并且是 append 串行寫，但通過聚合小對(duì)象、批量落盤對(duì)外可以體現(xiàn)出不錯(cuò)的并發(fā)能力哦;

Bitcask 適合小對(duì)象，但是不適合海量對(duì)象。主要是內(nèi)存索引的限制。當(dāng)然也不絕對(duì)的。原生論文只是提供了一個(gè)設(shè)計(jì)思路，我們可以在此基礎(chǔ)上有很多變形設(shè)計(jì);

參考資料

[1]Bitcask 論文: https://riak.com/assets/bitcask-intro.pdf

后記

Bitcask 在設(shè)計(jì)上和 LSM 有異曲同工之處，都是通過日志的形式來承接寫，提供最優(yōu)的寫的性能。雖然功能不如 LSM 豐富，但它簡單穩(wěn)定，非常值得學(xué)習(xí)。