开发者学堂课程【从0到1数据库内核实战教程：《OceanBase 存储引擎结构》下】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/16140
《OceanBase 存储引擎结构》下
《OceanBase 存储引擎结构》下
之前介绍的 OceanBase 存储 MiniOB 相关的知识和 Compassion 策略。为了更进一步了解 OceanBase 的数据库，对 OceanBase 存储有更深的认识，在这里介绍在分布式架构下 OceanBase 的分层存储结构以及 OceanBase 存储引擎下的内存存储格式和磁盘存储格式。为了让大家对 OceanBase 存储模型有一个更具体的了解，将从数据写入到查询的流程介绍 OceanBase 的各项工作流程。
在这里选择了两种通用的查询场景，一种是主表的查询，一种是索引表的查询。最后将简单总结查询执行的各项优化工作如过滤下压、言辞雾化、向量化等。
OceanBase 是一款分布式数据库，对于分布式数据库分区是其天然属性。从上往下看 OceanBase 最顶层是一个 partition group。partition group 对应着一个分区组，很多时候我们将其升为 PG，partition group 是一个为了取得极限性能而抽象出的一个概念，在一个用户的事物中可能会操作很多张不同的表，在OceanBase分布式架构下很难保证这些不同的表在相同的服务器上，那么，这就会带来分布式事物，而分布式事务是依赖两阶段提交的会有更大的开销，如果这些不同的表都在相同的服务器上，我们就可能对这个事物做一阶段优化以取得更好的性能，但大多数情况下对表的位置是没办法保证的，对于互联网下的很多应用，业务都会根据user ID 做表的分区，并且多张表的分区规则都是相同的，对于这些表提供的语法来构建 table group。对于 table group 中相应的分区，称之为partition group。
OceanBase保证同一个partition group始终绑定在一起，对于同一个partition group 的事物操作就会被优化成单机事物，以取得更好的性能。在一个partition group 中可能包含多个partition 注意这些Party型的分区间和分局规则要完全相同，Partition group是 OceanBase 实力的选举和迁移复制的最小单位。Partition就是表的一个分区和oracle mexico，对于分区的定义基本相同，OceanBase支持的分区规则，由哈希分区、论级分区和List分区甚至二级分区，但对于存储，这些都是一个 Partition。在 Partition内部可能包含多个table store，每个table store相当于一个快照点的数据集合，它包含有按照数据重热温冷的顺序包含有Mini SSTable、 Minor SSTable 和 Major SSTable。
最新写的数据会写入ActiveMenTable，当MenTable的大小达到了一定大小之后，冻结不再显露创建新的写作MenTable，为了节省内存冻结的MenTable会转储写到磁盘文件上生成Mini SSTable，当Mini SSTable文件个数增多，Mini SSTable间组建交叉的概率会增大影响查询效率，这次会触发多个Minor SSTable 或者Minor SSTable 合并成一个Major SSTable的过程。在Mini SSTable 和Major SSTable中包含了一段连续时间内写入的数据，以及这这段时间内数据的多版本信息。对于读多写少的场景，大多的情况下，只需要读取数据的最新记录。这时，就引入了Major SSTable。Major SSTable主要是在数据的多版本信息中选取一个快照点，然后读取这个快照点之前数据的最新记录将它写入一个单独的SSTable中，我们称之为Major SSTable。Major SSTable主要是查询优化以及多个副本之间的check sum一致性而用的。
前面学习到数据首先会写入MenTable。MenTable是数据的内存存储格式。MenTable内部记录了BTree和Hash table两种数据结构，每种数据结构都是指向数据记录的指针。在写读数据的时候并不知道数据的提交版本。当数据提交之后，通过回调函数填充数据的提交信息。
Hash table 和 BTree 各有优缺点，Hash table 主要是适合于单痕迹的查找。比如点查，在 DML中，很多情况下再插入一条数据的时候需要知道这条数据有没有被锁住，有没有和之前的数据组件有冲突，这个时候就需要单行查找，比较适合Hash table。BTree比较适合于范围查找，比如给您一个论及查询这个论及之类的组件信息以及对应的行的记录。
接下来讲数据的磁盘存储格式 OceanBase 的存储的磁盘数据文件叫 SSTable，OceanBase 是一款高效的HTAP系统。HTAP系统要同时兼顾读和写的性能，为了提高读写性能，在 SSTable 内部将数据按照数据块的大小分为红块和微块。红块是电厂的两兆的数据块大小，是写IO的基本单位。微块是一个变长的数据块，它是读IO的基本单位。微块一般是压缩前选取16K数据大小为一个微块。在这个图里面可以看到微块存储有两种存储格式，一种是扁平的存储格式称为行存，另外一种是列存的种族格式，我们称之为Encoding， Encoding可大大提高存储数据的压缩效压缩率，节省数据的存储成本。在这个图里面我们可以看到在红快的最开始的部分是红块的原信息，里面记录了红块的endkey等操作，主要用于一些红色的定位像二分查找。在红块的原数据后面跟着的是数据微块也就是实际的数据。为了在红块内部快速检索一个数据微块，在红块的尾部记录了这些微块的索引信息。微块的索引包含了微块的偏移以及微块的 end kings 等。这样我们在范围查找的时候可以根据一个roal king 的范围快速定位到相应的微块上面。
在前面了解的 OceanBase 的分层存储结构以及OceanBase的内存存储格式和磁盘存储格式之后。现在我将举个例子，譬如一些数据写入到查询，让大家对这个整个OceanBase的存储引擎，有一个比较具体的认识。
在这个例子里面，首先写了一题，对于这个表 T 写的一条记录 XYZ，在 T2时刻，对C2做了更新，在T3时刻，对 C3列做了更新。这个时候数据都在 MenTable 里面，然后在T4时刻，做了一个 Mini SSTable，把 MenTable的数据，download 到了磁盘文件上形成了Mini SSTable，可以看到，在这个 Mini SSTable中包含三条记录，一条记录是按最初的插入行XYZ，第二条记录是对C2年的更新XY1，第三条数据包含了数据的最新版本信息以及T3时刻的更新X1Y1Z1。可以看到在Mini SSTable中包含的数据，在T1、T2、T3时刻的多版本信息。在T5时刻，做了一个Major SSTable，Major SSTable的快照点，我们选择了一个大于T3时刻的快照点。在Major SSTable之后，在Major SSTable中存储的组件X对应的最新型XY1Z1。在T6时刻组建X的C2列做了更新，把Y1更新成了Y2，这个时候在MenTable中又插入了一条新的记录XY2。
可以看到在lsmtree架构下，我们无法做到对数据的原地更新,对数据的一条一条动态更新都是一条新的记录.这个快照点我们这行数据有三个数据源，一个是最新的Minor SSTable ，一个是保存了最新快照信息的Major SSTable还有一个保存了数据的多版本信息的Mini SSTable。最后要按照组建X对这个数据进行一次查询。首先会MenTable中找到数据的最新记录，比如说XY2，这次发现这个时候C3列没有值。需要填充C3列的值,这个时候就会从Major SSTable中找到数据的最新的快照。从C3的值拿到了XY1Z1这一行。拿到这两行数据之后，再上层会对这两行数据做一个Fields，也就是数据的融合,数据融合的过程很简单，就是按照重新盖旧的原则。比如说C2年最新的支持Y2，那么就选取Y2的值作为C2。然后C3年最新的就是Z1，那么就相信z1作为C3列的值，最后吐出X。Y2Z1的值这一行作为最终的结果返回去。
这个实际上是OceanBase里面最普通也最常用的一个组件查询，称为Get查询。在这个查询里面访问了两个数据源，一个是MenTable，一个是Major SSTable。
不是所有的查询都需要访问所有的数据源。如果在MenTable中有关于组建X的最新的完整记录。那么在读完MenTable之后就可以直接访问返回。比如，在这个查询里面在T6时刻对C2、C3列都做了更新，最后查询的时候，从MenTable中查到了这行数据的最新记录XY2Z2，每列的值都被填充上了，这个时候就可以直接返回给上层而不需要再Major和Minor SSTable 中继续查找。这也就是RSM tree查询的基本流程。
这里介绍了Get查询那接下来，只要简单抽象一下Get查询的基本流程。Get查询是主键查询，它是根据主键查询一条行数据的记录在DML以及按主键查找中会经常用到，所以对他的查询效率的要求也非常高，为了加速Get查询，在查询的链路上加入了locat的概念。比如在查询时，首先会从Located中查找这个组件是否有对应的开启记录以及这个Cache记录是否满足对应的快照位点，如果这两行都这这两个条件都满足，那就可以直接返回。如果发现这这开启里面没有这行数据或者这行数据对应的开启的快照太旧不是最新值，那么就会触发底层的数据源的迭代器从每个数据源中迭代出这个组件对应的行。同样也是采用重新挽救的原则进行迭代查找。在这个流程图里面MutipleMerge就对应着前面的Fruit的流程。
这里我给大家介绍了Get的查询流程，接下来介绍一下Scan的查询流程。
相对于Get查询来说，Scan查询是在不知道组建的情况，或者是只知道出现不分裂的情况下，需要对表的记录进行查询，这时又不能少整张表，因为这样太费操作了，所以会根据查询的特征抽取出一个论及范围，在这个组件论及范围之内，对整个表进行扫描。扫描的过程和给的查询略有不同，首先会构造各个SSTable的迭代器。每个SSTable会按照组建的顺序依次迭代出一行，然后利用归并排序的思想找出组建最小的行吐出给上层，如果遇到组件相同的就认为这个组件有交叉，这个时候就认为对这个组建有动态的更新。同样，会和Get查询类似，会按照重新挽救的原则，覆盖旧的原则，然后把这行frege支撑一个完整地行图给上层，譬如这个例子里面，我们在 Major快照二版本里面有三条记录，分别对应着X1X2X3，3个组件的记录行。再 Minor SSTable中对应着两条记录，分别是对于X1组件X1和组件X3的更新。
查询的范围是X移到组件X1到X3，首先会构造Major SSTable的迭代器和Minor SSTable的迭代器。Major SSTable首先会吐出组建最小的行X1Y1Z 1,Minor SSTable会吐出逐渐最小的行X1Y1。这个时候用归并排序的思想找到最小的组件X1发现两边的组件相等，我们认为Minor SSTable是对Major SSTable的更新，然后按照从以新盖旧的原则，最后吐出的行是X1Y1Z,吐出之后Major SSTable和 Minor SSTable接打器会同时往前推进一步。这个时候Major SSTable吐出的行下一行就是X2Y2Z2，Minor SSTable吐出的下一行是X3Y31Z31。这个时候同样利用归并排序的思想找到最小的组件是X2。Y2这个时候可以直接吐出给客户端，然后Major SSTable的客户端往前推进一步。这个时候Major SSTable下一个突出的行是X3Y3Z3，Minor SSTable之前吐的行也是X3Y31Z31，这时候发现两个归并排序的时候发现两行的组建也是相等的，这时候会认为minus table是对magi state的更新采用以新盖旧的原则。最后得出的行式X3Y31G31，这样就完成了一个组件范围X1X3范围内的扫描。
下面抽象一下整个scan的查询流程。在scan查询的时候，首先会根据要扫描的组件的范围定位到对应的Partition，从Partition中根据选取的查询快照以及组建的范围选取一个最小的需要访问的数据集合，向SSTable集合和Minor SSTable集合。分别构造这些推广的迭代器。打开这些table的迭代器之后再根据查询的范围进行定位，我们叫Rock的range。最大的红块和微块，在红块上面记录了红快的源信息，比如红块的end king，可以用这些end king进行二分查找，找到对应的红块ID。在红块ID内部再根据微块的索引信息找到对应的微块信息，这样就可以定位到实际的数据块，乐定位到实际的数据块之后我们就可以用迭代器对数据进行扫描，然后按组建的顺序吐出对应的行。每个点打气突出对应的行之后，会利用归并排序的思想找到组件最小的行。对于组件相同的行会按照重新盖旧的原则。Filed指出数据完整的行，最后投影和过滤。最后对满足过滤条件的行反馈给客户端，如果这一行不满足过滤条件，又会回到迭代器内部突出下一行，然后进行归并排序。进行field进行投影和过滤。在这里为了简化整个归并排序的流程，用了败者树的算法。
败者树实际上是一个像堆一样的结构，它维护了每个迭代器里面吐出的当前行以及他能迭代出每个数据源中的组建最小或者最大的行，并且维持这些行的数据版本信息，如果遇到组件相等的行，我们会按照重新往盖旧的原则，对这些行进行Field。败者是我大大简化了组件蹩脚的操作，也提高了整个实干流程的查询效率。
前面介绍的查询和实干查询这些是针对主表的查询，知道在数据库里面还有一种索引表。在OceanBase里面局部索引相当于数据表的二级索引。它记录了索引组件和主表主键的对应关系。
在根据索引查询对行的记录时，往往需要做索引回表。
主要分为两步，第一步是索引表的查询，也就是根据索引组件进行scan找到对应的主表组件，第二步是根据主表组件从主表中进行的查询找到对应的行记录。有时会优化回表的相关操作会同时发放多个组件的查询。我们称之为Market。从主表中查找对应行的记录。在这里已经简单介绍OceanBase中数据写入到查询的流程以及索引表查询的流程。但实际上，OceanBase是一款分布式数据库，它支持的数据的容量比较大。比如数据往往会达到上T或者几十T，这时会扫描的数据特别多，特别是在一些app场景下，对延迟的要求会比较高。
这时就需要做一些产品优化。比如常见的scan查询。我们需要定位到数据微块之后，数据微块往往并不在内存中，这时就需要做文件IO，将数据微块Load到内存并进行解压解析，这时我们就会阻塞整个查询流程，为了提高scan查询流程，提出的数据预期的算法，比如在来定位到数据微块之后会发动100线程论及范围之内的数据微块会进行解压。得到相关的Block开启中。真正对数据进行查询时，只需要从Blue开始查到对应的blue catch，然后直接扫描解压之后的数据就可以了，这个时候就不会阻塞整个查询流程。
在前面看到，数据的过滤，使得投影之后进行。而从数据迭代到过滤之间会经过败者数的比较数据的 Fields 数据的投影。如果这一行数据不满足国内条件，其实上这个操作是很费的。为了进一步提高查询效率，我们会把过滤算子下压到下面的迭代器中。比如 Major SSTable 中、Minor SSTable 中提前过滤，这样可以少迭代一些行或者少做一些投影操作。并且在 Major SSTable 中数据是按编码规则做得列存储。可以比如披露简单的举例 Cost 编码。就可以按照这种编码规则和过滤条件依次处理一批数据，这样可以极大地提升整个查询效率。也可以利用 CPU 的指令流水线在过滤的时候做一些向量化处理。这样可以非常大幅度的提升整个查询效率。
然后做完 Major 或者 Minor SSTable中，整个数据在磁盘属于冷数据。配合我们查询比较密集，不希望有比较多的，可以在数据合并之后发起一些查询预热等。将一些比较热的数据预先 Load 到内存里面，这些技术都可以大幅加速整个查询流程。在去年六月份实现了过滤下压、向量化等各种 app 场景下的优化查询优化。在30 T的场景下，在官方测试中取得了第二的好成绩。在 OceanBase 的存储引擎内部还有很多针对查询相关的优化，像不能过滤器各种的 cache、各种的单边扫描向量化等。
