LSM-based storage techniques: a survey
现如今，log-structured merge-tree（LSM- tree）广泛应用于现代NoSQL数据库底层，BigTable，HBase，LevelDB，RocksDB等.相比采用原地更新（in-place updates）的传统索引结构，LSM- tree 先buffer，Flush，merge ，异地更新（out-of-place update），有很多优点：优越的写性能，高空间利用率，可调节，简化并行控制和recovery。这篇文章基本涵盖LSM- tree 发展演进，基本知识和优化方向，现有研究工作分类。
1.背景
1.1 LSM- tree basic
索引更新
原地更新（in-place updates）:B+-tree
优点：
--读优化：只保留一份最新的数据更新
缺点：
--牺牲写性能：更新引入随机写IO
--空间利用率低：更新和删除引发碎片化
异地更新（out-of-place update）：LSM- tree
优点：
--优越写性能：顺序写
--简化recovery 过程
缺点：
--牺牲读性能
--需要额外数据重新组织的过程
顺序异地更新的机制，不是新的idea。
Differential files【1976】
--更新写到diff 文件中
--周期性的将diff 合并到main file 中
Postgres log-structured db【1980s】
--append writes --> sequential log以实现fast recovery。
--需要一个后台程序持续的回收过时的记录
LFS 之前的log- structured存储问题：
--查询性能低-
--空间利用率低
--很难调性能
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；
-- 每当Ci 达到满的条件是，就做rolling merge，合并Ci 到Ci+1；
-- 也就是采用leveling merge 策略；
-- size ratio Ti = Ci + 1/Ci；
--所以Ti 一样，以优化写性能
1.3 现代的LSM- tree
现代的LSM- tree
SSTable
查询操作-解释了为什么需要merge 过程
合并操作
两种merge 机制- leveling 和tiering
合并开销与收益
1.4 well- known 优化
优化1-bloom filter
优化2-partition
1.5 并发控制和恢复
1.6 开销分析
-
LSM- tree 改进
image.png
减少写放大
优化merge 操作
利用硬件
自动调节
3.LSM- tree base 系统
LevelDB
2011年Google开源level DB
提供简单的KV 接口（puts，gets，scans)
采用partition leveling merge 策略
RocksDB
Facebook 2012 年Fork 自levelDB；
增加许多特性；
采用LSM- tree动机是很好的空间利用率
size =10的情况下，leveling merge策略下90% 的数据在最大的level
