LotusDB 是一個(gè)基于 LSM Tree 進(jìn)行設(shè)計(jì)，并結(jié)合 B+ 樹優(yōu)勢(shì)的單機(jī) KV 存儲(chǔ)引擎，讀寫性能穩(wěn)定、快速。

在傳統(tǒng)的 LSM Tree 架構(gòu)中，增刪數(shù)據(jù)均是追加有序?qū)懭氲?SST 文件中，相同的 key 對(duì)應(yīng)的數(shù)據(jù)可能存在多份，需要通過復(fù)雜的 compaction 策略來進(jìn)行空間回收，這同時(shí)帶來了空間放大和寫放大問題。

LSM Tree 在磁盤上維護(hù)多級(jí) SSTable 文件，在數(shù)據(jù)讀取時(shí)，需要逐層掃描文件來查找指定的數(shù)據(jù)，最壞情況下需要掃描每一層的 SSTable，讀性能不穩(wěn)定。

和 LSM Tree 相對(duì)應(yīng)的，另一種常見的數(shù)據(jù)存儲(chǔ)模型是 B+ Tree，B+ 樹由于有著很好的適配磁盤頁的特性，在數(shù)據(jù)庫存儲(chǔ)引擎中廣泛應(yīng)用，例如最為人熟知的 Mysql 的 InnoDB 引擎。

B+ Tree 將數(shù)據(jù)維護(hù)在樹最底層葉子節(jié)點(diǎn)中，讀性能比較穩(wěn)定，但是數(shù)據(jù)的插入和更新均是隨機(jī) IO 進(jìn)行寫入，導(dǎo)致 B+ Tree 的寫性能相對(duì)較低。

我們知道，LSM 存儲(chǔ)模型誕生于 HDD(機(jī)械硬盤) 時(shí)代，HDD 的隨機(jī)和順序讀寫速度差別巨大，所以 LSM 的設(shè)計(jì)最大限度的發(fā)揮了順序 IO 的優(yōu)勢(shì)，所有的數(shù)據(jù)先到內(nèi)存 buffer 里緩存，然后批量有序?qū)懭氲轿募?。但是隨著存儲(chǔ)硬件的更新迭代，磁盤的隨機(jī)和順序讀寫差別變小了，在一些介質(zhì)中，順序和隨機(jī)讀寫甚至沒有太大的差別。

LSM Tree 針對(duì)順序 IO 的一些設(shè)計(jì)就會(huì)顯得過于復(fù)雜，導(dǎo)致整個(gè)系統(tǒng)難以實(shí)現(xiàn)和控制(如果你熟悉 rocksdb 的話，就會(huì)深有體會(huì))。

自行設(shè)計(jì)一個(gè)系統(tǒng)的底層存儲(chǔ)引擎，比掌握一個(gè)復(fù)雜的項(xiàng)目要更加容易，出現(xiàn)了相關(guān)的問題也更容易定位和解決，這也是為什么 cockroach 采用自研的 Pebble 存儲(chǔ)引擎替代 rocksdb，而 LotusDB 就是一個(gè)這樣可以輕易學(xué)習(xí)和掌握的存儲(chǔ)引擎，因?yàn)樗?jiǎn)潔、直觀且高效。

LotusDB 的整體架構(gòu)圖如下：

LotusDB 仍然保留了 LSM Tree 中的寫流程，因?yàn)檫@能夠最大限度的保證寫入數(shù)據(jù)的持久性以及寫吞吐，所以在磁盤上維護(hù)了 WAL 日志，新寫入的數(shù)據(jù)先追加到 WAL 中保證數(shù)據(jù)不丟失，然后再寫入到內(nèi)存中。內(nèi)存中維護(hù)了多個(gè)跳表結(jié)構(gòu)，最新的跳表叫做 active memtable，一個(gè) memtable 寫滿之后，會(huì)變?yōu)?immutable memtable，即不可變的 memtable，其不能接收新的寫入，并且等待被后臺(tái)線程 flush 到磁盤中。

Flush 的時(shí)候，數(shù)據(jù)索引信息會(huì)被存放到 B+ 樹中，而 value 會(huì)被單獨(dú)存放到 Value Log 中，value log 的結(jié)構(gòu)類似于 WAL，數(shù)據(jù)寫入都是采用日志追加，只不過 value log 會(huì)有一個(gè)閾值，寫滿之后會(huì)打開一個(gè)新的 value log，因此 value log 是存在多個(gè)的。

需要注意的是，B+ Tree 應(yīng)該盡量存儲(chǔ)新的存儲(chǔ)介質(zhì)中，例如固態(tài)硬盤，因?yàn)榍懊嫣岬竭^ B+ 樹是隨機(jī)寫入，如果使用傳統(tǒng)機(jī)械硬盤的話，寫性能受限制，寫放大嚴(yán)重，F(xiàn)lush 可能會(huì)是一個(gè)瓶頸。

這就是 LotusDB 的整體實(shí)現(xiàn)，在這種實(shí)現(xiàn)下，我們來看看基本的數(shù)據(jù)讀寫流程是什么樣的。

寫一個(gè) key/value：前面說過了，和 LSM 模型完全一致，先將 key/value 封裝成一條日志追加到 WAL 中，然后將 k/v 寫入到內(nèi)存的 active memtable。

根據(jù) key 讀一個(gè) value：先在內(nèi)存當(dāng)中的 active memtable 和 immutable memtable 中依次查找，如果找到直接返回。否則說明 value 可能在磁盤中，就從 B+ 樹獲取 key 的索引信息，索引信息是一個(gè)二元組 ，標(biāo)識(shí) value 位于 value log 中具體哪個(gè)文件，以及文件中的位置，然后直接根據(jù)這個(gè)索引信息到 value log 文件中獲取 value 即可。

最后再來總結(jié)下 LotusDB 架構(gòu)的優(yōu)點(diǎn)，簡(jiǎn)單歸納大概有如下幾點(diǎn)：

1.寫數(shù)據(jù)流程和傳統(tǒng) LSM 模型完全一致，保證了順序 IO 的高吞吐，以及數(shù)據(jù)持久性

2.讀性能相較于原生 LSM 模型更加穩(wěn)定，讀放大降低，因?yàn)橐肓?B+ 樹，得益于 B+ 樹穩(wěn)定的讀性能，整體的讀取效率會(huì)更加可控

3.完全去除了 LSM Tree 模型中的多級(jí) SSTable，沒有了 SSTable 的維護(hù)，并且采用已有的 B+ 樹實(shí)現(xiàn)(BoltDB)，大大降低了系統(tǒng)的復(fù)雜性

4.Compaction 對(duì)存儲(chǔ)介質(zhì)的損耗降低，LotusDB 中只有 value log 存在 Compaction;原生 LSM 不僅 SSTable 需要 Compaction，并且如果進(jìn)行了 kv 分離的話，value log 也同樣需要 Compaction

5.讀寫流程簡(jiǎn)潔直觀，沒有 bloom filter、block cache 等

LotusDB Github 地址：https://github.com/flower-corp/lotusdb