本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载自夜明的孤行灯
B+树使用广泛,而它最大的性能问题是会产生大量的随机IO,随着新数据的插入,叶子节点会慢慢分裂,逻辑上连续的叶子节点在物理上往往不连续,甚至分离的很远,但做范围查询时,会产生大量读随机IO。
LSM树最早是HBASE引入的,最初目的就是为了克服B+树的弱点。LSM树本质上就是在读写之间取得平衡,和B+树相比,它牺牲了部分读性能,用来大幅提高写性能。本质上就是把树拆开,拆成一个一个小树,当树足够大了再写入,当然读取的时候就需要访问多个树了。在写入硬盘后,也会在一定时机下,处理已经写入的树,进行再次合并。
LSB树会有一个WAL,因为内存中的数据有丢失风险,所以先写日志,当内存中对应的树刷盘以后删除对应日志就行了。
LSB树一般有三个放大点需要关注
- 写放大: 磁盘数据的写入量 / 用户写入的数据量
- 读放大: 磁盘数据的读入量 / 用户实际要读取的数据量
- 空间放大:磁盘空间占用 / 有效的用户数据量
其中写放大往往是最严重的,对它的计算和分析也相对较多。
写放大是最有意思的,根据LSM的原文,作者提到层与层之间的扇出系数(size ratio)是常量时,写放大最优。FaceBook的文档中有获得最优写放大倍数具体的计算方式,详细推导参见:http://smalldatum.blogspot.com/2018/12/lsm-math-how-many-levels-minimizes.html
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载自夜明的孤行灯