LSM Tree 作者:马育民 • 2022-11-25 17:30 • 阅读:10061 # 介绍 LSM Tree 是一种存储结构 起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》 ### 使用该结构的数据库 HBase、Cassandra、LevelDB、RocksDB # 写数据流程 [![](/upload/0/0/1IX4TklUMEVm.jpg)](/upload/0/0/1IX4TklUMEVm.jpg) 1. 当收到一个写请求时,会先把该条数据记录在 `WAL Log` 里面。可用作故障恢复。 2. 当写完 `WAL Log` 后,会把该条数据写入内存的 `SSTable` (删除是 **墓碑标记**,更新是新添加一条数据),也称 `Memtable`。 **注意:**根据Key有序地组织数据,为了实现排序,在内存里面采用红黑树或者跳跃表相关的数据结构。 3. 当 `Memtable` 超过一定的大小后,会在内存里面冻结,变成不可变的 `Memtable` ,同时为了不阻塞写操作需要新生成一个 `Memtable` 继续提供服务。 4. 把内存里面不可变的 `Memtable` 中的数据,写到硬盘上的 `SSTable` 层中,此步骤也称为 **`Minor Compaction`** **注意:**在L0层的SSTable是没有进行合并的,所以这里的key range在多个SSTable中可能会出现重叠。在层数大于0层之后的SSTable,不存在重叠key。 5. 当每层的磁盘上的 `SSTable` 的体积超过一定的大小或者个数,也会周期的进行合并。 此步骤也称为 **`Major Compaction`** ,这个阶段会 **真正的清除 标记为删除的数据,多版本数据的合并**,避免浪费空间 # 读数据流程 1. 当收到一个读请求的时候,会先在内存里面查询,如果查询到就返回。 2. 如果没有查询到就会依次下沉,直到把所有的Level层查询一遍得到最终结果。 ## 缺点 如果SSTable的分层较多,把所有的分层扫描一遍,效率低,性能差 ## 优化 1. 压缩。SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。 2. 缓存。因为SSTable在写入磁盘后,除了Compaction之外,是不会变化的,所以我可以将Scan的Block进行缓存,从而提高检索的效率 3. 索引,Bloom filters,正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,我们可以对每一个 SSTable 添加 Bloom Filter,因为布隆过滤器在判断一个SSTable不存在某个key的时候,那么就一定不会存在,利用这个特性可以减少不必要的磁盘扫描。 4. 合并。这个在前面的写入流程中已经介绍过,通过定期合并瘦身, 可以有效的清除无效数据,缩短读取路径,提高磁盘利用空间。但Compaction操作是非常消耗CPU和磁盘IO的,尤其是在业务高峰期,如果发生了Major Compaction,则会降低整个系统的吞吐量,这也是一些NoSQL数据库,比如Hbase里面常常会禁用Major Compaction,并在凌晨业务低峰期进行合并的原因。 参考: https://cloud.tencent.com/developer/article/1441835 https://zhuanlan.zhihu.com/p/181498475 原文出处:http://malaoshi.top/show_1IX4TmMoRDO9.html