Log Structure Merge Tree

LSM是一种基于日志追加写的数据结构，非常适合为具有高写入数据提供索引访问

LSM基于以下前提

• 内存读写速度远高于磁盘，但内存有限
• 磁盘顺序读写速度远高于随机读写

结构

WAL

WAL(write-ahead log)是用于在系统错误时提供持久化，在写入数据的时候会首先写入到WAL文件中

Memtable

LSM中在内存中的数据结构称之为memtable，通常是红黑树结构。

SSTable

SSTable(sorted strings table)是在磁盘中有序字符串表。

过程

LSM是多层结构，在内存中的是C0层，保存了最近写入的数据。当C0层达到阈值后将合并C1层形成新的C1层，如此循环往复下去

查询

查询是从C0查起，逐层查

逐层查太慢了

可以采用稀疏索引来优化。

1. 二分查找找到key的offset
2. 根据offset找到相应的value

此外，还可以运用bloom filter过滤掉一定不在的key

写入

1. 收到写请求，会将该数据记录在WAL(write ahead log，预写log)中，用于故障恢复
2. 接着将该数据写入内存的memtable（为维持有序性可以在内存中采用红黑树或者跳表）
3. 当内存memtable超过一定阈值，就会合并到SSTable

删除

每次删除时仅仅只是标记删除了，实际删除过程由后台进程compaction负责。

compaction会持续合并新旧segment

ref

1. https://en.wikipedia.org/wiki/Log-structured_merge-tree
2. https://medium.com/swlh/log-structured-merge-trees-9c8e2bea89e8
3. https://www.cnblogs.com/zxporz/p/16021373.html
4. https://yetanotherdevblog.com/lsm/