LSM Tree 全称是Log-structured merge-tree, 是一种分层,有序,面向磁盘的数据结构。其核心原理是磁盘批量顺序写比随机写性能高很多,可以通过围绕这一原理进行设计和优化,让写性能达到最优。相较于传统的B+树,它减少了磁盘随机读取的需求,从而在一定程度上改善了数据库的写能力,当然在一定程度上牺牲了数据库的读能力。LSM tree也是当今流行的各种NoSQL或NewSQL数据库最基础的底层数据结构,广泛使用在包括Hbase,Cassandra,Leveldb, RocksDB, TiDB等项目中。
传统的B+树的缺陷就是在访问节点时涉及到了大量的磁盘随机读写,因为你无法保证节点常驻内存,尤其是当B+树管理的索引量很大的时候,这导致数据库读写性能急剧下降。
LSM tree 采取的做法就是通过引入多部件索引来减少磁盘随机读写的需求。在大量插入情况下我们周期性地选取两部分索引进行合并,并且把合并后的有序文件(或内存块)添加到磁盘尾部(或成为新文件),修改节点信息以保证索引树的正确和完善,并且周期性地回收失效索引。因此与其说LSM tree是一种树,不如说它是通过传统索引组织有序文件或内存块的一种方式。
LSM tree的节点可以分为两种:
写操作直接作用于MemTable,因此写入性能接近写内存。每层SSTable文件到达一定条件后,进行合并操作,然后放置到更高层。合并操作在实现上一般的策略驱动、可插件化的。
LSM Tree 将随机写转化为顺序写,而作为代价带来了大量的重复写入。由此会引起写放大、读放大和空间放大。
以下是 HBase 中的写放大示意图
一个读请求,系统所需要读 n 个页面来完成查询,其读放大率是 n。逻辑上的读操作可能会命中引擎内部的 cache 或者文件系统 cache,命中不了 cache 就会进行实际的磁盘 IO,命中 cache 的读取操作的代价虽然很低,但是也会消耗 CPU。
以下是 HBase 中的读放大示意图
LSM tree 一般从以下几个方面进行优化:
SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。
因为 SSTable 在写入磁盘后,除了 Compaction 之外,是不会变化的,所以我可以将 Scan 的 Block 进行缓存,从而提高检索的效率。
正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,我们可以对每一个 SSTable 添加 Bloom Filter,因为 Bloom Filter 在判断一个 SSTable 不存在某个 key 的时候,那么就一定不会存在,利用这个特性可以减少不必要的磁盘扫描。
通过定期合并瘦身, 可以有效的清除无效数据,缩短读取路径,提高磁盘利用空间。但 Compaction 操作是非常消耗 CPU 和磁盘 IO 的,尤其是在业务高峰期,如果发生了 Major Compaction,则会降低整个系统的吞吐量,这也是在使用一些 NoSQL 数据库时,比如 Hbase,常常会禁用 Major Compaction,并在凌晨业务低峰期进行合并的原因。
ref:https://popesaga.github.io/2020/09/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%EF%BC%9ALSM%20tree/#%E5%86%99%E6%94%BE%E5%A4%A7%E3%80%81%E8%AF%BB%E6%94%BE%E5%A4%A7%E5%92%8C%E7%A9%BA%E9%97%B4%E6%94%BE%E5%A4%A7