文章目录
春节要开心过，同样也要充实过。这篇论文解决你对LSM-tree的理解不透彻、优化无从下手、业务该如何选型不知所措等疑难杂症，让你对NoSQL 的理解跨越千山万水。更主要的是希望能够让更多对LSM-tree感兴趣的同学有一个快速入门并深入理解的途径，欢迎一起讨论。内容较多，可选择性阅读/精读。
本篇中的相关论文大多均已收纳到github中：LSM - 优化汇总。
这篇文章的目录架构如下：
1. 概要
LSM-tree(Log-Structured Merged-tree) 现如今已经被广泛应用在了各个NoSQL 存储系统中，包括BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB 和 AsterixDB之中。相比于传统的in-place updates 索引结构，LSM-tree 将第一次写入都缓存到内存中，并通过后台的flush来顺序写入到磁盘中，也就是out-of-palce updates。 LSM-tree这样的实现方式有非常多的优点，包括写性能的提升、较高的空间利用率、简单的并发控制和异常恢复等。这一些优点能够很好的支持很多大型的workload形态，就像Facebook开发的基于LSM-tree的存储引擎 rocksdb 被广泛应用在了实时数据处理，图数据处理，流式数据处理 以及 OLTP(on line transaction processing) 等多种workload。
当然，相比于传统in-place updates 存在众多的优点的同时也会有不少缺点，但人家对很多workload友好，也不会妨碍LSM-tree 这样的架构被广泛应用。很多学术界和工业界 也都基于LSM-tree做了很多优化上的研究，并且这一些研究针对LSM-tree各个维度有各自的落地实现，所以今天分享的这一篇论文的核心并不是分享一种优化方法，而是将到现在为止(2020年) 之前学术界和工业界真对LSM-tree的开源优化实现做个汇总，来指导后续大家在LSM-tree上的持续研究，可以说是站在巨人的肩膀之上了（大部分的优化实践都被各个顶会收录）。分享的优化主体是几个非常有代表性的开源实现NoSQL系统，包括但不限于LevelDB, RocksDB, HBase, Cassandra 和 AsterixDB。
希望后续的分享大家各持所需，会以LSM-tree 的几个优化方向为主体 概要介绍非常多的优化系统，很多系统的详细设计细节需要大家去读论文/读代码/测试 之后才能有更加深刻的理解，从而选择适合自己业务workload的优化。
2. LSM-tree 概览
考虑到读者不一定都对LSM-tree有深刻的理解， 这里先做个LSM-tree的基础知识分享，主要包括以下三部分内容：
- LSM-tree的发展历史
- 基本设计架构
- 读/写 时间复杂度 和空间复杂度
2.1 历史中的LSM-tree 演进
首先要从索引结构更新的两种方式说起，一种是in-place updates, 另一种是out-of-place updates。
-
In-place updates 会直接通过新的数据覆盖写旧的数据，来达到数据更新的目的。比如：B+ -tree 索引。
比如下图(a)：将(k1,V1) 的value v1更改为v4, 则直接覆盖修改就可以。
-
Out-of-place updates 会追加新的记录，而不是直接覆盖原有记录。比如: LSM-tree
由以上两种数据更新方式，我们能够看到一些两者的对比差异：
- B±tree 这样的更新方式对读友好，因为不论怎样读到的数据一定是最新的，不需要像LSM-tree 不断更新追加，在读的时候需要扫描到最新的记录才行
- B±tree 因为覆盖写方式， 在更新/删除 场景会造成一些空间碎片（不断的更新会有B±tree的分裂），从而一定程度降低了B±tree的空间利用率；当然LSM-tree传统实现则有空间放大问题，旧的数据得不到及时清理，仍然消耗存储空间。
LSM-tree 这样的out-of-place updates 思想并不是现在最新提出的思想，在上世纪70年代以后已经被成功应用在当时的数据库系统中。
-
1976年实现的一个
Differential files系统就是应用了out-of-place updates思想的早期实现。在这个系统中，所有的更新会优先写入到一个defferential file中，后续该文件每隔一段时间会和main file合并。 -
1980年以后
Postgres项目率先提出了Log-structured 形态的数据库存储。Postgres会将所有的写入都追加到一个顺序性的log中，并且实现了快速查询和基于时间戳的查询方式(类似于snapshot，读某一个snapshot时只能读到基于当前snapshot之前的数据，而之后的无法读到)。这个系统使用了被称为vacuum cleaner的后台进程去持续得做垃圾回收，清理sequential log中的过时数据。而
Postgres这样的实现思想也被LFS（Log-Structured Fils System）这样的文件系统采用，用来提升磁盘带宽的利用率。
因为之前的这一些实现中并没有对LSM 架构做系统的性能分析，也没有抽象出一个模型来指导如何在读/写和空间利用率上做trade-off，也就导致了LSM 架构很难调优。大家也都只看到了LSM架构的关键问题：append-only 带来较差的读性能 和 较低的空间利用率，也就导致了大家普遍认为LSM 的架构是系统的瓶颈。
直到 LSM-tree 架构在1996年[1] 被正式提出，将这一些问题做了汇总并设计了一个合并进程，也将LSM-tree架构集成到其中，并且能够提供 较高的写入吞吐、基于边界的高效查找 、友好的空间利用率。这个LSM-tree的设计原型 顺序包含如下几种组件：
从c0,c1…,ck，每一个组件都是使用B±tree来实现的，其中C0在内存中，其他C1…Ck在磁盘上，当Ci满的时候，会触发合并进程将一个范围内的B±tree的leaf node合并到Ci+1中。
显然以上架构 并不是今天的LSM-tree架构，因为它的每一个组件通过B±tree来实现，复杂度较高。但是这个原型论文中提出的一个设计思想对现如今的LSM-tree架构以及在其上的优化带来很大的提升。原型中抽象出来一个模型，其中提出了在一个稳定的workload下，保持LSM-tree的层数不变，当每一层的大小比例 TiTi = |Ci+1|/|Ci| 在各个层之间维持一个稳定的值时， 写性能能够优化；当然原型论文中有详细的证明，最主要的是这一篇论文起了一个真对LSM-tree的性能模型抽象的开端，从而为后续的LSM-tree的设计提供了基础。
与此同时 另一个LSM-tree的架构[2]提出了一个逐步合并的类似方案 来提升写性能。它将各个组件组织成一个个Level形态，每一个level内有多个组件(B±tree 实现)，当level L 满了之后，其里面的T个组件(类似现如今的sstables，这个实现中应该叫做B±treetables)会一起合并成一个新的组件，并且输出到L+1层。这种逐步合并的方式也是现如今的tiering merge policy ，应用到了今天的LSM-tree的实现中。
2.2 今天的LSM-tree形态
2.2.1 基本架构
今天的LSM-tree架构仍然以out-of-place updates 为主 通过顺序I/O来提升写性能。所有的写入 都会追加到内存中的组件，不论是更新还是插入还是删除，都会以一个新的记录添加到内存中。
内存中的组件主要由sikplist组成，也可以由B±tree。磁盘上还是分层存储，每一层内包含多个小的组件，由B±tree 组成或者 sstable组成。如果是sstable，则会将key-value组织成一个一个datablock ，并为一个sstable建立一个对应的index block。
之前LSM-tree存在问题仍然存在， 读性能 、 写放大 以及 空间放大问题都存在，读性能 和 空间放大问题之前已经有过描述。
关于写放大的问题主要是由level 合并过程带来的：
在LSM中是compaction过程带来的一个非常严重的问题，需要将相同的key-value反复读取写入多次，会对SSD的寿命产生非常严重的影响，同时也会导致过多的系统硬件资源被消耗（读取和写入都会有CPU和IO的消耗）。
简单描述一下：
上图中灰色的部分是参与compaction的六个SST文件，三个来自L0，三个来自L1，都是key的边界有重叠的SST文件。
L1的文件是从L0 compaction下来的，所以这里统计L1文件的重写次数 已经是1次了。
compaction挑选文件规则：
- 为L0整层维护一个socre, 大于L0之后每一层的每一个sst文件维护一个score。
compaction 开始会选择一个score大于1的文件,如果有多个文件大于1 则选择分数最高的- 拿着选择的文件 先和当前层的文件进行比对，如果当前层有重叠则将当前层的文件选择上，同时选择的文件也会
和下一层所有的SST文件进行key边界比对，有key 范围重叠的，则下一层的文件也会被选择上参与compaction
如上L0 + L1 选择的文件范围是[1…68]，将选择的文件中的key-value读取到内存，一边读一边merge，将最终的key-value按照SST文件的限定大小写入到L1，结果如下：
此时L1 中key-value的重写次增加了一次：读到内存，没有做任何修改，又写入到了L1
随着上层IO的持续写入，L0又达到了可以进行compaction的限制（level0_file_num_compaction_trigger），又开始和L1进行comapction，又恰好和L1中的key 的范围重叠。
同理，L1 中可怜的key-value又被折腾了一轮，内容原封不动还了回去（key: 我容易吗，这样真的好玩吗。。。；LSM：。。。 (沉默) ）
2.2.2 著名的优化手段
接下来介绍有两个著名的LSM优化手段，而且在现如今的LSM-tree的实现中都已经合入了。
-
Bloom Filter 【3】, bloom 过滤器时一种空间高效的概览数据结构，核心目的是为了判断一个模式串是否在一个字符串内。
支持两种操作，插入一个key，从给定成员中查询一个key。
- insert key时，需要多个hash函数将key的字符内容映射到bit为单位的多个向量中，并且将这一些向量中的bit位置1。
- search key时，同样适用hash函数对给定的key求hash值，如果最后的结果映射到多个单位向量中的对应bit位为1，则会返回这个key可能存在；假如hash值映射的结果有一个向量的bit位为0，则一定能够确定这个key不存在。
Bloom filter能够极大得提升点查性能，而且针对一个LSM level内的一个组件(B±tree table/ sstable) 构建对应的bloom filter并不会消耗过多的存储空间，bloom filter每次生成组件的时候进行持久化，读对应组件的时候加载到内存中，这样并不会消耗过多的磁盘I/O，且对点查性能有非常大的帮助。
-
Partitining. 这个优化说白了就是将之前LSM 磁盘包含一个大key-range 的component 拆分成更小的分区。比如Rocksdb/LevelDB中实现的sstables，就是将较大的分区拆分成较小分区的案例。
以下将component 统称为sstable，更加易于理解一些
这个优化能够带来如下几个优点：
- 降低了每一次 sstables合并的开销，比如 256M大小的sst table 之间进行合并，需要消耗更多的排序时间和更多的临时存储空间。而换成一个比较合适的64M（当然这个数值其实也是经过不断的测试摸索的），降低单次合并的排序时间和临时空间的消耗，从而更容易控制sstables之间的合并。
- 一定程度降低写放大，减小了合并的工作负载。如果sstable大小合适，仅选择有key-range重叠的sstable来合并，这样不会消耗过多的I/O和CPU，每一次选择的sstables之间没有重叠key的比例就更大一些，来让每一次的合并效率更高。比如256M的sstable 之间的合并，每次重叠key也就占20%，剩下的80%的key就会被读上来再写下去，一定程度增加了工作负载；但是将256M减小到4M，那每一个sstable的无效key的比例会降低（仅选择重叠key的sstable来进行合并）。
后续描述的很多NoSQL系统都会在合并(compaction)部分做相关的优化，虽然是后台操作，但是在不同的workload下对系统性能还是有 不同的影响。
2.2.3 并发控制和异常恢复
简单对现如今的LSM-tree实现中的并发控制和异常恢复技术做一个介绍。
并发控制 在LSM-tree的体现就是 当多个客户端同时触发读/写时，LSM-tree的实现如何保证数据的一致性。LSM-tree普遍时通过锁模式 和 MVCC（multi version concurrent control）来实现类似于数据库中的隔离性。并发控制使用锁的话主要用来解决worklaod有写的冲突，比如读写，写写，写读 这样的。而同样LSM-tree的架构也非常方便得支持MVCC，每一个更新都会追加一条记录，对于同一个key的更新会有多个版本存在，通过后台的合并线程来进行垃圾回收。并发的flush和merge 操作则对于LSM架构师唯一的，也就是一个lsm-tree引擎可以并发调度多个版本的key，但是只能调度一个flush或者merge，因为这两个操作涉及LSM-tree内部各个组件的元数据，需要保证严格一致性。
eg: 你总不希望刚才删除的key-value又出现在引擎中吧。
MVCC 来保证读之间的隔离性，其内部会为每一个更新的key打入一个snapshot(类似于时间戳)，读的时候指定想要读的时间戳，那么只会读到这个时间戳之前最新的数据，从而达到隔离性的目的。
异常恢复 主要是LSM-tree架构所有的写入都是先写入内存组件，需要保证服务器异常之后内存组件中的数据能够被恢复回崩溃之前的状态。主要的实现是通过Write-Ahead-Log(WAL)机制。数据的写入是事务方式写入的，在内存中的组件不断接受写入，当所有活跃写事务都已经完成提交时才会flush，也就是内存组件崩溃的时候不一定所有的活跃事务都完成提交。这个时候通过WAL redo 时仅需要从崩溃的事务开始进行提交即可，之前说过LSM-tree的并发控制机制 会通过为多版本维护各自的时间戳来实现，这个时间戳也就是WAL重放时的事务标识，从指定的时间戳之后的事务崩溃时没有提交，WAL redo时仅需要从这个时间戳开始就可以了。
每一次重启之后完成所有未提交的事务的redo，则将当前WAL文件标记为delete，等待后续和过时的sstable一起被清理掉 – leveldb/rocksdb 的实现。
2.3 复杂度分析
为了帮助大家理解LSM-tree的性能，这里会将整个性能分析拆分为如下几个方面：
- 写入
- 点查
- 范围查找
- 空间放大
写入和查找的复杂度 是通过计算磁盘I/O来分析的，接下来的分析会以为拆分component的场景来进行，也就是这个场景是LSM-tree的性能最差的场景。
如下几个变量：
- LSM-tree Li 的大小和Li+1层的大小比为：
T - LSM-tree 总共的层数:
L - 每一个内存数据页能够保存的数据条目:
B - LSM-tree 内存组件总共有数据页个数:
P
由以上变量进行计算可以得到如下几个公式：
-
内存组件的总数据量: B*P
-
level(i) i>=0, 的数据量为：T^(i+1)*B*P。 level(0) = T*B*P; level(1)=T*T*B*P…
-
假如整个LSM-tree有N个entries，则这一些entries 最多能到的层数如下：
L = ∣ log T ( N B ⋅ P ⋅ T T + 1 ) ∣ L=\lvert{\log_T{(\frac{N}{B\cdot{P}} \cdot {\frac{T}{T+1}})}}\rvert L=∣logT(B⋅PN⋅T+1T)∣
关于这个公式的推导，也就是 从内存组件 一直加到Li 做成一个等式即可：B ∗ P + T ∗ B ∗ P + T 2 ∗ B ∗ P + . . . + T L + 1 ∗ B ∗ P = N B*P + T*B*P+T^2*B*P + ... + T^{L+1}*B*P = N B∗P+T∗B∗P+T2∗B∗P+...+TL+1∗B∗P=N
非常明显的一个等比数列求和公式，最后能够得到L的一个值如上。
2.3.1 写入性能分析
写入性能主要通过分析对于一个entry插入到LSM-tree时产生I/O开销，这个I/O开销还需要将写放大考虑进来。一个entry从写入内存组件到参与每一层的合并 直到最后一层，这个过程每一次合并都会产生对应的磁盘I/O开销。
- 对于Leveling 合并策略（从Li和Li+1层选择有重叠的组件参与合并，将合并后的结果写入到Li+1)， 一个key-value在每一层会被合并T-1次，直到层满被写入到下一层。
- 对于Tiering合并策略（从Li中选择有key重叠的组件进行合并，将结果写入到Li+1），显然一个key-value在每一层仅仅只会被合并一次就会被写入到下一层。
因为每一个磁盘页能够存储 B B B个条目，对于每一个key-value，在Leveling场景，写入消耗 O ( T ∗ L B ) O({T}*\frac{L}{B}) O(T∗BL)；Tiering 消耗 O ( L B ) O(\frac{L}{B}) O(BL)。
简单来说 在Leveling场景，写入代价与 层数和每一层的大小比强相关；在Tiering场景 仅于层数相关，显然Tiering的合并策略写放大更低。
2.3.2 点查性能分析
点查性能与LSM-tree中的组件个数强相关。
- 在没有Bloom Filter的加速下，查找代价对于Leveling策略是 O ( L ) O(L) O(L)，对于Tiering策略是 O ( T ∗ L ) O(T*L) O(T∗L)，因为Tiering策略允许每一层的key-value之间有重叠，且每一层的大小是上一层的T倍，相比于Leveing每一层重叠的key多了T倍，显然Tiering 的查找效率会大大降低。
- 有Bloom Filter加速的情况写，假如 Bloom filter有M个bit位，且在LSM-tree中每一层的误报率都一样。总共有N个keys的场景下，bloom filter的误报率为 O ( e − M N ) O(e^-\frac{M}{N}) O(e−NM)【3】（论文中有相关的证明），因此对于 Leveling策略其查找时间复杂度为 O ( L ∗ e − M N ) O(L*e^-\frac{M}{N}) O(L∗e−NM)，对于 Tiering策略 的查找耗时为 O ( L ∗ P ∗ e − M N ) O(L*P*e^-\frac{M}{N}) O(L∗P∗e−NM)，而在实际场景中，误报率会非常低 （rocksdb6.6 版本优化后的fullfilter 在16bits的配置下能够提供小于0.001的误报率，随着位数的增加，误报率线性降低），所以这个时候不论Leveling还是Tiering策略 点查性能都接近于 O ( 1 ) O(1) O(1)。
Rocksdb6.6实现的 fullbloom filter能够提供如下的误报率：
比如0.001的误报率，1000个keys 中 有1个不存在的key，会误报为true。
后续的RangeScan细节性能 分析大家可以参考一下论文 2.3节的第五段。Bloom filter对Range性能的提升意义并不大，所以对于Leveling 和Tiering策略，分别是 O ( L ) O(L) O(L)和 O ( T ∗ L ) O(T*L) O(T∗L) 的查找时间复杂度。
2.3.3 空间放大分析
空间放大问题在LSM-tree中显而易见，因其本身out-of-place updates方式 导致多版本的数据得不到及时的清理。
对于Leveling合并策略来说，最糟糕的情况是所有的数据集中在前 L − 1 L-1 L−1层，也就是真实数据仅占总数据的 1 T \frac{1}{T} T1，这一些数据都会在最后一层被真实写入，则Leveling 合并策略的放大系数为 O ( T + 1 T ) O(\frac{T+1}{T}) O(TT+1)；Tiering合并策略的放大系数为 O ( T ) O(T) O(T)，因为其最坏情况是最后一层包含所有的key数据。
2.3.4 性能分析总结
总的一个性能差异图如下：
由以上分析过程可以知道LSM-tree 是能够在不同的性能需求之间灵活调整的。比如可以将合并策略从Leveling调整为Tiering 来牺牲一小部分读来极大得提升写性能。这一些性能复杂度分析能够很好得帮助大家在理解LSM-tree的调优，能够在合适的workload 下选择适合自己的调优方向。同样，这一些性能分析复杂度分析也是后续中不同NoSQL系统优化优化的依据。
3. LSM-tree 的优化
这一节将从几个方面深入分析现有系统针对LSM-tree的优化。
3.1 可选的优化方向
尽管LSM-tree在现如今非常受欢迎，但它仍然存在一些问题和可提升性能的突破点。下文中每一个优化方向后续都会有对应实现系统的介绍。
-
写放大。 尽管LSM-tree相比于in-place updates B±tree这样的系统 通过减少随机I/O 后由非常高的写吞吐的提升，但其却引入了较高的写放大问题。Leveing 合并策略被LevelDB和RocksDB采用，也有非常明显的写放大问题。较高的写放大不仅会降低写吞吐，还会消耗SSD这样非易失性内存的寿命。关于写放大的优化，有非常多的NoSQL系统在尝试研究。
-
合并操作。 也就是LevelDB/rocksdb 中的compaction。合并操作是LSM-tree中需要仔细实现的一个操作，合并操作会对系统产生一些消极影响。比如当大量的component进行合并时会导致write-stall(I/O资源的竞争) 以及 cache-miss等影响用户读写性能的问题。
后文也有一些系统在这个方向有深入探索。
-
硬件。 为了最大化LSM-tree的性能，LSM-tree需要合适的硬件。近些年新硬件的发展也在日益增长，这也为数据库应用拥有更好的性能提供了基础。像大内存/持久化内存(intel optane pmem)，多核处理器(数百core)，NVME- SSD 等。
-
特殊workload。 除了硬件本身性能提升带来的LSM-tree的性能提升之外，一些用户特化的workload也应该被提出来去用作适配指定场景的性能需求。这种情况下对LSM-tree实现的一些调整能够帮助达成这一些特殊场景的性能大幅优化。
-
自动调优(Auto Tuning)。 基于RUM(read cost, update cost, memory or storage cost)假设，针对读，写，空间利用 这几个方面没有办法做到同时调优，必须是在其中某一个方面有取舍才行（类似于CAP对分布式系统的约束导致任何一个分布式系统都没法同时满足三个特性）。所以这里自动调优是一个不错的优化方向，能够根据用户的workload来自动调整变化LSM-tree的一些配置。比如写多读少，将合并策略调整为Tiering；写少读多时再切换为Leveling策略。但是因LSM-tree的有太多可以调整的变量，导致这个自动调优非常难以实现。比如内存分配，合并策略选择，不同层之间的大小比等。后文会提到一些自动调优的技术，但并不是针对LSM-tree在全workload场景下的完全自动调优。
-
二级索引优化。 一个LSM-tree仅仅会提供一些简单的key-value接口。想要提升范围查找性能，需要基于keys维护一些二级索引。这里有一个主要问题是如何在写入过程中高效创建二级索引，且保证足够低的写入开销。后续会介绍大量针对二级索引优化的系统，其中很多优化都非常有效。
后续提到的几十篇优化论文 大多数都已经下载好并放在:
https://github.com/BaronStack/book_paper/tree/master/LSM-Optimize-Papers，欢迎补充。
基于以上六个优化分类，作者总结了如下一张树状图，来作为后续展开优化细节的导图。
说实话，读到这里真心感觉这一篇论文价值千万啊，节省了大量的调研时间，而且相关资料已经分门别类 各有千秋得结论都整理好放这里了，就等各位挑选。
接下来用实际几十个开源NoSQL实现 带你看看业界如何优化LSM-tree的。
总的概览如下，其中♣️表示该系统优化的主要方向，三角表示这个系统次要优化的方向。
3.2 写放大优化
降低写放大是LSM-tree重点优化的一个方向。这里主要优化的是Tiering合并策略，因为它拥有较好的写性能，且不弱于Leveling策略的读性能。其他方面的提升是通过开发了一些高效合并技术和数据倾斜（将大量相同的key partition到同一个分区中）技术。
3.2.1 Tiering 优化
一种优化写放大的方法是采用Tiering合并策略，它本事比Leveling 合并策略有更低的写放大。但是根据2.3 节性能分析的过程中Tiering会合并策略允许不同的Level之间可以有重叠key，这就导致读性能的降低。接下来讲的一些优化系统其实有借鉴LSM-tree的partion传统优化思想（也就是讲底层key-value数据拆分成合适大小的component – 类似sstables）。
WriteBuffer(WB) Tree【4】
WriteBuffer tree所做的优化可以看作是一种垂直分组的分区分层的变体。详细描述如下：
- 通过Hash分片来限制每一个sst文件都拥有大小相同的数据，从而均衡用户态workload
- 将每一层的sst文件组（Tiering 会将每一层key范围相近的sst作为一个文件组，用作下次的合并） 组织成一个B±tree的形态，并且能够根据B±tree的数据量（节点个数）来动态调整level的层数。
- 其中每一个sst文件组 都会会被当作一个B±tree中的结点，当非叶子结点的文件组满了之后会触发合并，并将生成的sst文件组作为当前结点的子节点。
- 当叶子结点的文件组满了之后进行合并，会生成一个key的范围包含多个sst文件，将这一些文件按照范围拆分为两个sst文件组，从而形成两个叶子结点。
总的来说，WB-Tree 的优化保证了Tiering 本身写放大较低的优势，利用B±tree 的优势来提升读性能。
LWC(Light-weight compaction)-Tree 【5】
这个LWC-Tree的优化方向和WB-tree类似，也是提供了一种workload的均衡策略。概要细节如下：
- 在LWC-tree中sstable 的大小不再固定，而是根据在下一个level中的重叠度来控制的。
- 如果组中包含的条目太多，则合并之后该sstables组 的key的范围会被缩小，相应的会增加相邻的sstables 组的key的范围。
通过根据重叠度来确定sst文件的大小 能够一定程度减少写放大，按照固定大小来生成sstables 会将重叠度低的sstable文件也加入到合并过程，一定程度降低compaction效率，额外增加了计算代价（维护sstable在自己group的重叠度情况）。同时具体对读性能有多少的提升，因为并没有开源，没有测过。
PebblesDB 【6】
pebblesdb 的合并策略仍然采用分区分层(partitioned-tiered)合并，不同的是它增加了guards数据结构来管理sstables分组，并且不同的guard之间使用skiplist来管理。保持原来Tiering策略的写放大的情况下，使用Skiplist能够一定程度得加速点读，并且运训在range场景并发seek来加速查找性能。
关于pebblesdb的设计细节之前 精读过论文：
PebblesDB Building Key-Value Stores using FLSM-Tree(Fragmented)
PebblesDB学术实现已经开源https://github.com/utsaslab/pebblesdb，其基于LevelDB 1.17版本开发的，实际对pebblesdb的测试中确实有较低的写放大和较高的写吞吐的优化（对比相同配置下的leveldb），但点读相比于rocksdb的差2-3x，原理上pebblesdb的读会产生多次I/O（由于Tiering 合并策略引起的）。
dCompaction【7】
dCompaction比较有趣的一点是介绍了一种虚拟的sstables和虚拟的合并方式。当触发合并的时候 先进行虚拟合并，也就是将实际的sst文件的元数据（smallest-key, largest-key,size…etc）在内存中进行元数据的合并，将合并后的结果存放在内存中，并拆分成一个个虚拟的sst，每一个虚拟的sst采用B±tree的方式管理多个实际的sst文件。
实际参与合并的sst文件个数超过了阈值 则 触发实际的sst文件的合并；或者查找的过程中发现一个虚拟sst文件下有较多的实际sst文件则也会触发实际的compaction。
dcompaction的细节可以参考:
dCompaction: Speeding up Compaction of the LSM-Tree via Delayed Compaction
总的来说dComapction 采用延迟合并的方式，减少了compaction过程的频繁I/O，将compaction做了一个batch；也可以当作是一种Tiering 合并策略的变种（virtual sst就类似sst group）,同时也提供了两个触发实际compaction的阈值来 做为write和read的trade-off调优。如果读多写少，可以让realcompaction多一些，如果读少写多，可以让virtual compaction多一些。
这个思想其实很有趣，但是系统并没有开源，是中科院的几个博士开发的，所以没办法实际测试。
Tiering 方向的写放大优化总结
以上四种优化数据结构都在分层分区的合并策略基础上做了各自的优化。他们之间的主要区别是针对sstables group的不同管理方式来适配不同的workload。
比如WB-tree通过hash来保证sst中数据的均匀分布，因为其使用hash方式来控制sstable中keys的分布，也就对range 查找性能不友好了；LWC-tree能够动态得缩小sst组中的key的范围从而在读写之前进行trade-off，而pebblesdb则依赖选择参与合并的gurads内key的重叠度以及skiplist带来的查找优势；dCompaction通过虚拟合并和实际合并之间的权衡来降低写放大，trade-off读写。 实际上他们的这一些优化对我们想要的降低写放大，提升写吞吐能有多少的提升还是没有办法量化，需要实际的测试以及调参才行（类似dCompaction提供的阈值）。
3.2.2 跳跃合并 优化
Skip-tree 【8】
Skip-tree 提供了一种跳跃合并的想法来提升写吞吐，降低写放大。每一条entry必须从L0合并到最大一层才行，这样这一条entry就不会参与中间层的合并过程，从而能够一定程度减少写放大。
如上图：
Level L和level L+1的合并结果会直接放到level L+k之上的一个mutable buffer中，同时在write-buffer中的keys会和level L+K的中的keys进行合并。这样，Level L合并的结果就不会再次因为逐层合并而被反复读取合并，能够有效减少写放大。需要注意如下几点：
- 为了保证结果的正确性：一个key能够被允许从level L直接写入到level L+K的前提是这个key不会在L+1,L+2…,L+k-1的层内出现才行。这个判断，skip-tree可以通过bloom filter来高效完成。
- 通过WAL来保证write-buffer中的一致性，即L–>L+K 的写入会先写一个WAL。同时，为了降低写WAL的开销，skip-tree仅仅记录写入wal的key的原始id来增加对原始sstable的引用次数，防止sstable在write-buffer和level L+K合并时被删除，读取不到对应的key。
Skip-tree 通过引入了一些管理sstables和合并流程上的复杂度来达到有效降低写放大，提升写吞吐的目的。但它并没有和经过调优的LSM-tree进行性能对比，比如rocksdb也实现了dynamic-level 以及 降低每一层的放大比 ，这一些调优方式也能够对降低写放大有优化。
3.2.3 利用数据偏斜的优化
数据偏斜是指在分布式系统中由于数据分布不均匀导致的部分 分片集中了大量的数据，从而出现用户的访问压力集中在这个机器，而其他机器却很空闲。
TRIAD 【9】
Triad 利用区分冷热数据来变更LSM-tree的行为。主体是通过将热keys和冷keys 分割开来，热keys也就是访问比较频繁的key 会被放入到LSM-tree在内存中的组件，而相反反问不频繁的keys则会触发flush到磁盘参与合并。
- 虽然热keys 不会被flush到磁盘上，而是重新写回memtable，并且会维护他们的事务更新log，每隔一段时间会创建一个新的log文件，并将旧的log删除掉。这一些log是会持久化到磁盘的。当然level0存在的是trasaction-log的一个索引结构，CL-sstables,用来加速查找内存中的热keys数据。
- TRIAD 在L0的sstables个数达到阈值时才会触发合并，这个优化能够一定程度降低写放大。
热key flush之后会作为一个磁盘组件更新到磁盘之上，TRIAD会在其上构建一个索引来加速查找，但其对range性能并不友好。
flush之前 内存和磁盘上的组件形态：
flush之后 内存和磁盘的组件形态如下:
其实现已经开源:https://github.com/epfl-labos/TRIAD
3.2.4 总结
Tiering 合并策略被广泛应用在了LSM-tree中提升写吞吐，降低写放大，但却因降低了range性能和磁盘利用率而被诟病。前面的几种基于tiering的优化思想包括WB,LWC,PebblesDB,dCompaction已经描述完了，他们对sstables采用了不同的管理方式，对合并过程中的调度细节都有各自的优化差异，但都没有清楚的描述各自实现的优化细节对系统性能的整体影响，不过是一些比较有趣的研究方向。而skip-tree和TRIAD提供几个比较新的想法来提升写吞吐，但他们的优化都会引入一些针对系统管理的复杂度，其中skip-tree引入了level L+k的mutable-buffer组件，TRIAD引入了transaction log组件。
以上的写放大优化相比于我们通用的NoSQL系统 – LevelDB和RocksDB来说其实没有办法完全对比，因为这两种系统都是用的是Leveling合并策略 以及 不同层之间的size ratio是10。但上面的实现并不是可调的，他们并没有将自己的优化变更为能够配置的优化（Tiering形态的合并就没有办法变更），从而导致无法通过调整来和rocksdb-leveldb进行对比。所以想要进行对比的话，需要将rocksdb/leveldb的合并策略变更为他们的Tiering，以及调整对应的level size ratio。
但因为其中的一些系统没有开源，像WB-tree和dCompaction这样的系统，所以没有办法实际测试。像pebblesdb/TRAID这样的开源系统就能够很好的进行更加详细的优化提升对系统性能影响的对比评估。
3.3 合并(compaction) 优化
接下来会讨论一些对合并方面的优化策略，包括
- 提升合并的速度
- 降低合并后的buffer cache 失效率
- 阻止write-stall的发生。
3.3.1 提升合并的速度
VT-tree 【10】
VT-tree提供了一种拼接算操作提升合并的性能，本质上也是提升对于合并过程中未使用到的数据的复用率。
基本思想是 在合并多个sst文件的时候，如果输入的一个sst文件的keyrange 对应的磁盘block并没有在重叠部分，那最后合并完成之后生成的sstable仅仅需要将这个key-range block的偏移地址重新拼接到这个新的sstable就可以了， 不许需要重新分配存储空间以及对无重叠数据的copy。
这样的方式会极大得加速合并性能，但仍然有大量的劣势缺点：
-
造成一些磁盘空间的管理碎片，增加针对磁盘空间管理的复杂度，因为指针导致的sstable在磁盘上的数据区域不再连续。为了降低这个问题的影响，VT-tree提供了一种方法，就是当累积有超过K个连续的key-range的block没有重叠，则将其合并为一个拼接操作。
-
影响bloom filter的构建。因为这个sstable中存放的是key-range page的指针，并非实际的key-values数据，bloom filter没法直接扫描(LSM-tree实现的 seek 操作通过迭代器直接读取的key-value数据，无法在一个本应该是key的位置发现指针，并将迭代器指针移动到另一个磁盘page之上)。为了解决这个问题， VT-tree采用了quotient filters 过滤器，能够将不连续的filter直接组合到一块，这样 能够直接访问的sstable构建一个过滤器，复用的key-value部分构建另一个过滤器。
上图是论文中的合并过程，其中2，3，4 是三个参与合并的sst文件，1 是合并成功的新的sst文件。可以看到灰色的部分是重叠key的部分，这个时候对于不重叠的key-range，并不会参与实际合并过程中的排序之类的，直接将其对应的磁盘block偏移地址添加到新的sst文件对应的位置就可以了。
Zhang et al. 【11】
这一篇论文提出了一种pipeline 合并的实现，能够提升 CPU和I/O 并行度，从而提升合并性能。
实际的合并过程包含多个阶段：读取sstables数据，归并排序，写入新的sstables。读取过程会从挑选好的有重叠key的sstables中读取key-value数据到内存中，接下来进行按key字典序以及版本号进行排序并生成新的 key序列，将生成的新的key以及其value形成新的datablock写入到磁盘中。读阶段 和 写阶段 I/O占比较大，排序过程则是CPU占比较大。所以通过pipeline来将这三个阶段并行起来，从而进一步提升CPU和I/O资源的利用率。
过程如下图:
-
没有pipeline时三个阶段穿行， 在第一和第三阶段期间CPU利用率较低，而第二阶段排序时CPU利用率较高，I/O利用率较低。
-
有pipeline的时候 对于第一阶段，读完一个block 的时候不用等待，继续读下一个block；第一个block接下来会进入到merge sort的阶段，依此继续。
也就是利用pipeline能够让每一个阶段没有太多的空闲，只需要持续做自己阶段应该做的任务就可以了。
当然这个优化对整个系统的性能提升是有上限的，过多的I/O和CPU资源的带宽占用能够提升合并性能，但会抢占用户资源，间接影响用户侧看到的读写吞吐这样的性能。
3.3.2 降低合并后buffer cache 的失效率
合并过程会生成新的sst文件 并将旧的sst文件删除，这个过程也会对应将旧的sst文件在cache中的数据也清理掉，这样当新的读请求访问的时候会出现cache-miss，直到将所有新的sst文件数据重新读取到cache中才会提升cache命中率。而这个问题并不能被普通的cache策略缓解，即使在合并过程中将新生成的sst文件添加到cache中，但本身的cache淘汰策略总会淘汰其他的数据，对应的也会造成其他数据的cache-miss。
Ahmad et al.【12】
这篇论文研究了合并操作对整个系统性能的影响。他们发现合并操作会消耗大量的I/O和CPU资源，从而间接影响读请求的延时。为了解决这个问题，这篇论文提出将合并操作offload到远端节点 来降低合并操作对系统性能的影响。在远端节点合并完成后，一个缓存热度算法会将新的sst文件传输到当前db节点，并缓存在cache中来降低cache-misses。这样的实现需要能够快速的将落在旧的sst文件的读切换到新的sst文件之上，从而降低组件切换对查询性能的影响。
LSbM-tree 【13】
因为Ahmad et al.论文中提出的优化方案需要将合并操作卸载到远端节点，这个对于单机存储引擎来说不太友好（当然，实际单机存储引擎肯定是应用在分布式场景，对于分布式集群来说能够保证单机引擎的良好性能，这个方案也是能够被认可的）。同时新生成的sst文件被添加到当前节点的缓存中时会和原本缓存中的数据有冲突（比如，原本缓存的sst文件还没有来得及删除 – 一般合并操作全部完成时才会更新cache），所以仅仅通过缓存热度算法来获取远端新的sst文件是不够的。为了解决这个问题（不将合并操作放在远端，同时降低合并之后回填cache的冲突问题），LSbM-tree(log-structured buffered merge tree) 提出了一个新的方案。
如下图：
这个LSbM提出了buffer sstables的数据结构，该数据结构是一个缓存数据结构。如上图：L1的一个sst文件和L2的2个sst文件进行合并，合并完成之后不会立即删除旧的sst文件，而是将这三个文件追加称为buffer sstable。这样，buffer ssts能够继续存在于内存并接受用户I/O的查找，cache-miss 基本不存在。后续的删除会根据这一些旧文件的访问频率来删除（LFU），访问频率越低buffer sstable的肯定会优先被删除。同时，构建buffer sst文件的过程并不会产生额外的磁盘I/O，因为合并的过层中会将数据读取到内存中。
存在的问题是，这种优化是针对有热点的workload，如果用户的读取完全随机， 那其实这样的合并之后的buffer cache命中率的优化意义就不大了。
3.3.3 阻止write-stall的发生
虽然LSM-tree相比于B±tree有较好的写性能，但也总会因为后台的flush和compaction(合并) 等internal操作造成用户态的write-stall和读长尾。
bLSM-tree 【14】
bLSM提出了一种 spring-and-gread的合并调度器，来降低leveling合并策略的write-stall问题。
这里之所以选择对leveling的优化是因为其合并算法本身写放大比较严重，后台合并操作产生的CPU和I/O开销远高于Tiering方式的合并策略，而且leveling合并策略是leveldb和rocksdb的默认合并策略，所以针对leveling的优化是比较有代表性且收益较大的。
核心思想是 允许在每一层增加额外的调度组件来并发调度不同层的flush/compaction 过程。
整个过程就是在L+1和L进行合并生成新的sst文件之前，调度器会控制等待上一个要输出到L+1的job完成执行才会将当前的合并结果从内存写入的磁盘形成新的sst文件。通过这样的方式，能够降低频繁compaction的I/O次数。说白了，就是compaction限速(rocksdb的ratelimiter)，限制的是生成sst文件的速度，不是直接限制底层的compaction I/O。
这种调度方式存在的问题 是如果写入压力过大，且写入的速度大于合并的速度，就可能出现持续累积的待合并数据越来越多，这一些数据迟早是需要compaction的，而在这种算法中就只能累积，消耗过多的内存并且对读性能有影响；好处显而易见，后台合并的I/O减少了，用户态的write-stall文件也会有明显的减缓，且bLSM-tree也仅仅适用于Leveling的合并策略。
3.3.4 总结
合并操作的优化方向中 有几个主要的优化方向：提升合并速度，降低合并后的cache-misses，组织因合并导致的write-stall。
VT-tree通过拼接操作来让不重叠的key-range所在的block在compaction过程中被复用，而降低合并过程中的读/写总量 从而提升单次合并的性能。但却会造成磁盘碎片，尤其在机械硬盘*问不友好（不连续，机械硬盘的随机I/O性能极差）；更重要的是无法构建通用的bloom filter来加速读。
Pipelined合并优化的实现比较有趣，将合并操作的三部分使用pipeline来并发起来，从而提升了I/O和CPU的利用率，间接提升的合并性能。现在很多基于LSM-tree的系统也有开发了各自在合并过程中的预读和后写的功能。后写是指 合并过程形成一个个datablock，但并不会立即写盘，而是先暂存在内存中，等待总大小达到了一个sst文件的大小，再触发一次sync将整个新的sst文件的所有data block数据写入磁盘，减少了I/O次数。
Ahmad 和 LSbM都在降低合并后的buffer 中的cache-misses提出了自己的方案，这个方向的优化手段适用于有热点的workload。Ahmad将合并操作放在远端，并将执行结果拉回到本地cache，LSbM则在本地维护buffer sstables来降低合并过程的cache失效问题。
bLSM 则专注于leveling合并策略中的write-stall问题，通过限制合并过程中产生的I/O量来降低后台合并对I/O资源的占用(类似rocksdb的rate-limiter)，从而阻止write-stall的发生。但对于写heavy场景却会持续累积待合并的数据，间接影响读延时。
3.4 硬件 方向的优化
接下来看看LSM-tree在不同的硬件平台下的一些优化，包括但不限于大内存，多核，NVM-SSD 和 本地存储。一下基于硬件平台的优化都是对LSM-tree的数据结构做了一些基于硬件的适配，来最大化LSM-tree在对应硬件下的性能。
3.4.1 大内存方向
大内存 能够让LSM-tree 减少层数，并且提升写吞吐和读吞吐（让更多的数据处于内存之中，读写性能都会更好）。但是对于大内存的管理相比于原来却有新的挑战：
- 如果大内存使用的堆数据结构来管理，会引入数量庞大的小对象的管理（分配堆内存会造成内存碎片），从而带来负载较高的GC机制。
- 如果大内存使用的是非堆 类型的数据结构来管理（concurrent B±tree），大内存仍然会有较高的查找代价 和 大量的写入过程中的CPU cache-miss（对非堆数据结构的修改需要先找到原来的数据页，再修改）。
FloDB 【15】
FloDB提供了两种分层方式来管理大内存组件：
- 第一层是小的concurrent hastable 数据结构 来快速的接受写入
- 第二层是一个较大的跳表 数据结构 来支持高效的range性能
当hashtable满了之后，会通过batch算法 高效迁移到第二层的skiplist之中，因为hashtable 本身就是有序的，迁移的跳表之中也能避免再内存中的大量随机写入，从而对内存workload友好。
FloDB要求range scan时 hashtable中没有数据，这样仅仅在skiplist中高效查找就可以了（这里没有太明白），按照这样的逻辑range-scan时hashtable中有数据的话还得等待hashtable中的数据全部刷到skiplist中，(wtf)？
FloDB的设计也会引入两个问题：
- 大量的写入和range scan会一起操作同样的数据结构，这会一定程度降低各自的性能。
- 跳表会占用较多的内存，会降低内存的利用率
Accordion【16】
为了解决FloDB的问题，Accordion是用来更多层的方法来管理内存组件（这里肯定是大于两层的）。设计架构图如下：
在最上层，有一个mutable 组件来接受写入。当其写满了之后不会flush到磁盘，而是flush到immutable(只读的) 组件中。这一些immutable 有多个，之间可以通过内存中的合并操作进行合并，能够及时清理过时条目所占用的空间（提高了空间利用率）从而提高查询性能。
需要注意的是 in-memory的flush和合并操作不会触发磁盘I/O，这就是大内存组件的好处，能够很大程度降低磁盘I/O带来的开销。
3.4.2 多核方向
cLSM 【17】
cLSM 主要是在多核机器上对LSM-tree的优化，设计了新的并发控制算法。它将LSM-tree的组件组织成一个并发链表，能够降低由于sync带来的阻塞请求的操作（write-stall情况，wal sync代价比较大，需要等待wal写完才能写入memtable）。
Flush和合并操作 过程中针对链表的原子更新 被设计为不会阻塞读请求。当一个内存组件满了之后，会分配一个新的内存组件接受写入，旧的内存组件则flush到磁盘组件之上。这个过程中为了避免写请求更新到旧的内存组件中，写写入落到内存组件之前会请求一个共享锁才会更新，而flush线程会在flush之前获得一个排他锁，当写入想要更新到旧的内存组件时无法获得共享锁（flush线程的排他锁不允许写入线程获得共享锁）。
cLSM也支持多版本中基于快照的查找功能和read-modify-write 操作。支持这一些功能过程中的写入和冲突都会在内存组件中处理，比如写入内存组件过程会通过timeCounter为每一个请求打上时间戳，而后续的读取则会默认读取最新时间戳的请求，也可以指定时间戳来读取该时间戳以前的请求。
这里基于多核的优化中 多核是通过并发来体现的，也就是写入/读取都可以高并发来做，且之间不会互相影响。而快照读和RMW操作则是基于高并发之上的特有特性， 能够在内存组件之中完成快照读需要的时间戳更新和RMW更新操作。
其实这一些优化在现有通用LSM-tree的实现(rocksdb,leveldb)中都已经集成进去了。
3.4.3 SSD/NVM/PMEM 方向
SSD和NVM-SSD等新型存储介质的出现打破了原来机械硬盘只能对顺序I/O友好的特性，这一些新型存储介质对随机I/O同样有优异的性能。
NVMs 更能够提供按照字节寻址，随机访问 以及 数据持久化 的特性。
PMEM 是intel开发出来的持久内存，能够提供和内存一个量级的性能，并且拥有持久化能力。
所以基于新型存储介质的LSM-tree的构建需要做更多的适配，来将硬件的性能发挥到极致（on 机械硬盘的LSM-tree和on PMEM的LSM-tree 肯定需要不同的架构形态）。
本节会涉及到很多SSD/PMEM等存储介质的知识，对存储介质的底层存储单元有足够的了解 能够方便理解各自底层存储的特性。比如SSD/PMEM的非易失性的体现，SSD的磨损均衡的体现，PMEM和SSD的性能为什么有那么大的区别？详细可以参考：从NMOS 和 PCM 底层存储单元 来看NAND和3D XPoint的本质区别
FD-tree【18】
FD-tree时基于ssd构建的LSM-tree，主要是减少 on-ssd的随机写。相比于传统LSM-tree实现 ，FD-tree有一个巨大的差异 就是通过级联的方式来提升读性能 而非Bloom-filter。
如下图：
对于Level2中的page数据，很多page和一个Level1的page指针链接起来，这样读的时候能够通过二分查找在整个LSM-tree的磁盘组件上快速移动。但是这个优化会引入一些合并上的复杂度，当level L的sst合并到level L+1中是，所有之前从level0到level L-1的层中的sst文件都需要重新构建一下指针。同时，对于读取不存在的key，二分查找过程中仍然需要多次磁盘I/O 才能知道自己不存在。
所以现代的LSM-tree on ssd的实现还是通过bloom filter而非级联方式 来加速读。
关于FD-tree所说的减少随机写 感觉有点low，就是通过合并来让写入的数据有序。。。 （这不本来就是LSM-tree的特性？），没啥可参考的。
不过这种级联方式在PMEM这样的持久内存会更有优势一些（访问延时和内存处于一个量级，查找过程中的I/O耗时可以接受的），后续的MatrixKV设计会简单描述。
FD+ -tree【19】
FD±tree 在 FD-tree的基础上优化了合并过程的一些操作。在FD-tree的合并过程中，level0到level L的合并 需要新的组件先被创建出来，完成内合并之后才能删除旧的组件（需要变更级联指针），这个过程会让磁盘空间的消耗临时增加两倍。为了解决这个问题，FD±tree在合并过程中会逐步增加新的组件，而不是将当前参与合并的所有组件最后生成的新的组件的临时文件都创建出来；除此之外，会将会将旧组件中未使用的页面（没有重叠key 以及 指针指向的页面）回收掉。
说白了，就是填FD-tree设计上的坑，同样没啥可参考的。
MaSM【20】
这个MasM(materialized sort-merge)的优化是为了提升以HDD作为核心数据存储的系统性能。它的主要优化是通过加入SSD作为update cache来提升update性能(本来加个ssd也就会有性能提升呀。。。继续看吧)。MaSM将所有的更新操作先写入到SSD中，这个过程使用的是Tiering policy，能够保证高效的写吞吐和较低的写放大，但会引入读开销。接下来，在ssd的数据会通过合并操作存储到HDD中。也就是MaSM使用了ssd作为数据缓存，并且在ssd上的数据存放是通过Tiering策略存放的。
我们知道Tiering策略是通过牺牲读性能来提升写入性能的（Tiering策略允许不同的level之间有重叠key，每一次合并操作是选择当前层，写入到下一层, 写放大是O(L)），但是MaSM应用的场景是支持从数据仓库中进行远程访问，相比于从基于HDD的大数据量中的读请求来说，on SSD的Tiering 合并策略带来的读开销可以忽略。
基本架构图如下：
Wisckey【21】
Wisckey的设计完全是为了新型SSD及更高性能的存储设备。因为SSD能够提供高效的随机读写性能，而对于LSM-tree架构on SSD的写性能的提升 需要降低写放大，所以Wisckey提出了key-value分离存储的思想，数据的后台合并仅仅操作key就可以，对应的value并不会参与合并过程。这个思想在后续的HashKV，SifrDB都得到了应用。
整体的设计如下图：
Whiskey的设计将value 以及 key的index存放在追加写的log文件中，而key 和 key-index本身存放在LSM-tree中。其中key-index能够访问到对应append-log的value数据中。这种设计能够极大得减少合并过程中的写放大，因为合并的过程仅仅是小数据量的key参与，key-index也只是一个能代表偏移地址的int64 – 8bytes的数据。
- 带来得负面影响就是会严重影响range-scan性能，因为scan的时候key和value是分开存储的，还需要多一次I/O去对应的append-log中取value数据。
- 同时append-log中的value数据需要能够高效得清理过时数据来节省存储空间。之所以这样，是因为同一个key得多次写入会产生多个value，这一些旧的value在合并过程中需要被清理掉，也就是只需要保留最新key的key-index 对应的value数据就可以了，这个整体的GC过程分为三步：
- Wisckey扫描日志尾部key-index，并通过对LSM-tree中对应的key进行点查，确认key是否被修改，依次验证每一个扫描的key-index
- 将key-index未更改的key的数据追加到append-log中，并更新其在LSM-tree中的位置；如果key-index更改，则表示新的数据已经追加到append-log中了，不用管。
- 清理掉append-log的tail部分，并释放对应的空间。
目前Wisckey的实现中GC的大量的随机点查操作，已经被证明是其系统实现的瓶颈了，根据Pincap实现的https://github.com/tikv/titan 测试过程来看， GC+LSM tree如果同时进行，也会导致NVM-SSD带宽被打满。
HashKV【22】
HashKV也是Wisckey思想的一种实现系统，介绍了一种更加高效的GC过时value的方法。它用了一种Hash算法来根据key 将其value hash存储到不同的value-log分片中，并且让每一个分片中的value-log GC过程是独立进行的，不会互相影响（这种方式能够并行起来，确实能够提升GC的效率）。 为了实现针对每一个分片的GC，HashKV 对key按照hash值进行了分组，来方便得查找每一个key最新的value数据。有效的value 会被添加到新的value-log中，同时在LSM-tree中的meta中更新value 在value-log中的位置。 HashKV还有一个细节是将访问频率比较低的冷数据也分离存储了，这样冷数据就不需要和其他的value-log一起参与合并了。
设计图如下：
可以看到针对一个key-value的写入会 拆分成：
- Meta-key 存放到LSM-tree中
- Meta-key-value 存放到value-log中
其中的meta可以理解为能够标识key在value-log的位置。
而value-log则会根据hash 分为segment-group，一个segment-group包含两部分呢： Main-segment和log-segment，如果main-segment append存放空间不够了，则会动态增加log-segment的空间来存放。除此之外，还有cold-data-log数据区域单独存放cold-log数据，进一步减少GC和合并的I/O压力，而且各个segmemnt-group之间还是像Wisckey 提到的GC方式进行GC，但可以互不影响，从将整个GC的效率提升上来。
但是这一些优化在系统瓶颈达到磁盘之上时（大value 以及 T级别的数据量下，compaction和GC 产生的I/O会达到硬件瓶颈，这个时候想要提升系统性能，只能通过提升硬件性能了。。。。 PMEM将成为潮流）
Kreon【23】
Kreon将数据的写入变更为mmap ，通过减少不必要的数据拷贝降低CPU负载。Kreon在linux 内核中实现了一个mmap I/O管理器 来控制cache的页面替换。同时为了提升读性能，在读的时候会将读取到的key-value数据单独存放到一个新的cache中，下次在这个读cache中尝试是否能够命中。
感觉Kreon的实现过于定制化，包括对内核的适配和操作系统cache的管理，过于复杂，难以独立实现。
NoveLSM【24】
NoveLSM是LSM-tree再NVMs上的一种实现（这里的NVMs其实是一种持久化内存设备，类似之前提到过的基于3D XPoint存储介质的PMEM）。
NoveLSM的优化主要有三点：
-
NoveLSM在NVMs上增加了一个组件，当DRAM中的内存组件写满之后 后续的写入会落到在NVMs上的组件，从而减少write-stall。
-
去掉了WAL，因为NVMs本身提供了持久化能力，不需要WAL来保证数据一致性。
-
为了降低读延时，NoveLSM提供了不同Level 之间的并发查找能力。
关于NoveLSM on NVMs的这一些优化其实收益有限，比如第一点通过增加一个on NVMs的组件来减少写放大， 本身出现写放大的情况是internal 操作(flush/compaction)和用户I/O资源的竞争导致的，假如数据量足够到，internal 操作消耗足够多的带宽直到到达nvms的瓶颈，其实这一点优化在这个场景收益并不会很明显了。
第二点 去掉WAL，让memtable直接写入到NVMs，这个时候如果保证插入的性能，需要无锁memtable 并且跳表的实现需要落在NVMs上，指针的指向并不会像内存那样直接赋值，需要先读取存放指针的NVMs地址，将指针指向修改后再写回，这一些代价不一定比on DRAM的WAL性能更高。
MatrixKV【25】
MatrixKV 同样是基于NVMs的LSM-tree的优化。它的存储介质架构是DRAM-NVMs-SSDs。核心优化有两点：
- 基于NVMs的 column compaction
- 在NVMs之上构建cross-hint search （类似之前FD-tree的级联查找能力）
- compaction分离： L0->L1的compaction使用NVMs的column compaction；大于L1的compaction使用Rocksdb的默认Leveling compaction，并且大于L1的sst都存放在SSDs之上，间接得做了I/O隔离，让参与计算较多的L0->L1在读写性能更好的NVMs上，计算较少的Higher Level compactions在ssd上。
Column compaction的优化就是相当于将Flush 形成sstable ，到L0–>L1的compaction 过程重构到NVMs之上，类似Rocksdb的subcompaction特性，将L0–>L1的compaction 拆分成一个个key-range不重叠的范围，然后不同的范围之间并行compaction，从而起到加速L0–>L1的compaction的作用。
这个优化是结合PMEM的pmdk来做的，但其并没有和rocksdb的subcompaction进行性能对比，仅仅和NoveLSM,RocksDB-NVMs 这样的组合进行对比测试。
Cross-hing search同样是为了加速 on NVMs的查找性能，通过CAS来加速二分查找。
关于MatrixKV的开源实现: https://github.com/PDS-Lab/MatrixKV
关于MatrixKV的详细设计细节: https://vigourtyy-zhg.blog.csdn.net/article/details/112696567
3.4.4 本地存储方向
这个方向主要是尝试对存储设备(HDD-SSD)进行本机管理上的优化，从而起到对LSM-tree的实现优化目的。这里可能更多的是操作系统I/O调度这一部分的优化。
LDS【26】
LSM-tree-based Direct Storage system(LDS) 绕过了本地文件系统，能够更好得利用LSM-tree的顺序I/O 和 I/O聚合能力。LDS 在磁盘上的数据主要包含三部分：
-
Chunks
存储LSM-tree的实际key-value数据，类似sstable
-
Version log
存储LSM-tree每次flush和合并之后chunk发生变化的元数据，类似RocksDB的MANIFEST，每隔一段时间会对整个LSM-tree做一个checkpoint，并且将旧的文件数据清理掉。 -
Backup log
类似Rocksdb的WAL， 每一个请求的更新都会预先写入这个文件 保证了内存中数据的持久化，从而间接保证了数据的一致性。
LOCS【27】
LOCS是一个基于open-channel ssd的LSM-tree实现。Open -channel SSDs向外部提供了SSD内部能够并行处理数据的channel接口，每一个channel能够像一个本地磁盘一样处理数据。这个特性能够允许应用控制合适的并发压力来像磁盘写入，但是每一个channel的读取也是独立的，需要从各自的channel读取之前写入的数据（有点像rocksdb的Column family 形态）。
- 为了在LSM-tree上实现这个特性，LOC S在处理Flush和合并(compaction)的磁盘写入时通过一个least-weighted-queue- length 策略来平衡为每一个channel分配的写入负载。
- 为了进一步提升LSM-tree的并发读能力，LOCS将拥有相同前缀的sstable放入到相同的channel，从而保证了多个channel之间的并发读。
这个实现的复杂度相对来说更低一些，因为open-channel已经暴漏了操作channel的接口，我们只需要合理得利用就可以了。
但是接下来讲的这个则是对FTL的操作，实现复杂度急剧上升。
NoFTL-KV【28】
NoFTL-KV能够通过闪存的FTL 从key-value存储直接控制对底层存储设备的访问。FTL能够能够将逻辑块地址翻译为物理块地址实现磨损均衡，大体上就是让针对闪存的写入均匀分布在不同的块中，以此来提高每个SSD物理块的寿命。
NoFTL-KV 提取了很多FTL本身的优点，例如将LSM-tree中的一些任务下推到存储设备中、通过执行更有效的数据放置方式（将数据放在指定的空闲闪存块）提升I/O的并发度、将闪存垃圾回收机制和LSM-tree的compaction 集成到一块，一起由FTL调度 从而减少写放大（合并的粒度更小，且保证了没有重叠的key-range不会被调度参与compaction）。
架构图如下：
3.4.5 总结
这一节探讨了LSM-tree在硬件方向的一些优化手段，包括大内存，多核，SSD/NVM/PMEM 存储介质方向，本地存储管理 四个方向。
而且结合了很多系统实现来分析各个硬件平台对LSM-tree的优化收益：
- 为了充分利用大内存的优势，FloDB和Accordion都采用了多层方式对内存组件进行管理，限制针对同一个内存区域的随机写入
- 多核方向 cLSM提供了一种新的并发控制算法来提升LSM的并发度。
- 基于SSD/NVM等新型存储介的LSM- tree优化，主要是利用这一些介质 在随机读场景的高性能 以及 软件层面的变更（应用Tiering 合并策略和key-value分离等软件特性）来降低写放大，提升写性能，并且减缓这一些存储介质的寿命消耗。
- 在本地存储管理方式上的优化，结合新型存储设备 – Open-channel特性 以及 闪存的FTL 对LSM-tree进行管理。后者会将LSM-tree的flush和compaction下沉到FTL的管理，有效降低LSM-tree 的写放大。
总的来说，考虑到写放大收益，开发以及维护成本，基于NVM-PMEM的key-value分离策略会是比较有前景的方向。NVM-PMEM的低延时，高带宽，远低于内存的成本，key-value分离体现的较低写放大 都能看到引擎有较高的性能上限，而且实现复杂度低（tian已经实现了key-value分离），可维护性较强（不论是rocksdb还是PMEM的pmdk都是有良好的开发者团体持续维护迭代，可靠性能够得到有效保障）。
3.5 特殊的workload 优化方向
这一节探讨的是一些LSM-tree的系统在特定的workload下所做的优化。这里所考虑的一些特殊的workload包括时间戳的事务数据，小value数据，半分类数据 和 大部分的附加数据。
LHAM【29】
LHAM(The log-structured history access method)提升了基于时间戳事务数据的workload性能。LHAM的核心修改是去掉了一些对读并不友好的组件，来提升剩下的每一个组件在有时间戳的数据中的查找性能。LHAM能够进一步保证不同组件之间的key的范围时间戳不相交。这个是通过修改的合并过程，将拥有较新的时间戳的记录从Ci组件合并到Ci+1
LSM-trie【30】
LSM-trie是一个基于LSM-tree的数据结构，用来管理大量的小value的key-value数据（value < 500bytes），它对元数据管理方面做了大量的优化。K-V存储系统中会有大量用户的元数据信息的存储需求，这一些需求都是小value形态的存储，而这个时候针对小value的存储系统需要注意元数据的存储管理（比如LSM-tree中的index block和 filter block会常驻内存，加速对datablock的索引），防止元数据量过大效果过多的存储空间，并且拖慢小value的数据访问性能。
-
采用Tiering合并策略，能够减少写放大（它列在了优化之中，但本身这就是LSM-tree的一种合并策略，并不能算优化）
-
并不是将key-range直接存放到sst文件之中，而是使用key的hash值作为前缀 形成一个个sst group 进行存储，每一个group存放相同的hash前缀的key-value数据（因为相同前缀的出现，也是Trie的数据结构的思想，方便快速得找到相同前缀的数据）。
-
为了进一步减少索引对空间的消耗（index block/ filter block），LSM-trie根据key-value的hash值，将key-value数据放置在对应的hash桶之中（HTable），并且将它们的位置信息存放在可动态变更的元数据表之中。
-
LSM-trie中的读性能的提升是通过为每一个hash 桶构建自己的bloom filter , 每一层的每一个hash桶中都有多个sst文件，这样针对一个hash桶的点查只需要一次I/O就可以了。当整个LSM-trie的数据量足够大 ，元数据足够多的时候，这种方式的点查性能就非常有优势了。（针对多个sstable构建一个bloom-filter，效率还是很高的）
存在的问题就是LSM-trie的range scan性能并不友好，因为其数据分布是依赖hash的，仅仅能够提供良好的点查性能。
SlimDB【31】
SlimDB针对的是半分类数据的优化，比如用户输入的keys会包含以x为前缀，y为后缀的大量的keys，后续的workload会有针对相同前缀/相同后缀 以及 两者同时满足的key的查找。
-
SlimDB需要能够支持点查；给定前缀和后缀，依据前缀能够找到对应的所有前缀key数据。
-
降低写放大，在较低层(L0–>L1)之间的合并采用了Tiering合并策略；较高层(>L1)之间的合并策略采用Leveling合并策略。
较低层采用Tiering，因为较低层的重复数据较多，Leveling合并效率较低，需要能够保证L0–>L1的数据被及时合并到更高层。
-
对于使用Tiering合并策略的层 采用cuckoo filter提升在该层内sstable的点查性能，因为Tiering策略允许层内的不同sstable之间有数据重叠，所以该层的查找过程需要所有的sstable都参与才行。
每一层内，一个跨多层的cuckoo filter会将该层每一个最新版本key在对应ID的sstable的位置添加进来，这样每一个key的点查仅仅需要check一次filter就可以了。 -
为了减少元数据过多带来的管理复杂度，SlimDB使用了跨越多层的索引结构，将拥有相同前缀的key添加到各自的前缀列表中，这样如果需要找查找某个前缀key，仅仅只需要顺链遍历链表就可以了。同时也使用相同后缀key构建其page列表，从而方便得点查前缀key和后缀key。
Mathieu【32】
Mathieu提供了两种针对大量追加数据的合并策略(update, delete, put等)。Leveling和Tiering合并策略共有的问题是层数是由总的数据条目来决定的。按照文章开头分析的空间放大2.3.3 节 可以知道，在leveling和Tiering策略下 层数L和数据总量N之间正相关。
因此，对于大多数都是追加的workload，数据量的持续增加会导致层数越来越多。为了解决这个问题，Mathieu研究了一种在线合并策略，该策略能够对写入成本的理论下限进行分析，该策略适用于拥有最多K个组件的append-most workload场景。并开发了MinLatency和Binomial 两种合并策略来实现该理论下限。
以上四种workload的定制化LSM-tree的优化 适用场景非常有限，毕竟是定制化。比如LSM-trie仅仅支持点查，而SlimDB仅支持获取同一个prefix的所有value数据。实际的应用中大多数场景不会这样来使用，所以这几个系统的可参考性并不高。
3.6 自动调优（Auto-Tuning）
LSM-tree的自动调优 能力能够有效减少用户使用NoSQL系统的负担，所以接下来将仔细介绍一些自动调优技术。包括：参数的自动调优，合并策略的自动调优，bloomfilter 的自动调优和 数据放置策略的自动调优。
普通用户可能更关注参数的自动调优，比如能够根据用户的workload，自适应一组对该workload性能友好的参数。
更加关注底层 空间放大/读写放大 的用户可能希望从合并策略，bloom filter内存分配，数据放置策略 等来做自动调优。
3.6.1 参数的自动调优
Lim et al【33】
这篇论文展示了一种分析模型，能够将key的分布进行合并，对这一结果进行分析来计算LSM-tree各个操作的代价，从而给出一组对该操作友好的性能参数。如何根据key的分布来抽象出key的操作代价（读/写/空间放大代价），这个过程比较复杂。比如发现了一个key，但是这个key在前期的合并过程就已经被清理了，并不会参与后续的合并，所以这个key的写成本就比较低。
所以这一篇论文提出了一个模型 能够根据一个特定的key k k k 抽象出一个概率质量函数 f x ( k ) f_x(k) fx(k) 来表示 这个写入请求的写成本。
给定写入的总请求的个数
p
p
p，对于写入的这p个请求（可能会写入重复key），其在整个LSM-tree中唯一key的个数可以通过公式进行预估：
U
n
i
q
u
e
u
e
(
p
)
=
N
−
∑
k
∈
s
(
1
−
f
x
(
k
)
)
p
Uniqueue(p) = N - \sum_{k\in s}(1 - f_x(k))^p
Uniqueue(p)=N−k∈s∑(1−fx(k))p
其中N是整个LSM-tree中唯一key的总个数上限（比如设定的随机key是在int32_t范围内，则unique key的总个数
N
=
2
32
N = 2^{32}
N=232），写入的key的大小是
k
k
k。基于这个公式，能够计算出写入
p
p
p个请求在后续参与flush和compaction的总代价。
再通过分析模型来给出一组合适的调优参数，从而最小化写入代价。
论文细节很多，一些推导需要仔细研读才能理解。
Monkey【34，35】
这篇论文通过对合并策略，level大小比，不同组件之间的内存分配方式 和 Bloom filter设置来找到一个合适对LSM-tree workload友好的配置。Monkey的调研成果如下：
- 普通的bloom filter内存分配方案中，当LSM-tree为每一个key在构建 bloom filter时都分配相同的位数，后续的读性能并不一定能够提升。比如 有T个sst文件 处于最后一层，这个场景下最后一层的数据包含整个LSM-tree的大多数数据，为这T个sst文件中的key构造bloom filter会消耗掉大量的内存，但只能节省最多T次I/O（T个文件中都不存在指定的key，减少了T次读取datablock的情况）。
- 为了减少Bloom filter的误报率，Monkey的研究中发现应该为lower level的sst构建bloom filter分配更多的位数来降低误报率，higher level的sst文件中分配更少的位数（上一条中更高层的Level位数更多，占用内存更大，但是优化效果并不会特别明显）。
在这种模式下(不同的层使用不同误报率的bloom filter)， 点查产生的I/O成本将会由最后一层的I/O代价决定。这个时候读请求的时间复杂度将变为： Leveling 合并策略下 O ( e − M N ) O(e-^\frac{M}{N}) O(e−NM)，Tiering合并策略下 O ( T ⋅ − M N ) O(T\cdot^-\frac{M}{N}) O(T⋅−NM)。
然后，Monkey使用类似于第2.3节中所考虑的成本模型，以尽可能提升整体吞吐为目的找到最佳的LSM树配置组合，该模型考虑了不同workload的组合。
3.6.2 合并策略的自动调优
Dostoevsky【36】
Dostoevsky 研究表明已经存在的合并策略 ，像Tiering和Leveling这样的，对于业界已有的workload都不是最有优势的（Tiering引入的较高读延时，leveling引入较高写放大），其中读性能以及空间放大问题都是因为最后一层拥有较多数据量导致的，写相关的问题（写放大和写性能）则是每一层累积的问题。
-
为了解决Tiering和Leveling合并策略 最大层和所有层之间引入的读/写放大相关的问题，Dostoevsky提出了一种lazy-leveling合并策略，允许小于Level N的层使用Tiering合并策略（减少写放大），而在Largest Level使用Leveling合并策略（降低最后一层的读长尾延时、range scan长尾 和 空间放大）。
Dostoevsky也引入了在较短的range scan时性能性能比单纯使用leveling合并策略更差，因为小于Level N的层内允许sst文件有重叠key，也就是较短的range scan会较高概览落在小于LevelN的不同层，从而延时更大。
-
为了降低range scan在小于Level N层查找时的延时，Dostoevsky提供了 hybrid合并策略。即当小于Level N的sst文件总个数达到Z个 时使用Tiering合并策略；lagest level 的sst文件总个数达到K个时使用Leveling合并策略，否则就相反。而且，Z和K这两个数字是可调的。
Dostoevsky 提供了一种可调性比较好的配置，能够在比较通用的workload之下让LSM-tree拥有更为全面的性能表现。
3.6.3 动态分配bloom filter内存
现存所有的LSM-tree的实现中，针对bloom filter的使用都是静态方式 – Monkey（bloom filter的内存分配）。因为一旦为一个sstable 创建的bloom filter内存分配成功，它的误报率将不会发生变化。
ElasticBF【37】
这篇论文能够基于数据热度和数据访问频率来动态调整bloom filter的误报率，从而起到优化读性能的目的。
对于每一个key会有k （bit）的空间分配来构建bloomfilter,ElasticBF会使用不同的bit 位来提前构建多个较小的bloom filter ： k 1 , k 2 , k 3 , . . . , k n k_1, k_2, k_3,...,k_n k1,k2,k3,...,kn，其中 k 1 + k 2 + . . . + k n = k k_1 + k_2 + ... + k_n = k k1+k2+...+kn=k。当这一些bloom filter一起使用的时候就能够提供稳定的较低误报率的bloom filter。当ElasticBF根据用户数据的访问频率来动态的开启关闭其中的一些bloom filter时就能够降低整体的I/O消耗(访问频率较低的数据切换到较高的误报率来过滤，访问频率较高的数据切换到较低的误报率来过滤)。
ElasticBF 的使用场景是对bloom filter的内存使用有限制的情况，比如平均一个key消耗4bit的数据。内存较小的情况下，加载到内存的index block和filter block 的数据时有限的，这种情况下不同的误报率产生的磁盘I/O对系统读性能影响还是比较大的。而当内存比较大的时候，允许更多的filter block加载到内存中，且每个bloom filter允许有更多的位数，这样误报率能够明显降低，因为误报产生的磁盘I/O相比于实际查找到磁盘I/O的数量就微不足道了，这样对整个系统读性能的提升有很有限，bloom filter会占用更多的内存，而导致其他index block的内存占用减少。
所以在ElasticBF场景中，bloom filter的位数 和读性能之间需要做trade-off，越多的位数意味着越低的误报率，消耗更多的内存，但不一定对整体的读性能有提升。
3.6.4 数据放置策略的优化
Mutant【38】
Mutant 在云存储中优化了LSM-tree的数据放置策略。云存储厂商对外提供的存储服务会附带很多选项，像性能配置 或 价格配置。如果是选择不同的价格配置，那服务商就需要在该配置下选择合适的sstable放置策略以便最大化系统性能。Mutant 通过管理每一个SST文件的访问频率来解决这个问题，将热点sstable文件放置到高速存储设备之中（flash闪存 或 NVMs），当然高速存储设备的容量是有限的，能够保存的热点sst文件个数也是有限的。
所以对于这种 资源有限的情况下希望能够达到最优的目标期望值的问题 就很容易想到贪心算法思想或动态规划思想；比如固定时间内优先放置访问频率最高的sst文件到高速设备，并将已有的sst文件访问频率较低的回写到底层慢速设备中。
3.6.5 总结
这一节针对LSM-tree的优化方向是根据LSM-tree的worklaod来自动调优。Lim et al. 和 Monkey 两个系统都希望找到一种调优方法来提升整体的LSM-tree的性能。这两种调优方案其实是互相补充的，Lim et al 使用了一种新颖的分析模型 来调整 最大层的leveling 合并策略（读/空间放大的性能消耗主要体现在最大层之中，大量数据集中在largest level 导致读长尾 和得不到合并清理的多版本数据），从而达到提升性能的目的；Monkey通过调整LSM-tree所有的参数来找到最坏情况下的I/O性能的优化办法。所以将这两个系统的优化思想组合起来，能够更好得调优整体性能。
Dostoevsky能够动态调整LSM-tree不同层之间的合并策略，从而对有写入，点查 和 range scan的workload 性能友好。其他的调优系统则集中在LSM-tree的其他实现中，像Mutant 侧重LSM-tree中sst文件的放置策略优化上，ElasticBF 则对bloom filter的内存分配进行优化，能够在bloom filter的误报率和读性能之间进行trade-off。
还是说，调优方案的选择需要结合实际的应用场景，当然通用的存储引擎RocksDB也集成auto tune这样的优化思想，通过ratelimiter来限制compaciton和flush的后台I/O ，结合auto tune感知用户workload的变化并对底层的rate-limiter限速带宽进行微调整，从而达到降低flush/compation对上层读长尾影响的目的。
3.7 二级索引优化方向
LSM-tree的二级索引技术能够高效得提升读性能，接下来从几个方面探讨业界在二级索引上做的优化：
- 索引的数据结构
- 索引的维护
- 统计信息的收集
- 分布式索引
3.7.1 索引数据结构
LSII【39】
Kim et al【40】
Filters【41】
Qadar et al【42】
3.7.2 索引的维护
Diff-Index【43】
DELI【44】
Luo and Carey【45】
3.7.3 统计信息收集
Absalyamov et al【46】
3.7.4 分布式索引
Joseph et al【47】
Zhu et al.【48】
Duan et al. 【49】
3.7.5 总结
3.8 总的调优讨论
基于RUM(read cost, update cost, memory or storage cost)的假设以及以上业界实现的各个维度的系统优化中，确实能够看到并没有办法对所有的workoad都有调优策略，都是在不同的worklaod之间进行trade-off。
如下图，是各个业界实现的系统在RUM中的trade-off情况，其中↑ 表示增加，↓ 表示降低，− 表示无影响，×表示该系统不支持的功能。
总体来看，以写性能为例，写吞吐提升的越高（Tiering 策略或 key-value分离）其对 点读和range scan的性能影响越大。
4. LSM-tree 经典实现
之前已经对LSM-tree可有的优化细节做了比较详细的讨论，接下来对五个基于LSM-tree的业界经典开源NoSQL实现进行描述。
- LevelDB
- RocksDB
- Cassandra
- HBase
- AsterixDB
后续的讨论主要关注的是他们的存储层的实现，并不会对整个系统的完整实现进行详细讨论。
4.1 LevelDB【50】
LevelDB是基于LSM-tree的key-value存储系统，由Google在2011年开源。https://github.com/google/leveldb
它支持几种非常简单的key-value接口: gets, puts, scan. LevelDB定位不是一个成熟的数据库管理系统，而是为更高层级的数据库系统的构建提供可插拔的存储引擎。LevelDB核心贡献是它第一个实现了基于分片的leveling合并策略：实现了将数据分片存储到sstable 以及 以sstable为单位进行leveling策略的compaction。LevelDB的这个设计影响了后来许多基于LSM-tree的NoSQL实现和优化方向。
关于Leveling 合并策略 概要来说就是 将 L ( i ) + L ( i + 1 ) L(i) + L(i+1) L(i)+L(i+1)的sst文件进行合并，合并的结果输出到 L ( i + 1 ) L(i+1) L(i+1)，且Leveling合并策略不允许当前层内sst文件之间有重叠key。
4.2 RocksDB【51】
RocksDB 刚开始 是2012年从LevelDB fork出来的一个子仓库，自那以后Rocksdb开发了非常多的新特性。因为Rocksdb的高性能和灵活性，Rocksdb被广泛应用在了facebook 的内部和外部。https://github.com/facebook/rocksdb
Facebook 使用LSM-tree的初衷是因为它优于B±tree的空间利用率。B±tree的 in-place updates会导致大量的内存碎片，而LSM-tree 虽然Appen-only形态，存在空间放大，但空间利用率相比于B±tree高很多。
如果将Rocksdb的空间放大比设置为10，Rocksdb的leveling实现中能够保证90%的数据都存放在largest level，保证剩下最多不超过10%的空间会因为存放过时数据而被浪费(开启rocksdb的leve_compaction_dynamice_bytes配置)【52】。而相反，B±tree实现的引擎，数据页会有2/3因为内存碎片而被浪费【53】。
接下来从几个方面讨论一下Rocskdb的一些新的优化特性：合并策略，合并操作 和 新功能。
合并策略的优化
Rocksdb的合并策略 是在leveling 为主的基础上进行设计的，并增加了一些优化特性。因为 SST文件在level0并没有分片（level0内的sst文件进行合并写入到level1），从L0->L1的合并(选择一部分L0的sst文件 和 一部分L1的sst文件)往往就是重写L1的数据，这是L0->L1合并的性能瓶颈。为了解决这个问题，Rocksdb对L0采用tiering合并策略（即L0+L0 --> L1，不会造成L1的数据反复重写），这个优化因为仅仅是放在L0，也不会对读性能有太大的影响。
RocksDB同时也支持动态调整level的size 来减少空间放大（前面说的leve_compaction_dynamice_bytes 配置，能够让90%的数据集中在最后一层），之所以有这个优化的原因是 实际场景如果按照默认Leveling的合并策略，大多数的数据都无法集中到最后一层（eg: size_ratio=10, num_levels=7, target_base_level_bytes=256*1024*1024， 这个配置下 到 size (level5) = 2.56T ，size(level6)=25.6T ）,也就是空间放大在中间层比较严重，所以为了实现 O ( T + 1 T ) O(\frac{T+1}{T}) O(TT+1)的空间复杂度，需要将大多数数据集中到最后一层，从而有了动态调整level size的特性。
合并操作的优化
LevelDB在合并过程中选择文件方式使用的是轮询方式，即满足有重叠度覆盖的sst文件直接选择为待合并的sst文件。RocksDB支持两种合并操作的优先级： 冷数据优先和删除优先。
- 冷数据优先策略会选择访问频率较低的sstable优先进行compaction，这个优化操作的初衷是针对有热点的数据，将其放在较低的层，则更有利用热点数据的访问。
- 删除优先的合并操作会选择一个sstable内删除操作较多的sst文件优先进行compaciton，从而更有利于存储空间的及时清理。
Rocksdb还支持Compaction filter这样的操作，将接口暴露给用户，合并过程中调用用户的过滤接口，并且可以由用户指定在合并过程中清理什么样的数据，这个特性能够更加高效的适配特定场景的数据清理功能。
Rocksdb除了支持leveling合并策略，还支持Tiering和FIFO合并策略。RocksDB实现的Tiering合并策略主要由两个参数来控制，合并组件（这里的组件也可以理解为sstable）的个数（K）和 放大比（T）。对于一个新的组件 C i C_i Ci，确认其是否能够参与compaction，需要检测 C i Ci Ci之前的 K − 1 K-1 K−1个组件的总大小是否达到了 C i C_i Ci的 T T T倍，此时会合并 C i , C ( i − 1 ) , C ( i − 2 ) , . . . C ( i − k ) C_i, C_(i-1), C_(i-2), ... C_(i-k) Ci,C(i−1),C(i−2),...C(i−k)的所有组件；否则将 C i C_i Ci保存下来，等待下一个组件 C ( i + 1 ) C_(i+1) C(i+1)是否满足以上条件。FIFO compaction则不会主动进行合并，而是每隔一段时间就删除旧的sstable。
在基于LSM-tree的存储中，合并操经常会消耗大量的CPU负载和磁盘带宽，从而间接对LSM-tree系统的读性能造成影响。所以Rocskdb实现了Ratelimter来限制Flush和Compaction的磁盘I/O，通过用户指定一个token(实际的限速带宽)，只有当Flush/Compaction累积的限速带宽达到了token的值才会触发实际的磁盘I/O。当然，这个优化在写heavy场景并没有太明显的效果，毕竟累积的compaction持续增加，速度超过token的refill速度，这一些数据得不到落盘 同样会累积导致compaction增加。
新功能
RocksDB支持了一个RMW(read-modify-write)的新特性，实际很多应用需要针对已经存在的数据执行RMW操作，通过先读，再修改，再写入这三步才能完成。为了让这个操作更加高效，Rocksdb实现了Merge Operator，允许用户指定合并方式，并且将一个merge operator作为一个写请求直接写入到memtable中，指定其type为mergeType。后续RocksDB在合并的时候检测到key-type是MergeType就触发针对该Key的用户指定的处理方式。同时，如果用户触发真对该key的读请求，同样会将之前写入的MergeType进行合并。
这个特性能够高效得处理用户对RMW操作 的需求。
更多的RocksDB的设计细节可以参考: https://github.com/facebook/rocksdb/wiki
关于Rocksdb的细节实现可以关注我的专栏: https://blog.csdn.net/z_stand/category_10058454.html
4.3 HBase【54】
HBase是Apache开源的分布式存储系统 https://github.com/apache/hbase， 其作为Hadoop 子系统而存在。它是google提出 Bigtable【55】设计之后的实现。HBase是主从架构，它将数据集通过hash分片为一个个region，其中的每一个region都是通过LSM-tree管理的。HBase能够根据用户workload支持region的动态split和merge。接下来的描述主要集中在HBase的存储引擎，也就是每个region中的LSM-tree。
HBase的LSM-tree的实现是基于Tiering合并策略，同样也支持一些Tiering合并策略的变种： Exploring-Merge policy 和 Date-Tierd merge policy。
- Exploring-Merge 会检查所有可合并的组件(可以理解为sstable)，并选择其中写入成本最小的一个组件序列（key range重叠度越高，合并之后数据量越少，写入成本也越少）。这个合并策略比Tiering 策略更有优势，因为其不会受待合并组建因更新和删除数据产生的大小不一的影响。所以，这个合并策略是HBase的默认合并策略。
- Data-Tierd合并策略主要用于管理拥有时间序列的数据。它的合并过程顾名思义，是按照写入key- value数据的时间戳所处范围来合并的，所以在这个策略下的数据是按照时间分片的。
近期，HBase又开发了新的特性 – Stripping。对一个大的region进行分片，提升合并效率。主要思想是对key的存储空间进行分片，让每一个分片空间内的组件能够独立进行compaction。
个人理解，有点像是RocksDB实现的ColumnFamily，不同的ColumnFamily之间的数据是隔离的，公用compaction线程池，但不同column family的compaction job之间的合并互不影响。
需要注意的是HBase并不支持本地的二级索引，region在本地并没有二级索引的实现，不过实现的话是很容易的。可以构建一个单独的table将索引键和主键存储存储在一块 构成二级索引。
4.4 Cassandra【56】
Cassandra是Apache实现的一个开源分布式存储系统 https://github.com/apache/cassandra，其是在有了Amazon’s Dynamo和Google BigTable的设计之后实现的。
Cassandra 通过分布式架构来避免单点故障，其中每一个数据分区由基于LSM-tree的存储引擎实现的。
Cassandra支持类似于RocksDB和HBase的合并策略，包括Tiering合并策略，leveling合并策略，Date-Tierd合并策略。Cassandra支持二级索引来加速读。在更新的过程中，如果在内存中发现了一个比较旧的key，会直接将内存中的二级索引中的该key的索引清理掉，否则就延迟到合并完主键索引之后再清理二级索引中的record。
4.5 AsterixDB【57】
AsterixDB是Apache实现的一个开源大数据管理系统(BDMS)，主要是管理超大规模半结构化数据（类似Json）,接下来主要看看AsterixDB存储层的设计。
AsterixDB采用的是无共享的并行数据库架构（ shared-nothing parallel database style architecture 这句话不知道怎么翻译更好。。。），在多节点下的数据分布是通过对每一个record的主键进行hash分片得到的。每一个分片下的数据集是LSM-tree的存储引擎通过 一个主键索引，一个主键key 索引 以及 多个二级索引进行管理的。AsterixDB使用分层事务模型来保证数据在不同分片之间的一致性。
后续的一些主键索引和二级索引的构造，因为对这个系统并没有足够深入的理解和实战， 论文中的一些描述细节还需要后续持续研究才能补充上来。
5. 总结
随着以LSM-tree为存储引擎的NoSQL系统越来越多，相比于传统B±tree的高效写吞吐，空间利用率，以及 灵活的可调整性，可预见的未来中LSM-tree仍将被更加广泛得应用。能够看到LSM-tree的光辉未来，但仍有许多可优化的方向需要去探索。论文中展现了到现在为止的业界所做的一些有趣的探索，希望这篇文章能够站在前人的肩膀上帮助对LSM-tree引擎感兴趣的同学打开更全面更严谨的学习大门。
如文中相关论文细节表达有误，欢迎大家一起讨论。关于，二级索引的优化部分将持续更新，这里的论文描述细节较多，其中举例的一些优化系统需要花费较多的时间去探索其底层细节。
参考文献
[1] : O’Neil, P., et al.: The log-structured merge-tree (LSM-tree). Acta Inf. 33
[2] : Jagadish, H.V., et al.: Incremental organization for data recording and warehousing
[3] : Bloom,B.H.:Space/timetrade-offsinhashcodingwithallowableerrors. CACM 13
[4] : Design of a write-optimized data store. Tech. rep., Georgi
[5] : Buildingefficientkey-valuestoresviaalightweight compaction tree
[6] : PebblesDB: Building key-value stores using frag- mented log-structured merge
[7] : dCompaction: Speeding up Compaction of the LSM-Tree via Delayed Compaction
[8] : Building an efficient put-intensive key-value store with skip-tree.
[9] : TRIAD: Creating synergies between memory,disk and log in log structured key-value stores.
[10] : Building workload-independent storage with VT-trees.
[11] : Pipelined compaction for the LSM-tree.
[12] : Compaction management in dis-tributed key-value datastores.
[13] : LSbM-tree: Re-enabling buffer caching in data management for mixed reads and writes
[14] : bLSM:Ageneralpurposelogstruc-tured merge tree
[15] : FloDB: Unlocking memory in persistent key- value stores
[16] : Accordion: Better Memory Organization for LSM Key-Value Stores
[17] : Scaling Concurrent Log-Structured Data Stores
[18] : Tree Indexing on Solid State Drives
[19] : A practical concurrent index for solid-state drives.
[20] : MaSM: Efficient Online Updates in Data Warehouses
[21] : WiscKey: Separating Keys from Values in SSD-conscious Storage
[22] : HashKV: Enabling Efficient Updates in KV Storage via Hashing
[23] : An efficient memory-mapped key-value store for flash storage
[24] : Redesigning LSMs for Nonvolatile Memory with NoveLSM
[25] : MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with a Matrix Container in NVM
[26] : LSM-tree managed storage for large-scale key- value store
[27] : An efficient design and implementation of LSM- tree based key-value store on open-channel SSD
[28] : NoFTL-KV: Tackling write-amplification on KV-stores with native storage managment
[29] : Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method
[30] : LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data
[31] : SlimDB: a space-efficient key-value storage engine for semi-sorted data
[32] : Bigtable merge compaction
[33] : Towards accurate and fast evaluation of multi-stage log-structured designs
[34] : Monkey: Optimal navigable key-value store
[35] : Optimal Bloomfilters and adaptive merging for LSM-trees.
[36] : Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging
[37] : ElasticBF: Fine-grained and elastic bloom filter towards efficient read for LSM-tree based KV-stores
[38] : Mutant: Balancing storage cost and latency in LSM-tree data stores
[50] : LevelDB. http://leveldb.org
[51] : RocksDB. http://rocksdb.org
[52] : Optimizing space amplification in RocksDB.
[53] : On random 2–3 trees.
[54] : Hbase. https://hbase.apache.org/
[55] : Bigtable: A distributed storage system for struc-tured data.
[56] : Cassandra: http://cassandra.apache.org
[57] : AsterixDB: A scalable, open source BDMS