RocksDB LSM樹
RocksDB是Meta (Facebook) 開源的高性能持久化鍵值存儲庫，源于Google的LevelDB，并針對SSD和服務器工作負載進行了深度優化。它廣泛應用于需要處理海量數據（億級甚至更高）并要求高寫入吞吐的場景。
RocksDB 以 kv 對集合的形式存儲數據， key 和 value 是任意長度的字節數組（byte array）。RocksDB 提供了幾個用于操作 kv 集合的函數底層接口：

// 插入新的鍵值對或更新已有鍵值對
put(key, value)
// 將新值與給定鍵的原值進行合并
merge(key, value)
// 從集合中刪除鍵值對
delete(key)
// 通過點查來獲取 key 所關聯的 value
get(key)
// 通過迭代器進行范圍掃描——找到特定的key，并按順序訪問該key后續的鍵值對
iterator.seek(key_prefix); iterator.value(); iterator.next()

LSM樹
RocksDB 的核心數據結構被稱為日志結構合并樹 （Log Structured Merge Tree，LSM Tree）。LSM樹是一種專為寫密集型工作負載設計的數據結構，其思想最早由O'Neil等人在1996年的同名論文提出被大家所知。
在2000年左右，谷歌發布了大名鼎鼎的"三駕馬車"的論文，分別是Google File System(2003年)，MapReduce（2004年），BigTable（2006年）。其中在 “BigTable” 的論文中很多很酷的方面之一就是它所使用的文件組織方式，這個方法的名字叫 LSM樹 。

如上圖所示，LSM樹有以下四個重要組成部分。
1）MemTable（內存表）：MemTable是在內存中的數據結構，用于保存最近更新的數據，會按照Key有序地組織這些數據，LSM樹未明確定義有序組織的數據結構，例如RocksDB使用平衡二叉樹來保證內存中key的有序。
2）Immutable MemTable（不可變內存表）：Immutable MemTable是將轉MemTable變為SSTable的一種中間狀態。寫操作由新的MemTable處理，在轉存過程中不阻塞數據更新操作。
3）WAL：因為數據暫時保存在內存中，內存并不是可靠存儲，如果斷電會丟失數據，因此通常會通過預寫式日志（Write-ahead logging，WAL）的方式來保證數據的可靠性。
WAL是一個只允許追加（Append Only）的文件，包含一組更改記錄序列。每個記錄包含鍵值對、記錄類型（Put / Merge / Delete）和校驗和（checksum）。與 MemTable 不同，在 WAL 中，記錄不按 key 有序，而是按照請求到來的順序被追加到 WAL 中。
WAL是順序寫的，速度很快。若系統崩潰，可通過WAL恢復MemTable中的數據。
4）SSTable（Sorted String Table，有序字符串表）：SSTable是一種擁有持久化，有序且不可變的的鍵值存儲結構，它的key和value都是任意的字節數組，并且了提供了按指定key查找和指定范圍的key區間迭代遍歷的功能。
SSTable內部包含了一系列可配置大小的Block塊，典型的大小是64KB。與 WAL 的記錄類似，每個數據塊中都包含用于檢測數據是否損壞的校驗和。每次從硬盤讀取數據時，LSM樹都會使用這些校驗和進行校驗。
當一個SSTable被打開的時候，存儲在SSTable尾部的index會被加載到內存，然后根據key在內存index里面進行一個二分查找，查到該key對應的硬盤的offset之后，然后去硬盤把相應的塊數據讀取出來。

數據寫入
寫入一個<Key, Value>時，LSM樹的寫入順序是：
1）寫操作記錄到WAL（順序寫）。
2）寫操作插入到內存中的MemTable（有序插入）。
3）當MemTable寫滿，轉換為Immutable MemTable，同時創建新的MemTable和WAL文件接收新寫入。
4）后臺線程將Immutable MemTable的數據順序寫入磁盤，生成一個新的SSTable文件，通常放在Level-0層。
5）刷盤完成后，對應的WAL文件可以被安全刪除。 所有磁盤寫入（WAL和SSTable）都是順序的，極大地提高了寫入吞吐。
MemTable 的默認大小為 64 MB。 LSM樹定期把內存寫滿的MemTable轉變為Immutable MemTable ，并從內存持久化到硬盤。一旦刷盤（flush）完成，Immutable MemTable 和相應的 WAL就會被丟棄。LSM樹寫入新的 WAL、MemTable。
每次刷盤都會在 Level 0 層上產生一個新的SSTable文件。該文件一旦寫入硬盤后，就不再會修改。有序性使得 MemTable 刷盤時更高效，因為可以直接按順序迭代鍵值對順序寫入硬盤。將隨機寫變為順序寫是 LSM樹的核心設計之一。

數據刪除
對于需要刪除的數據，LSM 樹采用一個特殊的標志位，稱為墓碑（tombstone），刪除一條數據就是把它的值置為墓碑。如果查詢當前數據，返回的是空值。因此，刪除操作的本質是覆蓋寫，而不是清除一條數據，墓碑會在合并機制中被清理掉，于是置為墓碑的數據在新的 SSTable 中將不復存在。

合并機制
由于SSTable不可修改，更新和刪除操作實際上是寫入新的記錄（更新是新版本，刪除是打上“墓碑”標記Tombstone）。這樣的設計雖然大大提高了寫性能，但同時也會帶來一些問題。
1）空間放大 (Space Amplification)：磁盤上可能存在同一Key的多個版本或已刪除的“墓碑”，占用額外空間。
2）讀放大 (Read Amplification)：查詢一個Key時，可能需要從MemTable查起，然后逐層（從新到舊）查找多個SSTable，直到找到該Key或確認不存在。
3）寫放大 (Write Amplification)：實際寫入磁盤的數據量遠大于用戶寫入的數據量，因為數據在合并過程中會被多次重寫。
合并 (Compaction)機制是LSM樹維持性能和控制放大的關鍵：后臺線程定期將不同層級（Level）的SSTable進行合并。合并過程會讀取多個舊SSTable，將它們的有序鍵值對歸并排序，丟棄被覆蓋的舊值和已刪除的墓碑，然后將結果寫入新的SSTable（通常到下一層）。通過這種方式，減少SSTable數量（降低讀放大）、回收無效數據占用的空間（降低空間放大）。然而合并本身是I/O密集型操作，會產生寫放大，消耗處理器和磁盤帶寬。
RocksDB提供不同的合并策略，如：Leveled Compaction (分層合并)：將數據組織成多個層（L0, L1, L2...）。L0的SSTable可能有重疊的Key范圍，L1及以上層SSTable的Key范圍通常不重疊。合并時，從Ln層選擇一個SSTable，與Ln+1層中Key范圍重疊的SSTable進行合并。這種策略讀放大較小，但寫放大可能較高。
Tiered Compaction (分級合并，也稱Universal Compaction)：將SSTable按大小或時間分組，組內合并，或將多個小SSTable合并成一個大SSTable。寫放大較低，但讀放大可能較高。 RocksDB允許用戶根據應用特性選擇和配置合并策略，以在讀、寫、空間放大之間取得平衡。

數據查詢
查詢一個Key時，LSM樹的查找順序是：
1）Active MemTable。
2）Immutable MemTable。
3）SSTables on Level-0 （可能有多個，Key范圍可能重疊，需逐個查）。
4）SSTables on Level-1, Level-2, ..., Level-N（每層內Key范圍不重疊或部分不重疊，可快速定位）。
LSM樹在內存中對每個SSTable維護一個稀疏索引（Sparse index）。稀疏索引是指將有序數據切分成（固定大小的）塊，僅對各個塊開頭的一條數據做索引。與之相對的是全量索引（Dense index），即對全部數據編制索引，比如MySQL采用B+樹作為索引結構。
有稀疏索引之后，可以先在索引表中使用二分查找快速定位某個 key 位于SSTable哪一小塊數據中，這樣僅從硬盤中讀取這一塊數據即可獲得最終查詢結果，此時加載的數據量僅僅是整個 SSTable 的一小部分，因此 I/O 代價較小。
然而當要查詢的結果在 SSTable 中不存在時，將不得不依次掃描完所有的層級SSTable，這是最差的一種情況。因此，為加速查詢，特別是查詢不存在的Key，每個SSTable通常會關聯一個布隆過濾器（Bloom Filter）。查詢時先查布隆過濾器，若告知Key“肯定不存在”，則可直接跳過該SSTable的實際讀取，顯著減少不必要的I/O。布隆過濾器有一定假陽性率（可能誤報“存在”），但絕無假陰性（不會漏報）。

未完待續
很高興與你相遇！如果你喜歡本文內容，記得關注哦！！！