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