存儲架構 Bitcask 引擎的設計

Bitcask 是什麼?

Bitcask 是一種很有趣的存儲模型的設計，這是一種底層格式爲日誌模樣的 kv 存儲。Bitcask 起源於 Riak 分佈式數據庫，Bitcask 論文 詳細介紹了它的由來。

Bitcask 解決哪些的問題？

簡單梳理了下 Bitcask 論文中提到的架構設計目標：

  1. 讀寫的低時延；

  2. 高吞吐，在隨機寫入的場景；

  3. 數據量級要比 RAM 大；

  4. 持久化後的存儲，故障恢復也要方便；

  5. 也要方便備份，方便恢復；

符合這些目標的會是哪些場景呢？下面一步步看一下。

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 表。

總結下寫的流程

  1. 寫日誌文件，返回 file_id, offset, length 等關鍵信息；

  2. 更新內存 hash 表內容，把用戶 key 和上面的位置信息關聯起來；

思考兩點：

  1. 從 IO 次數來看，磁盤 IO 只需要整體落一次就夠了，不需要單獨寫索引；

  2. 從 IO 模型來看，寫永遠都是順序 IO，對機械盤來講，性能最優；

 4   讀取

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

file_id: 標示在哪個文件；
offset: 標示在文件的開始位置；
length: 標示值的長短（結束位置）；

通過以上三個信息，就能找到對應的文件取回數據了。

總結下讀的流程：

  1. 在內存 hash 表中找到 key 的值的文件位置；

  2. 下盤讀數據；

思考兩點：

 5   回收

Bitcask 回收的流程叫做 merge，其實很簡單，在日誌文件中刪除的標記已經打上了，內存裏又有全部索引，那隻需要把有效的數據讀出來寫到新文件，然後把舊文件一刪，就完成了空間的釋放。

但簡單的東西往往有內涵，在前面我們提到，用戶的寫入爲了順序化採用了日誌的格式，但是 merge 這個是後端程序有時候會和前段的寫入併發執行的，但底下磁盤只有一塊，兩個都是順序 IO ，但併發起來就成隨機 IO 了。所以它的精細之處就在於 merge 的時機選擇和速率，這個也是它的含金量之一。

前面提到，Bitcask 爲了索引 key/value 的位置，在內存中構建了全部的索引關係。 這個構建在初始化的時候可能會非常耗時，因爲要遍歷全部的日誌文件。怎麼解決這個問題呢？

乾脆直接把這個索引關係在合適的時機準備好，進程啓動加載的時候，直接讀這部分數據就行了。

最合適的時機不就是 merge 過程嘛。merge 過程無論怎樣都要遍歷了一次文件，生成一份索引關係歸檔起來就是順手的事情。這份歸檔的索引關係在 Bitcask 裏叫做 “hint file” 。

劃重點：內存的索引內容和文件的 “hint file” 是對應的。

不一樣的思考

每一種設計都有它針對的場景，通用的東西往往是平庸的。Bitcask 它也是如此，它不適用於所有場景，那它適用哪些場景呢？

Bitcask 主要是持久化日誌型文件加上易失的內存 hash 表組成。

這裏有很多可以思考的關鍵點：

  1. 內存 hash 表到底有多大？

  2. Bitcask 它適合存儲多大的數據？

  3. 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 的誕生和它關係密切 。

總結

  1. Bitcask 展示了一個極富思考的存儲架構，它簡單有效，並且可以有很多變形；

  2. Bitcask 並不是一個最快的存儲系統，但是它性能足夠，並且簡單、穩定；

  3. 估算的能力很重要，結合自己的場景，估算的數據能指導架構設計；

  4. Bitcask 無疑是適合小對象的。小對象的定義？奇伢淺顯的認爲一次 IO 能裝的下的都可以認爲是小對象；

  5. Bitcask 雖然只有一個可寫文件，並且是 append 串行寫，但通過聚合小對象、批量落盤對外可以體現出不錯的併發能力哦；

  6. Bitcask 適合小對象，但是不適合海量對象。主要是內存索引的限制。當然也不絕對的。原生論文只是提供了一個設計思路，我們可以在此基礎上有很多變形設計；

參考資料

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

後記

Bitcask 在設計上和 LSM 有異曲同工之處，都是通過日誌的形式來承接寫，提供最優的寫的性能。 雖然功能不如 LSM 豐富，但它簡單穩定，非常值得學習。

堅持思考，方向比努力更重要。關注我：奇伢雲存儲。歡迎加我好友，技術交流。

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

猜你喜歡