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