LevelDB源码分析——0.前置知识

零．前置知识

本节为LevelDB源码分析的第0章，主要介绍LevelDB相关的前置知识。包括：LSM Tree、Bloom Filter。

1. LSM Tree

LSM-Tree(Log-Structured Merged-tree) 现如今已经被广泛应用在了各个NoSQL 存储系统中，如BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB 和 AsterixDB。

相比于传统的in-place updates(就地更新) 索引结构，LSM-tree 第一次写入都缓存到内存中，并通过后台的flush来顺序追加到磁盘中，也就是out-of-place updates。 LSM-tree这样的实现方式有非常多的优点，包括写性能的提升、较高的空间利用率、简单的并发控制和异常恢复等。这些优点使LSM树可以服务于多种场景，如Facebook开发的基于LSM-Tree的存储引擎 RocksDB， 被广泛应用在实时数据处理/图数据处理/流式数据处理以及 OLTP(on line transaction processing) 等多种workload。

1.1 LSM Tree的历史

通常，索引结构可以选择两种策略来处理更新，即就地更新和非就地更新。 就地更新结构（例如B +树）直接覆盖旧记录以存储新更新。 例如，在图1a中，为了将与键k1相关的值从v1更新到v4，直接修改索引条目（k1，v1）以应用此更新。

由于仅存储每个记录的最新版本，因此通常对这些结构可以进行读取优化。 但是，这种设计会牺牲写入性能，因为更新会导致随机I / O。 而且，索引页通过更新和删除操作会产生分段，从而降低了空间利用率。

相反，out-of-update结构（例如LSM树）始终将更新变化存储到新位置，而不是覆盖旧条目。 例如，在图1b中，更新（k1，v4）被存储到一个新位置，而不是直接更新旧条目（k1，v1）。 该设计可以利用顺序I / O来处理写操作，因此可以提高写性能。 通过不覆盖旧数据，它也可以简化恢复过程。 但是，该设计的主要问题是，由于记录可能存储在多个位置中的任何一个位置，因此牺牲了读取性能。 此外，这些结构通常需要单独的数据重组过程以不断提高存储和查询效率。

顺序进行out-of-places更新的想法并不新鲜；

• 自1970年代以来，它已成功地应用于数据库系统。 差异文件于1976年提出，是out-of-places更新结构的早期示例。 在这种设计中，所有更新都首先应用于差异文件，该文件定期与主文件合并。
• 在1980年代，Postgres项目开创了日志结构数据库存储的想法。 Postgres将所有写入追加到顺序日志中，从而实现快速恢复和基于时间戳的查询。 它使用称为vacuum cleaner的后台进程连续从日志中收集并去除过时的记录——垃圾收集。 文件系统社区采用了类似的想法来充分利用磁盘写带宽，例如在日志结构文件系统（LFS）中。

在LSM树之前，用于日志结构化存储的方法存在几个关键问题。

• 首先，将数据存储到仅追加日志中会导致查询性能下降，因为相关记录分散在整个日志中。
• 另一个问题是由于尚未删除的过时记录而导致空间利用率低。 即使设计了各种数据重组过程，也没有统一标准的成本模型来分析写入/读取成本和空间利用率之间的折衷，这使得早期日志结构化存储难以优化。
• 数据重组很容易成为性能瓶颈。

1996年提出的LSM树通过设计一种集成到结构本身中的合并操作来解决上述问题，提供较高的写入吞吐、基于范围的高效查找 、友好的空间利用率。

• 原始的LSM树设计包含一系列组件C0，C1，…，Ck，如图2所示。每个组件都被构造为B+树。 C0驻留在内存中并处理传入的写操作，而所有其余组件C1，Ck都驻留在磁盘上。 Ci满时，将触发滚动合并过程，以将一系列范围从Ci的叶子页面合并为Ci + 1
• 如今，这种设计被引用到多层合并策略中。但是，正如我们稍后将要看到的那样，由于其实现复杂性，现今基于LSM的存储系统并未使用最初提出的滚动合并过程。关于LSM树的原始论文进一步表明，在稳定的workload下，层级数量保持不变，当所有相邻组件之间的大小比率Ti = ｜Ci+1｜/｜Ci｜相同时，写性能能得到优化。该原则影响了LSM树的所有后续实现和改进。

与LSM树并行，Jagadish等人。 提出了一种stepped-merge逐步合并策略的结构，可以实现更好的写入性能。 它将组件组织到各个级别中，并且当级别L充满T组件时，这些T组件将合并在一起成为级别L + 1的新组件。 该策略成为当今LSM树实施中使用的分层合并策略。

1.2 今天的LSM Tree

今天的LSM-tree架构仍然以out-of-place updates 为主 通过顺序I/O来提升写性能。所有的写入，都会追加到内存中的组件，不论是更新还是插入还是删除，都会以一个新的记录添加到内存中。

在内部，可以使用任何索引结构来实现LSM树组件。 当今的LSM树实现通常使用并发数据结构（如skip-list或B +树）来组织其内存组件，而它们使用B +树或排序字符串表（SSTables）来组织其磁盘组件。 SSTable包含一个数据块列表和一个索引块； 数据块存储按键排序的键值对，而索引块存储所有数据块的键范围。

在LSM树上的查询必须搜索多个组件，即查找每个key的最新版本。 点查询查询可获取特定键的值，可以简单地一个接一个地搜索所有组件，从最新到最旧，并在找到第一个匹配项后立即停止。 范围查询可以同时搜索所有组件，将搜索结果输入优先级队列以此获取最新数据。

磁盘组件随着时间的推移而逐渐变多，由于必须查询更多组件，因此LSM树的查询性能趋于下降。为了解决这个问题，磁盘组件逐渐合并以减少总数。

在实践中通常使用两种类型的合并策略。如图3所示，两个策略都将磁盘组件组织为层，并由大小比T控制。每个组件在图中均标有其相关的key范围。

在层合并策略（图3a）中，每个级别仅维护一个组件，但是级别L的组件比级别L-1的组件大T倍。因此，级别L的组件将与级别L-1的传入组件多次合并，直到其被填满，然后将其合并为级别L + 1。

例如，在图中，级别0的组件与级别1的组件合并，这将导致级别1的组件更大。相反，分层合并策略（图3b）在每个级别可能维护T个组件。当级别L已满时，这些组件将合并在一起成为级别L + 1的新组件。在图中，级别0的两个组件将合并在一起形成级别1的新组件。值得注意的是如果级别L已经是配置的最大级别时，则结果组件将保持在级别L。实际上，对于稳定的workload（插入量等于删除量），级别总数保持不变。通常，由于LSM树中要搜索的组件较少，因此层合并策略针对查询性能进行了优化。分层合并策略由于降低了合并频率而对写入进行了更多的优化。

2.Bloom Filter

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。

Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

2.1集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。