此前，带你读源码第五篇《戳这里回顾：OceanBase 源码解读（五）：租户的一生》为大家介绍了社区版中创建、删除租户、资源隔离的相关代码，本文将为大家详细讲解 OceanBase 存储引擎。
本文将回答关于 OceanBase 数据库的相关提问：
- OceanBase 是否依赖其他开源KV数据库（例如：LevelDB、RocksDB）？
- OceanBase 底层引擎是什么？是KV吗 ？
- OceanBase 内存结构是 B+Tree 还是 LSMTree ？
- OceanBase 如何实现高性能服务？
背景
目前业界数据库存储引擎主要分为两种：
- update-in-place ：原地更新，较常见于传统关系型数据库( MySQL、Oracle )采用的 B+Tree 结构。优点：更新记录时对原有记录进行覆盖写。有较好的数据局部性，对扫描比较友好。缺点：是引入大量的随机写，同时还有一定的并发问题；并且与业务流量叠加，对业务流量有一定的影响；
- log-structure storage：日志更新，例如LevelDB、RocksDB、HBase、BigTable 等采用的 LSMTree 结构。优点：日志更新无锁，不会引入并发问题，能够保证高效写入，并且没有空间碎片。缺点：是读路径变长，例如 LSMTree 结构在扫描时需要读取 memtable 、L0层及其余层的数据，并进行归并，需要通过异步 compaction 进行GC以及均衡各个层级的数据来避免过多的读放大。
为追求极致的数据库性能，scan 操作需要良好的空间局部性，get/put 操作需要高效的索引来定位，version/gc/compaction 会提升读操作的性能但可能影响整体性能，目前的存储引擎都存在着一定的局限性。
为此 OceanBase 选择完全自主实现存储引擎，没有借助于任何其他已有的开源方案。
从架构上看，OceanBase 的存储引擎可分为两层：
①底层的分布式引擎实现了线性扩展、Paxos 复制、分布式事务等分布式特性从而达到持续可用；②上层的单机引擎融合了传统关系数据库以及内存数据库的一些技术从而达到极致性能。
本文将从单机引擎和分布式架构视角分别介绍。
01 单机引擎
读写分离架构
OceanBase 的存储引擎采用分层 LSMTree 结构，数据分为两部分：基线数据和增量数据。
基线数据是持久到磁盘上的数据，一旦生成就不会再修改，称之为 SSTable。
增量数据存在于内存，用户写入都是先写到增量数据，称之为 MemTable，通过 Redo Log 来保证事务性。
当 MemTable 达到一定阈值时会触发冻结( Frozen MemTable )，并重新开启一个新的 MemTable( Active MemTable )，Frozen MemTable 被转存到转储 SSTable 中，然后在合并( LSMTree 结构特有的 compaction 动作 )时将转储 SSTable 合并入基线 SSTable，生成新的 SSTable 。
在查询时，需要将 MemTable 和 SSTable 的数据进行归并，才能得到最终的查询结果。
系统为基线数据和增量数据指定不同的版本，数据版本是连续递增的。
每生成一个新的 Active MemTable，都会设置为上个 MemTable 的版本加1（实际生产中，两次合并之间会有多次转储，这两次合并之间生成的所有MemTable 表示一个大版本，每个 MemTable 会用小版本表示，例如下图中的v3.1和v3.2）。当 SSTable 与 Frozen MemTable 合并之后，也会将版本设置为合并的 Frozen MemTable 的版本。
读写分离架构好处：因基线数据是静止状态，方便对其进行压缩，减少存储成本和提升查询性能；做行级缓存不用担心写入带来的缓存失效问题。
读写分离架构缺点：读路径变长，数据需要实时归并可能带来性能损耗，需要合并减少数据文件，同时我们引入多层 Cache 来缓存频繁访问的数据。
合并是基于 LSMTree 架构的存储引擎特有的动作，用于基线数据和增量数据的归并，在 HBase 和 RocksDB 称为 major compaction。
OceanBase 通常在每天的业务低峰期触发合并，非低峰期通过转储来释放内存，我们称之为“每日合并”。在合并窗口内做了数据压缩、数据校验、物化视图、schema 变更等事情。
合并提供很多好处，但也需承受一定的代价——对系统的 IO 和 CPU 会有较多的消耗。
目前业界的 LSMTree 数据库没能很好的解决该问题，为此 OceanBase 做了优化，包括增量合并、渐进合并、并行合并、轮转合并、IO隔离等技术。
相比较于传统关系型数据库，每日合并可以更好的利用业务低峰期的空闲IO，对数据压缩、校验、物化视图等也提供更好的支持。
转储是将内存中的增量数据存储于磁盘，类似于 HBase 和 RocksDB 的 minor compaction ，可以缓解 LSMTree 架构下的内存压力。
OceanBase 采用了分层转储的策略，达到了读取和写入之间的平衡，避免转储 SSTable 过多拖慢读性能，同时也避免了业务大量随机写造成的转储写放大。
OceanBase 还进行了资源隔离（包括CPU、内存、磁盘IO、网络IO等四个方面的资源隔离）避免转储消耗过多资源，减少对用户请求的影响。
这些方面的优化平滑了转储对性能的影响，使得 OceanBase 在 TPC-C 测试中性能曲线绝对平滑。
基线数据
SSTable 将数据按照主键的顺序有序存储，数据被划分为2MB的块，称之为宏块。
每个宏块对应一个主键范围的数据，为了避免读一行要加载一个宏块，宏块内部又划分为多个微块，微块的大小一般为16KB。合并时微块写满16KB时，根据行数据的规律探测编码规则，并根据选择的编码规则对数据进行编码及计算 checksum ，所以微块是读IO的最小单位。
OceanBase 的微块压缩后是“变长数据块”，空间浪费很少。而传统关系型数据库是“定长数据块”，开启压缩会不可避免的造成存储的空洞，存在较多的空间浪费，压缩率受影响。
在相同块大小（16KB），相同压缩算法，相同数据的情况下，在 OceanBase 中要比在传统关系型数据库中节省相当多的空间。
宏块是合并时的基本单位，SSTable 按照宏块来迭代，MemTable 按照行来迭代。如果 MemTable 的行不在宏块的数据范围里面，新版本的 SSTable 直接引用该宏块。如果宏块的数据范围内有更新数据，需要将宏块打开，解析微块索引，并迭代所有微块。
对于每一个微块，加载行索引，将所有行解析出来跟MemTable进行合并，如果已经 append 的行达到16KB，则构建成一个新微块，并进行编码压缩及计算 checksum。对于未修改过的微块，不用解析微块内的内容，直接将整个微块拷贝到新的宏块即可。
OceanBase 对数据质量保持着敬畏之心，合并时会做两方面的数据校验：
① 一方面同一份数据会有多个副本，会做副本间的一致性检验，保障业务数据在不同副本间是一致的；② 另一方面会做主表和索引表的一致性校验，保障数据在主表和索引表之间是一致的。
数据校验是 OceanBase 对自己的一道防火墙，保障交付给业务的数据是完全正确的，避免客户投诉才知晓。
增量数据
MemTable在内存中维护历史版本的事务，每一行将历史事务针对该行的操作按时间序从新到旧组织成行操作链，新事务提交时会在行操作链头部追加新的行操作。
如操作链保存的历史事务过多，将影响读取性能，此时需要触发 compaction 操作，融合历史事务生成新的行操作链，compaction 操作不会删除老的行操作链。
OceanBase 基于以上 MVCC 机制实现并发控制，读事务与写事务互不影响:
① 如读请求只涉及一个分区或者单台 OBServer 的多个分区，执行快照读即可；② 如涉及多台 OBServer 的多个分区，需要执行分布式快照读。
MemTable 中采用双索引结构，一块是 Hashtable ，用于KV类的快速查询；一块是BTree，用于Scan等扫描查询。在插入/更新/删除数据时，数据被写入内存块，在 Hashtable 和 BTree 中存储的均为指向对应数据的指针。
每次事务执行时，会自动维护两块索引之间的一致性。两种数据结构各有优劣：
① 插入一行数据的时候，需要先检查此行数据是否已经存在，检查冲突时，用 Hashtable 比 BTree 快；② 事务在插入或者更新一行数据时，需要找到此行并对其进行上锁，防止其他事务修改此行，在 ObMvccRow 中寻找行锁时，用 Hashtable 比 BTree 快；③ 范围查找时，由于 BTree 节点中的数据是有序的，能够提高搜索的局部性，而 Hashtable 是无序的，需要遍历整个 Hashtable 。
OceanBase 是一个准内存数据库，绝大部分的热点数据都是在内存中，以行的方式组织，且在内存不足时以MB粒度将数据写入磁盘，避免了传统关系型数据库以页面为单位的写入放大问题，从架构层面大大提升了性能。
OceanBase 还引入内存数据库的优化技术，包括内存多版本并发、无锁数据结构等，实现最低延迟及最高性能。
同等硬件下，OceanBase 性能相比传统关系型数据库有很大提升，再加上得益于多副本强同步而采用的普通PC服务器，数据库的硬件成本大大降低。
缓存
上文提到由于读路径变长，我们引入了多层 Cache 机制。
Cache 主要用于缓存 SSTable 中频繁访问的数据，有用于缓存 SSTable 数据的 block cache、有用于缓存微块索引的 block index cache 、有用于缓存数据行的row cache，有用于缓存 bloomfilter 可以快速过滤空查的 bloomfilter cache。
由于 SSTable 非合并期间只读，所以不用担心 Cache 失效的问题。
读请求来临时，首先从 Cache 中读取数据，如果 Cache 没有命中会产生磁盘IO读取微块数据，可以根据 Cache 命中次数及磁盘读取次数来计算逻辑读，逻辑读用于评估 SQL 执行计划的优劣。对于单行操作，如果行存在，则会命中 row cache；如果行不存在，则命中 bloomfilter cache。
因此绝大部分单行操作在基线数据中只需要一次缓存查找，没有额外开销。
OceanBase 中有两个模块会占用大量的内存:① MemTable 为不可动态伸缩的内存；② 就是 Cache 为可动态伸缩的内存。
与 linux 的 Cache 策略一样，OceanBase 中的 Cache 也会尽量使用内存，力求把除 MemTable 以外的内存用满。因此 OceanBase 为 Cache 设计了优先级控制策略及智能淘汰机制。
类似于 Oracle 的 AMM，设计了一套统一的 Cache 框架，所有不同租户不同类型的 Cache 都由框架统一管理，对于不同类型的 Cache，会配置不同的优先级。（例如 block index cache 优先级较高，一般是常驻内存很少淘汰，row cache 比 block cache 效率更高，所以优先级也会更高。）
不同类型的 Cache 会根据各自的优先级以及数据访问热度做相互挤占。优先级一般不需要配置，特殊场景下可以通过参数控制各种 Cache 的优先级。如果写入速度较快，MemTable 占用内存较多，会逐步淘汰 Cache 内存给MemTable 使用。
Cache 内存以2MB为单位进行淘汰，根据每个2MB内存块上各个元素的访问热度为其计算一个分值，访问越频繁的内存块的分越高，同时有一个后台线程来定期对所有2M内存块的分值做排序，淘汰掉分值较低的内存块。
在淘汰时，会考虑各个租户的内存上下限，控制各个租户中 Cache 内存的使用量。
极致性能
基以上介绍，OceanBase 的存储引擎非常接近于传统关系型数据库的单机引擎特性——一个数据分区的所有数据（基线数据 + 增量数据 + 缓存数据 + 事务日志）全部放于一个 OBServer 中。
因此针对一个数据分区的读写操作不会有跨机操作（除了事务日志通过 Paxos 协议形成多数派同步），再加上准内存数据库及极佳的 Cache 机制，从而能够提供极致的OLTP性能。
02 分布式架构
数据分区
OceanBase 的两种方式：
① 引入传统关系数据库中的数据分区表( Partition )的概念；
② 兼容传统关系型数据库的分区表语法，支持 hash 分区和 range 分区。
支持二级分区机制，例如对于历史库场景，单表数据量庞大，一级按用户分区，二级按时间分区。从而很好的解决大用户扩展性的问题，如果要删除过期数据，可以通过 drop 分区实现。
也支持生成列分区，生成列指这一列由其他列计算所得，该功能能够满足期望将某些字段进行一定处理后作为分区键的需求。
对分区表查询进行优化：
① 对于查询中包含分区键或者分区表达式的查询，能够准确的计算出该查询对应的分区，称为分区裁剪；
② 对于多分区查询，能够使用分区间并行查询、分区间排序消除、partition-wise join 等技术，从而大大提升查询性能。
同一数据分区的副本构成一个 Paxos Group，自主进行选主，推举出其中某个副本作为 Leader，其他副本自动成为 Follower，后续所有针对这个数据分区的读写请求，都会自动路由到对应的 Leader 进行服务。
OceanBase 采用 share-nothing 的分布式架构，每个 OBServer 都是对等的，管理不同的数据分区。
① 对一个数据分区所有读写操作都在其所在的 OBServer 完成，属于单分区事务；
② 多个数据分区的事务，采用两阶段提交的方式在多个 OBServer 上执行，属于分布式事务。
单机多分区事务，依然需要走两阶段提交，且针对单机做了专门的优化。分布式事务会增加事务延迟，可以通过表格组(table group) 将经常一起访问的多张表格聚集在一起，同一表格组的分区具有相同的 OBServer 分布，且 Leader 位于同一台机器上，避免跨机事务。
传统关系型数据库也支持分区功能，但所有分区仍存放在同一台机器上。
而 OceanBase 能够把所有分区打散到不同物理机器，从而能够真正体现出分布式架构的优势，从而彻底解决可扩展性问题。
当容量或者服务能力不足时，只需要增加更多的数据分区并打散到更多的 OBServer 即可，从而可以通过在线线性扩展的方式提升整体读写性能。在同样系统容量充足或者处理能力富余时，将机器下线，降低成本，提供良好的弹性伸缩能力。
多副本Paxos同步
OceanBase 中的数据分区冗余有多个副本（例如，同城三副本部署架构为3个，三地五副本部署架构为5个），分布于多个 OBServer 上。
事务提交时利用 Paxos 协议在多个副本间达成多数派提交，从而维护副本之间的一致性。当单台 OBServer 宕机时可以维护数据的完整性，并在较短的时间内恢复数据访问，达到 RPO=0、RTO<30秒的SLA。
用户无需关心数据所在的具体位置，客户端会根据用户请求来定位数据所在的位置，从而将读写请求发送给 Leader 进行处理，对外仍然展现为一个单机数据库。
基于以上介绍的多副本架构我们引入了轮转合并的概念，将用户请求流量与合并过程错开来。
比如：一个OceanBase集群中Partition的副本个数为3，这三个副本分布在3个不同的Zone(1,2,3)中，RootService在控制合并时，比如先合并Zone3，会首先将用户流量切到Zone(1,2)中，只要切换所有Partition的Leader到Zone(1,2)即可。Zone3合并完成之后，准备合并Zone2，则将Zone2的流量切走，之后再合并Zone1，最后三个副本全部合并完毕，恢复初始的Leader分布。
多副本架构带来了三个比较大的架构提升：
- 数据库服务的可用性得到提升，如果某个 OBServer 突发宕机或者网络分区，自动、迅速的把故障 OBServer 的读写服务切换到其他 OBServer 上，RPO=0，RTO<30秒。传统关系型数据库通过主备架构来容灾，在不使用共享存储的情况下，难以完美做到在主库故障时数据零丢失，且由于数据一致性问题无法自动切换，切换效率也难以保证；
- 数据库的资源使用率得到提升，利用 OceanBase 多库多活的特性，配置让三个 Zone 中的两个提供读写服务，第三个 Zone 作为热备库接受事务日志，随时待命提供读写服务。OceanBase 的机器使用率达到了2/3，而传统关系型数据库主备架构只能使用到1/2的机器；
- 数据库的数据压缩率得到提升，由于轮转合并的引入，用户请求流量与合并过程错峰，正在合并的 Zone 的 CPU 和磁盘IO可以大量用于复杂的数据编码/压缩，并选择最优的编码算法，并且对业务数据写入零影响。高压缩率不但节省了存储空间，同时也会极大的提升查询性能。传统关系型数据库原地更新数据，与业务流量叠加，在“高压缩率”和“低计算成本”两者之间只能选择后者，甚至建议用户谨慎使用该功能。
03 总结
基于 LSMTree 的单机引擎和基于多副本强同步的分布式架构，才是完整的 OceanBase 存储引擎。这种存储引擎有众多好处，既有类似于 Oracle 的关系型数据库上层，又有类似于 spanner 的分布式底层。
这是 OceanBase 的核心能力，能够规避 LSMTree 缺陷，获得极致性能和丝般顺滑，支持最核心的 OLTP 业务。同时又获得了分布式架构的优势，包括持续可用、线性扩展、自动容错、低成本等特性。
//作者感言
从2010年一路走来，每一步 OceanBase 犹如走在悬崖峭壁，走得十分小心翼翼。回头看，非处当时之情景，不能理解当时之设计。好的设计不是“想”出来的，而是“痛”出来的，希望大家在阅读时也能够感受到这份成果背后的“痛并快乐着”。
