寫這篇文章的目的，是為了幫助更多的人理解 rosedb，我會(huì)從零開始實(shí)現(xiàn)一個(gè)簡(jiǎn)單的包含 PUT、GET、DELETE 操作的 k-v 存儲(chǔ)引擎。

github.com/roseduan/rosedb

你可以將其看做是一個(gè)簡(jiǎn)易版本的 rosedb，就叫它 minidb 吧（mini 版本的 rosedb）。

無論你是 Go 語(yǔ)言初學(xué)者，還是想進(jìn)階 Go 語(yǔ)言，或者是對(duì) k-v 存儲(chǔ)感興趣，都可以嘗試自己動(dòng)手實(shí)現(xiàn)一下，我相信一定會(huì)對(duì)你幫助很大的。

說到存儲(chǔ)，其實(shí)解決的一個(gè)核心問題就是，怎么存放數(shù)據(jù)，怎么取出數(shù)據(jù)。在計(jì)算機(jī)的世界里，這個(gè)問題會(huì)更加的多樣化。

計(jì)算機(jī)當(dāng)中有內(nèi)存和磁盤，內(nèi)存是易失性的，掉電之后存儲(chǔ)的數(shù)據(jù)全部丟失，所以，如果想要系統(tǒng)崩潰再重啟之后依然正常使用，就不得不將數(shù)據(jù)存儲(chǔ)在非易失性介質(zhì)當(dāng)中，最常見的便是磁盤。

所以，針對(duì)一個(gè)單機(jī)版的 k-v，我們需要設(shè)計(jì)數(shù)據(jù)在內(nèi)存中應(yīng)該怎么存放，在磁盤中應(yīng)該怎么存放。

當(dāng)然，已經(jīng)有很多優(yōu)秀的前輩們?nèi)ヌ骄窟^了，并且已經(jīng)有了經(jīng)典的總結(jié)，主要將數(shù)據(jù)存儲(chǔ)的模型分為了兩類：B+ 樹和 LSM 樹。

本文的重點(diǎn)不是講這兩種模型，所以只做簡(jiǎn)單介紹。

B+ 樹

B+ 樹由二叉查找樹演化而來，通過增加每層節(jié)點(diǎn)的數(shù)量，來降低樹的高度，適配磁盤的頁(yè)，盡量減少磁盤 IO 操作。

B+ 樹查詢性能比較穩(wěn)定，在寫入或更新時(shí)，會(huì)查找并定位到磁盤中的位置并進(jìn)行原地操作，注意這里是隨機(jī) IO，并且大量的插入或刪除還有可能觸發(fā)頁(yè)分裂和合并，寫入性能一般，因此 B+ 樹適合讀多寫少的場(chǎng)景。

LSM 樹

LSM Tree（Log Structured Merge Tree，日志結(jié)構(gòu)合并樹）其實(shí)并不是一種具體的樹類型的數(shù)據(jù)結(jié)構(gòu)，而只是一種數(shù)據(jù)存儲(chǔ)的模型，它的核心思想基于一個(gè)事實(shí)：順序 IO 遠(yuǎn)快于隨機(jī) IO。

和 B+ 樹不同，在 LSM 中，數(shù)據(jù)的插入、更新、刪除都會(huì)被記錄成一條日志，然后追加寫入到磁盤文件當(dāng)中，這樣所有的操作都是順序 IO，因此 LSM 比較適用于寫多讀少的場(chǎng)景。

看了前面的兩種基礎(chǔ)存儲(chǔ)模型，相信你已經(jīng)對(duì)如何存取數(shù)據(jù)有了基本的了解，而 minidb 基于一種更加簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)，總體上它和 LSM 比較類似。

我先不直接干巴巴的講這個(gè)模型的概念，而是通過一個(gè)簡(jiǎn)單的例子來看一下 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），追加到磁盤文件當(dāng)中。Entry 的里面的內(nèi)容，大致是 key、value、key 的大小、value 的大小、寫入的時(shí)間。

所以磁盤文件的結(jié)構(gòu)非常簡(jiǎn)單，就是多個(gè) Entry 的集合。

磁盤更新完了，再更新內(nèi)存，內(nèi)存當(dāng)中可以選擇一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，比如哈希表。哈希表的 key 對(duì)應(yīng)存放的是 Entry 在磁盤中的位置，便于查找時(shí)進(jìn)行獲取。

這樣，在 minidb 當(dāng)中，一次數(shù)據(jù)存儲(chǔ)的流程就完了，只有兩個(gè)步驟：一次磁盤記錄的追加，一次內(nèi)存當(dāng)中的索引更新。

GET

再來看 GET 獲取數(shù)據(jù)，首先在內(nèi)存當(dāng)中的哈希表查找到 key 對(duì)應(yīng)的索引信息，這其中包含了 value 存儲(chǔ)在磁盤文件當(dāng)中的位置，然后直接根據(jù)這個(gè)位置，到磁盤當(dāng)中去取出 value 就可以了。

DEL

然后是刪除操作，這里并不會(huì)定位到原記錄進(jìn)行刪除，而還是將刪除的操作封裝成 Entry，追加到磁盤文件當(dāng)中，只是這里需要標(biāo)識(shí)一下 Entry 的類型是刪除。

然后在內(nèi)存當(dāng)中的哈希表刪除對(duì)應(yīng)的 key 的索引信息，這樣刪除操作便完成了。

可以看到，不管是插入、查詢、刪除，都只有兩個(gè)步驟：一次內(nèi)存中的索引更新，一次磁盤文件的記錄追加。所以無論數(shù)據(jù)規(guī)模如何， minidb 的寫入性能十分穩(wěn)定。

Merge

最后再來看一個(gè)比較重要的操作，前面說到，磁盤文件的記錄是一直在追加寫入的，這樣會(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，那么磁盤文件中就有三條記錄：

此時(shí) A 的最新值是 30，那么其實(shí)前兩條記錄已經(jīng)是無效的了。

針對(duì)這種情況，我們需要定期合并數(shù)據(jù)文件，清理無效的 Entry 數(shù)據(jù)，這個(gè)過程一般叫做 merge。

merge 的思路也很簡(jiǎn)單，需要取出原數(shù)據(jù)文件的所有 Entry，將有效的 Entry 重新寫入到一個(gè)新建的臨時(shí)文件中，最后將原數(shù)據(jù)文件刪除，臨時(shí)文件就是新的數(shù)據(jù)文件了。

這就是 minidb 底層的數(shù)據(jù)存儲(chǔ)模型，它的名字叫做 bitcask，當(dāng)然 rosedb 采用的也是這種模型。它本質(zhì)上屬于類 LSM 的模型，核心思想是利用順序 IO 來提升寫性能，只不過在實(shí)現(xiàn)上，比 LSM 簡(jiǎn)單多了。

介紹完了底層的存儲(chǔ)模型，就可以開始代碼實(shí)現(xiàn)了，我將完整的代碼實(shí)現(xiàn)放到了我的 Github 上面，地址：

github.com/roseduan/minidb

文章當(dāng)中就截取部分關(guān)鍵的代碼。

首先是打開數(shù)據(jù)庫(kù)，需要先加載數(shù)據(jù)文件，然后取出文件中的 Entry 數(shù)據(jù)，還原索引狀態(tài)，關(guān)鍵部分代碼如下：

再來看看 PUT 方法，流程和上面的描述一樣，先更新磁盤，寫入一條記錄，再更新內(nèi)存：

GET 方法需要先從內(nèi)存中取出索引信息，判斷是否存在，不存在直接返回，存在的話從磁盤當(dāng)中取出數(shù)據(jù)。

DEL 方法和 PUT 方法類似，只是 Entry 被標(biāo)識(shí)為了 DEL ，然后封裝成 Entry 寫到文件當(dāng)中：

最后是重要的合并數(shù)據(jù)文件操作，流程和上面的描述一樣，關(guān)鍵代碼如下：

除去測(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)潔易懂，但是問題也不少，rosedb 在實(shí)踐的過程當(dāng)中，對(duì)其進(jìn)行了一些優(yōu)化，但目前還是有不少的問題存在。

有的人可能比較疑惑，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 的代碼，可以提出自己的意見建議，一起完善這個(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/@arpitbhayan