会计师不使用橡皮擦，否则将入狱

不可变存储结构不允许直接修改记录，它会向文件追加一条新的记录。找到一个key对应的value，需要综合key所有修改记录。不可变存储结构，因为数据写入后就不会修改，具有并发安全性。对于b+ tree这种可变存储结构来说，每一次update都会找到磁盘上对应的记录，然后更新，磁盘io是随机的，因此新能较差，而类似于lsm-tree，所有的add、update都是向文件追加记录，不需要查找历史文件的记录，都是顺序io，所以写入性能较好。下面聚焦lsm-tree的两个问题：

• lsm-tree如何构建？
• 有哪些性质？

这里说的可变存储与不可变存储是指update操作是否会原地更新记录

LSM Trees（log-structured merge）

LSM tree 并不是一种树，LSM指的是一种思想，它将所以的修改以log的形式写入文件。由于写入到磁盘的文件不可修改，当文件数量较多时需要通过merge sort的方式合并文件，管理文件，回收磁盘空间。

因为文件不可变性，insert、update、delete不需要定位磁盘上数据记录的位置，没有随机的IO，可以极大的提高写入性能。这也会带来重复过时的记录，read会处理这些重复数据，只返回最新的数据。LSM tree非常适合于写远大于读的应用。除此之外，不可变的设计也是的存储引擎在并发的设计上比较简单高效。

LSM tree结构

LSM tree是由较小的内存table和较大的磁盘table组成，内存table作为写入的缓存，并对写入记录排序，然后flus到磁盘。
内存驻留的table被称作memtable，是可变的，它作为写入的缓存，并且服务一部分读操作。memtable的大小超过配置的阈值，就会被持久化到磁盘。内存中的数据在机器重启后就会丢失，为了恢复数据，需要将wirte操作记录写入（write ahead log） wal。在通知客户端写入成功之前，记录需要追加到wal file，然后写入内存。
所有的读写操作都会应用到驻留在内存的memtable，维护一个可并发访问的有序数据结构。
磁盘上的组件是由内存中的memtableflush到磁盘上创建的，只能用来被读操作，文件持久化之后，就不会被修改。

Multicomponent LSM Trees

LSM Trees由一个memtable 和多个磁盘table组成。系统经过一段时间的运行，磁盘上的不可变table就会越来越多。因为我们不知道哪个文件存储了我们想要的数据，一次查询操作可能需要访问多个文件，因此读操作的代价就会变高。为了缓解这个问题，一个称作compaction的周期性merge过程就会触发，读取多个磁盘table，合并数据，生成新的文件，旧的文件会被丢弃。

In-memory table

memtable使用大小阈值或者周期性触发刷盘操作。再刷盘之前，会有一些操作：

• 新的memtable被创建
• 写入操作会指向新的memtable，旧的memtable转变为flushing状态，这两部操作需要保证原子性
• flushing memtable继续保证可读直到flush完成。
• 旧memtable被丢弃，磁盘上新生成的table转换为可读

LSM component structure

update delete

LMS tree的insert, update, delete不需要在磁盘上定位记录的位置。而删除操作不能仅仅删除一条记录，因此磁盘或者内存驻留table会同时保存同一个key的记录。因此，删除操作是插入一条特殊标记的记录，表明该key之前的对应所有记录都是无效的,当然也可以通过谓词来标记删除记录。k2,k3这两条记录就会被屏蔽。
tombstone是compaction过程中保证正确调协数据很重要的信息。compaction 过程中，tombstone记录不会被直接丢弃，rocketdb会将其保存到最大level层的文件中，以确保不会存在其他记录。tombstone需要覆盖其之前写入对应key的所有记录

predicate

leveled compaction

lsm tree中有多种compaction策略，rocketdb使用的是leveled compaction。leveled compaction将磁盘驻留table分成不同的层次。level-0 table是memtable刷到磁盘生成的，因此内存中memtable中key的范围是不确定，用户写入什么key，范围就会发生变化，所以level-0 tables的key 范围是重叠的，level-1 及以上的table key范围都不会重复。merge一个level-0的table到level-1，可能需要读取所有的level-1的文件。
level-1 及以上的table的merge会选取当前level的一个table和下一个level key有重叠de两个文件，也有可能是多个文件，取决与key是否有重叠。

每一个level的table数量以及文件大小都有限制，一旦table数量超过阈值，该level的table就会merge到下一个level 可以有重叠的文件上。不同level 上的table 大小有指数级关系。

Apache Cassandra 实现了一种time window的compaction策略，对于时序数据负载，记录会存在特定的时间周期后就会失效。

read, write space 放大

当实现compaction策略时，我们需要考虑多种因素，其中一种便是回收被重复记录占用磁盘空间从而引起不断重写table导致的写放大问题。我们也可以避免持续的重写table,然而会导致读放大。

Sorted String Tables

磁盘驻留table通常使用 Sorted String Tables (SSTables)。SSTables重的记录是根据key来排序的，通常由两个文件组成：索引文件和数据文件。索引文件通常是由b-tree和hashtable来实现。数据文件中的记录都是有序存储的，虽然使用了hashtables来存储索引，但也不妨碍我们执行范围扫描，hashtables仅仅是用来获取数据文件中范围扫描的第一个key对应数据的位置。索引文件保存了key以及数据的在数据文件中offset.compaction过程不需要读取索引文件，因为数据文件中数据本来就是有序的。

Bloom Filters

LSM tree中查询一个不存在的数据会非常耗时，因为需要读取很多磁盘驻留的table。为了记录数据是否存在于LSM tree，rocketdb使用了Bloom Filters，bit array，可用来表示key可能存在，后者肯定不存在。Bloom Filters使用多个hash函数，计算key的哈希值，也就是位置，写入时在这些位置记录1，查询时使用相同的hash函数算出key的位置，判断所有值是否为1，只要有一个位置的值不为1，就说明该key不存在，但都存在时也不能说明该key一定存在，因为存储空间有限，hash函数计算的值可能存在碰撞. bloom filter