天天看點
傳回

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 回包前做了一些同步處理，本節我們先看下這部分的具體流程。調用路徑：

ObRootService::create_index -> ObIndexBuilder::create_index -> ObIndexBuilder::create_index::do_create_index -> ObIndexBuilder::do_create_local_index

上述的調用過程會做一些防禦性的檢查，例如系統表、資源回收筒中的表，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::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。

3.3 生成局部索引的控制任務 關鍵函數的調用路徑：

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。

4. 全局索引的建構流程

全局索引的控制任務 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

4.1 單副本建構

單副本建構是指在一個副本上完成索引表基線資料的補全，根據 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 校驗來檢查主表和索引表資料的一緻性。

4.2 基線補全

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

多副本拷貝是把單副本建構流程中建構好的基線資料拷貝到其他副本的過程，實際資料拷貝是通過 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 唯一性校驗

對于唯一索引，需要校驗索引列資料的唯一性，非唯一索引不需要執行該校驗。代碼路徑：

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執行校驗和的比對。

4.5 索引狀态變更

如果上述步驟全部成功完成，則通過 ObGlobalIndexBuilder::try_handle_index_build_take_effect 函數使索引生效，實際是修改索引表的 schema 狀态為 INDEX_STATUS_AVAILABLE，中控 obs 看到該狀态後，向用戶端 session 傳回成功。

如果上述任一步驟失敗，則通過函數将索引表狀态改為 INDEX_STATUS_INDEX_ERROR，中控 obs 看到該狀态後，向用戶端 session 傳回索引建構失敗。

4.6 中間結果清理索引建構結束後，無論結果是成功或是失敗，都要執行中間狀态清理，包括清理 sql 執行的中間結果，釋放快照，清理内部表等。代碼路徑：

ObGlobalIndexBuilder::try_handle_index_build_finish -> clear_intermediate_result -> ObIndexSSTableBuilder::clear_interm_result
                                                                                 -> release_snapshot

5. 局部索引的建構流程

局部索引的 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

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。

那這個監測任務是如何産生的呢？在一台 obs 的核心服務 partition_service 啟動時，會啟動子服務 ObBuildIndexScheduler，ObBuildIndexScheduler中有個定時任務 ObCheckTenantSchemaTask，不斷生成各租戶的 ObTenantDDLCheckSchemaTask，也放到 ObBuildIndexScheduler 的 ObDDLTaskExecutor 中執行，詳見 ObCheckTenantSchemaTask::runTimerTask。

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

局部索引建構的整體流程跟全局索引類似，也是先等事務結束，拿到快照點，然後選擇一個副本做單副本建構，等單副本建構完成後，拷貝基線資料到其他副本，然後（對唯一索引）做唯一性檢查，之後索引生效。其中基線資料的建構通過ObBuildIndexDag 完成，唯一性的檢查通過 ObUniqueCheckingDag 完成。

sql 存儲 java 排程 資料庫 索引 OceanBase java資料存儲 java存儲資料 java雲存儲 java項目oss存儲 java代碼存儲資料
上一篇: NodeJs 後端開發 04 使用axios調用第三方服務API
下一篇: Oracle RMAN删除歸檔日志腳本

繼續閱讀