常州语言网站建设中企动力天津科技有限公司
LSM是一种基于日志追加写的数据结构，非常适合为具有高写入数据提供索引访问
LSM基于以下前提
- 内存读写速度远高于磁盘，但内存有限
- 磁盘顺序读写速度远高于随机读写
结构
WAL
WAL(write-ahead log)是用于在系统错误时提供持久化，在写入数据的时候会首先写入到WAL文件中
Memtable
LSM中在内存中的数据结构称之为memtable，通常是红黑树结构。
SSTable
SSTable(sorted strings table)是在磁盘中有序字符串表。
过程
LSM是多层结构，在内存中的是C0层，保存了最近写入的数据。当C0层达到阈值后将合并C1层形成新的C1层，如此循环往复下去
查询
查询是从C0查起，逐层查
逐层查太慢了
可以采用稀疏索引来优化。
- 二分查找找到key的offset
- 根据offset找到相应的value
此外，还可以运用bloom filter过滤掉一定不在的key
写入
- 收到写请求，会将该数据记录在WAL(write ahead log，预写log)中，用于故障恢复
- 接着将该数据写入内存的memtable（为维持有序性可以在内存中采用红黑树或者跳表）
- 当内存memtable超过一定阈值，就会合并到SSTable
删除
每次删除时仅仅只是标记删除了，实际删除过程由后台进程compaction负责。
compaction会持续合并新旧segment
ref
- https://en.wikipedia.org/wiki/Log-structured_merge-tree
- https://medium.com/swlh/log-structured-merge-trees-9c8e2bea89e8
- https://www.cnblogs.com/zxporz/p/16021373.html
- https://yetanotherdevblog.com/lsm/