從零實現一個 K-V 存儲引擎
本文轉載自微信公眾號「roseduan寫字的地方」，作者roseduan。轉載本文請聯系roseduan寫字的地方公眾號。
寫這篇文章的目的，是為了幫助更多的人理解 rosedb，我會從零開始實現一個簡單的包含 PUT、GET、DELETE 操作的 k-v 存儲引擎。
你可以將其看做是一個簡易版本的 rosedb，就叫它 minidb 吧(mini 版本的 rosedb)。
無論你是 Go 語言初學者，還是想進階 Go 語言，或者是對 k-v 存儲感興趣，都可以嘗試自己動手實現一下，我相信一定會對你幫助很大的。
說到存儲，其實解決的一個核心問題就是，怎么存放數據，怎么取出數據。在計算機的世界里，這個問題會更加的多樣化。
計算機當中有內存和磁盤，內存是易失性的，掉電之后存儲的數據全部丟失，所以，如果想要系統崩潰再重啟之后依然正常使用，就不得不將數據存儲在非易失性介質當中，最常見的便是磁盤。
所以，針對一個單機版的 k-v，我們需要設計數據在內存中應該怎么存放，在磁盤中應該怎么存放。
當然，已經有很多優秀的前輩們去探究過了，并且已經有了經典的總結，主要將數據存儲的模型分為了兩類：B+ 樹和 LSM 樹。
本文的重點不是講這兩種模型，所以只做簡單介紹。
B+ 樹
B+ 樹由二叉查找樹演化而來，通過增加每層節點的數量，來降低樹的高度，適配磁盤的頁，盡量減少磁盤 IO 操作。
B+ 樹查詢性能比較穩定，在寫入或更新時，會查找并定位到磁盤中的位置并進行原地操作，注意這里是隨機 IO，并且大量的插入或刪除還有可能觸發頁分裂和合并，寫入性能一般，因此 B+ 樹適合讀多寫少的場景。
LSM 樹
LSM Tree(Log Structured Merge Tree，日志結構合并樹)其實并不是一種具體的樹類型的數據結構，而只是一種數據存儲的模型，它的核心思想基于一個事實：順序 IO 遠快于隨機 IO。
和 B+ 樹不同，在 LSM 中，數據的插入、更新、刪除都會被記錄成一條日志，然后追加寫入到磁盤文件當中，這樣所有的操作都是順序 IO，因此 LSM 比較適用于寫多讀少的場景。
看了前面的兩種基礎存儲模型，相信你已經對如何存取數據有了基本的了解，而 minidb 基于一種更加簡單的存儲結構，總體上它和 LSM 比較類似。
我先不直接干巴巴的講這個模型的概念，而是通過一個簡單的例子來看一下 minidb 當中數據 PUT、GET、DELETE 的流程，借此讓你理解這個簡單的存儲模型。
PUT
我們需要存儲一條數據，分別是 key 和 value，首先，為預防數據丟失，我們會將這個 key 和 value 封裝成一條記錄(這里把這條記錄叫做 Entry)，追加到磁盤文件當中。Entry 的里面的內容，大致是 key、value、key 的大小、value 的大小、寫入的時間。
所以磁盤文件的結構非常簡單，就是多個 Entry 的集合。
磁盤更新完了，再更新內存，內存當中可以選擇一個簡單的數據結構，比如哈希表。哈希表的 key 對應存放的是 Entry 在磁盤中的位置，便于查找時進行獲取。
這樣，在 minidb 當中，一次數據存儲的流程就完了，只有兩個步驟：一次磁盤記錄的追加，一次內存當中的索引更新。
GET
再來看 GET 獲取數據，首先在內存當中的哈希表查找到 key 對應的索引信息，這其中包含了 value 存儲在磁盤文件當中的位置，然后直接根據這個位置，到磁盤當中去取出 value 就可以了。
DEL
然后是刪除操作，這里并不會定位到原記錄進行刪除，而還是將刪除的操作封裝成 Entry，追加到磁盤文件當中，只是這里需要標識一下 Entry 的類型是刪除。
然后在內存當中的哈希表刪除對應的 key 的索引信息，這樣刪除操作便完成了。
可以看到，不管是插入、查詢、刪除，都只有兩個步驟：一次內存中的索引更新，一次磁盤文件的記錄追加。所以無論數據規模如何， minidb 的寫入性能十分穩定。
Merge
最后再來看一個比較重要的操作，前面說到，磁盤文件的記錄是一直在追加寫入的，這樣會導致文件容量也一直在增加。并且對于同一個 key，可能會在文件中存在多條 Entry(回想一下，更新或刪除 key 內容也會追加記錄)，那么在數據文件當中，其實存在冗余的 Entry 數據。
舉一個簡單的例子，比如針對 key A， 先后設置其 value 為 10、20、30，那么磁盤文件中就有三條記錄：
此時 A 的最新值是 30，那么其實前兩條記錄已經是無效的了。
針對這種情況，我們需要定期合并數據文件，清理無效的 Entry 數據，這個過程一般叫做 merge。
merge 的思路也很簡單，需要取出原數據文件的所有 Entry，將有效的 Entry 重新寫入到一個新建的臨時文件中，最后將原數據文件刪除，臨時文件就是新的數據文件了。
這就是 minidb 底層的數據存儲模型，它的名字叫做 bitcask，當然 rosedb 采用的也是這種模型。它本質上屬于類 LSM 的模型，核心思想是利用順序 IO 來提升寫性能，只不過在實現上，比 LSM 簡單多了。
介紹完了底層的存儲模型，就可以開始代碼實現了，我將完整的代碼實現放到了我的 Github 上面，地址：
https://github.com/roseduan/minidb
文章當中就截取部分關鍵的代碼。
首先是打開數據庫，需要先加載數據文件，然后取出文件中的 Entry 數據，還原索引狀態，關鍵部分代碼如下：
- func Open(dirPath string) (*MiniDB, error) {
- // 如果數據庫目錄不存在，則新建一個
- if _, err := os.Stat(dirPath); os.IsNotExist(err) {
- if err := os.MkdirAll(dirPath, os.ModePerm); err != nil {
- return nil, err
- }
- }
- // 加載數據文件
- dbFile, err := NewDBFile(dirPath)
- if err != nil {
- return nil, err
- }
- db := &MiniDB{
- dbFile: dbFile,
- indexes: make(map[string]int64),
- dirPath: dirPath,
- }
- // 加載索引
- db.loadIndexesFromFile(dbFile)
- return db, nil
- }
再來看看 PUT 方法，流程和上面的描述一樣，先更新磁盤，寫入一條記錄，再更新內存：
- func (db *MiniDB) Put(key []byte, value []byte) (err error) {
- offset := db.dbFile.Offset
- // 封裝成 Entry
- entry := NewEntry(key, value, PUT)
- // 追加到數據文件當中
- err = db.dbFile.Write(entry)
- // 寫到內存
- db.indexes[string(key)] = offset
- return
- }
GET 方法需要先從內存中取出索引信息，判斷是否存在，不存在直接返回，存在的話從磁盤當中取出數據。
- func (db *MiniDB) Get(key []byte) (val []byte, err error) {
- // 從內存當中取出索引信息
- offset, ok := db.indexes[string(key)]
- // key 不存在
- if !ok {
- return
- }
- // 從磁盤中讀取數據
- var e *Entry
- e, err = db.dbFile.Read(offset)
- if err != nil && err != io.EOF {
- return
- }
- if e != nil {
- val = e.Value
- }
- return
- }
DEL 方法和 PUT 方法類似，只是 Entry 被標識為了 DEL ，然后封裝成 Entry 寫到文件當中：
- func (db *MiniDB) Del(key []byte) (err error) {
- // 從內存當中取出索引信息
- _, ok := db.indexes[string(key)]
- // key 不存在，忽略
- if !ok {
- return
- }
- // 封裝成 Entry 并寫入
- e := NewEntry(key, nil, DEL)
- err = db.dbFile.Write(e)
- if err != nil {
- return
- }
- // 刪除內存中的 key
- delete(db.indexes, string(key))
- return
- }
最后是重要的合并數據文件操作，流程和上面的描述一樣，關鍵代碼如下：
- func (db *MiniDB) Merge() error {
- // 讀取原數據文件中的 Entry
- for {
- e, err := db.dbFile.Read(offset)
- if err != nil {
- if err == io.EOF {
- break
- }
- return err
- }
- // 內存中的索引狀態是最新的，直接對比過濾出有效的 Entry
- if off, ok := db.indexes[string(e.Key)]; ok && off == offset {
- validEntries = append(validEntries, e)
- }
- offset += e.GetSize()
- }
- if len(validEntries) > 0 {
- // 新建臨時文件
- mergeDBFile, err := NewMergeDBFile(db.dirPath)
- if err != nil {
- return err
- }
- defer os.Remove(mergeDBFile.File.Name())
- // 重新寫入有效的 entry
- for _, entry := range validEntries {
- writeOff := mergeDBFile.Offset
- err := mergeDBFile.Write(entry)
- if err != nil {
- return err
- }
- // 更新索引
- db.indexes[string(entry.Key)] = writeOff
- }
- // 刪除舊的數據文件
- os.Remove(db.dbFile.File.Name())
- // 臨時文件變更為新的數據文件
- os.Rename(mergeDBFile.File.Name(), db.dirPath+string(os.PathSeparator)+FileName)
- db.dbFile = mergeDBFile
- }
- return nil
- }
除去測試文件，minidb 的核心代碼只有 300 行，麻雀雖小，五臟俱全，它已經包含了 bitcask 這個存儲模型的主要思想，并且也是 rosedb 的底層基礎。
理解了 minidb 之后，基本上就能夠完全掌握 bitcask 這種存儲模型，多花點時間，相信對 rosedb 也能夠游刃有余了。
進一步，如果你對 k-v 存儲這方面感興趣，可以更加深入的去研究更多相關的知識，bitcask 雖然簡潔易懂，但是問題也不少，rosedb 在實踐的過程當中，對其進行了一些優化，但目前還是有不少的問題存在。
有的人可能比較疑惑，bitcask 這種模型簡單，是否只是一個玩具，在實際的生產環境中有應用嗎?答案是肯定的。
bitcask 最初源于 Riak 這個項目的底層存儲模型，而 Riak 是一個分布式 k-v 存儲，在 NoSQL 的排名中也名列前茅：
豆瓣所使用的的分布式 k-v 存儲，其實也是基于 bitcask 模型，并對其進行了很多優化。目前純粹基于 bitcask 模型的 k-v 并不是很多，所以你可以多去看看 rosedb 的代碼，可以提出自己的意見建議，一起完善這個項目。
最后，附上相關項目地址：
- minidb：https://github.com/roseduan/minidb
- rosedb：https://github.com/roseduan/rosedb
參考資料：
https://riak.com/assets/bitcask-intro.pdf
https://medium.com/@arpitbhayani/bitcask-a-log-structured-fast-kv-store-c6c728a9536b
題圖：from wallheaven.cc
