LotusDB 是一個基于 LSM Tree 進行設計，并結合 B+ 樹優勢的單機 KV 存儲引擎，讀寫性能穩定、快速。

在傳統的 LSM Tree 架構中，增刪數據均是追加有序寫入到 SST 文件中，相同的 key 對應的數據可能存在多份，需要通過復雜的 compaction 策略來進行空間回收，這同時帶來了空間放大和寫放大問題。

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

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

B+ Tree 將數據維護在樹最底層葉子節點中，讀性能比較穩定，但是數據的插入和更新均是隨機 IO 進行寫入，導致 B+ Tree 的寫性能相對較低。

我們知道，LSM 存儲模型誕生于 HDD(機械硬盤) 時代，HDD 的隨機和順序讀寫速度差別巨大，所以 LSM 的設計最大限度的發揮了順序 IO 的優勢，所有的數據先到內存 buffer 里緩存，然后批量有序寫入到文件中。但是隨著存儲硬件的更新迭代，磁盤的隨機和順序讀寫差別變小了，在一些介質中，順序和隨機讀寫甚至沒有太大的差別。

LSM Tree 針對順序 IO 的一些設計就會顯得過于復雜，導致整個系統難以實現和控制(如果你熟悉 rocksdb 的話，就會深有體會)。

自行設計一個系統的底層存儲引擎，比掌握一個復雜的項目要更加容易，出現了相關的問題也更容易定位和解決，這也是為什么 cockroach 采用自研的 Pebble 存儲引擎替代 rocksdb，而 LotusDB 就是一個這樣可以輕易學習和掌握的存儲引擎，因為它簡潔、直觀且高效。

LotusDB 的整體架構圖如下：

LotusDB 仍然保留了 LSM Tree 中的寫流程，因為這能夠最大限度的保證寫入數據的持久性以及寫吞吐，所以在磁盤上維護了 WAL 日志，新寫入的數據先追加到 WAL 中保證數據不丟失，然后再寫入到內存中。內存中維護了多個跳表結構，最新的跳表叫做 active memtable，一個 memtable 寫滿之后，會變為 immutable memtable，即不可變的 memtable，其不能接收新的寫入，并且等待被后臺線程 flush 到磁盤中。

Flush 的時候，數據索引信息會被存放到 B+ 樹中，而 value 會被單獨存放到 Value Log 中，value log 的結構類似于 WAL，數據寫入都是采用日志追加，只不過 value log 會有一個閾值，寫滿之后會打開一個新的 value log，因此 value log 是存在多個的。

需要注意的是，B+ Tree 應該盡量存儲新的存儲介質中，例如固態硬盤，因為前面提到過 B+ 樹是隨機寫入，如果使用傳統機械硬盤的話，寫性能受限制，寫放大嚴重，Flush 可能會是一個瓶頸。

這就是 LotusDB 的整體實現，在這種實現下，我們來看看基本的數據讀寫流程是什么樣的。

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

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

最后再來總結下 LotusDB 架構的優點，簡單歸納大概有如下幾點：

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

2.讀性能相較于原生 LSM 模型更加穩定，讀放大降低，因為引入了 B+ 樹，得益于 B+ 樹穩定的讀性能，整體的讀取效率會更加可控

3.完全去除了 LSM Tree 模型中的多級 SSTable，沒有了 SSTable 的維護，并且采用已有的 B+ 樹實現(BoltDB)，大大降低了系統的復雜性

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

5.讀寫流程簡潔直觀，沒有 bloom filter、block cache 等

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