Tutorial: Dissecting, Designing, and Optimizing LSM-based Data Stores
一篇 tutorial 性质的论文，主要介绍 LSM 的基本原理、存在的优化空间和目前已有的优化技术。论文主要内容分为三个部分：
- LSM Basics. 介绍 LSM 的基本原理。
- Optimizing Ingestion. 介绍优化写性能的具体策略。
- Tuning and Navigating the LSM Design Space. 分析了 LSM 策略的设计空间。
LSM Basics
LSM 概念
LSM-tree: Log Structured Merge tree
用户逻辑视角上看，LSM 是一个提供索引服务的结构。LSM-tree 存储着一系列的 key-value 键值对数据，用户可根据 key 对数据项进行 get, put, update, scan 等操作。（通常 LSM-tree 结构里存储的数据项会被排序）
物理组织上看，LSM-tree 由两大组件组成。
- 位于内存: 某种数据结构 (比如跳表，各种排序树，vector, hash-skiplist, hash-linkedlist, 视场景的 workload 而定)
- 位于硬盘: 类似的结构但存储空间更大。硬盘中的数据都来自内存，即蕴含着某种层级关系。 如果 LSM-tree 结构共有 L 层，通常内存存储 Level0 层的数据，硬盘存储 Level1~LevelL 层数据。
LSM-tree 基本运作原则
批量写：任何写操作（插入、删除、更新）都会先记录到内存的某个数据结构即 Level0，当它容量到达上限时，LSM-tree 会根据 key 排序将内存中的数据转移到硬盘上。
Out-of-place 更新和删除 ：更新和删除操作都视为插入操作（即一个数据实体在 LSM-tree 中可能存在多个版本，只需内部有策略维护其逻辑关系即可），相比原地更新删除的策略，out-of-place 可以提高吞吐量，不会产生 write stall. （不需要定位到实际的数据项所在的磁盘/内存位置，只需在内存中添加一个数据项即可）
// TODO:
- 多个版本 -> 不存在锁争用？
- 插入/更新/删除数据时，在内存中操作 memtable，是对整个 memtable 上锁？
不可更改的文件结构：LSM-tree 在硬盘上维护不可更改的（immutable）并且有序的文件。为了提高磁盘利用率，文件内部，LSM 中的数据项紧密得存储在一起。
定期重新组织数据分布：磁盘中有多个层级，LSM-tree 为每个层级分配以指数形式增长的最大容量。当某一层的数据量达到容量限制时，该层的数据（可能是所有数据也可能是一部分）会和下一层 key 范围有重叠的数据进行 sorted-merge。这个数据重新分布的过程叫做 compaction。
// TODO:
- LSM-tree 要求每一层的数据结构内部有序存储数据项吗？
LSM 不变量：Level i 的数据总是比 Level i+1 层的数据新。该性质一直都存在。