众所周知，数据库存储结构设计的好坏将直接影响数据库的性能，如浪费存储空间、降低读取效率等。而学习存储结构最好的办法，当然是带着充足的理论知识，亲身去参与一个数据库存储引擎的开发。
第一期「从0到1数据库内核实战教程」已经手把手教大家如何搭建和编译 MiniOB 和 OceanBase 研发环境，带领大家入门了数据库内核研发💪 。课后预习👉查看课程回放
8月18日 19:30 实战教程第二期将会带你学习数据库存储的基础知识以及 MiniOB 和 OceanBase 的存储引擎，开始实战数据库内核开发。不仅有丰富的理论知识解读，更搭配了 MiniOB 实战编码练习，让大家结合理论开始实战编码，真正的实现一个具备基础功能的数据库。
学完本期内容不仅可以了解 MiniOB 和 OceanBase 数据库存储结构的设计思路，更能在实战中理解数据库底层存储的工作原理。
本期能帮你解决什么问题？
1、学习了很多理论知识，苦于没有一个简单上手的项目让你亲身参与一个数据库存储引擎的编写。
2、在开发过程中经常有疑问“为什么这样设计数据库存储结构才能提升系统性能”？
3、在安装、配置数据库时，因不熟悉存储结构设计而不能合理规划数据的存放位置，来提升数据库性能？
直播内容抢“鲜”知
OceanBase 存储引擎
典型的数据库管理系统会包含多个组件，每个组件负责不同的功能，而存储引擎主要负责数据的存储与查询，向 SQL引擎组建提供主键插入、更新、删除、数据加锁、随机读取以及范围查询等操作，在进行查询操作时，SQL 引擎也可能将部分的过滤条件、表达式计算及 limit 操作下压到存储层，数据库功能层构建在存储引擎层之上。
许多分布式 KV 的数据库宣称所能提供的写入速度远远超过传统数据库，我们将从他们底层的 LSM-Tree 存储引擎作为切入点，介绍 LSM-Tree 和业界通用的 Compaction 策略，剖析如此优异的写入速度是如何实现的。最后介绍 OceanBase 基于 LSM-Tree 的 Compaction 类型，以及针对特别的使用场景所创造出来的 Compaction 算法。
LSM-Tree
LSM-Tree，全称 Log Structured Merge Tree，结构化合并树，最早在1996年 Patrick O'Neil, Edward Cheng 等人在论文《The Log-Structured Merge-Tree》中提出，随后便在新数据库引擎中得到广泛应用，例如 HBase，Cassandra， RocksDB。OceanBase 也选择 LSM-Tree 架构搭建存储引擎。
目前业界中实现存储引擎的两大顶流数据结构是 B+ 树和 LSM-Tree，那么 B+ 树和 LSM-Tree 的差别在哪里？为何传统数据库更青睐 B+ 树，而新数据库引擎更偏爱 LSM-Tree 呢？
B+ 树与 LSM-Tree
B+ 树是平衡搜索树的一种，是为了磁盘搜索而诞生的。B+ 树的所有数据都存储在叶子节点中，每次查询或写入时需要从根节点搜索到叶子节点，再对叶子节点对应的位置进行操作。传统数据库会将 B+ 树的每个叶子节点设置为一个磁盘页的大小，每次磁盘 I/O 就可以加载一个完整的叶子节点的数据到内存中，以此减少 I/O 的次数。
B+ 树查询/插入/删除的时间复杂度都是 O(logN)。
LSM -Tree 的核心思想就是将离散的随机写请求都转换成批量的顺序写请求。
当用户有数据写入时，会写入内存中的 Memtable 和数据日志 log，WAL(Write-Ahead Log) 机制可以保证重启后通过回放数据日志可以恢复到重启之前的状态。
当 Memtable 的数据量达到阈值，会将 Memtable 冻结为只读状态的 Frozen Memtable，冻结同时会创建一个新的 Memtable 用于提供数据写入。后台会将 Frozen Memtable 的数据以 rowkey 递增的次序，将数据顺序写入磁盘中，生成一个 SSTable。这个过程结束后，这个 Frozen Memtable 与其对应的log可以被回收。
磁盘上的 SSTable 被划分为多个层级（Level），层级数字越低表示数据被写入的时间越近，层级数字越大表示数据越旧。
为什么 OceanBase 选择了 LSM-Tree
B+ 树有原地更新和定长块的假设，这使得 B+ 树的数据块是不适合做压缩的，如果对数据块做了压缩会导致原地更新还需要额外的解压和压缩操作，使得查询性能非常差。而 LSM-Tree 是 append only 的模式，没有原地更新，将所有的 UPDATE/DELETE 操作都写做额外的数据，并且 SSTable 中的数据没有定长块的限制，压缩就变得比较自然。
后续 OceanBase 如果扩展到 OLAP 领域，列存就是一个绕不开的技术点。列存的设定是数据量大，且更新较少。那么B+树原地更新的优势在列存场景也会被削弱，在按列存储的模式中要对多列进行原地更新，实现难度比较大，代价也较高。LSM-Tree 的 delta 更新更适合列存场景。
Compaction
随着用户数据写入 Memtable，Memtable 超过内存阈值转化为磁盘上的 SSTable，SSTable 的数量会持续增多，使得查询需要访问的 SSTable 文件增多，降低查询的效率，所以引入了 LSM-Tree 最核心的概念：Compaction。
LSM-Tree 的 Compaction 操作是对数据的一次重新整合，其实质是多路归并排序，将若干个 SSTable 按照 Rowkey 递增排序，最后输出为一个 SSTable。
Compaction 虽然对于查询效率的提升效果显而易见，但是 Compaction 的执行过程是一个大量消耗机器资源的操作，过多的 Compaction 会导致资源倾斜到了 LSM-Tree 重整的步骤，而非用户的查询写入操作。
由于 Compaction 涉及磁盘上 SSTable 数据的读取和写入，这将占用大量 I/O 带宽；在读取和写入过程中涉及数据的压缩和解压、密集的 key 比较，是 CPU 密集型计算；而Compaction完成后会出现大量 Cache 失效等问题，造成性能抖动。比如内存中 Memtable 变成 SSTable 后，对内存 Memtable 的查询会变成对磁盘 SSTable 的查询，使得查询的耗时变长。
如何权衡 Compaction 带来的查询提速收益和 Compaction 占用的资源，这也是业界在持续关注的问题。
通用 Compaction 策略
说到 Compaction 就不得不提的三个概念：写放大、空间放大、读放大。
不同的 Compaction 策略其实是对三个维度的一个权衡，我们首先介绍三种权衡的定义：
- 写放大(Write Amplification) = 磁盘写入的数据量 / 实际写入的数据量
用户写入了一行数据，在 LSM-Tree 中可能触发若干轮的 Compaction 导致其他数据被读出写入，原本只是一行数据的 IO 写入却放大为 N 倍数据量的 I/O。
- 空间放大(Space Amplification) = 存储的数据量 / 实际存在的数据量
所有的写入都是顺序 append 写的，不是原地更新 ，所以过期数据不会马上被清理掉，相同 Rowkey 的行在多个SSTable都可能存在。
- 读放大(Read Amplification) = 本次扫描的数据量 / 实际返回的数据量
查询时需要从新到旧访问所有的SSTable直到查询到完整的数据，所以会导致扫描的行数比实际存储的行数更多。
业界常用的 Compaction 策略有 Classic Leveled、Size-Tiered、Tiered & Leveled 、FIFO 等。
OceanBase 的 Compaction 设计
OceanBase 的 LSM-Tree 划分为三层，使用的是 Tiered & Leveled 的 Compaction 策略，在 L0 层使用 Tiered 模式，在 L1 层、L2 层使用 Leveled 模式。
Compaction类型
OceanBase 共有三种 Compaction 类型：Mini / Minor / Major Compaction。
转储/Mini Compaction
内存中的 Frozen Memtable 通过 Mini Compaction 变成磁盘上的 Mini SSTable，是数据日志的一个checkpoint。Mini Compaction结束后，其对应的 Frozen Memtable 和 log 可以被释放。Mini Compaction 是一种Tiered 类型的 Compaction，核心就是释放内存和数据日志。
Minor Compaction
随着用户数据的写入，Mini SSTable 的数量会逐渐增多，在查询时需要访问的 SSTable 数量会增多，会影响查询的性能。Minor Compaction 就是将多个Mini SSTable合成一个，主要目的是减少 SSTable 的数量、减少读放大问题。
当 Mini SSTable 的数量超过阈值时自动触发 Minor Compaction。
1）L0 -> L0
Tiered类型的 Compaction，只将若干个 Mini SSTable 合成一个 Mini SSTable，放置于L0层；
2）L0 - > L1
Leveld类型的 Compaction，将若干个 Mini SSTable 与 Minor SSTable 合成一个新的 Minor SSTable，放置于 L1层。
如何确认是使用 Tiered 类型还是 Leveled 类型的 Minor?
上面的通用 Compaction 策略章节已有描述，Tiered 类型更适合数据量较少的情况，当 Mini SSTable 的数据量较大时，与 Minor SSTable 的数据量相近，则选择 Leveled 类型，减少读放大问题。
合并/Major Compaction
整个集群选择统一的 Major 位点，每个分区都使用该 Major 位点做快照查询，并将查询结果进行持久化生成Major SSTable。
合并触发有三种触发方式：自动触发、定时触发与手动触发。
- 自动触发：当用户做 Mini Compaction 的次数过多，积累的 SSTable 数量过多便触发一次 Major Compaction，缩减 SSTable 的数量，降低读放大；
- 定时触发：合并作为一个耗费资源的操作，应尽量避免在业务高峰期执行，用户可以通过设置触发时间，在业务低峰期定时触发合并；
- 手动触发：使用命令触发
ALTER SYSTEM MAJOR FREEZE;
更多详细内容，敬请关注 8月18日 19:30 「从 0 到 1 数据库内核实战教程」官方课程。带你详细解读 MiniOB & OceanBase 数据库存储引擎。
附录：
内核实战教程第一期 | 成为内核开发者的第一步：搭建研发环境
第一期课程回放
赶快扫描下方二维码进入「OceanBase 入门到实战」群
关注课程动态，和更多小伙伴一起学习进步
为帮助大家更好的学习数据库知识，结交新的朋友
未来 OceanBase Meetup 也会走到更多的城市中
大家进群后修改自己的群昵称哦【格式：姓名-城市-职位】
