摘要：它主要包括以下幾部分采用對文本進行文法分析，生成語法樹。對語法樹進一步進行分析，類似程序編譯器的語義分析，對語法合格的進一步進行檢查。優(yōu)化器對語法樹應用各種規(guī)則，生成不同的執(zhí)行計劃，形成一個搜索空間。

Trafodion是一個構建在Hadoop/HBase基礎之上的關系型數據庫，它完全開源免費。Trafodion能夠完整地支持ANSI SQL，并且提供ACID事務保證。和傳統(tǒng)關系數據庫不同的地方在于，Trafodion利用底層Hadoop的橫向擴展能力，可以提供極高的擴展性。而傳統(tǒng)數據庫，比如MySQL，在數據量達到P級別的時候就很難處理。而Trafodion卻可以借助HBase的擴展性，僅通過增加普通Linux服務器就可以增加計算和存儲能力，進而支持大數據應用。

比如原來使用MySQL的用戶，如果數據量持續(xù)增加，往往需要采用前后端cache，分庫分表，讀寫分離等技術。但是這些技術帶來的弊端也很多。比如分庫分表的構架下，不同分庫之間無法執(zhí)行join操作。采用這些復雜技術后，系統(tǒng)結構復雜，維護和開發(fā)成本提高。這是很多客戶正在面臨的問題。

而從使用開發(fā)的角度來看，Trafodion和MySQL是完全一樣的，他們同樣是關系型數據庫，基本的功能完全一致。因此一個經典的LAMP網絡應用也可以輕松地用LATP(Linux, Apache, Trafodion, PHP) 搭建。而采用Trafodion，當業(yè)務擴展時，通過增加節(jié)點就可以應付不斷增加的數據量，應用程序無需做任何修改，也無需考慮復雜的分庫分表，讀寫分離等技術。這樣就極大地降低了系統(tǒng)的復雜度。

這只是Trafodion的可能應用之一，Trafodion還是一個非常適合的實時大數據分析平臺。因為它不僅可以支持實時分析，而且能夠支持實時數據寫入，比如每秒上萬條的隨機數據插入。這是構建實時分析所必備的能力。Stinger或者Impala雖然可以提供實時查詢，但去無法支持實時的數據插入。

比如交通實時分析，利用Stinger/Impala等技術，雖然查詢和分析可以在1分鐘內完成，但是數據卻只能定期載入，如果1小時一次，那么分析的數據樣本是1小時前的數據，其分析結果也失去了時效性。比如，用戶已經在那里堵車堵了了1個小時。

關于Trafodion的使用場景讀者可以參閱其他介紹Trafodion的系列文章。本文簡要介紹Trafodion的技術體系結構，幫助讀者基本了解Trafodion內部運作的原理。

讀者還可以參考https://wiki.trafodion.org/wi...。

Trafodion的體系結構可以看作三層：ODBC接入層；SQL編譯執(zhí)行層；數據訪問和存儲層。其總體結構如下所示：

客戶端應用通過JDBC/ODBC訪問Trafodion。客戶連接由Trafodion的接入層負責。接入層為每一個客戶端連接分配一個master執(zhí)行器，master負責用戶連接所有query請求的執(zhí)行和結果返回。對于簡單的Query，Master進程本身就充當SQL執(zhí)行層；復雜的query，訪問大量數據和進行復雜運算的情況下，Master會啟動一系列的ESP（Executor Server Processes）進程進行大規(guī)模并發(fā)執(zhí)行。ESP進程是可以常駐內存的，以避免啟動開銷，但如果長期處于空閑狀態(tài)ESP進程會退出，釋放資源。每個ESP將執(zhí)行結果返回給Master，由Master匯總并將最終結果返回給客戶端。當Master或者ESP需要訪問數據層的時候，會通過DTM來進行事務管理，在DTM(分布式事務管理器)的控制下調用HBase的客戶端API進行數據的讀寫。下面分別介紹每一層的更多細節(jié)。

接入層的主要組件有兩個：DCSMaster和MXOSRVR 。DCS Master進程運行在Trafodion集群的單個節(jié)點上，負責監(jiān)聽客戶端的連接請求。當收到請求后，DCSMaster根據集群的工作負載平衡情況，選定集群中一個節(jié)點上的MXOSRVR 作為客戶端的執(zhí)行代理。DCS Master將選定的MXOSRVR信息返回客戶端，收到信息后，客戶端直接和MXOSRVR 進行連接，此后客戶端的所有請求都由該MXOSRVR 負責處理。類似Oracle的Dedicated 模式。

當多個客戶端請求連接時，DCSMaster會平均地將客戶端連接到不同的MXOSRVR ，從而均衡地利用集群中的每個計算節(jié)點。而且每個客戶端都有一個多帶帶的MXOSRVR 負責其后續(xù)計算請求的執(zhí)行，以保證快速的響應客戶query。一些數據庫系統(tǒng)只有單一的ODBC接入點，高并發(fā)的情況下，就會出現排隊現象，而采用了以上的模型后，每個客戶端都由一個接入點唯一負責，而且這些接入點平均分配在集群的各個節(jié)點，可以充分發(fā)揮每臺計算節(jié)點的能力。

為了降低延遲，Trafodion啟動的時候會預先在每個節(jié)點啟動一定數量的MXOSRVR 進程。這樣客戶端連接請求被處理時，就不需要啟動新MXOSRVR 進程的開銷。但是Trafodion也不會預先啟動非常多的MXOSRVR ，以免在連接請求不多的情況下浪費資源。當客戶請求數量大于預先啟動的MXOSRVR 進程數目時，DCS Master再為新的連接請求啟動新的MXOSRVR ，以便滿足高并發(fā)的客戶連接。

DCS Master是所有客戶端的唯一接入點，因此Trafodion為其提供了HA保護。當DCS Master故障退出，或者其所在節(jié)點崩潰時，Trafodion會在集群的其他健康節(jié)點上重新啟動一個新的DCS Master，并利用floating IP的技術保證客戶端可以繼續(xù)執(zhí)行連接。整個過程對客戶端完全透明。

Trafodion的HA機制非常復雜，需要一篇多帶帶的文章來詳細介紹，這里就不再展開敘述。

客戶請求被接受后，每個ODBC客戶端都有一個多帶帶的MXOSRVR 負責。該MXOSRVR 就是master進程，負責用戶query的執(zhí)行。一條用戶query的執(zhí)行流程大致如下：

首先，MXOSRVR 會調用compiler模塊對SQL語句進行編譯和優(yōu)化。Trafodion擁有一個非常成熟的SQL編譯器，經過了20年的不斷增強和改進，形成了一個強大的基于成本的優(yōu)化器，能夠生成用戶SQL的最佳執(zhí)行計劃，比如最優(yōu)的join表順序。此外，編譯器擁有一個執(zhí)行計劃緩存，如果SQL的執(zhí)行計劃已經在緩存中，則立即返回該計劃，節(jié)省了編譯的開銷。

執(zhí)行計劃會指導Master如何執(zhí)行用戶query。對于簡單的query，執(zhí)行計劃僅僅需要master本身即可完成。對于復雜的query，master根據計劃會啟動多個ESP進程，并發(fā)地執(zhí)行query。Trafodion的執(zhí)行器是一個MPP構架的并發(fā)處理模型。它的多數執(zhí)行操作符都支持并發(fā)，比如并發(fā)join，并發(fā)aggregation等等。

Trafodion編譯器的主要職責就是將SQL文本解析為一個最優(yōu)的執(zhí)行計劃。它主要包括以下幾部分：

Parser：parser采用bison對SQL文本進行文法分析，生成語法樹。Parser也負責維護執(zhí)行計劃緩存。如果能夠在這一步決定輸入的SQL文本在緩存中，則直接返回執(zhí)行計劃。

Binder：Binder對語法樹進一步進行分析，類似程序編譯器的語義分析，對語法合格的SQL進一步進行檢查。比如檢查Table是否存在，column數據類型是否匹配等。Binder還維護執(zhí)行計劃緩存。

Normalizer：Normalizer對Binder生成的語法樹進行邏輯優(yōu)化。實施傳統(tǒng)意義上的基于規(guī)則的優(yōu)化，比如將查詢條件下推；將子查詢修改為semi-join；將DISTINCT轉換為groupby等等。

Analyzer：Analyzer對語法樹進行一些補充，以幫助優(yōu)化器判斷是否可以運用某些規(guī)則。比如對于底層數據分區(qū)的訪問可以有多種方式，可以直接從base table訪問，或者從索引訪問。Analyzer收集數據表的索引情況，添加進語法樹，以便優(yōu)化器做選擇。

Optimizer：可以說這是Trafodion最值得驕傲和關注的一個核心技術。優(yōu)化器采用Cascades框架，是一個基于成本的優(yōu)化器，而且Cascades框架非常易于擴展，開發(fā)人員可以添加新的規(guī)則來擴展新的優(yōu)化方法。優(yōu)化器實際上可以看作一個對問題空間的搜索過程，對于同一條query，通過規(guī)則，可以生成很多等價的執(zhí)行計劃。舉一個例子：簡單的規(guī)則，比如Ajoin B => B join A，應用該規(guī)則就會生成兩個不同的等價計劃。

優(yōu)化器對語法樹應用各種規(guī)則，生成不同的執(zhí)行計劃，形成一個搜索空間。然后在這個搜索空間內通過比較每個計劃的成本，來找出最優(yōu)的方案。由于規(guī)則眾多，等價的執(zhí)行計劃數量會指數級增長，導致搜索空間非常巨大，因此采用窮舉法一條一條的進行比較是不現實的。傳統(tǒng)的優(yōu)化器框架比如 Dynamic programming是自底向上的策略，很難縮小搜索空間，而Cascades采用自頂向下的搜索策略，可以很方便地利用branch-and-bound算法，將一些分支進行裁剪，即不需要再深入分支進行優(yōu)化。比如某分支的cost已經超出當前的總cost，則對于該分支就不再進行進一步搜索。

Cascades還擁有MEMO數據結構，能夠記憶曾經搜索過的分支，這進一步增加了搜索的效率。

此外Trafodion優(yōu)化器還在多年的實踐中總結出了很多的經驗式規(guī)則(heuristics )，能夠進一步減小搜索空間。

最后優(yōu)化器支持multi-pass的模式，對于簡單的query，先enable非常少量的規(guī)則，將搜索空間限定在很小范圍，因此可以高效地找到最優(yōu)解；對于復雜query，進入第二個pass，enable所有的規(guī)則，進一步找出更好的執(zhí)行計劃。

Pre-Code generator：optimizer選出了最優(yōu)的執(zhí)行計劃，在生成物理執(zhí)行計劃之前，pre-codegenerator再應用一些物理優(yōu)化策略，比如常數折疊，舉例如下：假設Where條件為a=5 and b=a。 可以將b=a進一步替換為b=5。

Generator：最后Generator將執(zhí)行計劃翻譯為可以被Trafodion執(zhí)行器執(zhí)行的物理執(zhí)行計劃。這里有一個重要步驟，優(yōu)化標量表達式。所謂標量表達式，即其解析結果為標量的表達式，比如a+b+c等。Trafodion利用LLVM將多數標量表達式編譯成運行時的機器代碼，從而進一步提高了執(zhí)行速度，類似JIT將部分javabytecode編譯為機器指令以便加速java程序的執(zhí)行。

成本模塊：Trafodion編譯器還有一個經過長期調節(jié)和校準的cost成本模塊，對各種SQL operator的成本進行估計。成本計算需要對存放在表內數據的分布情況有所了解，這是依賴對表數據進行掃描和采樣統(tǒng)計計算出的直方圖來支持。成本模塊從直方圖中得到數據的分布情況，計算出Cardinality。它還綜合考慮了CPU，內存消耗，消息通訊和磁盤IO等條件為各個SQL操作算子計算出一個cost vector，提供比較準確的成本估計。

以上各個系統(tǒng)組件協(xié)同工作，如上圖所示，SQL語句經過parser和Normalizer的分析之后，輸入優(yōu)化器進行基于成本的優(yōu)化；成本估計模塊通過直方圖獲得數據分布，然后根據每個操作符自身的特點，進行成本估計，將成本輸入優(yōu)化器。根據這些輸入，優(yōu)化器最終生成一個最優(yōu)的執(zhí)行計劃。

Trafodion的執(zhí)行器是一個MPP構架的并發(fā)執(zhí)行器。它的工作模式是數據驅動，因此一旦有數據就緒，就可以返回用戶，而無需等待整個query完全結束執(zhí)行，提高了用戶響應速度。執(zhí)行器由不同的SQL操作符組成，數據在各個操作符之間通過IPC流動，無需將中間計算結果保存到磁盤。如果中間數據太大，超過了RAM的容量，操作符會將數據overflow到磁盤上，因此Trafodion的query執(zhí)行不受物理內存大小限制。

并發(fā)執(zhí)行

Trafodion執(zhí)行器最大的優(yōu)點是極佳的并發(fā)能力。多數SQL操作算子都有并發(fā)執(zhí)行的能力，包括GROUPBY，JOIN，INSERT都支持并發(fā)執(zhí)行。

這里舉一個小例子來說明Trafodion如何并發(fā)執(zhí)行一個簡單的sum(col1)聚集操作：master會在集群的每個節(jié)點啟動一個ESP進程，該進程負責對存儲在該節(jié)點上的數據分區(qū)進行sum聚集操作。多個ESP同時并發(fā)執(zhí)行，將最終結果發(fā)還給master，由master匯總。對于聚集，Trafodion還可以將該操作下推到數據訪問層執(zhí)行，而不需要將數據分區(qū)的每一行數據返回給ESP，由ESP逐一統(tǒng)計，而是由底層的數據訪問層進行統(tǒng)計操作，僅僅將聚集結果發(fā)給ESP，ESP再返回給master。

再看看Trafodion的Join。Trafodion支持所有的join類型，內連接，外連接，non-equijoin，semi-join，全連接等等。在Join的實現方式上，支持nestloop join，merge join和hashjoin。無論哪一種join算法，都有并發(fā)執(zhí)行的能力。Trafodion支持多種并發(fā)join方法，由優(yōu)化器選擇最優(yōu)的一種。

首先介紹大家最熟悉的兩種并發(fā)join算法，即broadcast和repartition。

broadcast parallel join(hash join)

broadcast類型的join中，一個表比較小，可以完全放入單個節(jié)點的內存中。在這種情況下Trafodion會將小表廣播到所有節(jié)點上。該并發(fā)執(zhí)行方法用于hashjoin。每個節(jié)點上的ESP將小表放入內存并建立hash表，然后順序讀入本節(jié)點上的大表分區(qū)，執(zhí)行hashjoin操作。

repartition parallel join

repartition類型的join中，兩個表都很大，無法放入單機內存。這種情況下，優(yōu)化器生成的執(zhí)行計劃會自動派生兩層ESP，第一層讀取數據后按照join column進行repartition操作，將兩個Join表的數據重新分區(qū)，將join column值相同的數據匯集到同一個第二層ESP中執(zhí)行join操作。然后，所有的第二層ESP將Join結果返回master進行匯總。

以上兩種在Hadoop的應用中經常被使用到，被稱為mapper join和reducer join。這兩種并發(fā)join方法都需要非常大的網絡開銷和內存開銷。Trafodion優(yōu)化器能夠智能地在可能的情況下選擇以下幾種并發(fā)join方法：

Matching PartitionsJoin

如果參加join的兩張表都是按照join column分區(qū)的，那么直接可以在各個節(jié)點的ESP中執(zhí)行本地join，因為肯定不需要其他節(jié)點上的數據。這是最理想的情況。

Inner Child ParallelAccess (for Nested Join)

這種方法只適用于Nest Loop Join。TblA作為outer table；TblB作為inner table。TblA有兩個分區(qū)，因此啟動2個ESP，ESP1從TblA的分區(qū)1逐行讀取數據，然后逐一從TblB讀取相應的數據行進行連接操作；同理ESP2也做同樣的工作。這種類型的join比broadcast的方法節(jié)約內存開銷，但多個ESP可能會競爭讀取outer table。但可以支持非等值join。

Trafodion的MPP并發(fā)執(zhí)行器還有很多其他的先進技術，比如HP的專利MDAM，Adaptive Segmentation，Skewbuster等都可以顯著加速query的執(zhí)行效率降低延遲，從而達到sub-second的實時響應。限于篇幅，MDAM等技術在這里就不展開敘述，Trafodion團隊將陸續(xù)推出專題技術文章來多帶帶介紹這些專利技術。

當執(zhí)行器對底層數據庫表進行讀寫時，就需要調用數據訪問層的服務。Trafodion的數據都存放在HBaseTable中。HBase本身支持對數據的隨機讀寫，但是不支持ACID事務處理。因此數據訪問層必須和DTM(分布式事務管理器)相互配合，實現有事務保護的讀寫。事務處理在下一個小結詳細介紹。

DTM對HBase的API進行了封裝，添加了必要的事務處理支持。其余的讀寫邏輯和原生的HBase讀寫是一樣的。因此如果不考慮事務，數據訪問層就是一個標準的HBase客戶端，通過HBaseclient API訪問HBase。HBase是Trafodion數據訪問和存儲層的核心。也是Trafodion區(qū)別于傳統(tǒng)數據庫的最重要的地方。借助于HBase，Trafodion也可以提供極佳的水平擴展能力，同時具有很強的可靠性，而這些能力是傳統(tǒng)數據庫所不具備的。

Trafodion支持的三種底層數據庫表：Trafodion表，Hive表和HBase表。數據訪問層需要負責對這三種存儲類型的訪問控制。

Trafodion表

Trafodion表是用戶用Trafodion的DDL語句直接創(chuàng)建的數據庫表。在底層是一張HBase表，因此從Trafodion表到HBaseTable需要一定的映射和編碼。

映射

即如何將Trafodion數據庫表映射到HBase Table。我們考慮如下這個DDL創(chuàng)建的Trafodion表：

create table sales.item(item_id int not null,

                          item_name char(10) ,

                          primary key (item_id));

首先是如何將關系數據庫的schame+table_name映射到HBaseTable。這個映射原則非常簡單，即一個trafodion表在HBase中存儲的表名為。例子中的item表在HBase中被映射為TRAFODION.SALES.ITEM這個HBaseTable。

其次是Trafodion表的各個column如何映射到HBase的存儲模式中。HBase的表內部有ColumnFamily，每個ColumnFamily中可以有任意多的ColumnQualifier，每一個行有一個rowkey，和一個timestamp。這四個維度定義了一個數據Cell。那么Trafodion的二維表如何映射到HBase這樣的存儲模型中呢？

Trafodion將表的主鍵列組合起來作為HBase的rowkey。Column映射到HBase的columnqualifier，而timestamp被用作事務管理的時間戳。在目前的release中，所有列數據都存放在同一個ColumnFamily中，支持多ColumnFamily已經在Trafodion的藍圖中，因此未來這個映射會有所改變。

編碼

HBase存儲的數據是沒有數據類型的。Trafodion的表卻支持不同的SQL數據類型，比如CHAR型，即按字符串進行存儲，”1”被編碼為ASCII碼0x41。如果SQL數據類型為INTEGER，在存儲到HBase中時，Trafodion會直接寫入二進制數0x00,0x00,0x00,0x01，占用4個byte；相應的LONG型占8個byte。

Trafodion會自動進行類型處理，無需應用程序自己進行編解碼的工作。

數據分區(qū)

HBase會自動通過split技術對數據進行分區(qū)，但是某些情況下，比如時間序列數據順序插入的情況下，大量的數據讀寫會集中在某個單一Region上，從而使得單臺RegionServer的負載高于其他的RegionServer。Trafodion支持slatedpartition功能，在創(chuàng)建表的時候通過指定SALT關鍵字，Trafodion會自動為rowkey加入hash前綴，對表進行pre-split，保證平均地將數據分布在集群中。用戶也可以不指定SALT關鍵字，而依賴底層HBase自動進行數據分區(qū)。

訪問原生HBase表

Trafodion也可以直接訪問原生HBase表，提供兩種訪問方式: Cell-Per-Row和Rowwise Per-Row。

通過Cell-Per-Row方式訪問HBase表，每一個HBase的Cell會作為SQL結果集中的一行數據。通過Rowwise Per-Row模式訪問，每一行HBase數據作為SQL結果集的一行數據。

假設Table1有2行數據，每行兩個Cell:[(row1, CF1:Col1, v1), (row1,CF1:Col2, v2) , (row2, CF1:Col1, d1), (row2,CF1:Col2, d2)]。

Cell-Per-Row訪問：

select * from hbase.”_CELL_”.”table1”  

 

返回4行數據

通過Rowwise-Per-Row方式訪問：

select * from hbase.”_ROW_”.”table1”;

返回兩行數據

訪問原生Hive表

Trafodion可以直接訪問原生Hive表。采用特殊的schema “hive”，用戶直接使用SQL語句即可訪問。比如

select * fromhive.hive.table1;

SQL引擎會識別”hive.hive”這個特殊的schema，讀取Hive的metastore獲取table1的元數據，然后直接通過libhdfs訪問HDFS上的Hive表數據。因此繞過了DTM。所以，對于原生Hive表的訪問，Trafodion不提供事務保護

Trafodion的威爾士本意即事務，因此事務處理是Trafodion非常重要的一個方面。事務是一系列query的組合。一個事務由若干操作構成，并由begin開始，由commit或者abort結束。

Trafodion采用兩階段提交協(xié)議來保證分布式事務的完整性。每個節(jié)點均運行TM進程，所有的TM都是peerto peer對等的，而避免了單一的事務管理器的擴展性問題和SinglePoint of Failure問題。高并發(fā)情況下，所有的活躍事務由不同節(jié)點上的TM分別管理，提供了很高的擴展能力。

原生的HBase本身僅支持單行的ACID事務保證，Trafodion基于開源項目hbase-trx（https://github.com/hbase-trx/...）開發(fā)了目前版本的Transactionon HBase機制。提供了跨行跨表的ACID保證。hbase-trx采用MVCC機制，提供SnapShotIsolation事務隔離級別。原生的hbase-trx僅支持HBase0.94，且采用了侵入式的開發(fā)方法，大量修改了HBase的基本代碼。Trafodion團隊吸取了hbase-trx的基本思路，利用HBase協(xié)處理器重新開發(fā)了hbase-trx，并支持HBase0.98版本。并改進了日志實現，能夠保證各種failure情況下數據的安全性。

目前TrafodionDTM團隊正在和中國科學院計算所合作開發(fā)新的Transactionon HBase算法Stateful-stateless Concurrency Control (SSCC)。關于SSCC的原理，讀者可以進一步參考開源項目Domino:https://github.com/domino-suc...，預計將于TrafodionR1.2版本開始提供產品使用。SSCC提供比SnapShot Isolation更高級的隔離級別，同時對無狀態(tài)寫操作有很高效的支持，提供更高的并發(fā)度。無狀態(tài)寫在web應用中非常普遍，采用這一機制，Trafodion可以高效地為相關的web應用提供強大的支持。

Trafodion是一個復雜的大系統(tǒng)，一篇短文無論如何也不可能完全說明其內部運作原理。筆者僅希望用最簡單的描述給各位讀者一個大體的概念，作為一個開源項目，Trafodion歡迎各位研讀源代碼，并共同改進。

通過本文，希望讀者認同以下幾個關鍵點：

Trafodion有一個成熟的SQL編譯器，能夠進行基于成本的優(yōu)化

Trafodion有一個先進的MPP并發(fā)執(zhí)行引擎

Trafodion有一個創(chuàng)新的Transaction實現

Trafodion有一個成熟的ODBC/JDBC接入層

Trafodion構架在HBase之上，繼承了所有HBase的優(yōu)點。為用戶提供極佳的水平擴展性

本文沒有涉及到的技術話題還有很多，比如Trafodion的HA實現，安全體系，NoSQL支持等。Trafodion團隊會努力完善文檔，也歡迎各位讀者能夠下載Trafodion源代碼進行使用和學習，并貢獻您的理解和分析。

作者：劉明-易鯨捷首席架構師