記錄於 2023.4.6，源於 hbase 原理的學習。
LSM 的核心思想#
LSM 樹有以下三個重要組成部分：
-
MemTable
MemTable 是在內存中的數據結構，用於保存最近更新的數據，會按照 Key 有序地組織這些數據，LSM 樹對於具體如何組織有序地組織數據並沒有明確的數據結構定義，例如 Hbase 使跳躍表來保證內存中 key 的有序。
因為數據暫時保存在內存中，內存並不是可靠存儲，如果斷電會丟失數據，因此通常會通過 WAL (Write-ahead logging，預寫式日誌) 的方式來保證數據的可靠性。
-
Immutable MemTable
當 MemTable 達到一定大小後，會轉化成 Immutable MemTable。Immutable MemTable 是將轉 MemTable 變為 SSTable 的一種中間狀態。寫操作由新的 MemTable 處理，在轉存過程中不阻塞數據更新操作。
-
SSTable(Sorted String Table)
有序鍵值對集合，是 LSM 樹組在磁盤中的數據結構。為了加快 SSTable 的讀取，可以通過建立 key 的索引以及布隆過濾器來加快 key 的查找。
LSM 樹的 Compact 策略#
主要介紹兩種基本策略：size-tiered 和 leveled。
重要的概念
- 讀放大：讀取數據時實際讀取的數據量大於真正的數據量。例如在 LSM 樹中需要先在 MemTable 查看當前 key 是否存在，不存在繼續從 SSTable 中尋找。
- 寫放大：寫入數據時實際寫入的數據量大於真正的數據量。例如在 LSM 樹中寫入時可能觸發 Compact 操作，導致實際寫入的數據量遠大於該 key 的數據量。
- 空間放大：數據實際佔用的磁盤空間比數據的真正大小更多。上面提到的冗余存儲，對於一個 key 來說，只有最新的那條記錄是有效的，而之前的記錄都是可以被清理回收的。
size-tiered 策略#
size-tiered 策略保證每層 SSTable 的大小相近，同時限制每一層 SSTable 的數量。如上圖，每層限制 SSTable 為 N，當每層 SSTable 達到 N 後，則觸發 Compact 操作合併這些 SSTable，並將合併後的結果寫入到下一層成為一個更大的 sstable。
由此可以看出，當層數達到一定數量時，最底層的單個 SSTable 的大小會變得非常大。並且 size-tiered 策略會導致空間放大比較嚴重。即使對於同一層的 SSTable，每個 key 的記錄是可能存在多份的，只有當該層的 SSTable 執行 compact 操作才會消除這些 key 的冗余記錄。
leveled 策略#
leveled 策略也是採用分層的思想，每一層限制總文件的大小。
但是跟 size-tiered 策略不同的是，leveled 會將每一層切分成多個大小相近的 SSTable。這些 SSTable 是這一層是全局有序的，意味著一個 key 在每一層至多只有 1 條記錄，不存在冗余記錄。
leveled 策略相較於 size-tiered 策略來說，每層內 key 是不會重複的，即使是最壞的情況，除開最底層外，其餘層都是重複 key，按照相鄰層大小比例為 10 來算，冗余佔比也很小。因此空間放大問題得到緩解。但是寫放大問題會更加突出