作者简介：文渠，OceanBase 内核存储研发工程师
作者简介：海芊，一个致力于当网红的 OceanBase 文档工程师。个人频道：Amber loves OB
OceanBase 索引构建过程涉及的模块较多，通常不太容易理解，而且由于历史原因，当前的开源版本中存在了两套索引构建流程（全局索引和局部索引）。
本文会尝试从代码导读的角度简要介绍 OceanBase（下文简称ob）的索引构建流程，带领大家读懂索引构建的相关代码。
什么是索引
首先请思考，在一个一般的数据库中，索引表的语义是什么？
索引表，其实是在主表（也称数据表）之外，再创建一份冗余且有序的数据，用于加速某些查询流程。为什么索引表可以加速查询，是因为索引表是按照索引键排序的，如果某个查询语句的查询条件中指定了索引前缀，那么通过二分查找即可快速找到对应的行。索引表的行中包括了主键信息，所以可以通过主键快速找到主表的完整行，这个过程也叫索引回表。
知道了索引表的语义，那创建索引要做哪些事呢？
其实索引表也跟主表一样，有自己的schema、内存结构和持久化的数据（通常存放于本地磁盘上）。在分布式场景下，还可能有自己的位置信息。那创建索引也就是要创建索引表的schema，然后在某个位置创建索引表的内存结构，创建索引表的持久化数据。
在创建索引的过程中，我们不希望影响主表的正常读写，即建索引过程中业务是在线（online）的。为了做到在线建索引，不同厂商对在线的有不同的实现机制，本文会介绍OceanBase是如何实现在线建索引的，对其他方案感兴趣的同学可以自行参考相关文档。
索引创建过程总览
用户视角
我们先从用户的视角看一下索引构建的过程是怎样的。例如：用户在一个session上发送了建索引的语句create index i1 on t1(c2)，然后用户就在当前session上不断等待，直到索引构建成功或者失败。
中控observer的视角
那在observer的视角，这其中包含哪些流程呢？首先这条语句的文本被随机发送到一个observer（observer下文简称obs），收到这条语句的obs叫做中控obs。跟其他语句一样，这条建索引的sql语句首先经过parser和resolver，发现这是一条ddl语句，并且将这条语句解析成了ObCreateIndexArg这样一个结构体。对于ddl语句，ob是发送到rootservice（rootservice下文简称rs）来处理，所以中控obs向rs发送一个建索引的rpc请求，这个rpc请求中携带了ObCreateIndexArg。rs收到该请求后，通过 ObRootService::create_index 函数来处理这个请求，这个接口做完必要的同步处理后，就向中控obs发送rpc的回包，但注意，此时索引构建还未完成，实际rs会通过异步任务来真正推进索引构建。中控obs收到rs的回包后，会不断查询索引表的schema状态来获取建索引的结果，如果构建成功，则向客户端返回构建成功，如果构建失败，则向客户端返回失败的错误码。
RS的同步处理流程
上文说到rs在向中控obs回包前做了一些同步处理，本节我们先看下这部分的具体流程。调用路径：
ObRootService::create_index -> ObIndexBuilder::create_index -> ObIndexBuilder::create_index::do_create_index -> ObIndexBuilder::do_create_local_index
-> ObIndexBuilder::do_create_global_index
上述的调用过程会做一些防御性的检查，例如系统表、回收站中的表，ob是不支持建索引的，如果一个表的索引数量超过上限，也是不允许建索引的。通过检查后，根据索引类型选择走local还是global的构建索引流程。
global和local的概念
全局（global）索引和局部（local）索引的区别是什么？其实最主要的区别是局部索引是分区级的，即索引表的分区一一对应主表的分区，全局索引是表级的，即全局索引表的分区与主表的分区没有对应关系。换句话说，local指的是分区级的local，global指的是表级的global。例如，t1表有两个hash分区，如果建局部索引i1，则i1一定有两个分区，并且i1的第一个分区是对t1的第一个分区的索引，i1的第二个分区是对t1的第二个分区的索引。如果对t1建全局索引i2，则i2可以有一个分区，也可以有多个分区，且分区不与主表一一对应。因为局部索引跟主表的分区是一一对应的，所以在ob中，我们将局部索引的分区与主表的分区紧密绑定在一起，这样主表分区和索引表分区的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的基础信息，表级信息主要继承自主表（问6），索引表主要考虑列信息，正常索引只要带索引列和主键列，重复的主键列省掉。唯一索引需要带索引列，隐藏主键列和主键列。什么是隐藏主键，隐藏主键是为了解索引列值为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
单副本构建
单副本构建是指在一个副本上完成索引表基线数据的补全，根据ob的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的行为其实是ob实现在线建索引的关键。基于该快照点构建基线数据（存量数据）后，又因为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住该快照点（问7），注意，如果这里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更改基线补全的任务状态。（问8）
上述代码路径看似复杂，其实最终是通过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
多副本拷贝
代码路径：
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
多副本拷贝是把单副本构建流程中构建好的基线数据拷贝到其他副本的过程（问9），实际数据拷贝是通过ObCopySSTableTask完成的，该任务被rs的ObRebalanceTaskMgr调度执行，入口在ObCopySSTableTask::execute，实际上是发送copy_sstable_batch的rpc，收到该rpc的obs的执行入口是ObService::copy_sstable_batch。完成基线数据拷贝任务后，obs向rs汇报结果，rs执行回调ObGlobalIndexBuilder::on_copy_multi_replica_reply更新多副本拷贝任务的状态。
唯一性校验
对于唯一索引，需要校验索引列数据的唯一性，非唯一索引不需要执行该校验。代码路径：
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。
拿到快照点后，发送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执行校验和的比对。
索引状态变更
如果上述步骤全部成功完成，则通过ObGlobalIndexBuilder::try_handle_index_build_take_effect函数使索引生效，实际是修改索引表的schema状态为INDEX_STATUS_AVAILABLE，中控obs看到该状态后，向客户端session返回成功。
如果上述任一步骤失败，则通过函数将索引表状态改为INDEX_STATUS_INDEX_ERROR，中控obs看到该状态后，向客户端session返回索引构建失败。
中间结果清理
索引构建结束后，无论结果是成功或是失败，都要执行中间状态清理，包括清理sql执行的中间结果，释放快照，清理内部表等。代码路径：
ObGlobalIndexBuilder::try_handle_index_build_finish -> clear_intermediate_result -> ObIndexSSTableBuilder::clear_interm_result
-> release_snapshot
局部索引的构建流程
局部索引的rs端控制流程比较简单，这是因为rs端不是主要战场。代码路径：
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
任务触发
因为局部索引的分区与主表的分区一一绑定，所以局部索引构建流程的主战场就在主表分区所在的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。
那这个监测任务是如何产生的呢？在一台obs的核心服务partition_service启动时，会启动子服务ObBuildIndexScheduler，ObBuildIndexScheduler中有个定时任务ObCheckTenantSchemaTask，不断生成各租户的ObTenantDDLCheckSchemaTask，也放到ObBuildIndexScheduler的ObDDLTaskExecutor中执行，详见ObCheckTenantSchemaTask::runTimerTask。
局部索引构建
代码路径：
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
局部索引构建的整体流程跟全局索引类似，也是先等事务结束，拿到快照点，然后选择一个副本做单副本构建，等单副本构建完成后，拷贝基线数据到其他副本，然后（对唯一索引）做唯一性检查，之后索引生效。其中基线数据的构建通过ObBuildIndexDag完成，唯一性的检查通过ObUniqueCheckingDag完成。
结语
以上就是 OceanBase 实现索引的大概流程，有任何问题欢迎留言讨论。目前 OceanBase 已经开源，感兴趣的小伙伴可以去 GitHub 仓库 研读代码。想体验 OceanBase 索引创建的小伙伴请参考文档 创建索引。
欢迎加入OceanBase，探索数据库的乐趣，一起做最先进的分布式数据库！
最后的最后：
如果大家有任何疑问，可以通过以下方式与我们进行交流：
测试遇到问题?
企业用户想享受技术顾问的免费一对一咨询服务？
快加入 OB 创计划→
https://open.oceanbase.com/articles/8000125?sou0c001
钉钉群：33254054
