LSM-Tree全称是Log Structured Merge Tree，是一种分层，有序，面向磁盘的数据结构, 其核心特点是利用顺序写提高写性能, 但因为分层(内存和文件)的设计会降低读性能.
image.png
LSM由三部分组成

  1. MemTable
  2. Immutable MemTable

  3. SSTable

    MemTable

    MemTable是内存中的数据结构, 用于保存最近更新的数据, 会按照Key有序的组织这些数据, LSM树对于具体如何有序地组织数据并没有定义. e.g: HBase用跳跃表保证内存中key有序.
    因为数据暂时保存在内存中, 但断电会丢失数据, 因此一般会引入WAL保证数据的可靠性

    Immutable MemTable

    MemTable达到一定大小后会转换成Immutable MemTable. Immutable MemTable是将MemTable转换为SSTable的一种中间态. 写操作由新的MemTable处理, 转存过程中不阻塞数据更新操作.

    SSTable

    有序键值对集合, 是LSM树在磁盘中的数据结构. 为了加快SSTable的读取, 可以通过建立Key索引及布隆过滤器来加快Key的查找.
    image.png
    LSM树会将所有的数据插入、修改、删除等操作记录保存在内存中, 当此类操作达到一定量后再批量的顺序写入到磁盘中. 这与B+树不同, B+树数据的更新会直接在原数据所在处修改对应的值, 但LSM树的数据更新是日志式的, 当一条数据更新是append一条更新记录完成的. 这样设计的目的就是为了顺序写, 不断地将Immutable MemTable Flush到持久化存储而不用去修改之前的SSTable中的Key, 以此保证顺序写.
    因此, 当MemTable达到阈值Flush到持久化存储变成SSTable后, 在不同的SSTable中, 可能存在相同Key的记录, 当然最新的那条记录才是准确的. 这样设计大大提高了写性能, 但也带来了一些问题:

  4. 冗余存储: 对于某个Key, 除了最新的记录外的其他记录都是冗余的, 但这些记录仍占用了存储空间. 因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录.

  5. 顺序读带来的不确定性: 读取时需要从最新的倒查, 直到找到某个Key的记录. 最坏情况需要查询所有的SSTable, 这里可以通过前面提到的索引/布隆过滤器来优化查找速度

参考资料:
LSM树详解
深入理解什么是LSM
HBase中的LSM树