论文阅读|LSM Tree

参考资料

背景

为了了解LSM Tree是个什么东西，我们需要先知道：需要解决什么样的问题❓才能看懂为什么之后要这么设计。

通常数据结构的更新有如图1的两种方式：

a. 就地更新。

b. 异地更新。

举个例子：比如我们有一个数据结构存放数据data[]，当我们想要修改data[1]=value，可以选择在原处修改，或者是增加一条log，说：“我们将data 偏移值为1的地方修改为了value”。

对于在内存中的数据，因为可以随机读写，所以我们通常就地更新。但是对于磁盘中的数据，随机读写貌似就不如顺序读写友善了。(建议看一眼：SSD 为什么顺序写比随机写性能更好？ - CobbLiu - 博客园 (cnblogs.com))

但是对于通过追加文件的方式，有了新的问题。

如果快速找到某个索引值？
当我们追加多条log，比如data[1]=a;data[1]=b;data[1]=c;，只有最后一条是有效的，随着系统的使用，会出现大量垃圾。

LSM Tree就解决了这些问题。

结构概览

在内部，可以使用任何索引结构实现LSM树组件。今天的LSM树实现——通常使用跳表或B +树等并发数据结构来组织内存组件，而使用B+树或排序字符串表(sorted-string tables， SSTables)来组织磁盘组件。SSTable包含一个数据块列表和一个索引块：数据块存储按键排序的键值对，索引块存储所有数据块的键范围（存储key的最大值和最小值）。

对 LSM 树的查询必须搜索多个组件才能执行协调，即查找每个键的最新版本。点查找(point lookup query)查询获取特定键的值，可以简单地从最新到最旧逐个搜索所有组件，并在找到第一个匹配项后立即停止。范围查询可以同时搜索所有组件，将搜索结果馈送到优先级队列中以执行协调。

但是随着时间推移，会出现我们之前提到过的那个问题：一个组件随着追加记录的写入，会越来越大。于是我们要进行组件合并。

在论文中，提到了下图的两种合并策略：

第一种：水平合并策略

每层只维护一个组件，比如Level 0 有一个组件，能存500条记录，Level1 有一个组件，能存2500条记录，现在有1500条记录在上面。

当level0 满了，将自己的500条记录合并到Level1, 现在Level1 有2000/2500条记录（也不一定，比如有些new key覆盖了old key,可能只有300条新的记录）。然后Level 0 组件此时空了，当又满了500条， Level 0继续将自己的组件向下合并。如果Level1的这个组件满了，就会选择向level2合并。

第二种：分层合并策略

每级最多维护 T 个组件。当 $L_i$ 级已满时，这T个组件将合并一起变成 $L_{i+1}$ 级的新组件。在图中，级别 0 的两个组件合并在一起，形成级别 1 的新组件。应该注意的是，如果 L 级已经是配置的最大级别，则生成的组件将保持在 L 级。在实践中，对于插入量等于删除量的稳定工作负载，级别总数保持静态。通常，水平合并策略会针对查询性能进行优化，因为在 LSM 树中要搜索的组件较少（每层只有一个）。分层合并策略的写入优化程度更高，因为它降低了合并频率。

之后会继续讨论两个合并策略的性能。

一些常见的优化

Bloom filter。Bloom过滤器是一种空间效率高的概率数据结构，旨在帮助回答集合成员查询（set membership queries）。它支持两种操作，即插入键和测试给定键的成员关系。为了插入一个键，它应用多个哈希函数将键映射到位向量中的多个位置，并将这些位置上的位设为1。为了检查给定键是否存在，该键再次散列到多个位置。如果所有位都是1，则Bloom过滤器报告键可能存在。按照设计，Bloom过滤器可以报告假阳性，但不能报告假阴性。

大意是：Bloom 过滤器可以维护一个键是否存在。如果该键不存在，那么if_exist(key)一定返回false，但是对于返回true的情况，可以存在该键，也可能不存在该键（hash冲突的情况）

布隆滤镜可以构建在磁盘组件之上，以大大提高点查找性能。要搜索磁盘组件，点查找查询可以首先检查其Bloom 过滤器，然后仅当其关联的 Bloom 过滤器报告肯定答案时才继续搜索其 B 树。或者，可以为磁盘组件的每个叶页构建 Bloom 筛选器。在此设计中，点查找查询可以首先搜索 B 树的非叶页以找到叶页，其中假定非叶页足够小，可以缓存，然后在获取叶页之前检查关联的 Bloom 筛选器，以减少磁盘 I/O。

Partitioning。另一种常用的优化是将LSM树的磁盘组件范围划分为多个(通常是固定大小的)小分区。为了尽量减少由不同术语造成的混淆，我们使用LevelDB中的术语SSTable来表示这样的分区。这种优化有几个优点。首先，分区将一个大的组件合并操作分解为多个较小的操作，限制了合并操作的处理时间以及创建新组件所需的磁盘空间。此外，分区可以通过只合并具有重叠键范围的组件来优化具有顺序创建键或倾斜更新的工作负载。对于按顺序创建的键，基本上不执行合并，因为没有键范围重叠的组件。对于倾斜更新，冷更新范围的组件的合并频率可以大大降低。需要注意的是，原来的LSM-tree会自动利用分区，因为它可以滚动合并。然而，由于滚动合并的实现复杂性，今天的LSM树实现通常选择实际的物理分区而不是滚动合并。

我们现在有了四种合并选择

合并策略/分区策略	分区	不分区
水平合并	LevelDB,RocksDB	?
分层合并	HBase	?

水平合并，分区

在LevelDB的分区leveling merge policy中，每个级别（Level）的磁盘组件被范围划分为多个固定大小的SSTable，如图4所示。每个SSTable在图中都有其key范围的标记。注意，Level 0的磁盘组件没有分区，因为它们是直接从内存中刷下的。这种设计还可以帮助系统吸收突发写（absorb write bursts），因为它可以在Level 0容忍多个未分区组件。为了将Level L的SSTable合并为Level L+1的SSTable，我们将选取其所有Level L+1的重叠的SSTable，并将这些重叠的SSTable与之合并，生成新的仍在Level L+1的SSTable。例如在图4中，Level 1标记为0-30的SSTable与Level 2标记为0-15和16-32的SSTable合并。这个合并操作产生在第2级标记为0-10、11-19和20-32的新的SSTables，然后旧的SSTable将被垃圾收集。可以使用不同的策略来选择接下来在每个Level合并哪个SSTable。例如，LevelDB使用循环策略（round-robin policy）以最小化总的写开销。

一些我看的时候的Note: Leveling Merge每层只有一个组件，图上的意思是一个组件可能有多个分区，每个分区被表示为一个SSTable。图上表示的是第一张图的三个灰色SSTable合并，生成了第二张图的三个新的SSTable。

分级合并，分区

垂直分区

如图，每个组件拥有范围重叠的多个SSTable。

水平分区

每个组件之中的SSTable互不重叠。存在多个水平组件。这种情况下合并。

并发控制

现在，我们简要讨论当今 LSM 树实现所使用的并发控制和恢复技术。对于并发控制，LSM 树需要处理并发读取和写入，并处理并发刷新和合并操作。确保并发读取和写入的正确性是数据库系统中访问方法的一般要求。根据事务隔离要求，当今的 LSM 树实现要幺使用锁定方案，要幺使用多版本方案。多版本方案适用于 LSM 树，因为在合并期间可以自然地对密钥的过时版本进行垃圾回收。但是，并发刷新和合并操作是 LSM 树所特有的。这些操作修改 LSM 树的元数据，例如活动组件列表。因此，必须正确同步对组件元数据的访问。为了防止正在使用的组件被删除，每个组件都可以维护一个引用计数器。在访问 LSM 树的组件之前，查询可以首先获取活动组件的快照并递增其使用中的计数器。

由于所有写操作都是先追加到内存中，因此可以执行预写日志记录(write- ahead logging, WAL)以确保它们的持久性。为了简化恢复过程，现有系统通常采用no-steal的缓冲区管理策略。也就是说，只有当所有活跃的写事务都终止时，内存组件才能刷新。在LSM-tree的恢复过程中，将重放事务日志以重做所有成功的事务，但由于no-steal策略**(no-steal策略不允许未提交的数据持久化！)，不需要撤消。同时，在发生崩溃的情况下，还必须恢复活跃磁盘组件列表。对于未分区的LSM树，可以通过向每个磁盘组件添加一对时间戳来实现这一点，这些时间戳指示存储条目的时间戳范围**。这个时间戳可以简单地使用本地壁钟时间（local wall-lock time）或单调的序列号生成。要重建组件列表，恢复过程只需找到所有时间戳不相交的组件。如果多个组件具有重叠的时间戳，则选择时间戳范围最大的组件，其余组件可以简单地删除，因为它们将被合并成所选组件。对于分区的LSM树，这种基于时间戳的方法不再有效，因为每个组件都进一步进行了范围分区。为了解决这个问题，在LevelDB和RocksDB中使用的一种典型方法是维护一个单独的元数据日志（上图的MANIFEST），以存储对结构元数据的所有更改，如添加或删除SSTable。然后，可以通过在恢复期间REDO元数据日志来重新构建LSM-tree结构的状态。

API

插入

直接插入内存中的数据结构（平衡二叉树）

删除

通过直接往内存中插入墓碑标记完成操作。时间复杂度控制在平衡二叉树中。不用进行磁盘读写

修改

如果目标数据在内存中，直接修改。

否则直接往内存中写入新的数据，防止读磁盘。

查询

查询是性能比较低的。

因为我们要找最新的数据，所以只能按照内存->level1->level2的顺序去找。

如果找到了第一个key,直接返回。否则我们要一直找，因为不能确定下一层有没有目标key。最坏情况下，需要查找到最后一层。

所幸的是，可以通过前面提到的布隆过滤器和稀疏索引来进行优化。

合并

合并类似于合并两个有序链表，但是如果key相同，只需要保留最新的数据。

回想之前提到的，一个组件中有多个SSTable,这些SSTable都是互不重叠的，所以可以并发执行。

如果是之前说的垂直分区呢，我想到了23. 合并 K 个升序链表 - 力扣（LeetCode）。（可能是类似的方法）

LSM-Tree 的优化

如果情况真像我写的那么简单就好了。

事实上，还存在许多性能上的问题。

问题分类

Write amplification 写放大 尽管 LSM 树可以通过减少随机 I/O 来提供比 B+ 树等就地更新结构更好的写入吞吐量，但 LevelDB 和 RocksDB 等现代键值存储所采用的leveling merge策略仍然会产生相对较高的写入放大。高写入放大不仅限制了 LSM 树的写入性能，还由于频繁使用磁盘而缩短了 SSD 的使用寿命。已经进行了大量的研究来减少LSM树的写入放大。

Merge operations 合并操作。合并操作对LSM树的性能至关重要，因此必须谨慎地实现合并操作。此外，合并操作可能会对系统产生负面影响，包括合并后的缓冲区缓存丢失和大型合并期间的写暂停。为了解决这些问题，已经提出了一些改进措施来优化合并操作。

Hardware 硬件。为了使性能最大化，必须仔细地实现LSM树以充分利用底层硬件平台。最初的LSM树是为硬盘设计的，其目标是减少随机I/O。近年来，新的硬件平台为数据库系统提供了实现更好性能的新机会。最新研究很重要的一部分是在致力于改进LSM树，以充分利用硬件平台，包括大内存、多核、SSD/NVM和本地存储。

Special workloads 特殊负载。除了硬件机会之外，还可以考虑某些特殊的工作负载，以便在这些用例中获得更好的性能。在这种情况下，必须对基本的LSM树实现进行调整和定制，以利用这些特殊工作负载所显示的独特特性。

Auto-tuning 自动调优。基于RUM猜想，任何访问方法都不能同时是读最优、写最优和空间最优。LSM树的可调性是一个很有前途的解决方案，可以实现给定工作负载的最优权衡。但是，LSM树可能很难调优，因为有太多的调优旋钮（tuning knobs），比如内存分配、合并策略、大小比率等。为了解决这个问题，有文献提出了几种自动调优技术。

Secondary indexing 二级索引。给定的LSM树只提供简单的键-值接口。为了支持对非键属性的查询的有效处理，必须维护二级索引。这方面的一个问题是如何以较小的写性能开销有效地维护一组相关的二级索引。多种基于LSM的二级索引结构和技术被设计出来并且被评估。

图7是LSM Tree改进的分类。

接下来内容太多了。直接机翻，然后找了一些相关的图片再解释。

减少写放大

leveling的写方法问题很严重，因为它每层只有一个组件，满了就得merge。

Tiering

本小节改进大部分都是基于tiering，因为它的写性能要比leveling好得多。其他提出的改进包括开发新的技术来执行合并跳过（merge skipping）或利用数据倾斜（data skews）。

WriteBuffer (WB) Tree可以看作是具有垂直分组的分区分层设计的一个变体。它做了如下修改。首先，它依靠散列分区（hash-partitioning）来实现工作负载平衡，以便每个SSTable组大致存储相同数量的数据。此外，它将SSTable组组织成一个B+树状结构，以使自平衡最小化总level数。具体来说，每个SSTable组都被视为B+树中的一个节点。当非叶节点被T个SSTable填满时，这些T个SSTable被合并在一起，形成新的SSTable，并添加到子节点中。当一个叶节点被T个SSTable填满时，它会拆分为两个叶子节点，通过将它的所有SSTable合并成两个key范围更小的叶子节点实现，使得每个新的节点有T/2个SSTable。

3-Figure1-1

4-Figure2-1

图二描述了WB Tree分裂的过程。

**The lightweight compaction tree (LWC-tree)**采用了类似的垂直分组的分区分层设计。进一步提出了一种实现SSTable组工作负载平衡的方法。回想一下，在垂直分组方案下，SSTable不再是严格的固定大小，因为它们是根据下一层重叠组的关键范围而不是根据它们的大小生产的。在LWC-tree中，如果一个组包含过多的条目，它将在合并组后收缩该组的键范围，并相应地扩大其同级组的键范围。

4-Figure1-1

PebblesDB [58]也采用了垂直分组的分区分层设计。主要的区别在于，它利用跳跃表[54]所启发的守卫（Guard）思想来决定SSTable组的关键范围。守卫是SSTable组的key范围，它是基于已插入key的概率选择，以实现工作负载平衡。一旦选择了一个守卫，它将在下一次合并期间惰性地应用。PebblesDB进一步执行SSTables的并行查找，以提高范围查询性能。

dCompaction [52]引入了虚拟SSTables和虚拟合并的概念来降低合并频率。一个虚拟的合并操作产生一个虚拟的SSTable，它简单地指向输入的SSTable，而不执行实际的合并。然而，由于虚拟SSTable指向多个范围重叠的SSTable，查询性能将会下降。为了解决这个问题，dCompaction引入了一个基于实际SSTable数量的阈值来触发实际的合并。如果在查询处理过程中遇到指向太多SSTable的虚拟SSTable，它还允许查询触发实际的合并。一般来说，dCompaction会延迟合并操作，直到多个SSTable被合并在一起，因此它也可以看作是分级合并策略（tiering merge policy）的变体。

可以看到，上面描述的四种结构都有一个类似的基于垂直分组的分区分层的高级设计。它们主要区别于如何执行SSTable组的工作负载平衡。例如，WB-tree[6]依赖于哈希散列，但是这样做就放弃了支持范围查询的能力。LWC-tree[78,79]动态收缩密集SSTable组的关键范围，而PebblesDB[58]依赖于概率选择的守卫。相反，dCompaction[52]不提供工作负载平衡的内置支持。目前尚不清楚倾斜的SSTable组将如何影响这些结构的性能，需要未来的研究来理解这个问题并评估这些工作负载平衡策略。

….

看了下这部分就是文献综述，讲了各种各样的优化方式。感觉不花时间去看提到的内容是没啥意义的。

二级索引

到目前为止，论文讨论了仅包含单个 LSM 树的键值存储设置中的 LSM 树改进。现在，我们将讨论基于 LSM 的二级索引技术，以支持高效的查询处理，包括索引结构、索引维护、统计信息收集和分布式索引。

在详细介绍这些研究成果之前，我们首先讨论基于LSM的二级索引技术的一些基本概念。通常，基于LSM的存储系统会包含一个主索引和多个二级索引。主索引存储按其主键索引的记录值。每个辅助索引使用组合键方法（composite key）或键列表（key list）方法存储每个辅助键对应的主键。在组合键方法中，二级索引的索引键是二级键和主键的组合。在键列表方法中，辅助索引将主键列表与每个辅助键关联起来。无论哪种方式，要使用辅助索引处理查询，首先搜索辅助索引以返回匹配的主键列表，然后在需要时使用这些主键从主索引中获取记录。图15给出了一个基于LSM的二级索引示例。示例用户数据集有三个字段，即Id、Name和Age，其中Id是主键。主索引存储按Id索引的完整记录，而两个辅助索引存储辅助键，即Name和Age，以及它们对应的Id。

讲解：这段话说的很多，其实很多索引都是长这样的。对于主键，key为主键，value为这行的数据。对于辅助索引，key为辅助的索引列，value为主键。
要通过辅助索引获取数据，还要经过先拿到主键，再通过主键获取value的过程。这一部分被叫做回表，数据库优化中会尽量减少这个操作。

倒排索引

日志结构倒置索引(log-structured inverted index, LSII)是一种针对微博（microblogs）上的精确实时关键词搜索而设计的索引结构。一个查询q搜索得分最高的前K个微博，将其计算为显著性、新鲜度和相关性的加权和。为了支持高效的查询处理，磁盘组件中的每个关键字存储了三个主键的倒置列表，分别按重要性、新鲜度和频率降序排列。存储三个倒置的列表使查询能够通过阈值算法[27]有效地处理，一旦未见微博的得分上限低于当前的前K个答案，该算法就会停止计算。然而，内存组件中只存储了一个倒置列表，因为内存组件中的文档通常具有很高的新鲜度，并且大多数文档会被查询访问。此外，存储多个倒置表将显著增加内存组件的写成本。

论文原文：LSII: An indexing structure for exact real-time search on microblogs (edwlin.github.io)

维护索引

维护基于LSM的二级索引的一个关键挑战是处理更新。对于主LSM树，更新可以盲目地将新条目(具有相同的键)添加到内存组件中，以便自动删除旧条目。但是，这种机制不适用于辅助索引，因为辅助键值在更新期间可能会更改。在更新期间，必须执行额外的工作来清除二级索引中过时的条目。

下面是一些维护索引的方法：

**Diff-Index[66]**提出了基于LSM的二级索引的四种索引维护方案，即同步全索引、同步插入索引、异步简单索引和异步会话索引（sync-full, sync-insert, async-simple, and async-session.）。在更新期间，更新二级索引必须执行两个步骤，即插入新条目和清除旧条目。对于LSM-tree，插入新条目非常有效，但是清除旧条目通常非常昂贵，因为它需要点查找来获取旧记录。Sync-full在ingestion时间内同步执行这两个步骤。它优化了查询性能，因为二级索引总是最新的，但由于点查找，在data ingestion期间会产生很高的开销。Sync-insert只将新数据插入二级索引，而通过查询来惰性地清除过时的条目。Async-simple异步执行索引维护，但通过将更新附加到异步更新队列中来保证其均匀执行。最后，通过将新更新临时存储到客户端本地缓存中，async-session增强了async-simple应用程序的session一致性。

递延轻量级索引(Deferred lightweight indexing, DELI)[67]增强了Diff-Index[66]的同步-插入更新方案，采用了一种新的方法，通过扫描主索引组件来清除二级索引。具体来说，当扫描主索引组件时遇到多个具有相同键的记录时，将使用废弃记录产生反物质条目来清理二级索引。请注意，这个过程可以自然地与主索引的合并过程集成，以减少额外的开销。同时，由于二级索引并不总是最新的，查询必须总是通过从主索引获取记录来验证搜索结果。因此，DELI不能有效地支持仅索引查询，因为必须执行点查找以进行验证。

Luo和Carey[45]提出了几种有效开发和维护基于LSM的辅助结构的技术，包括二级索引和过滤器。他们首先进行了一项实验研究，以评估各种点查找优化的有效性，包括一种新提出的批处理查找算法，该算法为一批键顺序访问组件，有状态B+树搜索游标，以及阻塞的bloom过滤器[55]。他们发现，批处理查找算法是减少随机I/O的最有效优化，而其他两种算法主要对非选择性查询有效，进一步降低内存搜索成本。为了有效地维护辅助结构，进一步提出了两种策略。关键的见解是维护和利用主键索引，该索引只存储主键和时间戳，以减少磁盘I/O。提出了一种在后台惰性维护二级索引的验证策略，消除了同步点查找开销。查询必须验证由辅助索引返回的主键，方法是直接从主索引获取记录，或者搜索主键索引，以确保返回的主键仍然具有最新的时间戳。在后台使用主键索引有效地清理二级索引，以避免访问完整的记录;清理的基本思想是搜索主键索引，以验证每个辅助索引条目是否仍然具有最新的时间戳，就像查询验证一样。与DELI[67]相比，验证策略[45]显著降低了清理二级索引的I/O成本，因为只访问主键索引。此外，还引入了可变位图策略，以有效地使用过滤器维护主索引。它为每个磁盘组件附加了一个可变位图，以便可以直接将旧记录标记为已删除，从而避免了基于旧记录维护过滤器的需要。

3.7.3 Statistics collection

Absalyamov等人为基于LSM的系统提出了一个轻量级统计收集框架。其基本思想是将统计信息收集任务集成到刷新和合并操作中，以最小化统计信息维护开销。在刷新和合并操作期间，动态创建统计同步图(如直方图和小波)并将其发送回系统编目。由于LSM树的多组件特性，系统目录存储数据集的多重统计信息。为了减少查询优化过程中的开销，可合并的统计信息，如等宽直方图，会提前合并。对于不可合并的统计量，保留多个概要以提高基数估计的准确性。

3.7.4 Distributed indexing

Joseph等人的[25]在HBase[32]的基础上描述了分布式二级索引的两种基本实现，即全局二级索引和局部二级索引，这是在并行数据库中对数据进行索引的两种常见方法的基础上实现的。全局二级索引是一个单独的表，用来存储二级键和它们对应的主键，使用HBase提供的协处理器(类似于数据库触发器)来维护。这种方法易于实现，但是在数据摄取期间会产生更高的通信成本，因为二级索引分区可能存储在与主索引分区不同的单独节点上。本地二级索引通过将每个二级索引分区与相应的主索引分区放在一起，避免了数据摄入过程中的通信开销。然而，HBase的缺点是这种方法必须从头开始实现。此外，必须搜索本地二级索引的所有分区，即使对于高度选择性查询也是如此，因为本地二级索引是根据主键(而不是辅助键)划分的。

Zhu等[85]引入了一种高效的全局二级索引加载方法，该方法采用了三个步骤:首先，扫描每个分区上的主索引并对其排序，创建一个局部二级索引。同时收集备用密钥的统计信息，便于下一步操作。其次，根据从第一阶段收集的统计信息，将对二级索引的索引项进行范围分区，并将这些分区分配给物理节点。最后，每个节点根据所分配的辅助键范围，从所有其他节点中获取辅助键及其主键，通过扫描第一阶段构建的本地辅助索引可以有效地完成这一任务。

Duan等人[26]提出了一种分布式LSM树上物化视图的惰性维护方法。其基本思想是将新的更新追加到实体化视图的增量列表中，以减少数据摄取期间的开销。然后，在查询处理期间，增量列表中的更改被惰性地应用到物化视图。

优化总结

原文给出了一张表，列出了所提及的优化

已有的开源LSM实现

在详细讨论了LSM树及其改进之后，我们现在介绍了5个具有代表性的基于LSM的开源NoSQL系统，即LevelDB[40]、RocksDB[57]、Cassandra[14]、HBase[32]和AsterixDB[3]。我们将重点关注它们的存储层。

LevelDB

google/leveldb: LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values. (github.com)

LevelDB[40]是一个基于LSM的键值存储，在2011年由谷歌开源。它支持一个简单的键值接口，包括puts、gets和scans。LevelDB不是一个成熟的数据管理系统，而是一个嵌入式存储引擎，旨在支持更高级别的应用程序。LevelDB的主要贡献是它率先设计和实现了partitioned leveling合并策略，这在第2.2.1节中有描述。正如我们在这次调查中所看到的，这种设计影响了许多后续的LSM树改进和实现。由于我们已经在第2.2.1节中描述了partitioned leveling，我们在这里省略了进一步的讨论。

RocksDB

facebook/rocksdb: A library that provides an embeddable, persistent key-value store for fast storage. (github.com)

关键词： FIFO合并策略，自定义合并过滤器，冷优先和删除优先，Read-Modify-Write

RocksDB[57]最初是Facebook于2012年创建的LevelDB分支。从那时起，RocksDB添加了大量新功能。由于其高性能和灵活性，RocksDB已成功应用于Facebook内外的各种系统[24]。与Facebook一致，他们采用基于lsm的存储的主要动机是其良好的空间利用率[24]。在默认大小比率为10的情况下，RocksDB的升级实现在最大级别上拥有大约90%的总数据，确保总存储空间最多有10%被浪费在存储过时的条目上。如前所述，这种方法的性能优于传统的基于b树的存储引擎，在传统的b树存储引擎中，由于分片处理，页面通常平均满2/3[77]。这里我们将讨论RocksDB所做的各种改进，包括合并策略、合并操作和新功能方面的改进。

RocksDB的lsm树实现仍然基于partitioned leveling设计，但有一些改进。由于级别0的SSTable没有被分区，从级别0合并一个SSTable到级别1通常会导致所有级别1的SSTable被重写，这通常会使级别0成为性能瓶颈。为了部分解决这个问题，RocksDB可以使用tiering合并策略在0级合并SSTable。这种弹性设计允许RocksDB在不降低查询性能的情况下更好地吸收写突发。RocksDB进一步支持动态级大小方案来限制空间放大。问题是，理想的leveling空间放大 $O(\frac{T+1}{T})$只有在最后一层达到最大尺寸时才能实现，但在实践中可能并不总是发生。为了解决这个问题，RocksDB根据最后一层的当前大小动态调整所有较低层的最大容量，从而确保空间放大始终为$O(\frac{T+1}{T})$ 。除了LevelDB中使用的轮询策略来选择要合并的SSTable外，RocksDB还支持两个额外的策略，即冷优先和删除优先。冷优先策略选择冷SSTable进行合并，以优化倾斜的工作负载。它确保频繁更新的热SSTable将保持在较低的级别，以减少它们的总写成本。删除优先策略选择具有大量反物质条目的SSTable，快速回收被删除条目占用的磁盘空间。最后，RocksDB支持一个名为合并过滤器（merge filter的API，允许用户提供自定义逻辑，以便在合并期间有效地收集废弃项。在合并过程中，RocksDB会使用每个键值对调用用户提供的合并过滤器，并且只将那些没有被过滤的键值对添加到生成的SSTable中。

除了partitioned leveling合并策略外，RocksDB还支持tiering和FIFO等其他合并策略。在RocksDB和其他系统中，实际的tiering策略与本文(和其他文献)中描述的略有不同。RocksDB的tiering合并策略由两个参数控制，即合并组件的数量( $K$)和大小比($T$)。它的工作原理是检查从最老到最新的组件，对于每个组件 $C_i$ ，它检查$K-1$个较年轻的组件 $C_{i-1},C_{i-2},C_{i-3}…C_{i-K},$是否大于 $C_{i}$ 的 $T$倍。如果大于，该策略将所有这些组件合并在一起；否则，它将继续检查下一个较年轻的组件。RocksDB对其tiering合并策略执行有限分区（limited partitioned），类似于水平分组设计(章节2.2.2)，以限定SSTable的最大大小。其动机是最大页面大小被限制为4GB，但是巨大组件(存储为单个SSTable)的索引页面可能超过这个大小限制。然而，在大的合并期间，由于RocksDB将每个SSTable组视为一个整体，只在合并操作完全完成时删除旧的SSTable，因此磁盘空间仍然可能临时增加一倍。在FIFO合并策略中，根本不合并组件，但将根据指定的生存期删除旧的组件。

在基于lsm的存储中，合并操作通常会消耗大量CPU和磁盘资源，从而对查询性能产生负面影响。而且，合并的时间通常是不可预测的，因为它直接取决于写速率。为了缓解这一问题，RocksDB支持基于漏桶（leaky bucket）机制的速率限制来控制合并操作的磁盘写入速度[72]。其基本思想是维护一个存有许多token的桶，token由token填充速度控制。在执行每次写操作之前，所有刷新和合并操作都必须请求一定数量的token。因此，刷新和合并操作的磁盘写入速度将受指定的token填充速度限制。

最后，RocksDB支持一种叫做Read-Modify-Write的新操作。在实践中，许多应用程序通常通过先读取现有的值来更新它们。为了有效地支持这种操作，RocksDB允许用户直接将增量记录（delta record）写入内存，从而避免读取原始记录。然后，在查询处理期间将增量记录与基础记录组合起来，并根据用户提供的组合逻辑进行合并。如果可以应用，RocksDB会在合并过程中进一步将多个增量记录合并在一起，以提高后续的查询性能。

HBase

apache/hbase: Apache HBase (github.com)

Apache HBase[32]是Hadoop生态系统中的分布式数据存储系统；它是模仿谷歌的Bigtable设计[16]。HBase基于主从架构。它将数据集划分(散列或范围)为一组区域，其中每个区域由LSM树管理。HBase支持区域的动态拆分和合并，可以根据给定的工作负载对系统资源进行弹性管理。这里我们重点介绍HBase的存储引擎。

HBase的LSM-tree实现一般基于基本的tiering合并策略。它还支持tiering合并策略的一些变体，如探查合并策略（exploring merge policy）和日期分层合并策略（date-tiered merge policy）。探查合并策略检查所有可合并的组件序列，并选择写开销最小的组件序列。这种合并策略比基本的分层合并策略更健壮，特别是当组件由于加载和删除而大小不规则时。因此，它作为HBase默认的合并策略。日期分层合并策略是为管理时间序列数据而设计的。它根据组件的时间范围而不是它们的大小合并组件，因此组件将被时间范围划分。这可以有效地处理时态查询。

最近，HBase引入了一个叫做剥离（stripping）的新特性，可以对一个大的区域进行分区，以提高合并效率。其思想是对键空间进行分区，以便每个包含组件列表的分区独立合并。这与PE文件[35]提出的设计类似，但与2.2.1节描述的分区tiering合并策略不同。

HBase本身不支持二级索引。无论如何，二级索引可以实现为一个单独的表，使用协处理器存储二级键及其主键，如[25]中所述。

Cassandra

apache/cassandra: Mirror of Apache Cassandra (github.com)

Apache Cassandra[14]是基于Amazon的Dynamo[23]和谷歌的BigTable[16]开发的开源分布式数据存储系统。Cassandra依靠一个去中心化的架构来消除单点故障的可能性。Cassandra中的每个数据分区都由一个基于lsm的存储引擎提供支持。

Cassandra支持一组类似于RocksDB和HBase的合并策略，包括(未分区)tiering合并策略、分区leveling合并策略和日期分层（date-tiered）合并策略。此外，Cassandra还支持本地二级索引，方便查询处理。为了避免高点查找开销，二级索引是惰性主索引，类似于DELI[67]。在更新过程中，如果在内存组件中发现旧记录，则使用它直接清理二级索引。否则，当合并主索引组件时，二级索引将被清空。

AsterixDB

apache/asterixdb: Mirror of Apache AsterixDB (github.com)

Apache AsterixDB[3]是一个开源的大数据管理系统(BDMS)，旨在有效管理大量半结构化(如JSON)数据。这里我们主要关注AsterixDB[4]的存储管理方面。

AsterixDB使用无共享并行数据库风格的体系结构。每个数据集的记录都基于它们的主键跨多个节点进行散列分区。数据集的每个分区由一个基于LSM的存储引擎管理，该存储引擎具有一个主索引、一个主键索引和多个本地二级索引。AsterixDB使用记录级事务模型来确保每个分区内的所有索引保持一致。主索引存储按主键索引的记录，而主键索引仅存储主键。建立主键索引是为了有效地支持count(*)风格的查询以及各种索引维护操作[45]，因为它比主索引小得多。

辅助索引使用辅助键和主键的组合作为它们的索引键。AsterixDB支持基于LSM的B+树、R树和使用通用LSM-ification （LSM转换）框架的反向索引，该框架可以将就地索引转换为基于LSM的索引。为LSM-based R-tree，一个线性顺序，如希尔伯特曲线点数据和非点数据的Z-order曲线数据，被用于在磁盘组件条目的排序，而在内存组件中，删除的键被记录在单独的B +树中，以避免删除期间的多路径遍历。AsterixDB还支持基于LSM的反向索引，以有效地处理全文查询和相似查询[38]。默认情况下，每个LSM索引组件都使用类似tiering的合并策略独立地合并。AsterixDB还支持一种关联的合并策略，该策略将所有数据集索引的合并同步到一起，以提高过滤器的查询性能。该策略的基本思想是将合并调度委托给主索引。当一个主索引组件序列被合并时，来自其他索引的所有相应组件也将被合并。

Future research directions

对文献中现有的LSM树改进进行分类和总结，可以发现一些有趣的outages和机遇，并为今后在基于LSM的存储方面的工作提供了机会。我们现在简要讨论一些由调查结果提出的未来的研究方向。

全面的性能评估（Thorough performance evaluation）。如前所述，迄今为止的许多研究工作都没有充分考虑LSM树的可调性。改进工作通常是根据LevelDB或RocksDB的默认(未调优)配置进行评估的。对于给定的工作负载，这些改进将如何与调优的基线LSM树进行比较尚不清楚。此外，许多改进建议主要评估了它们对查询性能的影响，而空间利用率往往被忽略。这种情况可以在未来的研究中通过更仔细地考虑LSM树的可调性来解决。

分区tiering结构（Partitioned tiering structure）。tiering已经被许多LSM树改进所使用，以减少LSM树的写放大。在2.2.1节中，我们已经确定了两种可能的分区tiering方案，即水平分组和垂直分组，它们几乎涵盖了最近提出的所有与tiering相关的LSM树改进。然而，这两种方案的性能特点和权衡尚不清楚。一般来说，垂直分组在选择合并SSTable时具有更大的自由度，而水平分组则确保SSTable的大小是固定的。系统地评价这两种方案，并可能设计出结合两者优点的新方案，将是今后的工作。

混合合并策略（Hybrid merge policy）。直到最近，大多数LSM树的改进都假定在LSM树的所有级别上采用一种同质的合并策略。然而，对于某些工作负载[20]，这已被证明是次优的。leveling和tiering的混合合并策略可以提供比leveling更好的写性能，并且对点查找、长距离查询和空间放大的影响最小。作为未来的一个方向，设计和实现带有混合合并策略的LSM树，并重新考虑这种设计选择所提出的一些关键问题将是有趣的。

最小化的性能差异（Minimizing performance variance）。在实践中，性能差异是与绝对吞吐量同样重要的性能度量。不幸的是，LSM树经常表现出很大的性能差异，因为它们将内存中写与昂贵的后台I/O解耦。正如我们在本次调查中所看到的，bLSM[61]是唯一试图最小化LSM树所展示的写停顿的方法。然而，bLSM本身仍有一些局限性。它是专为未分区leveling合并策略而设计的，并且它只最小化了由于写暂停而导致的长写延迟，而不是总体摄入吞吐量的变化。作为未来的工作，设计最小化LSM树性能差异的机制将是非常有用的。

面向数据库存储引擎（Toward database storage engines）。最后，大多数现有的LSM树改进都非常局限于涉及单个LSM树的键-值存储设置。随着LSM树逐渐在DBMS存储引擎中广泛使用，应该针对这种更通用的(多索引)设置开发新的查询处理和数据摄取技术。可能的例子包括辅助结构的自适应维护以促进查询处理，支持LSM的查询优化，以及LSM树维护任务与查询执行的协同规划。

总结

这篇论文前面还好。后面优化部分是在太多了，可能一段就是别人一篇论文的内容，还得看。至于具体的实现，看了LevelDB的源码，感觉还有挺多细节。