OceanBase 源码解读（七）：一文读懂数据库索引实现原理
此前，带你读源码第六篇《戳这里回顾：OceanBase 源码解读（六）：存储引擎详解》为大家详细讲解了 OceanBase 存储引擎，并为大家回答了关于 OceanBase 数据库的相关提问。
本期“源码解读”将尝试从代码导读的角度，简要介绍 OceanBase 的索引构建流程，带领大家读懂索引构建的相关代码，必须速速收藏！
首先请思考，在一个一般的数据库中，索引表的语义是什么？
索引表，其实是在主表（也称数据表）之外，再创建一份冗余且有序的数据，用于加速某些查询流程。为什么索引表可以加速查询，是因为索引表是按照索引键排序的，如果某个查询语句的查询条件中指定了索引前缀，那么通过二分查找即可快速找到对应的行。索引表的行中包括了主键信息，所以可以通过主键快速找到主表的完整行，这个过程也叫索引回表。
知道了索引表的语义，那创建索引要做哪些事呢？
其实索引表也跟主表一样，有自己的 schema、内存结构和持久化的数据（通常存放于本地磁盘上）。在分布式场景下，还可能有自己的位置信息。那创建索引也就是要创建索引表的 schema，然后在某个位置创建索引表的内存结构，创建索引表的持久化数据。
在创建索引的过程中，我们不希望影响主表的正常读写，即建索引过程中业务是在线（online）的。为了做到在线建索引，不同厂商对在线的有不同的实现机制，本文会介绍 OceanBase 是如何实现在线建索引的，对其他方案感兴趣的同学可以自行参考相关文档。
那在 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 状态来获取建索引的结果，如果构建成功，则向客户端返回构建成功，如果构建失败，则向客户端返回失败的错误码。
上文说到 rs 在向中控 obs 回包前做了一些同步处理，本节我们先看下这部分的具体流程。调用路径：
ObRootService::create_index -> ObIndexBuilder::create_index -> ObIndexBuilder::create_index::do_create_index -> ObIndexBuilder::do_create_local_index
-> ObIndexBuilder::do_create_global_index
全局（global）索引和局部（local）索引的区别是什么？其实主要的区别是局部索引是分区级的，即索引表的分区一一对应主表的分区，全局索引是表级的，即全局索引表的分区与主表的分区没有对应关系。
换句话说，local 指的是分区级的 local，global 指的是表级的 global。例如，t1 表有两个 hash 分区，如果建局部索引 i1，则 i1 一定有两个分区，并且 i1 的个分区是对 t1 的个分区的索引，i1 的第二个分区是对 t1 的第二个分区的索引。如果对 t1 建全局索引 i2，则 i2 可以有一个分区，也可以有多个分区，且分区不与主表一一对应。
因为局部索引跟主表的分区是一一对应的，所以在 OceanBase 中，我们将局部索引的分区与主表的分区紧密绑定在一起，这样主表分区和索引表分区的 location 信息是一致的（一定在一台机器上），从而避免跨机的分布式事务。也因此，上述选择索引构建路径时，对全局索引有个优化，如果全局索引的主表和索引表都是非分区表，那这种全局索引可以走局部索引的构建流程。
ObIndexBuilder::do_create_global_index -> ObIndexBuilder::generate_schema
-> ObDDLService::create_global_index -> ObDDLService::generate_global_index_locality_and_primary_zone
-> ObDDLService::create_user_table -> ObDDLService::create_table_in_trans -> ObDDLOperator::create_table
-> ObDDLService::create_table_partitions
-> ObDDLService::publish_schema
-> ObIndexBuilder::submit_build_global_index_task -> ObGlobalIndexBuilder::submit_build_global_index_task
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。
ObIndexBuilder::do_create_local_index -> ObIndexBuilder::generate_schema
-> ObDDLService::create_user_table -> ObDDLService::create_table_in_trans -> ObDDLOperator::create_table
-> ObDDLService::create_table_partitions
-> ObDDLService::publish_schema
-> ObIndexBuilder::submit_build_local_index_task -> ObRSBuildIndexScheduler::push_task
局部索引生成 schema 以及创建内存对象的的逻辑跟全局索引几乎相同，的区别是局部索引不需要生成索引表的位置信息，其他逻辑这里不再赘述。
完成上述索引表的 schema 和内存结构的创建后，通过ObRSBuildIndexScheduler::push_task将局部索引的控制任务ObRSBuildIndexTask放入队列，同时更新内部表__all_index_build_stat。
局部索引的控制任务由ObDDLTaskExecutor负责执行，这个 executor 只有1个线程，队列长度受限于内存（内存上限为1G），任务执行的入口是ObDDLTaskExecutor::run1 -> ObRSBuildIndexTask::process。
全局索引的控制任务 ObGlobalIndexTask 设计了一个简单的状态推进，对每种任务状态，执行相应的函数。整体思路是，先在索引表的一个副本上构建基线数据，然后将基线数据拷贝到其他副本，再执行必要的一致性和性检查，后让索引生效。
代码路径：
process_function task_status
----------------------------------------------------------------------------
ObGlobalIndexBuilder::try_drive -> try_build_single_replica GIBS_BUILD_SINGLE_REPLICA
-> try_copy_multi_replica GIBS_MULTI_REPLICA_COPY
-> try_unique_index_calc_checksum GIBS_UNIQUE_INDEX_CALC_CHECKSUM
-> try_unique_index_check GIBS_UNIQUE_INDEX_CHECK
-> try_handle_index_build_take_effect GIBS_INDEX_BUILD_TAKE_EFFECT
-> try_handle_index_build_failed GIBS_INDEX_BUILD_FAILED
-> try_handle_index_build_finish GIBS_INDEX_BUILD_FINISH
单副本构建是指在一个副本上完成索引表基线数据的补全，根据 OceanBase 的 lsm-tree 的结构，这里的基线数据是指建索引表的 major sstable。
代码路径：
ObGlobalIndexBuilder::try_build_single_replica -> launch_new_build_single_replica -> get_global_index_build_snapshot -> do_get_associated_snapshot
-> hold_snapshot
-> update_task_global_index_build_snapshot
-> do_build_single_replica -> ObRootService::submit_index_sstable_build_task
-> drive_this_build_single_replica -> ObIndexChecksumOperator::check_column_checksum
单副本构建首先要选一个快照点，保证该快照点之后，对主表的 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 校验来检查主表和索引表数据的一致性。
ObIndexSSTableBuildTask 任务由 IdxBuild 线程池负责执行，任务队列4096，线程数16。
看下 ObIndexSSTableBuildTask 的执行过程，代码路径：
ObIndexSSTableBuildTask::process -> ObIndexSSTableBuilder::init
-> ObIndexSSTableBuilder::build -> ObCommonSqlProxy::execute -> ObInnerSQLConnection::execute -> ObInnerSQLConnection::query -> ObInnerSQLConnection::do_query -> ObIndexSSTableBuilder::ObBuildExecutor::execute -> ObIndexSSTableBuilder::build
-> ObIndexSSTableBuilder::ObBuildExecutor::process_result -> ObResultSet::get_next_row
-> ObGlobalIndexBuilder::on_build_single_replica_reply
ObIndexSSTableBuilder::build 函数是同步执行，也就是说，系统中多有16个基线补全的任务同时执行，执行结束后，通过on_build_single_replica_reply更改基线补全的任务状态。
上述代码路径看似复杂，其实终是通过 ObIndexSSTableBuilder::build 构建了一个物理执行计划，通过 ObResultSet::get_next_row 来执行该计划，下面的代码路径给出了物理执行计划的生成过程，PHY 开头的常量是指物理算子的类型。
ObIndexSSTableBuilder::build -> generate_build_param -> split_ranges
-> store_build_param
-> gen_data_scan PHY_TABLE_SCAN_WITH_CHECKSUM
PHY_UK_ROW_TRANSFORM
-> gen_data_exchange PHY_DETERMINATE_TASK_TRANSMIT
PHY_TASK_ORDER_RECEIVE
-> gen_build_macro PHY_SORT
PHY_APPEND_LOCAL_SORT_DATA
-> gen_macro_exchange PHY_DETERMINATE_TASK_TRANSMIT
PHY_TASK_ORDER_RECEIVE
-> gen_build_sstable PHY_APPEND_SSTABLE
-> gen_sstable_exchange PHY_DETERMINATE_TASK_TRANSMIT
PHY_TASK_ORDER_RECEIVE
coordinator | ObTaskOrderReceive
transmit | ObDeterminateTaskTransmit
append_sstable | ObTableAppendSSTable
receive | ObTaskOrderReceive
transmit_macro_block | ObDeterminateTaskTransmit
append_local_sort_data | ObTableAppendLocalSortData
sort | ObSort
receive | ObTaskOrderReceive
transmit_by_range | ObDeterminateTaskTransmit
table_scan_with_checksum | ObTableScanWithChecksum
4.3 多副本拷贝
ObGlobalIndexBuilder::try_copy_multi_replica -> launch_new_copy_multi_replica -> build_task_partition_sstable_stat -> generate_task_partition_sstable_array
-> drive_this_copy_multi_replica -> check_partition_copy_replica_stat
-> build_replica_sstable_copy_task -> ObCopySSTableTask::build
-> ObRebalanceTaskMgr::add_task
4.4 性校验
对于索引，需要校验索引列数据的性，非索引不需要执行该校验。代码路径：
ObGlobalIndexBuilder::try_unique_index_calc_checksum -> launch_new_unique_index_calc_checksum -> get_checksum_calculation_snapshot -> do_get_associated_snapshot
-> do_checksum_calculation -> build_task_partition_col_checksum_stat
-> send_checksum_calculation_request -> send_col_checksum_calc_rpc
-> drive_this_unique_index_calc_checksum
为了校验性，需要选一个快照点，在此快照点之后，对主表的 dml 操作（增量数据）都可以看到该索引表的基线，因此可以在 dml 过程中校验性，在此快照点之前的数据（存量数据），计算该快照点的主表和索引表列 checksum，通过 checksum 比对，校验其性。该快照点，需要所有副本的新事务都可以看到基线数据，假设各副本看到基线数据的时间戳的大值是 sstable_ts，则需要等待所有事务的事务上下文创建时间戳推过 sstable_ts。get_checksum_calculation_snapshot 函数完成上述操作，检查事务上下文创建时间戳是否推过 sstable_ts 的函数入口是 ObPartitionService::check_ctx_create_timestamp_elapsed。
如果上述步骤全部成功完成，则通过 ObGlobalIndexBuilder::try_handle_index_build_take_effect 函数使索引生效，实际是修改索引表的 schema 状态为 INDEX_STATUS_AVAILABLE，中控 obs 看到该状态后，向客户端 session 返回成功。
如果上述任一步骤失败，则通过函数将索引表状态改为 INDEX_STATUS_INDEX_ERROR，中控 obs 看到该状态后，向客户端 session 返回索引构建失败。
ObGlobalIndexBuilder::try_handle_index_build_finish -> clear_intermediate_result -> ObIndexSSTableBuilder::clear_interm_result
-> release_snapshot
ObRSBuildIndexTask::process -> wait_trans_end -> ObIndexWaitTransStatus::get_wait_trans_status
-> calc_snapshot_version
-> acquire_snapshot
-> wait_build_index_end -> report_index_status
-> report_index_status
-> release_snapshot
5.1 任务触发
因为局部索引的分区与主表的分区一一绑定，所以局部索引构建流程的主战场就在主表分区所在的 obs 上。obs 通过监测每个租户的 ddl 变更，来触发构建局部索引的任务：在索引表的 schema 发布后，主表所在的 obs 会刷新到该 schema，然后发起局部索引构建任务。
代码路径：
ObTenantDDLCheckSchemaTask::process -> process_schedule_build_index_task -> get_candidate_tables
-> find_build_index_partitions
-> generate_schedule_index_task -> ObBuildIndexScheduler::push_task(ObBuildIndexScheduleTask)
ObTenantDDLCheckSchemaTask 会找到要构建索引的 partition_key ，然后生成一个 ObBuildIndexScheduleTask，放入 ObBuildIndexScheduler 的ObDDLTaskExecutor 中执行。这个 executor 有4个线程，队列长度受限于内存，任务队列的内存上限为1GB。
5.2 局部索引构建
ObBuildIndexScheduleTask::process -> check_partition_need_build_index
-> wait_trans_end -> check_trans_end -> ObPartitionService::check_schema_version_elapsed
-> report_trans_status
-> wait_snapshot_ready -> get_snapshot_version
-> check_rs_snapshot_elapsed -> ObTsMgr::wait_gts_elapse
-> ObPartitionService::check_ctx_create_timestamp_elapsed
-> choose_build_index_replica -> get_candidate_source_replica
-> check_need_choose_replica
-> ObIndexTaskTableOperator::generate_new_build_index_record
-> wait_choose_or_build_index_end -> get_candidate_source_replica
-> check_need_schedule_dag
-> schedule_dag -> ObPartitionStorage::get_build_index_param
-> ObPartitionStorage::get_build_index_context
-> ObBuildIndexDag::init
-> alloc_index_prepare_task -> ObIndexPrepareTask::init
-> ObIDag::add_task
-> ObDagScheduler::add_dag
-> copy_build_index_data -> send_copy_replica_rpc
-> ObPartitionService::check_single_replica_major_sstable_exist
-> unique_index_checking -> ObUniqueCheckingDag::init
-> ObUniqueCheckingDag::alloc_local_index_task_callback
-> ObUniqueCheckingDag::alloc_unique_checking_prepare_task -> ObUniqueCheckingPrepareTask::init
-> ObIDag::add_task
-> ObDagScheduler::add_dag
-> wait_report_status -> check_all_replica_report_build_index_end
相关文章