存儲架構｜Bitcask 引擎的設計，秒！
Bitcask 是什么?
Bitcask 是一種很有趣的存儲模型的設計，這是一種底層格式為日志模樣的 kv 存儲。Bitcask 起源于 Riak 分布式數據庫，Bitcask 論文 詳細介紹了它的由來。
Bitcask 解決哪些的問題?
簡單梳理了下 Bitcask 論文中提到的架構設計目標：
- 讀寫的低時延;
- 高吞吐，在隨機寫入的場景;
- 數據量級要比 RAM 大;
- 持久化后的存儲，故障恢復也要方便;
- 也要方便備份，方便恢復;
符合這些目標的會是哪些場景呢?下面一步步看一下。
Bitcask 架構設計
1 聊聊整體設計
要點一：基于文件系統，而非裸盤
這樣管理空間就方便了，而且可以把一些功能交給內核文件系統，比如讀 cache，寫 buffer 等。
要點二：一個磁盤只有一個寫入點
換句話說只有一個可寫的文件。這個文件叫做 active data file，其他的為只讀文件。active data file 寫到一個預定的閾值大小之后，就可以輪轉成只讀的文件。
比如，active data file 寫到 10 G 大小就不寫了，切成只讀模式，新建一個文件來寫。這個新文件就變成 active data file 。
要點三：active data file 只有 append 寫入
日志文件的標配嘛，永遠 append ，這樣才能保證最大程度的順序 IO ，壓榨出機械硬盤的順序性能。
要點四：刪除也是寫入
這個其實承接上面的。也是日志類型文件采用的手段，外面看來的原有對象的更新其實是操作日志的記錄，這樣才能最大限度的保持順序 IO 。
要點五：日志式文件本質是無序文件，依靠內存索引
在 LSM 的架構中也提供，日志文件只做 append ，從用戶內容來看是無序的(寫入時間上看是有序的)，所以為了解決讀的問題，必須要靠各種索引結構來解決，在 LSM 里就是通過構建內存的跳表來解決索引的問題。
在 Bitcask 也是如此，Bitcask 在內存中構建所有 key 的 hash 表解決這個問題。
要點六：空間的回收叫做 merge ，其實就是 compact
Bitcask 內部的回收流程叫做 merge ，其實就是 compact ，原理很簡單：遍歷文件，讀舊寫新，遇到標記刪除了的內容丟掉即可。
要點七：文件 merge 之后，順帶生成一份 “hint file”
Bitcask 的索引全構建在內存，換句話說，就是在進程啟動的時候要解析所有的底層日志文件。那這時候底層文件的大小、內部對象數量的多少就決定了你構建的快慢，Bitcask 為了加速構建，所以提前把一些元數據信息放到尾端。這樣進程啟動的時候，就能直接讀 “hint file” 來獲取元數據了。
2 看看架構圖
Bitcask 是基于文件系統的：
Bitcask 只有一個可寫的文件。可寫的文件叫做 active file，只讀的叫做非 active：
Bitcask 它的文件是有格式的：
Bitcask 它內存的索引大概是這樣的：
3 寫入
寫入的過程很簡單，Bitcask 先寫文件，持久化落盤之后更新內存 hash 表。
總結下寫的流程
寫日志文件，返回 file_id, offset, length 等關鍵信息;
更新內存 hash 表內容，把用戶 key 和上面的位置信息關聯起來;
思考兩點：
從 IO 次數來看，磁盤 IO 只需要整體落一次就夠了，不需要單獨寫索引;
從 IO 模型來看，寫永遠都是順序 IO，對機械盤來講，性能最優;
4 讀取
讀取的過程很簡單，先在內存 hash 表中查找用戶 key ，從而獲取到用戶 value 在日志文件的位置。
- file_id: 標示在哪個文件；
- offset: 標示在文件的開始位置；
- length: 標示值的長短（結束位置）；
通過以上三個信息，就能找到對應的文件取回數據了。
總結下讀的流程：
在內存 hash 表中找到 key 的值的文件位置;
下盤讀數據;
思考兩點：
- 從 IO 次數來看，這里性能應該還是不錯的，因為只有讀數據的時候才需要磁盤 IO ;
- 從 IO 模型來考慮，讀是非常大概率導致隨機 IO 的，但這個可以依賴于文件系統的緩存，讀過的數據將可以加速訪問;
5 回收
Bitcask 回收的流程叫做 merge，其實很簡單，在日志文件中刪除的標記已經打上了，內存里又有全部索引，那只需要把有效的數據讀出來寫到新文件，然后把舊文件一刪，就完成了空間的釋放。
但簡單的東西往往有內涵，在前面我們提到，用戶的寫入為了順序化采用了日志的格式，但是 merge 這個是后端程序有時候會和前段的寫入并發執行的，但底下磁盤只有一塊，兩個都是順序 IO ，但并發起來就成隨機 IO 了。所以它的精細之處就在于 merge 的時機選擇和速率，這個也是它的含金量之一。
前面提到，Bitcask 為了索引 key/value 的位置，在內存中構建了全部的索引關系。這個構建在初始化的時候可能會非常耗時，因為要遍歷全部的日志文件。怎么解決這個問題呢?
干脆直接把這個索引關系在合適的時機準備好，進程啟動加載的時候，直接讀這部分數據就行了。
最合適的時機不就是 merge 過程嘛。merge 過程無論怎樣都要遍歷了一次文件，生成一份索引關系歸檔起來就是順手的事情。這份歸檔的索引關系在 Bitcask 里叫做 “hint file” 。
劃重點：內存的索引內容和文件的 “hint file” 是對應的。
不一樣的思考
每一種設計都有它針對的場景，通用的東西往往是平庸的。Bitcask 它也是如此，它不適用于所有場景，那它適用哪些場景呢?
Bitcask 主要是持久化日志型文件加上易失的內存 hash 表組成。
這里有很多可以思考的關鍵點：
- 內存 hash 表到底有多大?
- Bitcask 它適合存儲多大的數據?
- Bitcask 它適合存儲大對象還是小對象?
為了回答上面幾個問題，需要假定一些數據結構：
日志結構：
- |crc|timestamp|key size|value size|key|value|
我們假設前面頭部元數據用 4+4+4+4 個字節。
hash 表的結構：
- key -> |file_id| record size | record offset | timestamp |
假定是 4+4+4+4 個字節(注意，由于這里用 offset 用 4 個字節表示，所以日志文件尋址范圍在 0-4G 之間)。
進一步假設用戶 key 的平均大小為 32 字節。
1 內存 hash 表到底有多大?
一個 key/value 在內存中最少占用 32+16 字節，假設 32 GiB 的內存，那么可以存儲 32 GiB/ 48 Byte = 715,827,882 個索引。
7 億個健值對?
貌似還挺多，但也不一定。很多人對這個沒什么概念，我們再推進一個假設，假設用戶 value 平均大小是 8 KiB，那么就能算得的總空間是 ( 715,827,882 * 8 * 1024 ) / ( 1024 * 1024 * 1024 * 1024 ) = 5.3 TiB 。
5.3 TiB ?
實話實說，貌似不太大。現在一個機械盤 16 TiB 的都很普遍了。
現在反過來推算下，假設現在有一個 16 TiB 的盤，用戶 key 平均 32 字節，value 平均 8 KiB，如果寫滿的話，需要多少內存?
算一下，( 16 TiB / (16+32+8KiB) ) * 48 Byte = 95 GiB ，一個 16 TiB 的盤寫滿的話需要 95 GiB 內存來存儲它的索引。這其實是很大的開銷，因為一臺機器可能 64 塊盤。。。。
95 GiB * N 的內存消耗能抗的住嗎?
不一定，看你公司的機型嘍。這都是錢嘛，畢竟內存是很貴的。
索引全內存構建，這個構建時間你能接受嗎?
不一定，如果說滿載的數據構建要 1 個小時，你還會接受嗎?當然不。
2 Bitcask 它適合存儲多大的數據?
那到底 Bitcask 適合存儲多少數據呢?
這個沒有標準答案，還是要看場景分析。就拿我上面舉的例子來講，對于 60 盤( 單盤 16 TiB )的場景來講，原生的Bitcask 可能就不大適合。
對于某些動輒就說 Bitcask 適合存儲海量小對象而不加任何前提的說法，奇伢覺得還是不夠嚴謹。
在 這篇Bitcask 論文[1] 中其實有這么一段話
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.
它這里的基本目標好像是 10 倍的 RAM ?
假設內存 32 GiB，那換算下就是 320 GiB 的磁盤空間。這，似乎是內存+ SSD 盤更適合 Bitcask 的場景，而不是真正超大容量 HDD 磁盤存儲的場景。
3 Bitcask 它適合存儲大對象還是小對象?
這個就很有意思了，Bitcask 能不能存儲海量數據相信通過的計算讀者已經有數了。但是它適合的是大對象還是小對象呢?
這個其實還是比較明顯的，Bitcask 無疑是適合小對象的。理由很簡單，它從設計上就規定了只有一個寫入點( active file )，也就是說用戶的寫入是串行的，那么如果說用戶的 value 特別大，比如 100 M，那么系統吞吐會非常差(比如說，這個時候來了個 1K 的對象，卻只能排隊)。而如果都是些小對象，那么完全可以聚合很多 key/value ，一次性落盤。這樣既滿足了順序 IO ，又提供了很好的系統的吞吐能力。
所以這里很重要的一點是：對象的大小。架構的設計受此影響頗深。
拋出一個思考的問題：你認為什么樣的才是小對象?
奇伢認為，大小不夠一筆 IO 的都可以認為是小對象。比如說某系統 IO 落盤以 1M 為單位，那么 1M 以內的都可認為是小的對象，這樣就可以很好的做到 IO 的聚合，這也是 Bitcask 非常適合的場景。這樣就能做到：即使底下是串行的寫入也能提供用戶并發的性能。當然這個并不嚴謹，實際情況要具體分析。
項目實現
Riak 是以 Erlang 編寫的一個高度可擴展的分布式數據存儲，是一個很出名的 nosql 的數據庫 , Bitcask 的誕生和它關系密切 。
總結
Bitcask 展示了一個極富思考的存儲架構，它簡單有效，并且可以有很多變形;
Bitcask 并不是一個最快的存儲系統，但是它性能足夠，并且簡單、穩定;
估算的能力很重要，結合自己的場景，估算的數據能指導架構設計;
Bitcask 無疑是適合小對象的。小對象的定義?奇伢淺顯的認為一次 IO 能裝的下的都可以認為是小對象;
Bitcask 雖然只有一個可寫文件，并且是 append 串行寫，但通過聚合小對象、批量落盤對外可以體現出不錯的并發能力哦;
Bitcask 適合小對象，但是不適合海量對象。主要是內存索引的限制。當然也不絕對的。原生論文只是提供了一個設計思路，我們可以在此基礎上有很多變形設計;
參考資料
[1]Bitcask 論文: https://riak.com/assets/bitcask-intro.pdf
后記
Bitcask 在設計上和 LSM 有異曲同工之處，都是通過日志的形式來承接寫，提供最優的寫的性能。雖然功能不如 LSM 豐富，但它簡單穩定，非常值得學習。
