OB君：本文是 “OceanBase 2.0 技術解析系列” 的第七篇文章。今天我們來聊聊資料的持續可用，說說2.0的索引實時生效功能。更多精彩歡迎關注OceanBase公衆号持續訂閱本系列内容！
引言
随着業務的快速發展，其對資料庫的資料通路規則是不斷變化的，在資料庫中建立索引來加速業務查詢是很常見的需求。
網際網路的業務規模和發展速度對資料庫的索引建構提出了更高的要求，一方面，在海量的業務規模下，非故障導緻的停機是不可接受的，這意味着索引建構的同時，正常業務的讀寫請求不能被影響；另一方面，業務的快速發展和疊代，對索引建構的效率也有着更高的要求，索引更快速的生效，能加速新業務的開發和疊代過程。
傳統單機關系資料庫經過幾十年的發展，逐漸實作了索引實時生效功能，這些資料庫主要解決的問題是在索引建構的時候，避免長時間的鎖表影響正常的業務請求。而分布式資料庫由于其分布式的特性，在實作索引實時生效時，面臨和單機資料庫不同的問題.
OceanBase 1.x中通過把索引建構放在合并流程中避免了這些問題，但并沒有做到索引實時生效，從使用者執行建立索引表語句到索引表生效需要經過一或兩次合并，OceanBase 2.0中解決了其中的問題，索引建構不再與合并耦合，使用者執行建立索引後，能立即進入索引建構流程，較大地縮短了索引建構生效時間。
本文首先介紹了關系型資料庫索引建構的發展現狀，接着描述了OceanBase 1.x中索引建構遇到的問題，最後分析了OceanBase 2.0的索引建構設計，并給出了解決這些問題的方法。
索引建構的現狀
根據架構不同，關系型資料庫分為單機資料庫和分布式資料庫。不同的架構下，索引建構的方案有所不同，本節将分别介紹業界單機資料庫和分布式資料庫的索引建構方案。
單機資料庫
我們以MySQL為例，來描述單機資料庫的索引建構方案。MySQL從5.6開始支援索引實時生效，首先，執行完建立索引語句之後，新事務中新索引表的資料會寫入到Row Log中，與此同時，會等待未往索引表中寫入過資料的事務都結束。當所有的事務都結束後，開始索引建構流程，主要是處理兩部分資料，一部分是等事務結束之後的主表快照點資料，此部分資料在索引表中是不存在的，需要通過主表資料建構出來，另一部分資料是記錄在Row Log中的資料，需要應用到最終的索引表中。建構完成之後，将索引設定成可讀寫狀态，進而優化器能使用該索引來優化使用者的查詢。
MySQL索引建構的特點如下：
是為In Place Update的存儲引擎設計的，為了避免索引建構和使用者事務對索引表更新的并發問題，索引建構過程中的更新資料會記錄到Row Log的特殊存儲中，這部分資料需要重新寫入到索引表中，寫入的時候會有一定的加鎖時間；
基于快照點的建構流程是串行的，面對大資料量場景下性能可能存在不足；
中繼資料隻有單版本，在更新相關中繼資料時，會加鎖。
分布式資料庫
和單機資料庫不同的是，分布式資料庫的資料分布和請求執行可能是分布在多台機器上的，導緻索引建構方案也有所不同。本節将介紹Google研發的分布式資料庫F1的索引建構方案。
如上圖，Google F1采用的是存儲計算分離的架構，架構上總共分為三層，最底層是分布式Key-Value存儲引擎，第二層是無狀态的計算層F1 Server，第三層為代理層，應用程式通過代理層和F1互動。
在此種架構下，事務執行時，有可能出現不同的SQL語句在不同的F1 Server執行的情況，那麼不同的語句可能使用了不同版本的關系型中繼資料（為了設計和實作簡單，F1隻允許系統中同時出現兩種不同版本的中繼資料），這會導緻如下問題。
假設中繼資料版本S1 < S2，且S2比S1多了一張索引表，有如下執行過程。
在S2版本的F1 Server上執行INSERT語句，由于S2版本包括索引表，是以會生成索引表相關的KV記錄；
在S1版本的F1 Server上執行DELETE語句，且和1中INSERT語句使用相同的主鍵，由于S1版本不包括索引表，是以索引表相關的KV記錄不會被删除。
當上述事務執行完成後，索引表将會有多餘的中間資料，導緻資料表和索引表的資料不一緻。
F1為了解決這個問題，引入了中間狀态和最終狀态，其中中間狀态包括，delete-only和write-only，delete-only表示索引表隻能被delete和update，而write-only表示索引表隻能被insert、delete和update。最終狀态包括absent和public，分别表示索引表不存在和索引表生效。在上述出問題的場景中，添加索引表的變更經過了absent->write-only->public的過程，由于absent狀态時，索引表不存在，導緻無法删除索引表的資料，是以，F1将添加索引的流程變成了absent->delete-only->write-only->public，這樣就能保證索引建構完成後，資料和主表保持一緻。
總體來看，Google F1的索引建構方案有如下特點：
F1 Server中最多存在兩個不同版本的中繼資料，這意味着如果有機器在一個中繼資料更新租約時間内沒有重新整理到新版本中繼資料，那麼F1 Server必須要自動退出以保證這個限制，使得這種方案比較适用于計算存儲分離的架構，另外，為了避免F1 Server頻繁因網絡抖動主動退出，中繼資料更新租約時間一般是分鐘級别，是以，對于資料量較小的表格建構索引，也需要分鐘級别才能生效。
OceanBase 索引建構方案
本節先簡單介紹下OceanBase的整體架構、存儲引擎特點以及索引表的寫入流程，接着讨論OceanBase 1.x索引建構中碰到的問題，最後描述了OceanBase 2.0中的索引建構方案。
整體架構
OceanBase的一個叢集通常由多個zone組成，一個zone由一個或多個ObServer組成的，每個ObServer都具有計算和存儲的功能。在ObServer中有一個較為特殊，負責總控服務的節點稱為RootService，負責管理叢集的中繼資料和路由資訊，其中，中繼資料是按照多版本方式管理的。OceanBase按照分區的方式管理資料，一張表包含一個或多個分區，每個分區的資料會存儲在多個zone中，每個zone都是一份完整的資料拷貝（副本）。每個分區的副本中會有一個Leader副本，負責處理該分區的讀寫請求。
存儲引擎
OceanBase的存儲引擎是按照Log Structured Merge Tree（LSM Tree）方式組織的，分為基線資料和增量資料兩部分。基線資料存儲在基線SSTable中，增量資料存儲在Memtable和轉儲SSTable中。基線SSTable按照版本遞增的方式來管理，某個版本的基線SSTable一旦生成後就變成隻讀狀态，修改的資料會存儲在Memtable中，當達到一定記憶體門檻值後會先進行minor compaction（轉儲）轉換成轉儲SSTable，當轉儲SSTable達到一定數量時，會将基線SSTable和轉儲SSTable做major compaction（合并），生成更高版本的基線SSTable。
在SSTable和Memtable中資料都是按照表的主鍵排序的，例如，有一張資料表test，包含列c1、c2、c3、c4和c5，其中主鍵為c1，那麼test的資料是按照列c1的升序方式存儲的；如果在資料表test上建立一個索引index，假設包含列c3和c2，那麼index是按照主鍵c3、c2和c1的升序方式存儲的，其中存儲c1列是為了友善回表查詢。
索引表的寫入流程
在介紹索引表寫入流程之前，先來看看OceanBase索引表的分區管理方式。OceanBase中索引表分為局部索引和全局索引。
局部索引是指分區規則和主表相同的索引，由于分區規則相同，局部索引和主表共用相應的分區，是以，局部索引分區和主表是在同一台機器上的。
全局索引是指分區規則和主表不同的索引，分區規則的不同導緻了全局索引和主表無法共用分區，而分區是OceanBase管理的基本機關，分區不同意味着全局索引和主表的分區是可能不在同一台機器上的。
索引表的寫入通常是由主表驅動的，對主表的寫入操作一般分為INSERT、DELETE和UPDATE，以上面的test主表和index索引表為例，對于INSERT，假如對test主表執行INSERT INTO test values(a,b,c,d,e)，會根據索引表的列生成索引行(c,b,a)，寫入到索引表中；對于DELETE，假如對test主表執行DELETE FROM test where c1 = 'a'，會通過主表中的資料，擷取索引列c3和c2，假設值為c和b，拼成完整的索引行(c,b,a)并删除索引表中對應的行；對于UPDATE，假如對test主表執行UPDATE SET c3 = c' where c1 = 'a'，首先會先擷取主表中的資料，擷取索引列c3和c2的資料，假設值為c和b，拼成完整的行(c,b,a)并删除索引表中對應的行，然後生成新的行(c',b,a)并寫入索引表。對于唯一索引，更新時會檢查寫入的資料是否滿足唯一性限制，具體地，需要檢查索引表已有的資料中是否存在将要寫入的行，如果存在，則會報唯一性沖突。
OceanBase 1.x 索引建構面臨的問題
在OceanBase 1.x中，使用者執行建立索引語句後，會等到叢集下次合并時開始建構，建構過程中先等待主表合并到新版本後，再基于主表的最新版本的基線SSTable資料，建構出索引表的資料。OceanBase 1.x索引建構有如下問題：
OceanBase 1.x缺少指定快照點讀取資料的功能，索引建構依賴合并的快照點；
OceanBase 1.x中隻有局部索引，能通過同台機器的主表資料建構索引表的資料，而OceanBase 2.0中新增了全局索引，建構過程變成了分布式排序，如何以較小代價實作分布式排序呢？
OceanBase 1.x中主表和索引表SSTable版本号是統一管理的，兩者的版本号需要統一推進，而如果索引實時建構的話，可能在索引建構的同時，主表資料已經更新了多個版本，OceanBase 1.x的SSTable版本管理方法無法滿足該需求。
OceanBase 2.0 索引建構方案
本節通過描述整個索引建構的流程，來介紹索引建構的方案設計以及如何解決相關問題的。總體上，OceanBase 2.0中，索引建構分為準備、建構、拷貝和收尾共四個階段。
準備階段
在索引建構準備階段主要做了兩件事情：
生成索引表的中繼資料資訊，其中索引表設定成隻寫狀态，根據LSM Tree存儲引擎的特點，索引表建構期間的資料直接寫入到索引表的Memtable中，帶來的好處是這部分資料直接成為索引表的一部分，後面無須再将這部分資料插入到索引表中，并且可以複用前面小節描述的索引表寫入流程的代碼；
等待之前未往索引表插入過資料的事務結束，當所有的事務都結束後，擷取建構快照點，建構階段将基于此快照點掃描主表資料，并寫入到索引表基線SSTable中，而使用者事務産生的資料寫入到Memtable中，這樣就無須處理索引表建構和使用者事務同時對索引表寫入導緻的并發更新問題。
步驟1中涉及到中繼資料的變更，OceanBase中采用多版本方式管理中繼資料，為了避免分布式環境下不同ObServer中繼資料版本不同帶來的問題，采用如下方案解決。
ObProxy将同一個事務的請求發送給同一個中控ObServer處理，這樣可以保證事務的不同語句在中控ObServer看到的中繼資料版本是遞增的，進而避免語句級别的中繼資料版本回退導緻資料不一緻的問題；
同一條語句可能會涉及到多個ObServer，可能會出現多個ObServer的中繼資料版本不同的情況，如果出現和中控ObServer的中繼資料版本不一緻時，則進行語句重試。
準備階段最重要的輸出為快照點，在傳統單機資料庫中，擷取快照點比較容易的，一般擷取系統目前時間戳即可，但在分布式資料庫中，由于每台機器的時間戳不可能是完全一緻的，是以，不能簡單的擷取某個機器的時間戳作為快照點。OceanBase 2.0中實作了租戶級全局時間戳，每個租戶提供一個授時服務，每個租戶的事務版本号都通過授時服務來獲得，同樣，索引建構準備階段的快照點也通過授時服務來獲得。
建構階段
建構階段的目标是基于主表快照點掃描出索引表所需資料，并按照索引列排序規則生成索引表基線SSTable資料。
在OceanBase 1.x中，Memtable轉換成轉儲SSTable時，多版本的資料會被歸并成單版本的，是以，資料一旦發生轉儲，且快照點落在轉儲SSTable範圍内，則無法讀取快照點資料。為了能夠基于某個快照點掃描主表的資料，OceanBase 2.0中，Memtable轉成轉儲SSTable時，會把Memtable中所有資料及其版本号都記錄下來，進而掃描資料時，能根據快照點和資料的版本号，讀取到所需版本的資料。
排序根據索引類型不同，執行過程也不相同，對于局部索引，索引表分區和主表相同，是以，建構階段的資料流動僅僅是在本機，而對于全局索引，索引表分區和主表不同，一個索引表分區的資料通常來自主表的多個分區，而這些分區可能是在不同ObServer上的，是一個分布式排序過程，整個建構過程描述成了一個SQL的plan。
和面向OLTP的分布式執行不同，索引建構的分布式排序更關注容災，在機器故障等情況下，能以較小的代價快速恢複，OceanBase 2.0的SQL執行架構中支援建構過程的中間結果持久化，建構過程出現機器當機時，隻需要選擇其他機器重新執行故障機器相關的任務。同時，為了加速建構過程，将資料掃描和排序都做了并行化，充分利用磁盤和CPU的并行能力。
建構階段可能會遇到合并，此時主表的基線SSTable的版本會增加，在索引表建構好之後，其版本号是落後于主表的。為了能描述這種場景，我們對基線SSTable管理功能做了重構，每個SSTable單獨管理版本号，能夠保證索引建構時，即使索引表落後主表多個版本，也能建構成功。
在生産環境，主表資料量通常比較大，索引建構往往是比較耗時的操作，為了避免索引建構對正常使用者請求産生影響，OceanBase 2.0中會基于使用者IO請求來限速，當使用者請求的IO響應時間超過一定門檻值時，會自動限制建構過程中IOPS。
拷貝階段
鑒于索引建構比較耗時，OceanBase 2.0中隻在單副本上建構索引表，其他副本從建構好的副本拷貝資料。在單副本建構期間寫入索引表的資料會通過一緻性算法同步到索引表多個副本上，是以，拷貝階段僅僅需要将建構好的基線SSTable拷貝到其他的副本上。和建構一樣，我們對拷貝過程也做了并行化，每個分區會按照資料量切分成多個任務，由多個線程批量地執行任務。為了避免并行拷貝過度的消耗資源，會對拷貝階段整體網絡帶寬作限制，同時也提供了拷貝的并行度控制，友善運維。
收尾階段
收尾階段分為兩步，分别是資料校驗和索引生效。資料校驗根據索引類型的不同，會做不同的操作，對于普通索引，會根據建構階段計算的主表的列校驗和索引表的列校驗和進行比對，保證建構出來的索引表的資料和主表的資料是一緻的；對于唯一索引，因為建構過程中也有可能寫入資料，而建構過程中索引表的基線資料還未建構完成，唯一性校驗可能不完整，是以，需要在索引表基線資料建構和拷貝完成後，對唯一索引做唯一性校驗，同時為了保證索引建構的資料正确性，我們采用将主表和索引表資料進行校驗，既驗證了資料正确性，也驗證了索引是否滿足唯一性。
當資料校驗通過時，将索引表設定成可讀寫狀态，進而SQL優化器能使用新的索引來加速查詢，當資料校驗不通過時（一般是唯一索引唯一性限制不滿足），會将索引設定成不可用狀态。
總結
OceanBase的索引實時生效包括兩層含義，第一是索引建構過程從合并中解耦，使用者觸發後能立即進行建構流程，第二是通過專門為LSM Tree存儲引擎優化的建構流程，建構流程的并行化，單副本建構，副本拷貝的并行化，以及容災時快速恢複等技術手段，有效地加快了索引生效的速度。
OceanBase的索引建構時能對占用的資源做控制，減少對正常使用者請求的影響。通過完備的資料校驗，保證了建構完成的索引表的資料正确性。另外，目前的索引建構方案對計算存儲一體化以及計算存儲分離的架構都是适用的。
參考文獻
- Innodb Online DDL Operations
- Online, Asynchronous Schema Change in F1