LSM-based storage techniques: a survey
現(xiàn)如今，log-structured merge-tree（LSM- tree）廣泛應(yīng)用于現(xiàn)代NoSQL數(shù)據(jù)庫底層，BigTable，HBase，LevelDB，RocksDB等.相比采用原地更新（in-place updates）的傳統(tǒng)索引結(jié)構(gòu)，LSM- tree 先buffer，F(xiàn)lush，merge ，異地更新（out-of-place update），有很多優(yōu)點：優(yōu)越的寫性能，高空間利用率，可調(diào)節(jié)，簡化并行控制和recovery。這篇文章基本涵蓋LSM- tree 發(fā)展演進，基本知識和優(yōu)化方向，現(xiàn)有研究工作分類。
1.背景
1.1 LSM- tree basic
索引更新
原地更新（in-place updates）:B+-tree
優(yōu)點：
--讀優(yōu)化：只保留一份最新的數(shù)據(jù)更新
缺點：
--犧牲寫性能：更新引入隨機寫IO
--空間利用率低：更新和刪除引發(fā)碎片化
異地更新（out-of-place update）：LSM- tree
優(yōu)點：
--優(yōu)越寫性能：順序?qū)?br>
--簡化recovery 過程
缺點：
--犧牲讀性能
--需要額外數(shù)據(jù)重新組織的過程
順序異地更新的機制，不是新的idea。
Differential files【1976】
--更新寫到diff 文件中
--周期性的將diff 合并到main file 中
Postgres log-structured db【1980s】
--append writes --> sequential log以實現(xiàn)fast recovery。
--需要一個后臺程序持續(xù)的回收過時的記錄
LFS 之前的log- structured存儲問題：
--查詢性能低-
--空間利用率低
--很難調(diào)性能
LFS（log-structure file systems]【1991】
1.2 LSM- tree original design
LSM- tree【1996】
-- 合入merge 過程
--高寫入性能
--查詢性能
--空間利用率
original LSM-tree :
--包含一個部件序列：C0,C1,...Ck
--每個部件是一個B+-tree；
--新寫請求，會先插入到C0；
-- 每當(dāng)Ci 達到滿的條件是，就做rolling merge，合并Ci 到Ci+1；
-- 也就是采用leveling merge 策略；
-- size ratio Ti = Ci + 1/Ci；
--所以Ti 一樣，以優(yōu)化寫性能
1.3 現(xiàn)代的LSM- tree
現(xiàn)代的LSM- tree
SSTable
查詢操作-解釋了為什么需要merge 過程
合并操作
兩種merge 機制- leveling 和tiering
合并開銷與收益
1.4 well- known 優(yōu)化
優(yōu)化1-bloom filter
優(yōu)化2-partition
1.5 并發(fā)控制和恢復(fù)
1.6 開銷分析
-
LSM- tree 改進
image.png
減少寫放大
優(yōu)化merge 操作
利用硬件
自動調(diào)節(jié)
3.LSM- tree base 系統(tǒng)
LevelDB
2011年Google開源level DB
提供簡單的KV 接口（puts，gets，scans)
采用partition leveling merge 策略
RocksDB
Facebook 2012 年Fork 自levelDB；
增加許多特性；
采用LSM- tree動機是很好的空間利用率
size =10的情況下，leveling merge策略下90% 的數(shù)據(jù)在最大的level
