LSM Tree 笔记
写入（Write path）
先从磁盘（HDD）写入的特性引入 append-only 的 WAL。
对于 KV 结构，如果写入是 append only的，那么就需要合并，不然读取性能太差。
单文件合并性能差，因此需要按阈值切分为多个小文件，通过归并排序的思路优化合并的效率。
多路归并要求每个文件有序，为了保证每个文件有序，就需要，数据写入的时候，不直接把 operation 直接写入到磁盘，而是先在内存缓存一段时间，并且在内存排好序，然后再一次把整个文件 flush 到磁盘。
- 内存有序的数据结构：跳表、红黑树、B+ 树
- buffer 在内存的数据丢了怎么办？先写 redo log
有序数据结构
RocksDB 的数据结构比较：选择跳表的原因是跳表支持并发插入。
LSMT 的数据分类
- 内存数据：MemTable
- 磁盘数据：SSTable（Sorted Sequence Table）
- 日志：redo log
内存数据组织
内存的数据需要保证有序，同时支持高性能的插入和查找。
- ART：自适应基树（比如 Bitcask 采用）；
- SkipList：LevelDB、RocksDB 等。
SSTable 文件格式
按 Block 进行存储，可以参考 LevelDB 和 RocksDB 的 SST 文件的格式。
Compaction
- Leveling compaction
- 当某个 level 出现一个新的 sorted run 的时候触发；
- 每一级的文件只会组成一个 sorted run，也就是说不同文件的 key range 不会重叠；
- 写放大较大，但查询性能好，适合写少读多的 workload。
- Tiering compaction
- 当某个 level 的 size 达到阈值时触发；
- 每一级可能存在多个 sorted run；
- 读放大和空间放大小，但 compaction 开销大，适合读多写少的 workload。
对于 tiering 和 leveling 的比较，我们可以考虑一种极限情况：只有一个 level。此时 tiering 变成一个 append only 的 log，每次产生一个新的 SST 只会 append 到 SST file queue 末尾，这种情况下写性能较高因为 flush 不涉及到已有的 SST，而读取性能则较差，因为有可能需要遍历所有的 SST。而 leveling 要求一层内只有一个 sorted run，因此会变成一个 sorted array，每次 flush 都会导致现有的 SST 被完整重写以排序，因此写放大较大而读性能好。
- 事实上工业级的 LSMT 往往会采用混合策略，比如 RocksDB 在 Level 0 使用 tiering compaction 以提高写性能而在其他 level 使用 leveling compaction 以提高查询性能。
读取（Read path）
核心原则：先热后冷读取最新的数据，一旦读取到就停止。
- 优先读取 MemTable，然后读取 SSTable
读取的优化
- 通过 BloomFilter 优化不存在的数据的判断
- SSTable 分区
- 压缩
LSMT 的问题
读放大
一次 key 的读取需要由新到旧依次读取，涉及到不止一次IO，在范围查询的时候尤其明显。
写放大
后台合并（compaction）导致一个文件可能需要被写入多次。
空间放大
Append-only 导致过期数据一致存在，直到被清理
总结
- 写放大：尽管 LSM Tree 通过顺序 IO 提供了更大的写入吞吐，但是写入放大的问题会争抢正常写入的磁盘带宽，从而降低性能和磁盘的使用寿命。
- 合并：后台的合并操作导致 write stall
- 新硬件：Remote compaction，Compaction offloading，AEP
索引存储
- 索引不存储
- buntdb：每次重启重建
- 索引存储
- 分离存储
- Bitcask
- MySQL MyISAM
- 一起存储
- BoltDB
- MySQL Innodb
- LevelDB (SStable)
- 分离存储