支付寶支撐2135億成交額的數(shù)據(jù)庫架構(gòu)原理

OceanBase的SQL優(yōu)化器和分布式并行執(zhí)行
摘要：本文主要介紹螞蟻金服自主研發(fā)的通用關(guān)系型數(shù)據(jù)庫OceanBase，OceanBase采用了分布式架構(gòu)，其通過技術(shù)創(chuàng)新在普通PC服務(wù)器集群上實現(xiàn)了更好的可靠性、可用性和可擴展行。本文中，螞蟻金服OceanBase團隊資深技術(shù)專家潘毅（花名：柏澤）為大家介紹了OceanBase，并分享了SQL優(yōu)化器，分布式事務(wù)的執(zhí)行邏輯等內(nèi)容，為大家全面展現(xiàn)OceanBase底層事務(wù)引擎的技術(shù)創(chuàng)新。

一、OceanBase簡介

OceanBase是螞蟻金服自主研發(fā)的通用關(guān)系型數(shù)據(jù)庫，其采用了分布式架構(gòu)，目前支撐了螞蟻金服全部核心鏈路系統(tǒng)。

為什么要開發(fā)OceanBase
數(shù)據(jù)庫作為基礎(chǔ)軟件，研發(fā)耗時較長且投入較大，那么，螞蟻金服為什么不能采用現(xiàn)成的方案，如商業(yè)數(shù)據(jù)庫或者開源數(shù)據(jù)庫呢？曾經(jīng)，阿里巴巴擁有亞洲最大的Oracle集群，但是隨著互聯(lián)網(wǎng)業(yè)務(wù)的發(fā)展，尤其是近十年的發(fā)展非常迅速，阿里每年的流量呈指數(shù)型上升，而且在某些特定日期流量會出現(xiàn)激增，這也是互聯(lián)網(wǎng)行業(yè)與傳統(tǒng)銀行、電信等行業(yè)在數(shù)據(jù)庫應(yīng)用方面的不同。傳統(tǒng)行業(yè)可以制定未來幾年的規(guī)劃，如客戶規(guī)模、業(yè)務(wù)量等，這些在一定程度上都是可預測的。但是互聯(lián)網(wǎng)行業(yè)則不同，互聯(lián)網(wǎng)行業(yè)的流量變化非?？?，一方面使用商用數(shù)據(jù)庫很難進行迅速擴展來應(yīng)對阿里巴巴飛速增長的規(guī)模；另一方面，傳統(tǒng)數(shù)據(jù)庫的可靠性、高可用性等都需要依靠極其昂貴的硬件來實現(xiàn)，成本將會非常高昂。同時，阿里巴巴在高峰和平峰流量差別巨大，因此通過硬件實現(xiàn)特殊日期的高流量支持會造成嚴重的資源浪費。綜上所述，現(xiàn)有的商業(yè)數(shù)據(jù)庫并不能很好的支持阿里巴巴的整個互聯(lián)網(wǎng)產(chǎn)業(yè)。而采用開源數(shù)據(jù)庫同樣也會導致一系列的問題，以MySQL為例，第一點，互聯(lián)網(wǎng)產(chǎn)業(yè)的業(yè)務(wù)流量大，且并發(fā)高，需要每一個查詢都要在極短的時間內(nèi)執(zhí)行，因此對于通用數(shù)據(jù)庫而言，必須要掌握核心的代碼才能保證穩(wěn)定的業(yè)務(wù)需求。第二點，金融行業(yè)需要具備強大的分析、查詢能力的數(shù)據(jù)庫，而MySQL在分析查詢方面的能力比較薄弱，無法滿足業(yè)務(wù)需求。出于以上原因，螞蟻金服需要開發(fā)一款數(shù)據(jù)庫來滿足自身的業(yè)務(wù)需求。

二、OceanBase架構(gòu)

該部分將從集群拓撲、分區(qū)&分布式協(xié)議、存儲引擎三個部分介紹OceanBase的架構(gòu)設(shè)計。
1. 集群拓撲
多副本：一般部署為三個子集群，每個子集群由多臺機器組成，數(shù)據(jù)存儲在不同的集群中。
全對等節(jié)點：每個節(jié)點的功能對等，各自管理不同的數(shù)據(jù)分區(qū)。
不依賴共享存儲：共享存儲的價格較為昂貴，故采用本機存儲的方式。

2．分區(qū)&分布式協(xié)議
數(shù)據(jù)分區(qū)：支持數(shù)據(jù)分區(qū)，每一個數(shù)據(jù)以分區(qū)為單位作為管理組，各分區(qū)獨立選主，寫日志。
高可用&強一致：通過PAXOS協(xié)議保證數(shù)據(jù)（日志）同步到多數(shù)機器，發(fā)生故障時自動切主。

3. 存儲引擎
OceanBase采用的存儲引擎是經(jīng)典的LSM-Tree架構(gòu)，數(shù)據(jù)主要分為兩個部分，分別是是存儲于硬盤的基線數(shù)據(jù)（SSTable）以及存儲于內(nèi)存的增量數(shù)據(jù)（MenTable）。在該存儲引擎中，所有數(shù)據(jù)的增刪改操作都會在內(nèi)存中進行，并形成增量數(shù)據(jù)，每隔一段時間將增量數(shù)據(jù)和基線數(shù)據(jù)進行合并，來避免對于SSD的隨機寫。因為對于數(shù)據(jù)庫的操作為全內(nèi)存操作，所以DML操作的效果非常好，但如果某一段時間的數(shù)據(jù)修改操作非常多，數(shù)據(jù)量過大，導致內(nèi)存溢出，在這種情況下OceanBase提供了相應(yīng)的解決方案，即轉(zhuǎn)儲操作，轉(zhuǎn)儲會將數(shù)據(jù)移動至硬盤上，但不會進行數(shù)據(jù)的合并操作，在后續(xù)合并時，會同時對增量數(shù)據(jù)，基線數(shù)據(jù)和轉(zhuǎn)儲數(shù)據(jù)一起進行合并?？梢钥闯鲞@個架構(gòu)會面臨一個很大的挑戰(zhàn)，即在進行增刪改的操作后，再進行查詢操作，可能需要對基線數(shù)據(jù)和增量數(shù)據(jù)進行融合，因此在該架構(gòu)下，讀操作可能會受到一定的時間懲罰，這也是SQL優(yōu)化器需要進行考慮的問題。事實上如果優(yōu)化器不是基于自身架構(gòu)和業(yè)務(wù)需求來進行開發(fā)的，可能不會獲得良好的效果，這也是為什么要自研數(shù)據(jù)庫的另一個理由。

三、SQL優(yōu)化器

SQL優(yōu)化的目標是最小化SQL的執(zhí)行時間（計劃生成+計劃執(zhí)行），該部分主要會從OLTP（Online Transaction Processing）和OLAP（Online Analytical Processing）兩個方面進行SQL優(yōu)化的介紹。對于數(shù)據(jù)量巨大的查詢來說，計劃執(zhí)行往往占據(jù)大部分的時間，但是對于很多數(shù)據(jù)量較小的查詢，更多的要考慮計劃生成的優(yōu)化方案。

1.基于LSM-Tree結(jié)構(gòu)的代價優(yōu)化器
OceanBase優(yōu)化器是基于經(jīng)典的System R模式，主要進行兩個階段的優(yōu)化。第一階段是生成基于所有關(guān)系都是本地的最優(yōu)計劃，主要考慮的是CPU和IO的代價；第二階段是并行執(zhí)行優(yōu)化，考慮的是CPU，IO，Network和Overhead的代價。同時，代價模型也需要考慮LSM-Tree結(jié)構(gòu)的特點，比如進行MemTable和SSTable的數(shù)據(jù)融合，不同表的代價可能不同，因此代價需要采用動態(tài)采樣計算；系統(tǒng)為分布式share nothing系統(tǒng)；索引回表操作會有額外的代價開銷，使用的是邏輯的rowkey而不是物理的rowid，因此回表的時間消耗會增加等，這些都是優(yōu)化器需要考慮的因素。

2.優(yōu)化器的基本能力
優(yōu)化器主要包括兩種類型，分別是邏輯優(yōu)化器和物理優(yōu)化器，邏輯優(yōu)化器主要做查詢改寫等操作的優(yōu)化，比如基于規(guī)則和基于代價的優(yōu)化，物理優(yōu)化器主要對連接順序，連接算法，訪問路徑進行優(yōu)化，同時會考慮到Meta Data，比如統(tǒng)計信息，表分區(qū)信息。當有了統(tǒng)計信息和代價模型后，就能估算出模型的執(zhí)行代價，然后選擇出代價最好的模型進行相應(yīng)的操作。而計劃管理模塊，對于OLTP的意義更加重要，可以更好的對短查詢進行優(yōu)化。

3.優(yōu)化器的統(tǒng)計信息
OceanBase優(yōu)化器實現(xiàn)了非常完備的統(tǒng)計信息，包括表（avg rowlen, # of rows），列（column NDV, null value, histogram， min/max），分區(qū)／行級的統(tǒng)計信息。為了防止引入額外的開銷，統(tǒng)計只會在數(shù)據(jù)進行大版本合并的時候進行。存儲引擎對于某些謂詞可以提供較精準的數(shù)據(jù)量Cardinality估計，比如通過謂詞可以推算出掃描索引的開始和結(jié)束區(qū)間，在SStable中每個block都有metadata統(tǒng)計行數(shù)，在MemTable中可以統(tǒng)計關(guān)于insert，delete，update操作的metadata。在OceanBase中，如果數(shù)據(jù)在合并過程中進行了修改，會導致數(shù)據(jù)不夠精準，此時將采用動態(tài)采樣的方式來解決該問題。

4.訪問路徑
因為OLTP的SQL查詢計劃比較簡單，一般來說往往是單表，單索引的查詢，所以訪問路徑對于OLTP非常重要。因此進行SQL查詢時要進行相應(yīng)的選擇，例如主鍵掃描還是索引掃描，采用單列索引還是多列索引。選擇的標準主要基于規(guī)則模型和代價模型，規(guī)則模型包括決定性規(guī)則（如主鍵全覆蓋則采用主鍵掃描進行查詢）和剪枝規(guī)則（運用skyline剪枝規(guī)則，多個維度比較，選擇更好的索引）。之后再通過代價模型的比較選出最優(yōu)模型進行查詢。模型主要考慮的因素包括：掃描范圍，是否回表，過濾條件，Interesting order等。

5.計劃緩存
計劃緩存是指在一個計劃生成之后，后續(xù)如果出現(xiàn)同一個查詢或者相似的查詢，可以使用現(xiàn)有的計劃而無需重新生成計劃，計劃緩存通過高效的詞法解析器匹配輸入的查詢語句，使用參數(shù)化查詢優(yōu)化進行匹配。下面為一個計劃查詢的例子。

可以看到，在計劃緩存中對于查詢語句會進行參數(shù)的模糊匹配，但對于特定含義的參數(shù)會加入限定條件，比如order by 3中的參數(shù)3代表是第三列，該參數(shù)的修改可能會導致計劃緩存的不適用，因此存儲計劃緩存時加入了限定條件@3 = 3。

6.自適應(yīng)共享計劃
對于一個查詢語句只要參數(shù)相似就一定能進行計劃緩存的匹配嗎？答案是否定的，舉一個例子，在一個查詢語句中對于salesman因為數(shù)據(jù)量較大，會采用全表掃描的方式進行查詢，而對于president，因為數(shù)據(jù)量非常少，可能通過索引的方式進行查詢的代價要比全表掃描的代價更好，因此對于這種情況，同樣需要加入相應(yīng)的限定條件。但重新生成的計劃可能和原有計劃相同，發(fā)生這種情況后，便會對于原有的限定條件進行修改，方便之后的查詢語句進行計劃匹配，以此來達到自適應(yīng)計劃共享。

7. Hint/Outline
在OceanBase中如果對于自動化生成的計劃不滿意，也可以通過創(chuàng)建Outline的方式來綁定自定義的計劃，也就是通過Hint來制定計劃的生成，Hint的類型十分豐富，包括：access path, join order, join method, parallel distribution等，下面是Outline綁定的兩個例子。

8.SQL計劃管理及演進
很多用戶特別是企業(yè)級用戶對于穩(wěn)定性的要求非常高，因此OceanBase在進行系統(tǒng)升級，統(tǒng)計信息更新，硬件更新后會自動進行一個流量的演進，即同時運行新計劃和老計劃，當確定新計劃相較于老計劃無性能回退時，才會逐漸將老計劃替換成新計劃。

9.分區(qū)及分區(qū)裁剪
OceanBase支持多種分區(qū)類型，包括Range，Hash，Key，List。對于二級分區(qū)支持Range/Range, Range/Hash, Range/List, Hash/Hash, Hash/Range等。對于靜態(tài)或動態(tài)分區(qū)裁剪支持inlist， 函數(shù)表達式，join filter等多種方式。

10.查詢改寫
查詢改寫主要包括基于規(guī)則的改寫以及基于代價的改寫，基于規(guī)則的改寫主要包括視圖合并，子查詢展開，過濾條件下推， 連接條件下推，等價條件推導，外連接消除等?；诖鷥r的改寫主要包括OR-expansion，Window function等，查詢改寫對于OLAP的優(yōu)化效果非常好。下圖為基于代價模型的改寫框架。

四、SQL執(zhí)行引擎

優(yōu)化器和執(zhí)行引擎是相輔相成的，優(yōu)化器所能優(yōu)化的計劃取決于執(zhí)行引擎的執(zhí)行計劃。
1.并行執(zhí)行
并行執(zhí)行的概念就是分治，分治包括垂直分治（比如拆分計劃為子計劃單元）和水平分治（比如GI(Granule Iterator)獲取掃描任務(wù)），并行執(zhí)行主要用于OLAP場景中，解決查詢RT時間的問題，這在很多在線分析的場景下是十分必要的。RT時間對于RDBMS查詢是一個重要指標，傳統(tǒng)的Map-Reduce的執(zhí)行性能并不能滿足OLAP的性能需求，因此如何找到高效的執(zhí)行計劃及數(shù)據(jù)流水線非常關(guān)鍵。在OceanBase中采用兩級調(diào)度，自適應(yīng)的子計劃調(diào)度框架，各節(jié)點獨立的任務(wù)切分等方案來進行并行執(zhí)行。對于數(shù)據(jù)重分布，OceanBase支持大多數(shù)常見的數(shù)據(jù)分布，包括Hash， Broadcast/Replicate,，Round Robin，Merge Sort等。

2.兩級調(diào)度
在OceanBase中通過下面所述的方式形成兩級調(diào)度。即將查詢涉及到的各個機器上分別創(chuàng)建一個執(zhí)行節(jié)點（SQC），來讓主控節(jié)點（QC）控制SQC，其中QC為機器級的控制，SQC為線程級的控制。QC進行全局調(diào)度，依據(jù)總并行度分配各節(jié)點各子計劃并行度， SQC進行本機調(diào)度，其中各節(jié)點獨立決定水平并行粒度及執(zhí)行。

3.計劃動態(tài)調(diào)度
計劃動態(tài)調(diào)度是指根據(jù)用戶指定或系統(tǒng)資源自適應(yīng)決定在允許的資源使用范圍內(nèi)，減少中間結(jié)果緩存，構(gòu)建2組或以上計劃子樹的執(zhí)行流水線(垂直并行)，這種方式可以有效的避免物化，減少物化算子對并行執(zhí)行所造成的不良影響。該功能正在開發(fā)測試中。

4.并行執(zhí)行計劃
OceanBase中擁有所有主要算子的并行執(zhí)行方法，包括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)等。
事實上，并行查詢的優(yōu)化技術(shù)在MPP架構(gòu)下產(chǎn)生了新的問題，比如分區(qū)連接要求各表的分區(qū)從邏輯上和物理上都是一樣的，這也是一個需要考慮和優(yōu)化的方向。

5.編譯執(zhí)行
傳統(tǒng)執(zhí)行方式如類型檢查，多態(tài)(虛函數(shù))對于內(nèi)存操作很低效。OceanBase考慮采用LLVM 動態(tài)生成執(zhí)行碼，SQL表達式可以支持動態(tài)生成執(zhí)行碼，存儲過程采用直接編譯執(zhí)行的方式，來進行性能提升。

整理：楊德宇