看过 LSM-Tree 论文的都知道这个存储引擎最核心功能就是 SSTable 层次划分和多个 SSTable 压缩操作，本文将针对两个问题进行深入剖析相关实现的细节和一些容易出现问题的地方；如何划分多个 SSTable 层次关系？如何进行多SSTable 合并？并且如何解决数据版本和操作写入一致性问题？针对这些问题怎么做怎么解决？还有被标记📌为删除过期的记录存在多文件数据版本冲突问题，我看某些基于 LSM-Tree 实现的数据库是在第一次合并的时候遇到被标记的就删除完全没有考虑到多数据版本和写入时间顺序一致性问题？那样做起来我个人感觉是非常不严谨的做法。可以看看业界一些主流的基于 LSM-Tree 实现的数据库是怎么做的，本文将继续探讨这方面问题。
RUM模型
Read-Updated-Memory 分为存储的读、写开销和内存占用开销比例模型，RUM猜想指出如果要设计一个存储相关应用程序首先是考虑读和写请求处理的速度，还有内存占用率；最理想的状态是最小的化读取开销，还能保证小的写入开销且内存占用也很低，这在现状的存储架构来说几乎是不可能的，想要优化某参数就必须牺牲另外一个参数为代价，所以设计一个存储系统必须要考虑这些因素。
层次划分
由于 LSM-Tree 的核心就是以追加的方式进行数据操作记录，因为是增删改查的操作都是以追加的方式进行的，这时对硬盘容量就提出了要求，必须设计一个能自动回收无效的数据的算法来解决这个问题。压缩操作在目前主流实现分为两种，第一种为 Leveld Compaction 的层次划分方式，第二种为 Size-Tiered Compaction 的大小划分方式。
层次划分： 针对磁盘上的 SST 文件进行等级划分，分为多个等级的文件组，每组都有文件个数限制并且都有相应的 SST 文件的编号，这些编号都是从上往下的，高层次都在底层，而低层次的在高层；每层次文件达到阀值时会挑选几个文件与其高一层的文件进行合并，合并过程可以是并行执行多个文件的层次的，但是注意不要交集执行，那样会数据出现重复压缩情况。压缩会不断排除掉一些重复的记录，注意这里不是指被删除的记录！当压缩完成之后会生成 SST 文件放入高层次中，被压缩的旧文件会被清理掉，这样最新的数据在最低层上，而老的数据在最高层上，就减少了查找数据时要读取多个 SST 文件的情况，并且新数据会处于文件尾部，而读取操作是从文件尾部倒着开始读的，所以新值一定会最先被读到；但是每层的多个 SST 文件相互之间是无序的，所以需要进行层次之间排序：下图就为并行合并压缩情况示意图：
那怎么选择每层和下一层合并的文件进行合并？例如第一层容量为3，下一层容量为4，我这里层次容量公式是i * 3 / 1.5 + 4，假设经过什么的公式推算出了的4层架构是：
Level 0 ： size = 4
Level 1 ： size = 6
Level 2 ： size = 8
Level 3 ： size = 10
Level 4 ： size = 12如果单个文件大小为 1GB ，那么最后一层可以存储 1GB * 12 的旧数据，对应一个普通型的存储还是完全是够的，如果不够还可以进行添加层次。怎么挑选文件呢？这里我以每层顺序方式进行的，当某个文件被选择中，内存中的压缩器会记录这些文件排除被交集并行重压缩的可能。
文件大小划分： 这种方式针对每个 SST 文件按照自身的体积进行划分的归类的，也是基于大小规则但是针对是文件大小，较小的文件和较小在一起，而较大的文件和较大放到一起；例如较低层的表是内存表刷入进来的，也有可能其他大表经过压缩而降级移动过来的。但是弊端也是有的被压缩之后还是很小，数据记录由于墓碑遮蔽了没有合并写入到表里，这样导致合并算法一直在处理小 SST 文件，而高层的 SST 文件墓碑却一直不能被回收的情况，导致出现高层次表饥饿的情况，这时就不得不采用强制执行压缩，过程示意图：
两种方式只是针对 SST 文件如何管理做了相应的划分，按照层次划分的话每层文件都有序号最新的数据在最底的层次之上；按大小划分最新的数据在 SST 文件大小最小的文件身上，老数据在大文件身上；因为是随着时间的顺序数据跟着变化的，如果外部频繁删除请求说明对文件压缩的准确度来说不需要那么准备无误，因为频繁删除键记录说明老的数据文件里面的脏数据越多，大概率清理即可，针对这种时间变化的时间 Apache Cassandra 是用了一个滑动窗口的算法进行定期压缩 SST 文件。
脏数据剔除
由于删除记录也是通过添加的方式进行的，就会带来另外一个问题，数据记录怎么删除？官方论文解决方案是通过添加一条🪦墓碑记录来完成删除记录操作，也是最新的查找的数据记录从最低层往最高层次查找，如果发现记录被记录为 tombstone 状态则说明这条记录已经被删除直接返回查询请求即可；但是另外一个问题压缩器如何解决被墓碑标记的数据重复记录问题？先写入的请求可能在多个 SST 文件的数据存储着，而删除墓碑可能在最新层次存储着，垃圾回收器如何工作？如果垃圾回收器删除过早你会将其他还存储数据文件中的记录死而复生，不删除又导致写放大和读放大问题？压缩合并是从底层开始还是从高层开始？是从 SST 文件前面开始还是从后面开始合并？还有排除被数据的记录，在不同层次 SST 文件重复的数据记录怎么办？怎么清理保留唯一一个记录？
我看到市面上有一部分的 Github 开源项目只做了第一步就是踢除被删除的记录，而且并且踢除功能实现还很简单就遇到被标记的记录就不进行合并就可以了，这种做法我不清楚他们的实现者有没有考虑到没有合并只是当前删除的记录，而与其键同名的老记录或许在其他文件中一直存在，这是一种严重不合符合逻辑的做法且是错误的！
在 Compaction 最重要的一个环节就是如何解决同一个键相关联的数据记录的协调和冲突解决方案，怎么设计合并算法来解决单键多记录问题，从而让无用的记录被丢弃只保留最新的记录，最理想的设计方案如下图所示：
注意这里高层是往下走的等级越高，越上层越等级越低！
按照推理逻辑来说，如果按照写入记录前后顺序的话应该是从高层次开始取记录合并，因为高层次的记录是老记录，而底层的是新记录，这样拿取就是还原整个数据记录的写入过程，在内存中重放这些操作，最后内存表中剩下的就是被合并的数据记录，在写入到新 SST 文件中，放入下一层。
很多论文里面称之为upsert操作，也就是在内存里还原一次在过去某个时间段内的所有数据操作，但是之后保留在最后一次操作的记录数据，然后将其写入到新的文件中，而老的脏数据会被丢弃，但是这种要注意的是墓碑记录要一直保留到最高层，直到最高层没有数据时即可删除掉，因为每层合并只是2个层次的合并，不能保证更高层次的数据记录没有被标记删除，我称之为墓碑下沉操作。
上面的方式为普通的做法需要在内存中全量加载数据记录做重放，需要一定内存空间占用，这时我们就需要另外一种固定大小内存排序方案。这里我要介绍就是通过优先队列来做的，固定优先队列元素个数，这个总个数对应就是输入源个数，具体做法可以查看上一篇文章。因为每个 SST 文件里面数据都是不重复的并且是有序的，所以这里使用优先队列优势就出来了，我们只需要在内存维护一个小顶堆就可以排序临时从多个 SST 文件输入的数据，输出一个合理的值到新的 SST 文件中。
因此合并迭代的时候需要从多个数据源中合并数据，难免会出现同键多数据记录版本情况，这时就需要做出协调，从多个数据版本挑选出最新版本，具体怎么做可以自定义实现，在输出记录的同时要在内存中维护一个新的稀疏索引来记录每条数据记录大小，最后写入到 SST 文件末尾，版本冲突解决我这里给出几个方案：
- 因为每个 SST 文件是代表着一段时间的内存快照，这时在合并的时候先区分每个键来自哪个 SST 文件，底时间窗口的不用比较直接覆盖高时间窗口的段记录。
- 因为每次元素添加到优先队列中需要看是否存在同名的键，同名了就可以比较这个键时间戳，高时间戳遮蔽底时间戳记录。
- 因为磁盘分层表能在逻辑上形成一个环形表结构所以最终数据会不断合并重整，最后留在磁盘肯定是活跃的键值记录。
我看到很多第三方资料也是说删除数据记录就是添加一个标记，下次合并的时候直接过滤掉此记录就可以，这时一个严重的问题并且估计某些作者也没有深入研究过 LSM-Tree 具体实现细节。一个键可能在 24 小时内能被操作N次，其中老的数据记录肯定在高层存活着，那么下次查询的时候旧记录不就复活了吗？而且也不能保证前一个请求刚刚删除，下一个请求就重新写入一个同名键数据记录情况，这也就是为什么我所说墓碑要操作做下沉操作；而不是一次层次合并遇到墓碑就扔掉就行了，某些文章的作者逻辑也没有考虑到这一点，只是“强不知以为知”的把东西拼凑出来而已，没有思考问题本质在解决什么问题🤔。
Wisckey存储
上面的 LSM-Tree 删除数据要通过标记一个墓碑来删除数据记录，这种方式删除可以不需要关心索引问题和数据记录关系；而另外一个演进的版本是 Wisckey 的方式，类似于 Bitcask 那样把索引存储来内存中，但是实际数据记录存储在磁盘表中，唯一的区别就是键在内存中是排序的，而数据记录则像 Bitcask 那样无序存储，内存索引组织方式类似于 LSM-Tree 那样，但是会通过指针指向磁盘实际的数据记录，如下图：
相比 LSM-Tree 去删除一个记录要标记然后等着被压缩回收记录空间的做法，Wisckey 的删除方式很简单只需要在内存排序表中删除键和映射指针即可，而更新记录则追加一条记录然后将其内存表指针更新到新记录上即可，之前老记录等着后台 Compaction 扫描去完成压缩，但是会对内存表临时加锁影响外部并发读写请求情况，和编程语言中的STW一样。
这里笔者针对这个问题要采用小范围子树扫描清理法，每次 Compaction 只扫描内存表一部分键而不是全部，如果是全部会导致长时间外部写请求阻塞情况，或者先对冷数据键进行清理。
其他的问题
关于实现LSM-Tree有很多细节要考虑的问题，例如我下面整理的一些问题：
- 程序在合并的多个 SST 文件时突发一些环境因素导致关闭，此时内存合并表丢失，但是磁盘上有写到一半残留的SST文件怎么搞？
- Minor Compaction 和 Major Compaction 前后顺序是怎么样的？如果是二者并行合并文件，怎么避免冲突？
- SST文件的稀疏索引存放单独文件好还是直接添加到尾部好？
- 如果最高层合并出现了文件个数超出限制情况该如何处理？是调整当个文件大小？还是将其本层多个文件合并成一个更大的文件？
- 批量删除某个范围的键记录怎么做才最高效？例如删除K2至K5之间的数据记录，该如何做？
