分享：数据库存储与索引技术（三）LSM 树实现案例

2023-03-28
浙江
本文字数：8768 字
阅读完需：约 29 分钟

欢迎访问 OceanBase 官网获取更多信息：https://www.oceanbase.com/

本文来自 OceanBase 社区分享，仅限交流探讨。原作者马伟，长期从事互联网广告检索系统的研发，对数据库，编译器等领域也有浓厚兴趣。

我们在前文介绍过，多款分布式数据库都使用了 LSM 树作为底层的存储引擎，其中就包括 TiDB 和 Oceanbase。与 TiDB 等数据库的存储引擎将 RocksDB 作为一个黑盒使用不同，虽然 OceanBase 的存储虽然也是基于 LSM 树，但却是完全自己实现，并且和自己的存储引擎做了深度的定制和整合。与 RocksDB 中可能存在 5，6 层的 LSM 不同，OceanBase 的实现中，将 LSM 树划分为三层，第一层 MemTable，第二层 OceanBase 成为增量层，也称转储层(即 LSM 树 C0 层)，第三层 OB 称为基线层(即 LSM 树 C1)层。

与 RocksDB 中实现一样，OceanBase 的增量层(C0)多个 SSTable 之间 Key 会存在区间重叠的关系，读取的时候需要遍历查找每个增量 SSTable 才能确定 Key 是否存在，本文将以 OceanBase 3.x 版本为例，讲解其如何针对这一问题进行优化。OceanBase 的基线层数据是全局有序的，所有 SSTable 之间的 Key 不会存在区间重叠的问题。

1. MemTable

OceanBase 数据库的内存存储引擎 MemTable 由 BTree 和 Hashtable 组成。在插入/更新/删除数据时，首先记录 Redo 日志，并通过 RPC 进行 Paxos 协议复制到其他多数副本，然后再将数据写入内存块，在 HashTable 和 BTree 中存储的均为指向对应数据的指针。副本通过接收 Master 节点发送过来的 Redo 日志进行重做回放将数据到自身的 MemTable。

MemTable 在内存中维护了历史版本的事务，每⼀⾏将历史事务针对该⾏的操作按照时间顺序组织成⾏操作链，新事务提交时会往⾏操作链尾部追加新的⾏操作。如果⾏操作链保存的历史事务过多，将影响读取性能，此时需要触发内存 compaction 操作，融合这些历史事务以⽣成新的⾏操作链。

两种索引结构各自有优缺点，单独无法很好的完成数据库的点查和范围查找的需求，所以 OB 将两者结合起来使用，唯一的代价就是在多线程并发环境下数据写入需要对两种数据结构都进行操作，实现相对复杂。

2. SSTable

当 MemTable 的大小达到某个阈值后，OceanBase 数据库会将 MemTable 中的数据转存于磁盘上，转储后的结构称之为 SSTable。OceanBase 的 SSTable 是不定长的，其内部会被切分为 2MB 一个的定长数据块，OB 称之为宏块(Macro Block)。宏块是 OB 写数据到磁盘的基本 IO 单位。

宏块内部会被划分为多个 16KB 左右的变长数据块，OB 称之为微块(Micro Block)。微块中会存储若干数据行(Row)，微块是 OB 数据文件读取的基本单位。微块在构造时会写入连续的数据行，到 16KB 左右，然后再通过通用压缩算法(LZ4, ZSTD 等)，然后再加入到宏块当中。

宏块是定长的，大小为固定的 2MB，长度不可以被调整；微块默认大小为 16KB，经通用压缩后是变长的。OB 在进行 IO 读取时，会按照 4KB 来做 IO 对齐，因此一次 IO 读的长度并不一定与微块长度完全一致。微块长度可以被修改，通过以下的语句可以对于不同的表设置不同的微块长度：

ALTER TABLE mytest SET block_size = 131072;

复制代码

一般来说微块长度越大，数据的压缩比会越高，但相应的一次 IO 读的代价也会越大；微块长度越小，数据的压缩比会越低，但相应的一次 IO 读的代价会更小。

3. 数据压缩

3.1. 传统关系数据库数据压缩实现

传统关系型数据库理论和架构在 20 世纪 70，80 年代被确定下来，直到 2010 年的移动互联网时代之前，其架构都没有大的改变。早期数据库系统，CPU 算力较弱，而数据压缩是非常耗费 CPU 的操作，因此传统基于页面行存的关系数据库中一开始都没有为数据压缩进行顶层设计。到互联网时代面对海量数据，传统的关系型数据库也开始考虑增加压缩特性，降低用户的存储成本。

传统的关系型数据库的压缩，主要有两个方向，一个是针对 OLTP，即事务处理的 workload 提供的方案。另外一种是针对 OLAP，即数据分析型的 workload 提供的方案。

针对 OLTP 的 workload 提供的方案主要是基于页面的通用压缩。OLTP 型的 workload，通常需要对行内的数据进行更改，一般来说，采用行存储性能较好。这种负载下，一个页面内的行可能会被上层应用反复修改，因此行与行之间的数据压缩基本难以进行，主流厂商一般都是才用了基于页面的整体通用压缩。以 MySQL 的 InnoDB 引擎为例，一个页面未压缩前，在磁盘上占用 16KB 的空间，压缩后只有 11KB，那么按照 4KB 进行 IO 对齐的话，压缩后的数据占用 12KB 的磁盘空间。InnoDB 的这个页面在文件中仍然占用 16KB 的空间，但是利用操作系统的稀疏文件(Sparse File)特性，操作系统实际只为这个页面申请了 12KB 的磁盘空间，因此可以节约 4KB 的空间。

这种压缩方式也会带来很多问题：

如果一个页面被修改很频繁的话，反复的读出和写入数据的过程中需要进行压缩/解压，对 CPU 的开销也不可忽略。
如果页面被修改并压缩后，其大小比原来增加了，如原来压缩后是 12KB，现在压缩后是 13KB。操作系统需要为新增加的数据分配磁盘空间，此时分配的磁盘空间通常都不是和之前的 12KB 的空间连续的。这样对这个页面的读取，IO 是不连续的，性能会变差。

总结起来就是，传统数据库的基于行存页面的压缩，通常情况下，只能帮助用户节约一部分存储空间，并不会带来性能的提升。如果运用不当，性能有可能还会下降。

OLAP 型负载的数据压缩，通常数据都是只读的，没有了数据更新的限制，数据压缩做的非常激进。在页面内的数据可以不按行存，而是按照列存。相同列的数据放在一起，可以做非常多的压缩，如常量编码，字典编码，Delta 编码，RLE 编码等等。这些数据编码可以有效减少页面的存储空间，同时不会对数据查询有任何的影响。由于 OB 也采用了类似的压缩方案，因此这里的列存压缩方案，会放到 OB 的压缩实现中去讲。

传统的基于页面存储的关系数据库还有一个问题就是，OLAP 和 OLTP 两种负载的不可调和性。要想 OLAP 处理能力强，数据一般都是行存的；要想 OLTP 处理能力强，数据需要是列存的。如果要想两者都要(小孩才做选择，成年人全都要)，那么必须要部署两套异构的存储(尽管数据库服务程序可能是一个/一套)，一套专门用于 OLTP，一套用于 OLAP，二者之间还需要通过数据链路进行同步。这无疑显著增加了硬件和运维管理的成本。

3.2. LSM 树数据压缩优势综述

基于 LSM 的存储引擎，其在磁盘上的数据，在下一次合并之前，都是只读而不会被修改的。通过 BigTable 和 LevelDB 引入的 SSTable，SSTable 内部再分 Block 存储的概念目前已经是 LSM 树实现的标配。这些只读的 Block，类比传统数据库的页的话，是非常好的压缩目标。相比 OLTP 数据库的页面，SSTable 的 Block 压缩有以下几个优势：

数据只读，不会因为反复修改而带来反复的压缩/解压的 CPU 消耗，也不会因为反复修改带来的数据膨胀导致的 IO 不连续。
数据内聚，一个 Block 内通常有几十乃至更多的行，可以在 Block 写入的时候一次性的针对这些行做列式压缩，可以得到更好的压缩比，而且可以加速后续的查询。

业内基于 LSM 的存储其实也看到了这些压缩优势并有了相当的实现，如 Facebook 提出的 RCFile。但是这类应用通常也都是 Hadoop 等批处理场景，实际在 OLTP 数据库场景运用这种压缩方案的，据了解就 Spanner 和 OceanBase。

3.3. OB 数据压缩实现

我们前面提到，OB 的 SSTable 的格式，是分为 SSTable，Macro Block, Micro Block 三级。OB 的开源 3.x 版本只实现了 Micro Block 内的行存储，内部版本中实现了 Micro Block 内的列存储。OB 在 Micro Block 内基于列存储进行高效的编码压缩，然后在整体以 Micro Block 为单位进行通用算法压缩。按照 OB 早期的文章的宣称，客户在进行 MySQL 数据迁移的时候，经验公式是按照 6:1 进行容量规划的，即 OB 按照列式编码压缩+通用压缩之后的数据，只有同等 MySQL 的 1/6(该结论未做深入考证，不确定是否包含 OB 三副本，以及 MySQL 数据是否启用压缩，仅供参考)。

3.3.1. 通用压缩

我们现在能见到的，压缩解压代价相对可控的通用压缩算法，基本都是基于 Abraham Lempel 与 Jacob Ziv 在 1977/1978 论文中发表的 LZ77/LZ78 算法变种得来，如 LZW，LZ4，Snappy，ZSTD 等。LZ 系的通用压缩算法本质是一种在字节流上的基于滑动窗口的字典压缩算法。算法会动态的在最近一段数据流中寻找重复出现的字节片段，然后进行压缩。

OB 在 Micro Block 粒度是支持选择通用压缩算法来对整个 Micro Block 进行通用压缩的，用户可以通过表的属性来进行设置。通用压缩虽然也能带来一定的数据压缩比，但是这是有性能损失的。OB 的 Micro Block 在压缩前是 16KB，是一次读 IO 读取的数据的大小。当 OB 的 Micro Block 被通用压缩之后，OB 一次 IO 的大小仍然是 16KB。压缩后的数据还需要解压之后才能使用。即是是当前最快的通用压缩算法 LZ4，其解压速度也只有约 5GB/S，只有内存数据拷贝(memcpy)的 35%左右。

况且，通用的数据压缩算法并不是为数据库专门设计的，这些压缩算法将输入看成是一个连续的字节流，并不对数据的 pattern 做任何先验假设。但实际上数据库中存放的是结构化数据，是有明确的 schema 的，每行数据每个字段都有明确的类型和大小。利用这些信息，采用一定的数据编码技术，就可以实现比直接使用通用压缩算法好得多的压缩效果。这些数据编码技术，不但能提高数据的压缩比，还能基本不降低数据的查询效率。某些查询情况下，甚至还能加速查询。

3.3.2. 编码压缩

OB 中的 Micro Block 正是在列存的基础上，结合了数据 schema，进行了一系列的高效的数据编码压缩。其主要的数据编码压缩算法有以下几类。

字典编码：所有数据编码技术中最常用、也是最有效的方法。字典编码的思想很简单，就是把重复性较高的数据进行去重，把去重后的数据建立字典，而把原来存放数据的地方存成指向特定字典下标的引用。数据的访问逻辑是非常直接的，没有解码过程。特别要注意，字典中的各数据是按类型序排序的，这样做有两个好处：一是有序的数据更有利于压缩；二是有序的数据意味着我们在做谓词计算时，可以将谓词逻辑直接下压到字典，并通过二分逻辑完成快速迭代，这点在我们支持复杂计算时，将发挥非常重要的作用。
RLE 编码：适用于连续相等的数据，比如形如 1，1，1，2，2，...之类的，我们可以把这些连续相等的数据去重，并只保留其起始行号，RLE 编码在数据库中主要用于处理有序的数据（比如索引的前缀）。
常量编码：针对近似常量化的数据，编码识别一个最常见的数据作为常量，而只记录所有不等于这个常量的异常值和它们的行号，常量编码在实际业务数据中非常有用，后者往往存在着一些业务增加、但是并不使用的字段，这些字段同样占据了空间，并呈现出常量化（默认值）的数据分布。
差值编码(数值字段)：适用于在一个小值域范围内分布的整数型数据，通过计算区间内的 MIN、MAX，将数据减去 MIN 后，用更小的位宽进行编码。比较常见的数据是时间类型，连续生成的时间类型数据通常有非常好的局部性（比如差值在几秒钟以内）。
差值编码(字符字段)：适用于定长的、有确定业务规则的字符型数据，通过构造公共串，将数据中只记录差异部分。这类数据在业务中非常常见，通常用于主键，比如订单号、用户账号等。
前缀编码：适用于前缀相同的字符型数据，通过构造公共前缀，将数据中只记录差异的后缀。其它一些数据库，比如 SQL Server、HBase 中也经常使用，这类数据在业务中也很常见，比如部分主键。前面提到的数据编码都是列内编码，即只考虑同一列内各字段的数据相似性，除此之外，OceanBase 还实现了一组列间的数据编码，也就是考虑同一行的不同列间数据的相似性。
列间编码(数值字段)：适用于两列近似相等的整数型数据，这样，其中的一列只需要存储和另一列的差异值。这种列间相等的数据编码有它很强的适用场景，比如我们知道业务在数据表中通常都会记录生成和最近一次更新的时间戳，如果某些流水数据从不会发生更新，那么这两个字段就存在很强的列间相等关系。
列间编码(字符字段)：适用于两列存在子串关系的字符型数据，也就是一列是另一列的子串（包括前缀、后缀、相等关系）。实际业务中许多长字符型字段并不是由用户随意生成的，而是基于一定的业务规则，将多个基础字段拼接而成，这时候这些基础字段就和前者存在子串关系。

OB 所采用的这些编码压缩算法，解码过程非常简单，解码特定一行的数据，并不需要依赖其它行，这种近似 O(1)复杂度的设计提高了数据投影的性能，使得其能够被用于在线系统。

虽然这些编码压缩算法解码简单，但是编码过程却并不那么 trivial。尽管 OB 知道每张表每一列数据的属性，但是数据的分布 OB 却并没那么的了解，如某一列虽然是 64 位整数，但是 OB 事前并不一定知道它所有值都是一个有限的枚举类型，只有等到需要 Compact 压缩一个 Micro Block 的时候才能知道。为了减轻 DBA 的心智负担，OB 并不希望把每一列的编码压缩算法都由 DBA 来指定，而希望是 OB 自己根据当前数据的分布来智能选择。这就涉及到一个比较大的问题，如何智能的为每一列来选择最优的编码压缩算法。

OB 的做法是如果上一个 Micro Block 某一列通过计算选择了某种编码算法，那么如果数据分布稳定的话，下一个 Micro Block 的相同列大概率最优的编码算法跟上一个 Block 一样。OB 会优先尝试通过这个编码算法对列进行压缩，如果压缩后的结果(压缩比)证明这个选择正确，那么就会采用这个编码算法来压缩当前列；否则会退回重新选择合适的编码算法。

OB 的公开资料表示，这块还有较大的优化空间。而且业内目前也有一些新颖的想法，如通过机器学习来预测数据的最优编码压缩算法。相信后续 OB 的新版本中会有持续改进和提升。

3.4. TiDB 数据压缩实现

TiDB 的存储层 TiKV 是基础 RocksDB 的，前文我们也提到，RocksDB 是在 LevelDB 的基础上改进来的，而原始的 LevelDB 只实现了基于 Block 的整体通用压缩，并未在 Block 内采用列存及数据编码压缩。因此采用 RocksDB 作为底层存储的 TiDB，也未使用 Block 内的列存及数据编码压缩。

TiDB 为了应对 OLAP 类需求，专门另外涉及并实现了一套存储格式，采用了列存的方式，此处不展开讨论，有兴趣的同学可以参考文档(PS: TiDB 不愧是开源标杆，文档非常完善，随便翻翻也能学习到不少东西)。部署时，需要部署专门的从库来接收主库的数据同步，然后改为列存存储以应对 OLAP 查询需求。

4. 缓存策略

由于很多数据存储于 SSTable，为了加速查询，OB 需要对数据进行缓存。OceanBase 数据库并不需要对缓存的大小进行设置，类似于 Linux 对于 page cache 的控制策略，OceanBase 数据库会尽量使用租户的内存，直到租户的内存达到一定阈值后，才会触发对 Cache 的淘汰。同时 OceanBase 数据库也是一个多租户系统，对于每一个租户都会有各自的 Cache，但 OceanBase 数据库会对所有租户的缓存进行统一管理。

4.1. Row Cache

传统关系型数据库并不对单独的某行进行缓存，OB 基于 LSM 的存储引擎却实现了行级缓存。OB 的 Row Cache 缓存具体的数据行，在进行 Get/MultiGet 查询时，可能会将对应查到的数据行放入 Row Cache，这样在进行热点行的查询时，就可以极大地提升查询性能。

4.2. Block Cache

传统的关系数据库中，缓存是以 IO 页面为单位进行缓存的。在 LSM 为存储引擎的数据库中，IO 页面为单位的缓存策略也需要随着 LSM 结构来进行适配。我们之前提到过，OB 的 IO 读的最小单位是微块，OB 的 Block Cache 是以微块(Micro Block)为单位的，其缓存的数据是解压缩后的微块数据，大小是变长的。

另外，数据查询的时候，如果没有在 Row Cache 或者 MemTable 中查询到数据话，我们需要去 Block Cache 或者磁盘中查询数据。查询数据的第一步是需要先确定数据在哪个微块，这也需要我们将一部分微块的索引缓存在内存中。

OB 的 Block Index Cache 即缓存微块的索引，类似于 BTree 的中间层，在数据结构上和 Block Cache 有一些区别，由于中间层通常不大，Block Index Cache 的命中率通常都比较高。

4.3. Filter Cache

LSM 树是基于排序的的存储结构，这类结构通常在进行点查询的时候，对不存在的数据的查询和确认是不高效的。不存在的数据，通常我们在内存中也无法缓存，内存查询也就无法命中，只有通过 IO 去读取数据所在范围的 SSTable(微块)来确认数据是否存在。这样对于数据的存在性查询将变得非常低效。因此各种 LSM 树的实现中都引入了 Blook Filter 来进行存在性过滤，OB 也在宏块(Macro Block)层引入了 Bloom Filter 用于数据存在性过滤。

Bloom Filter 是一种只能插入元素，无法删除元素的数据结构。在传统的关系数据库中，IO 页面(Page)随时可能会被应用修改，一行数据随时都可能被删除，因此无法高效的使用 Bloom Filter 来作为空数据过滤器。而基于 LSM 树存储引擎则不同，其磁盘上的数据，在下一次合并(Compaction)之前，都是不可变的。Compaction 间隔时间通常都是以小时为单位，这种场景非常适合 Bloom Filter 的使用。Bloom Filter 也是一种可以非常容易通过空间来调整查询错误率的数据结构，应用可以轻易的通过调整每个元素所占用的空间(Row per bits)，来调整查询的错误率(即数据不在 SSTable 中，但是通过 Bloom Filter 查询被确认存在的概率)。

OB 中的 Bloom Filter 的构建策略是按需构建，当一个宏块上的空查次数超过某个阈值时，就会自动构建 Bloom Filter，并将 Bloom Filter 放入 Cache。

5. 合并策略

前面我们已经讲过合并是 LSM 树类存储系统中最复杂，也是对系统性能/稳定性影响最大的一个过程。因此，OB 实现的 LSM 树在数据合并上也是进行了非常细致的涉及，提供了多种合并策略，力求合并过程平滑可控。OceanBase 的合并策略，根据表上是否有 DDL 操作，如加列，减列，修改压缩算法等，会才去不同的策略。当表上无 DDL 操作时，OceanBase 主要采取增量合并策略；反之则会采用渐进合并或者全量合并策略。

5.1. 增量合并

增量合并的情况下，我们知道表的 Schema 没有修改，因此可以在合并的时候，在不同粒度上看数据是否可以重用。OB 的 Macro Block 划分为 2M 一个，这个是一个相对较小的尺寸。当表相对较大的时候，如一张 100G 的表，系统里会有 102400 个 Macro Block。数据更新的时候，这些 Macro Block 中很多有可能都没有被修改过，因此可以直接重用，这种方式称之为增量合并。

相对于全量合并的把所有的宏块的重写一边而言，增量合并只重写发生了修改的宏块。增量合并极大地减少了合并的工作量，也是 OceanBase 数据库目前默认的合并算法。

更进一步地，对于宏块内部的微块，很多情况下也并不是所有的微块都会被修改。当发现宏块有行被修改过时，在处理每一个微块时，会先判断这个微块是否有行被修改过，如果没有，只需要把这个微块的数据直接拷贝到新的宏块上，这样没被修改过的微块就省去了解析行、选择编码规则、对行进行编码以及计算列 Checksum 等操作。微块级增量合并进一步减少了合并的时间。

5.2. 渐进合并

在执行某些 DDL 操作时，例如执行表的加列、减列、修改压缩算法等操作后，数据需要完全重写一遍才能在磁盘上生效。OceanBase 数据库并不会立即对数据执行重写操作，而是将重写动作延迟到合并时进行。基于增量合并的方式，无法完成对未修改数据的重写，为此 OceanBase 数据库引入了“渐进合并”，即把数据的重写分散到多次合并中去做，在一次合并中只进行部分数据的重写。

用户可以通过参数指定渐进合并的轮次，如：

ALTER TABLE mytest SET progressive_merge_num=60;

复制代码

表示将 mytest 表的渐进轮次设置为 60，在 DDL 操作完成之后的 60 次渐进合并过程中，每一次合并会重写 60 分之一的数据，在 60 轮合并过后，数据就被整体重写了一遍。

当未对表的 progressive_merge_num 进行设置时，其默认值为 0，目前语义为在执行需要重写数据的 DDL 操作之后，做渐进轮次为 100 的渐进合并。当表的 progressive_merge_num 被设置为 1 时，表示强制走全量合并。

5.3. 全量合并

OB 的全量合并和 HBase 与 Rocksdb 的 Major Compaction 过程是类似的。顾名思义，在全量合并过程中，会把当前的基线数据都读取出来，和增量数据合并后，再写到磁盘上去作为新的基线数据。在这个过程中，会把所有数据都重写一遍。全量合并会极大的耗费磁盘 IO 和空间，如非必要或者 DBA 强制指定，OceanBase 数据库一般不会主动做全量合并。

OceanBase 数据库发起的全量合并一般发生在列类型修改等 DDL 操作之后。DDL 变更是实时生效的，不阻塞读写，也不会影响到多副本间的 Paxos 同步，将对存储数据的变更延后到合并的时候来做，这时就需要将所有数据重写一遍。