本文主要介紹螞蟻金服自主研發的通用關系型資料庫OceanBase，OceanBase采用了分布式架構，其通過技術創新在普通PC伺服器叢集上實作了更好的可靠性、可用性和可擴充行。本文中，螞蟻金服OceanBase團隊資深技術專家潘毅（花名：柏澤）為大家介紹了OceanBase，并分享了SQL優化器，分布式事務的執行邏輯等内容，為大家全面展現OceanBase底層事務引擎的技術創新。
OceanBase的SQL優化器和分布式并行執行
摘要：本文主要介紹螞蟻金服自主研發的通用關系型資料庫OceanBase，OceanBase采用了分布式架構，其通過技術創新在普通PC伺服器叢集上實作了更好的可靠性、可用性和可擴充行。本文中，螞蟻金服OceanBase團隊資深技術專家潘毅（花名：柏澤）為大家介紹了OceanBase，并分享了SQL優化器，分布式事務的執行邏輯等内容，為大家全面展現OceanBase底層事務引擎的技術創新。
一、OceanBase簡介
OceanBase是螞蟻金服自主研發的通用關系型資料庫，其采用了分布式架構，目前支撐了螞蟻金服全部核心鍊路系統。
為什麼要開發OceanBase
資料庫作為基礎軟體，研發耗時較長且投入較大，那麼，螞蟻金服為什麼不能采用現成的方案，如商業資料庫或者開源資料庫呢？曾經，阿裡巴巴擁有亞洲最大的Oracle叢集，但是随着網際網路業務的發展，尤其是近十年的發展非常迅速，阿裡每年的流量呈指數型上升，而且在某些特定日期流量會出現激增，這也是網際網路行業與傳統銀行、電信等行業在資料庫應用方面的不同。傳統行業可以制定未來幾年的規劃，如客戶規模、業務量等，這些在一定程度上都是可預測的。但是網際網路行業則不同，網際網路行業的流量變化非常快，一方面使用商用資料庫很難進行迅速擴充來應對阿裡巴巴飛速增長的規模；另一方面，傳統資料庫的可靠性、高可用性等都需要依靠極其昂貴的硬體來實作，成本将會非常高昂。同時，阿裡巴巴在高峰和平峰流量差别巨大，是以通過硬體實作特殊日期的高流量支援會造成嚴重的資源浪費。綜上所述，現有的商業資料庫并不能很好的支援阿裡巴巴的整個網際網路産業。而采用開源資料庫同樣也會導緻一系列的問題，以MySQL為例，第一點，網際網路産業的業務流量大，且并發高，需要每一個查詢都要在極短的時間内執行，是以對于通用資料庫而言，必須要掌握核心的代碼才能保證穩定的業務需求。第二點，金融行業需要具備強大的分析、查詢能力的資料庫，而MySQL在分析查詢方面的能力比較薄弱，無法滿足業務需求。出于以上原因，螞蟻金服需要開發一款資料庫來滿足自身的業務需求。
二、OceanBase架構
該部分将從叢集拓撲、分區&分布式協定、存儲引擎三個部分介紹OceanBase的架構設計。
1. 叢集拓撲
多副本：一般部署為三個子叢集，每個子叢集由多台機器組成，資料存儲在不同的叢集中。
全對等節點：每個節點的功能對等，各自管理不同的資料分區。
不依賴共享存儲：共享存儲的價格較為昂貴，故采用本機存儲的方式。
2．分區&分布式協定
資料分區：支援資料分區，每一個資料以分區為機關作為管理組，各分區獨立選主，寫日志。
高可用&強一緻：通過PAXOS協定保證資料（日志）同步到多數機器，發生故障時自動切主。
3. 存儲引擎
OceanBase采用的存儲引擎是經典的LSM-Tree架構，資料主要分為兩個部分，分别是是存儲于硬碟的基線資料（SSTable）以及存儲于記憶體的增量資料（MenTable）。在該存儲引擎中，所有資料的增删改操作都會在記憶體中進行，并形成增量資料，每隔一段時間将增量資料和基線資料進行合并，來避免對于SSD的随機寫。因為對于資料庫的操作為全記憶體操作，是以DML操作的效果非常好，但如果某一段時間的資料修改操作非常多，資料量過大，導緻記憶體溢出，在這種情況下OceanBase提供了相應的解決方案，即轉儲操作，轉儲會将資料移動至硬碟上，但不會進行資料的合并操作，在後續合并時，會同時對增量資料，基線資料和轉儲資料一起進行合并。可以看出這個架構會面臨一個很大的挑戰，即在進行增删改的操作後，再進行查詢操作，可能需要對基線資料和增量資料進行融合，是以在該架構下，讀操作可能會受到一定的時間懲罰，這也是SQL優化器需要進行考慮的問題。事實上如果優化器不是基于自身架構和業務需求來進行開發的，可能不會獲得良好的效果，這也是為什麼要自研資料庫的另一個理由。
三、SQL優化器
SQL優化的目标是最小化SQL的執行時間（計劃生成+計劃執行），該部分主要會從OLTP（Online Transaction Processing）和OLAP（Online Analytical Processing）兩個方面進行SQL優化的介紹。對于資料量巨大的查詢來說，計劃執行往往占據大部分的時間，但是對于很多資料量較小的查詢，更多的要考慮計劃生成的優化方案。
1.基于LSM-Tree結構的代價優化器
OceanBase優化器是基于經典的System R模式，主要進行兩個階段的優化。第一階段是生成基于所有關系都是本地的最優計劃，主要考慮的是CPU和IO的代價；第二階段是并行執行優化，考慮的是CPU，IO，Network和Overhead的代價。同時，代價模型也需要考慮LSM-Tree結構的特點，比如進行MemTable和SSTable的資料融合，不同表的代價可能不同，是以代價需要采用動态采樣計算；系統為分布式share nothing系統；索引回表操作會有額外的代價開銷，使用的是邏輯的rowkey而不是實體的rowid，是以回表的時間消耗會增加等，這些都是優化器需要考慮的因素。
2.優化器的基本能力
優化器主要包括兩種類型，分别是邏輯優化器和實體優化器，邏輯優化器主要做查詢改寫等操作的優化，比如基于規則和基于代價的優化，實體優化器主要對連接配接順序，連接配接算法，通路路徑進行優化，同時會考慮到Meta Data，比如統計資訊，表分區資訊。當有了統計資訊和代價模型後，就能估算出模型的執行代價，然後選擇出代價最好的模型進行相應的操作。而計劃管理子產品，對于OLTP的意義更加重要，可以更好的對短查詢進行優化。
3.優化器的統計資訊
OceanBase優化器實作了非常完備的統計資訊，包括表（avg rowlen, # of rows），列（column NDV, null value, histogram， min/max），分區／行級的統計資訊。為了防止引入額外的開銷，統計隻會在資料進行大版本合并的時候進行。存儲引擎對于某些謂詞可以提供較精準的資料量Cardinality估計，比如通過謂詞可以推算出掃描索引的開始和結束區間，在SStable中每個block都有metadata統計行數，在MemTable中可以統計關于insert，delete，update操作的metadata。在OceanBase中，如果資料在合并過程中進行了修改，會導緻資料不夠精準，此時将采用動态采樣的方式來解決該問題。
4.通路路徑
因為OLTP的SQL查詢計劃比較簡單，一般來說往往是單表，單索引的查詢，是以通路路徑對于OLTP非常重要。是以進行SQL查詢時要進行相應的選擇，例如主鍵掃描還是索引掃描，采用單列索引還是多列索引。選擇的标準主要基于規則模型和代價模型，規則模型包括決定性規則（如主鍵全覆寫則采用主鍵掃描進行查詢）和剪枝規則（運用skyline剪枝規則，多個次元比較，選擇更好的索引）。之後再通過代價模型的比較選出最優模型進行查詢。模型主要考慮的因素包括：掃描範圍，是否回表，過濾條件，Interesting order等。
5.計劃緩存
計劃緩存是指在一個計劃生成之後，後續如果出現同一個查詢或者相似的查詢，可以使用現有的計劃而無需重新生成計劃，計劃緩存通過高效的詞法解析器比對輸入的查詢語句，使用參數化查詢優化進行比對。下面為一個計劃查詢的例子。
可以看到，在計劃緩存中對于查詢語句會進行參數的模糊比對，但對于特定含義的參數會加入限定條件，比如order by 3中的參數3代表是第三列，該參數的修改可能會導緻計劃緩存的不适用，是以存儲計劃緩存時加入了限定條件@3 = 3。
6.自适應共享計劃
對于一個查詢語句隻要參數相似就一定能進行計劃緩存的比對嗎？答案是否定的，舉一個例子，在一個查詢語句中對于salesman因為資料量較大，會采用全表掃描的方式進行查詢，而對于president，因為資料量非常少，可能通過索引的方式進行查詢的代價要比全表掃描的代價更好，是以對于這種情況，同樣需要加入相應的限定條件。但重新生成的計劃可能和原有計劃相同，發生這種情況後，便會對于原有的限定條件進行修改，友善之後的查詢語句進行計劃比對，以此來達到自适應計劃共享。
7. Hint/Outline
在OceanBase中如果對于自動化生成的計劃不滿意，也可以通過建立Outline的方式來綁定自定義的計劃，也就是通過Hint來制定計劃的生成，Hint的類型十分豐富，包括：access path, join order, join method, parallel distribution等，下面是Outline綁定的兩個例子。
8.SQL計劃管理及演進
很多使用者特别是企業級使用者對于穩定性的要求非常高，是以OceanBase在進行系統更新，統計資訊更新，硬體更新後會自動進行一個流量的演進，即同時運作新計劃和老計劃，當确定新計劃相較于老計劃無性能回退時，才會逐漸将老計劃替換成新計劃。
9.分區及分區裁剪
OceanBase支援多種分區類型，包括Range，Hash，Key，List。對于二級分區支援Range/Range, Range/Hash, Range/List, Hash/Hash, Hash/Range等。對于靜态或動态分區裁剪支援inlist， 函數表達式，join filter等多種方式。
10.查詢改寫
查詢改寫主要包括基于規則的改寫以及基于代價的改寫，基于規則的改寫主要包括視圖合并，子查詢展開，過濾條件下推， 連接配接條件下推，等價條件推導，外連接配接消除等。基于代價的改寫主要包括OR-expansion，Window function等，查詢改寫對于OLAP的優化效果非常好。下圖為基于代價模型的改寫架構。
四、SQL執行引擎
優化器和執行引擎是相輔相成的，優化器所能優化的計劃取決于執行引擎的執行計劃。
1.并行執行
并行執行的概念就是分治，分治包括垂直分治（比如拆分計劃為子計劃單元）和水準分治（比如GI(Granule Iterator)擷取掃描任務），并行執行主要用于OLAP場景中，解決查詢RT時間的問題，這在很多線上分析的場景下是十分必要的。RT時間對于RDBMS查詢是一個重要名額，傳統的Map-Reduce的執行性能并不能滿足OLAP的性能需求，是以如何找到高效的執行計劃及資料流水線非常關鍵。在OceanBase中采用兩級排程，自适應的子計劃排程架構，各節點獨立的任務切分等方案來進行并行執行。對于資料重分布，OceanBase支援大多數常見的資料分布，包括Hash， Broadcast/Replicate,，Round Robin，Merge Sort等。
2.兩級排程
在OceanBase中通過下面所述的方式形成兩級排程。即将查詢涉及到的各個機器上分别建立一個執行節點（SQC），來讓主要節點（QC）控制SQC，其中QC為機器級的控制，SQC為線程級的控制。QC進行全局排程，依據總并行度配置設定各節點各子計劃并行度， SQC進行本機排程，其中各節點獨立決定水準并行粒度及執行。
3.計劃動态排程
計劃動态排程是指根據使用者指定或系統資源自适應決定在允許的資源使用範圍内，減少中間結果緩存，建構2組或以上計劃子樹的執行流水線(垂直并行)，這種方式可以有效的避免物化，減少物化算子對并行執行所造成的不良影響。該功能正在開發測試中。
4.并行執行計劃
OceanBase中擁有所有主要算子的并行執行方法，包括nested-loop join, merge join, hash join,aggregation, distinct, group by,window function, count, limit等，同時支援豐富的重分布方法和多種候選計劃，例如partition-wise join, partial partitionwise join,broadcast, hash, sort(for distributedorder by)等。
事實上，并行查詢的優化技術在MPP架構下産生了新的問題，比如分區連接配接要求各表的分區從邏輯上和實體上都是一樣的，這也是一個需要考慮和優化的方向。
5.編譯執行
傳統執行方式如類型檢查，多态(虛函數)對于記憶體操作很低效。OceanBase考慮采用LLVM 動态生成執行碼，SQL表達式可以支援動态生成執行碼，存儲過程采用直接編譯執行的方式，來進行性能提升。
整理：楊德宇