开发者学堂课程【从0到1数据库内核实战教程：Ocean Base 存储引擎结构（上）】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/16095
Ocean Base 存储引擎结构（上）
主要内容：
一、LSM-Tree
二、Compassion
三、Compaction in Ocean Base
四、总结
实际上比较典型的数据库管理系统会包含多个组件，每个组件负责不同的功能。而存储引擎主要是负责数据的存储和查询，提供组件插入、更新、删除、数据、数据加锁、随机读取以及范围查询等操作。许多分布式的数据库能够提供的写入速度是远远超过传统数据库的。故此本节课程将从底层的LSM-Tree 存储引擎作为切入点介绍的策略，进行剖析如此优异的写入速度实现的方法，最后介绍Ocean Base 基于的类型，以及针对一些特别的使用场景因素提出的优化算法。
一、LSM-Tree
LSM-Tree 全称为Log Structured Merge Tree，结构化合并树，最早在1996年Patrick O'Neil, Edward Cheng等人在论文《The Log-Structured Merge-Tree》中提出，随后在新的数据库引擎中得到广泛应用，例如HBASE 、cassandra 、RocksDB等都选择了LSM-Tree ，oceanBase采用的也是LSM-Tree架构，基于LSM-Tree进行搭建存储引擎。
1、B+树与 LSM-Tree
目前页面实现存储引擎的两大顶流的数据结构是 B+树与 LSM-Tree，
两者之间是有差别的，传统数据库更加青睐B+树，而新数据库则更偏爱LSM-Tree，其实是平衡搜索无数的一种。B+树是平衡搜索树的一种，是为了磁盘搜索而诞生的，一个叶子结点设定为一个磁盘块
。B+树的所有的数据都存在叶子结点里面，每次查询或者写入时，都需要从根节点开始搜索到叶子结点，再从叶子结点对应的位置进行操作，即原地更新。传统数据库会将B+树的每个叶子节点设置为一个磁盘页的大小，每次磁盘IO可以加载一个完整的叶子节点到内存中，以此减少IO次数。B+树查询/插入/删除的时间复杂度都是O(logN)。
2、LSM-Tree 架构
LSM-Tree 的核心思想为将离散的随机写请求都转换成批量的顺序写请求。当有数据写入时，会先存储到Memttable 以及用户的数据日志，此write-log-frozen 机制需要回放数据日志就可以恢复到重启之前的状态。当Memttable 占用内存数据量达到一定预定值之后，Memttable 则会转化成Frozen Memttable ，变成只读状态，冻结的同时会创建一个新的Memttable 进行数据的写入。后台会将Memttable 写在磁盘上，变成一个SSTable 。此过程全部结束之后，Frozen Memttable 与数据日志可以被回收，实际上Memttable 是一个纯内存结构，一般会使用红黑树或者跳表这种有顺序的数据结构，为了便于后续数据的读取并写入磁盘变成SSTable。磁盘上的SSTable全称为sorted string table，是从Google的big table所借用的一个概念。被译为内部有序的磁盘文件，数据是按照rookie递增来排序的,可以使用二分搜索的方式来快速的定位到的数据。磁盘上的SSTable通常会被划分为多个层级，层级的数字越低表示数据写入的时间越临近，例如L0层的数据就是最近写入的，数据的数字越大就表示此数据越老旧。LSM-Tree 是一个Append-Only 的类型，update 与delete的操作都作为一个额外的行来写入。故此rowkey 若发生多次更新，在LSM-Tree 中会存储rowkey 的多个行。
LSM-Tree 的查询是先从内存中的Memttable 开始查起，若内存中的Memttable 没有找到rowkey ，再从Memttable L0层、L1层直至LN层，直到查询结束。对于B+树与LSM-Tree已有一定了解，接下来对比两者之间的差别。首先B+树有原地更新与一个电厂块的假设，此使得B+树的数据块是不太适合做压缩的，若对数据块做了压缩会使得原地更新会需要有额外的解压与压缩操作，则会导致更新性能变差。LSM-Tree 是一个Append-Only 类型，将更新写作额外的行，并且SSTable当中的数据没有经常的假设，故压缩就会变得比较自然。
二、Compassion
Compassion实质是对数据的重新整合，将多个SSTable的数据作为输入，然后进行规律的排序，并输出为一个SSTable， Compassion减少了SSTable的数量，提升了我们查询的性能。但Compassion其实是一个资源消耗特别高的操作，其涉及到磁盘上SSTable的读取与写入，此表明会占用大量IO的代换，并且在读取与写入中会涉及到数据的压缩、解压、checksum 计算以及rowkey 的比较，故此是一个CPU 密集型的操作。并且Compassion 完善之后可能会产生性能的抖动，例如内存中的Memttable 转化成完善的SSTable，则之前对内存Memttable 的查询会变成对磁盘SSTable的查询，故此会使查询耗时延长。为了权衡Compassion 查询提速时以及Compassion 带来的资源消耗，此为业界持续关注的问题。
1、Compaction - Amplification
不同的Compaction策略是对写放大、空间放大、读放大的一个权衡
- 写放大(Write Amplification)=磁盘写入的数据量/实际的数据量，用户写入一行数据，在LSM-Tree中会触发若干名Compaction，则会导致其他一些数据被读出写入，即原本写入一行数据的IO，就被放大成N倍数据量的IO。
- 空间放大(Space Amplification)=存储的数据量/实际的数据量，由于写入的数据都是Append系列，不是原地更新，故之前的数据不会立刻被清理，相同rowkey的行在多个SSTable中都是存在的，故实际存储的数据量比实际存在的数据量会大得多。
- 读放大(Read Amplification)=本次扫描的数据量/实际返回的数据量，查询需要访问多个SSTable，则会导致扫描的行数比实际返回至用户的行数会多得多，此为读放大。
接下来讲解LSM-Tree业界通用的Compaction 策略
2、Classic Leveled Compaction
LSM-Tree划分为N个Level，每个Level仅包含一个SSTable，相邻的SSTable的大小有倍数关系，通常称之为find out，即为上出。
Classic Leveled Compaction触发的条件为某个Level的存储数据量达到阈值之后则会触发一次Compaction，L(n)+ L(n+1) = new L(n+1)，例如下图，当L1层达到设定的阈值则触发一次Leveled Compaction，将L1层的数据与L2层中rowkey range有交集的部分进行 Compaction ，以此得到一个新的L2层的数据。
实际上在最差的情况下，此 Leveled 型策略可以达到find out ,即为set 的倍数，并且 Leveled 策略比较容易存在雪崩效应。例如假设在LSM-Tree中，SSTable 数据量都比较接近每一层的阈值时，在L0层写入少量数据，触发了L0层至L1层的Compaction ，使得L1层的数据量超过阈值，此急跌反应可能会导致每个Leveled 都触发Compaction ，此情况是十分严重的。
3、Size-Tiered Compaction
在此模式里LSM-Tree划分为N个Level，每个Level 包含多个SSTable， several L(n+1) = new L(n+1)。先统计的SSTable 可能会存在一定的交集，故在查询时需要访问此Level 所有的SSTable，这使得查询性能一般。Compaction触发条件是某个Level的存储数据量超过设定阈值，然后将LN层的SSTable 进行Compaction后形成一个新的SSTable 放至N+1层，但并不与N+1层原有的数据进行Compaction。相比于Level 的写放大会更优，但由于查询的SSTable 数据量较多，故读放大较差。实际上Level 模式与Tiered 模式的优点与缺点都是比较鲜明的，但对现实的场景都不适用，故取长补短的混合模型更加适用于存储引擎：Tiered & Leveled Compaction
4、Tiered & Leveled Compaction
对于层级较小的Level，使用Size-Tiered模式减少写放大问题，因为层级较小的Level 的数据量较小，写入的数据更新（更新的局部性原理）可能性较大，故选择Tiered模式。对于层级较大的Level，写入的数据量比较大、耗时长，不太可能被更新，故使用Leveled模式减少空间放大问题。RocksDB、OceanBase都是选择Tiered & Leveled 的混合模式。
5、FIFO Compaction
此模式LSM-Tree只有一个Level，故所有的SSTable都放在L0层的一个Level中，所有的SSTable以时间序排列，每次Compaction
淘汰生成时间最早的SSTable，此为最简单的Compaction策略，但容易丢失数据，故适合时序数据库这类有时间属性和时间效用的数据。
6、Tiered、Leveled 、Tiered & Leveled 总结对比
以上介绍了Tiered、Leveled 、Tiered & Leveled 、FIFO 四种Compaction 类型，抛开FIFO 不谈，因为它可能会丢失数据，故此对前三种的Compaction 类型进行总结对比。对比每种Compaction 策略的设定、优势与劣势。
Leveled的Compaction 为每个Level包含一个SSTable；Tiered类型每个Level包含多个SSTable，相同Level的SSTable的owkey range可能存在交集；Tiered & Leveled 对层级较小的使用Tiered模式,例如L0层可以有多个SSTable，对于层级较高的使用Leveled ，因为数据量较大，每一层只有一个SSTable。对于Leveled来说，是以写放大作为牺牲，而换取读放大与空间放大的优异表现，代表数据库有RocksDB的Major Compaction；Tiered为写放大比较优异，但由于SSTable 数据量与数量比较多，故读放大与空间放大则较差一些，代表数据库有Cassandra比较早期的SizeTiered Compaction Strategy以及RocksDB的Universal Compaction 。对于Tiered & Leveled 的混合模式取长补短，写放大比Leveled更佳，且读放大与空间放大比Tiered更优，代表数据库为RocksDB默认的Leveled Compaction 以及oceanBase 也是选择Tiered & Leveled 的混合模式。实际上Compaction 策略本身并没有好差之分，LSM-Tree可以根据不同的应用场景、服务的业务场景进行选择最合适的Compaction 策略。可以看出，对于读放大、写放大与空间放大三者的权衡，空间放大是呈现一种伴随状态出现的，即空间放大是由于SSTable 的数量较多，同一个rowkey存储较多的行会导致查询时需要扫描更多的行，因此对应的读放大也会增高。而读放大与写放大是呈现一种对立态势，两者互相拉扯，不能同时达到最优，就像鱼与熊掌不得兼得。 Leveled 与Tiered 都是追求局部的自由，而Tiered & Leveled 混合模式则追求读放大与写放大的平衡。
7、墓碑问题
墓碑问题是LSM-Tree的经典问题，随着Compaction的执行，相同Rowkey 所有行会进行从新往旧地compact，以此减少空间放大，以下图为例：
Key A引出value 值分别为1与1，后续将之UPDATE，将第二个value 值更新为3，此两个行处于不同的SSTable 中，Compaction 之后则会将两行compact 成一行，得到一个最新的value 值为3的最新结果。对于delete 操作来说有一点特别，理论上insert 行与update 行加上一个delete 行，结果为delete 行。实际上所有的rowkey应该被删除，但是由于rowkey 在所有SSTable 都有可能存在，故delete 行就需要将所有的相同的rowkey 行删掉，此delete 行才能被删掉，此delete 行则被称之为墓碑，必须与最底层即LN层进行compact ，delete 行才能被完整删除，以上则为墓碑问题。
三、Compaction in Ocean Base
此为Ocean Base 对Compaction 设计，首先介绍LSM-Tree 在Ocean Base 中的设定，与传统的LSM-Tree 相类似，分为内存中的Memtable 与磁盘上的SSTable，Ocean Base 将磁盘上的SSTable 划分为三层，分别为L0层、 L1层、L2层。在L0层使用Tiered 模式，可以允许L0层可以有多个Mini SSTable ，L1层只能有一个Minor SSTable，L2只能有一个Major SSTable。Ocean Base 中的Compaction 分为三种类型，分别为Mini、Minor 与Major。
1、Compaction in OceanBase -Mini Compaction
内存中的Frozen Memtable通过 Mini Compaction变成磁盘上的 Mini SSTable，是Tiered类型的Compaction，是数据日志的一个 checkpoint。Mini Compaction结束后，其对应的Frozen Memtable和数据log 可以被释放。
2、compaction in OceanBase - Minor compaction
针对LO和L1层的SSTable，Minor compaction 就是将多个Mini sSTable合成一个，主要目的是减少SSTable的数量、减少读放大问题。当Mini SSTable 的数量超过阈值时自动触发Minor Compaction。
Minor 实际上被细分为两类，第一类为L0层>L0层，即多个Mini SSTable 合成一个SSTable ，是一种Tiered 模式。第二大类为L0层->L1层，是一种Leveled 类型的compaction 模式，即将多个Mini 与一个Minor进行compaction 之后生成一个SSTable ，对于两者不同模式的选择取决于Mini 的数据量，当Mini 的数据量较少时使用Tiered 模式 ，当Mini 的数据量较多且Minor 数据量与Mini 数据量相近时则选择Leveled 模式，将所有数据都合成至Minor SSTable 中。
3、Compaction in OceanBase - Major compaction
Major Compaction是整个集群选择统一的Major位点，每个分区都使用该Major位点做快照查询，并将查询结果进行持久化生成 Major SSTable。合并触发有三种触发方式:自动触发、定时触发与手动触发。自动触发:Mini Compaction执行次数达阈值，缩减SSTable的数量，降低读放大，故调用一次合并。定时触发:因为合并是一个资源消耗型的操作，故尽量避开在业务高峰期进行合并，通过设置触发时间，在业务低峰期定时触发合并。手动触发:使用命令触发合并。讲解完三种Compaction 触发类型，接下来讲解OceanBase 对于一些特定的业务场景，在领域中做了某些优化算法。
4、Compaction 算法
（1）、Compaction in OceanBase -全量合并
全量合并和HBase与 Rocksdb 的 Major compaction过程是类似，在全量合并过程中，会把当前的Major SSTable数据都读取出来，和所有的 Mini / Minor SSTable合并后，再写到磁盘上去作为新的Major SSTable。此过程是十分消耗 SSTable 磁盘空间的，若非必要则不会使用全量合并。而且在 Ocean Base 中，一个SSTable 实际上是一个宏块的集合，每个宏块则是若干微块的集合，则可以想到，在一个SSTable中若部分宏块旁边的微块没有被修改的情况下，则并不需要完整的数据成型，故提出优化算法，称之为增量合并。
（2）、Compaction in OceanBase -增量合并
增量合并是相对于全量合并而言，大多数情况下，增量合并只重写发生了修改的宏块/微块，未修改的直接放入新 Major SSTable 中。更进一步，若宏块和微块并没有进行修改，也可以直接放入新的 SSTable 中，故此宏块和微块的重用省去了行解析、编码以及计算列checksum等操作，同时改善写放大问题。
（3）、Compaction in OceanBase -渐进合并
在执行某些DDL操作时，例如执行表的加列、减列、修改压缩算法等操作后，可能需要将数据重写一遍。但0ceanBase数据库并不会立即对数据执行重写操作，而是将重写动作延迟到合并时进行。数据重写将增量合并回退到全量合并，使得Compaction耗时变长，故提出了渐近合并思想。渐进合并的核心是把数据的重写分散到多次合并中执行，在一次合并中只进行部分数据的重写。以下代码为例：
alter table t1 set progressive_merge_num = 60;将t1表渐近合并的轮次设置为60，即一次合并只能重写SSTable 中1/60的数据，当60轮合并执行完毕之后，所有的数据都被重写，以上内容为渐近合并。
（4）、Compaction in Ocean Base -轮转合并
轮转合并的诞生是为了规避合并对业务的影响多副本轮流执行合并操作，一般来说，合并是在业务的巅峰期进行，但并不是所有的业务都有巅峰期，故在合并过程中为了减少资源消耗、对业务的IO 或者查询带来影响，以此引入了轮转合并，轮转合并介入了Ocean Base多副本的分布式架构。一般情况下，OB会以三个数据副本进行部署，以下示意图为例：
当L3副本进行Compaction 时，会将用户的查询尽量放至L1进行执行，当zone 3副本合并结束之后，再将用户的查询导入至zone 3，再由zone 1进行Compaction 。即三个副本轮流进行Compaction ，轮流执行入库的查询操作，故此业务的高峰以及Compaction 的资源消耗就不会放置在同一个副本上。
（5）、compaction in OceanBase -并行合并
当合并参与的SSTable数据量特别大时，整个合并的过程会非常耗时。算法将整个需要完成的 Rowkey值域按照当前tablet_size划分为若干个子任务，子任务之间可以并发执行，当所有子任务执行结束之后本次合并才算结束。并行合并默认开启，对于数据量大的 Compaction后台自动划分并行任务。
四、总结
首先介绍了 LSM-Tree 与B+树的对比，然后介绍了LSM-Tree 中的Memttable 、SSTable 、DML模式；第二大块介绍了业界通用的Compaction 策略，分别为Tiered、Leveled 、Tiered & Leveled混合模式 、FIFO，同时介绍了LSM-Tree 的墓碑问题。最后一部分介绍了 Ocean Base 对Compaction的设计，讲解了Mini/Minor/Major Compaction以及对于一些特定场景的优化算法：全量Compaction、增量 Compaction、渐近 Compaction、轮转 Compaction以及并行Compaction。
