OceanBase 源码解读（七）：一文读懂数据库索引实现原理
此前，带你读源码第六篇《戳这里回顾：OceanBase 源码解读（六）：存储引擎详解》为大家详细讲解了 OceanBase 存储引擎，并为大家回答了关于 OceanBase 数据库的相关提问。
本期“源码解读”将尝试从代码导读的角度，简要介绍 OceanBase 的索引构建流程，带领大家读懂索引构建的相关代码，必须速速收藏！
1. 什么是索引
首先请思考，在一个一般的数据库中，索引表的语义是什么？
索引表，其实是在主表（也称数据表）之外，再创建一份冗余且有序的数据，用于加速某些查询流程。为什么索引表可以加速查询，是因为索引表是按照索引键排序的，如果某个查询语句的查询条件中指定了索引前缀，那么通过二分查找即可快速找到对应的行。索引表的行中包括了主键信息，所以可以通过主键快速找到主表的完整行，这个过程也叫索引回表。
知道了索引表的语义，那创建索引要做哪些事呢？
其实索引表也跟主表一样，有自己的 schema、内存结构和持久化的数据（通常存放于本地磁盘上）。在分布式场景下，还可能有自己的位置信息。那创建索引也就是要创建索引表的 schema，然后在某个位置创建索引表的内存结构，创建索引表的持久化数据。
在创建索引的过程中，我们不希望影响主表的正常读写，即建索引过程中业务是在线（online）的。为了做到在线建索引，不同厂商对在线的有不同的实现机制，本文会介绍 OceanBase 是如何实现在线建索引的，对其他方案感兴趣的同学可以自行参考相关文档。
2. 索引创建过程总览
2.1 用户视角
我们先从用户的视角看一下索引构建的过程是怎样的。例如：用户在一个 session 上发送了建索引的语句 create index i1 on t1(c2)，然后用户就在当前 session 上不断等待，直到索引构建成功或者失败。
2.2 中控 observer 的视角
那在 observer 的视角，这其中包含哪些流程呢？首先这条语句的文本被随机发送到一个 observer（observer 下文简称 obs），收到这条语句的 obs 叫做中控 obs。跟其他语句一样，这条建索引的 sql 语句首先经过 parser 和 resolver，发现这是一条 ddl 语句，并且将这条语句解析成了 OceanBaseCreateIndexArg 这样一个结构体。对于 ddl 语句，OceanBase 是发送到 rootservice（rootservice 下文简称 rs）来处理，所以中控 obs 向 rs 发送一个建索引的 rpc 请求，这个 rpc 请求中携带了 OceanBaseCreateIndexArg。
rs 收到该请求后，通过 ObRootService::create_index 函数来处理这个请求，这个接口做完必要的同步处理后，就向中控 obs 发送 rpc 的回包，但注意，此时索引构建还未完成，实际 rs 会通过异步任务来真正推进索引构建。中控 obs 收到 rs 的回包后，会不断查询索引表的 schema 状态来获取建索引的结果，如果构建成功，则向客户端返回构建成功，如果构建失败，则向客户端返回失败的错误码。
3. RS 的同步处理流程
上文说到 rs 在向中控 obs 回包前做了一些同步处理，本节我们先看下这部分的具体流程。调用路径：
上述的调用过程会做一些防御性的检查，例如系统表、回收站中的表，OceanBase 是不支持建索引的，如果一个表的索引数量超过上限，也是不允许建索引的。通过检查后，根据索引类型选择走 local 还是 global 的构建索引流程。
3.1 global 和 local 的概念
全局（global）索引和局部（local）索引的区别是什么？其实最主要的区别是局部索引是分区级的，即索引表的分区一一对应主表的分区，全局索引是表级的，即全局索引表的分区与主表的分区没有对应关系。
换句话说，local 指的是分区级的 local，global 指的是表级的 global。例如，t1 表有两个 hash 分区，如果建局部索引 i1，则 i1 一定有两个分区，并且 i1 的第一个分区是对 t1 的第一个分区的索引，i1 的第二个分区是对 t1 的第二个分区的索引。如果对 t1 建全局索引 i2，则 i2 可以有一个分区，也可以有多个分区，且分区不与主表一一对应。
因为局部索引跟主表的分区是一一对应的，所以在 OceanBase 中，我们将局部索引的分区与主表的分区紧密绑定在一起，这样主表分区和索引表分区的 location 信息是一致的（一定在一台机器上），从而避免跨机的分布式事务。也因此，上述选择索引构建路径时，对全局索引有个优化，如果全局索引的主表和索引表都是非分区表，那这种全局索引可以走局部索引的构建流程。
3.2 生成全局索引的控制任务
关键函数的调用路径：
ObIndexBuilder::generate_schema 负责生成索引表 schema 的基础信息，表级信息主要继承自主表，索引表主要考虑列信息，正常索引只要带索引列和主键列，重复的主键列省掉。唯一索引需要带索引列，隐藏主键列和主键列。什么是隐藏主键，隐藏主键是为了解索引列值为 null 时的比较问题。
因为 sql 语义中，null 与 null 是不相等的，但在代码比较中 null 与 null 的数值是相等的，所以如果索引列存在 null 时，隐藏主键列会填上主键的具体值，如果索引列不为 null，则隐藏主键列填 null 值，索引键比较时带上隐藏主键列就可以实现 null 与 null 不相等的语义。generate_schema 只是生成列索引表 schema 的内存对象，此时索引表还不可用，所以在 schema 中将索引表的状态置为 INDEX_STATUS_UNAVAILABLE。
生成好索引表的 schema 后，需要将 schema 写入内部表，这一步是通过ObDDLOperator::create_table完成的。
然后还需要在相关机器创建索引表的的内存结构，因此通过 ObDDLService::generate_global_index_locality_and_primary_zone 生成了索引表的位置信息，通过 ObDDLService::create_table_partitions 向目标机器发送 rpc，通知他们创建索引表的各个分区的内存结构，包括 memtable，table_store，以及 partition_key 到 table_store 的映射等。然后，通过 ObDDLService::publish_schema 通知其他机器刷新 schema。
完成上述索引表的 schema 和内存结构的创建后，通过 ObGlobalIndexBuilder::submit_build_global_index_task 提交全局索引的数据补全的控制任务到队列中，后续通过该控制任务，推进全局索引的数据补全流程。
在提交该控制任务同时，submit_build_global_index_task 会在__all_index_build_stat 中创建一条任务记录，之后该控制任务的状态推进也会更新到__all_index_build_stat 表中。
全局索引控制任务由 ObGlobalIndexBuilder 负责执行，这个线程池只有 1 个线程，队列长度受限于内存（未设置内存上限），任务执行的入口是 ObGlobalIndexBuilder::run3 -> ObGlobalIndexBuilder::try_drive。
3.3 生成局部索引的控制任务
关键函数的调用路径：
局部索引生成 schema 以及创建内存对象的的逻辑跟全局索引几乎相同，唯一的区别是局部索引不需要生成索引表的位置信息，其他逻辑这里不再赘述。
完成上述索引表的 schema 和内存结构的创建后，通过 ObRSBuildIndexScheduler::push_task 将局部索引的控制任务 ObRSBuildIndexTask 放入队列，同时更新内部表__all_index_build_stat。
局部索引的控制任务由 ObDDLTaskExecutor 负责执行，这个 executor 只有 1 个线程，队列长度受限于内存（内存上限为 1G），任务执行的入口是 ObDDLTaskExecutor::run1 -> ObRSBuildIndexTask::process。
4. 全局索引的构建流程
全局索引的控制任务 ObGlobalIndexTask 设计了一个简单的状态推进，对每种任务状态，执行相应的函数。整体思路是，先在索引表的一个副本上构建基线数据，然后将基线数据拷贝到其他副本，再执行必要的一致性和唯一性检查，最后让索引生效。
代码路径：
4.1 单副本构建
单副本构建是指在一个副本上完成索引表基线数据的补全，根据 OceanBase 的 lsm-tree 的结构，这里的基线数据是指建索引表的 major sstable。
代码路径：
单副本构建首先要选一个快照点，保证该快照点之后，对主表的 dml 操作（增量数据）都可以看到该索引表，这意味着快照点之后的 DML 操作都会同步修改索引表，但对查询操作来说，该索引表不可用，这种 write-only 的行为其实是 OceanBase 实现在线建索引的关键。
基于该快照点构建基线数据（存量数据）后，又因为 lsm-tree 的查询会 fuse 多层的数据，所以可以通过幂等性保证索引表数据的完整性。为了拿到该快照点，假设创建索引表时 schema_version 是 v1，那么需要等待所有依赖 schema_version <= v1 的事务都结束。do_get_associated_snapshot 函数就是发送 rpc 给主表分区的 leader，询问这些事务是否都已经结束，收到该请求的 obs 通过 ObService::check_schema_version_elapsed 接口处理，之后 do_get_associated_snapshot 通过 wait_all 等待所有 rpc 的返回，注意这里其实是批量的同步 rpc，所以分区数特别多时，可能会阻塞索引任务推动线程。
为了保证单副本构建过程中，选中的快照点不被释放，需要 hold 住该快照点，注意，如果这里 hold 住快照的时间过长的话，可能会导致 table_store 的数量爆掉。然后将选好的构建快照点更新到内部表__all_index_build_stat 中。最后提交一个索引表基线数据的构建任务 ObIndexSSTableBuildTask。
基线补全任务提交后，通过 drive_this_build_single_replica 不断检查基线补全的任务状态，如果基线构建完成，则通过 checksum 校验来检查主表和索引表数据的一致性。
4.2 基线补全
ObIndexSSTableBuildTask 任务由 IdxBuild 线程池负责执行，任务队列 4096，线程数 16。
看下 ObIndexSSTableBuildTask 的执行过程，代码路径：
ObIndexSSTableBuilder::build 函数是同步执行，也就是说，系统中最多有 16 个基线补全的任务同时执行，执行结束后，通过 on_build_single_replica_reply 更改基线补全的任务状态。
上述代码路径看似复杂，其实最终是通过 ObIndexSSTableBuilder::build 构建了一个物理执行计划，通过 ObResultSet::get_next_row 来执行该计划，下面的代码路径给出了物理执行计划的生成过程，PHY 开头的常量是指物理算子的类型。
最终的物理执行计划如下：
4.3 多副本拷贝
代码路径：
多副本拷贝是把单副本构建流程中构建好的基线数据拷贝到其他副本的过程，实际数据拷贝是通过 ObCopySSTableTask 完成的，该任务被 rs 的 ObRebalanceTaskMgr 调度执行，入口在 ObCopySSTableTask::execute，实际上是发送 copy_sstable_batch 的 rpc，收到该 rpc 的 obs 的执行入口是 ObService::copy_sstable_batch。完成基线数据拷贝任务后，obs 向 rs 汇报结果，rs 执行回调 ObGlobalIndexBuilder::on_copy_multi_replica_reply 更新多副本拷贝任务的状态。
4.4 唯一性校验
对于唯一索引，需要校验索引列数据的唯一性，非唯一索引不需要执行该校验。代码路径：
为了校验唯一性，需要选一个快照点，在此快照点之后，对主表的 dml 操作（增量数据）都可以看到该索引表的基线，因此可以在 dml 过程中校验唯一性，在此快照点之前的数据（存量数据），计算该快照点的主表和索引表列 checksum，通过 checksum 比对，校验其唯一性。该快照点，需要所有副本的新事务都可以看到基线数据，假设各副本看到基线数据的时间戳的最大值是 sstable_ts，则需要等待所有事务的事务上下文创建时间戳推过 sstable_ts。get_checksum_calculation_snapshot 函数完成上述操作，检查事务上下文创建时间戳是否推过 sstable_ts 的函数入口是 ObPartitionService::check_ctx_create_timestamp_elapsed。
拿到快照点后，发送 rpc 请主表和索引表的 leader 计算改快照点的列校验和，收到该 rpc 的 obs 的处理入口是 ObService::calc_column_checksum_request。计算完成后，将列校验和记录在内部表 __all_index_checksum 中，并通过 rpc 通知 rs，rs 执行回调 ObGlobalIndexBuilder::on_col_checksum_calculation_reply，更新 checksum 计算任务的状态。drive_this_unique_index_calc_checksum 不断检查 checksum 计算任务的状态，如果 checksum 全部计算完成，则通过 ObGlobalIndexBuilder::try_unique_index_check -> ObIndexChecksumOperator::check_column_checksum 执行校验和的比对。
4.5 索引状态变更
如果上述步骤全部成功完成，则通过 ObGlobalIndexBuilder::try_handle_index_build_take_effect 函数使索引生效，实际是修改索引表的 schema 状态为 INDEX_STATUS_AVAILABLE，中控 obs 看到该状态后，向客户端 session 返回成功。
如果上述任一步骤失败，则通过函数将索引表状态改为 INDEX_STATUS_INDEX_ERROR，中控 obs 看到该状态后，向客户端 session 返回索引构建失败。
4.6 中间结果清理
索引构建结束后，无论结果是成功或是失败，都要执行中间状态清理，包括清理 sql 执行的中间结果，释放快照，清理内部表等。代码路径：
5. 局部索引的构建流程
局部索引的 rs 端控制流程比较简单，这是因为 rs 端不是主要战场。代码路径：
5.1 任务触发
因为局部索引的分区与主表的分区一一绑定，所以局部索引构建流程的主战场就在主表分区所在的 obs 上。obs 通过监测每个租户的 ddl 变更，来触发构建局部索引的任务：在索引表的 schema 发布后，主表所在的 obs 会刷新到该 schema，然后发起局部索引构建任务。
代码路径：
ObTenantDDLCheckSchemaTask 会找到要构建索引的 partition_key ，然后生成一个 ObBuildIndexScheduleTask，放入 ObBuildIndexScheduler 的 ObDDLTaskExecutor 中执行。这个 executor 有 4 个线程，队列长度受限于内存，任务队列的内存上限为 1GB。
那这个监测任务是如何产生的呢？在一台 obs 的核心服务 partition_service 启动时，会启动子服务 ObBuildIndexScheduler，ObBuildIndexScheduler 中有个定时任务 ObCheckTenantSchemaTask，不断生成各租户的 ObTenantDDLCheckSchemaTask，也放到 ObBuildIndexScheduler 的 ObDDLTaskExecutor 中执行，详见 ObCheckTenantSchemaTask::runTimerTask。
5.2 局部索引构建
代码路径：
局部索引构建的整体流程跟全局索引类似，也是先等事务结束，拿到快照点，然后选择一个副本做单副本构建，等单副本构建完成后，拷贝基线数据到其他副本，然后（对唯一索引）做唯一性检查，之后索引生效。其中基线数据的构建通过 ObBuildIndexDag 完成，唯一性的检查通过 ObUniqueCheckingDag 完成。
如果大家有任何疑问，欢迎留言讨论：
测试遇到问题?
技术顾问的免费一对一咨询服务？
快加入 OB 创计划→
https://open.oceanbase.com/articles/8000125?sou0c001
钉钉群：33254054
往期推荐:
新成就！OceanBase 入选 Forrester 首份分布式数据库报告
50强诞生！2021 OceanBase 数据库大赛百所高校争霸！
参与更多技术交流，请至 OceanBase 社区版【问答区】。
版权声明: 本文为 InfoQ 作者【OceanBase 数据库】的原创文章。
原文链接:【http://xie.infoq.cn/article/0cc6e33908684fa365d084963】。文章转载请联系作者。
企业级原生分布式数据库 2020.05.06 加入
github：https://github.com/oceanbase/oceanbase 欢迎大家
评论