Cobar源碼分析之AST
本文轉(zhuǎn)載自微信公眾號「捉蟲大師」，作者捉蟲大師。轉(zhuǎn)載本文請聯(lián)系捉蟲大師公眾號。
背景
Cobar
Cobar是阿里開源的數(shù)據(jù)庫中間件，關(guān)于它的介紹這里不再贅述，可以參考之前的文章《Cobar SQL審計的設(shè)計與實現(xiàn)》
SQL
SQL是一種領(lǐng)域語言(編程語言)，常用于關(guān)系型數(shù)據(jù)庫，方便管理結(jié)構(gòu)化數(shù)據(jù)。數(shù)據(jù)庫執(zhí)行SQL時先對SQL進(jìn)行詞法分析、語法分析、語義分析生成抽象語法樹(Abstract Syntax Tree，簡稱AST)，再被優(yōu)化器處理生成執(zhí)行計劃，由執(zhí)行引擎執(zhí)行。
SQL Parser
將SQL解析為AST的解析器叫SQL Parser，開發(fā)這個解析器通常有兩種方式：
- 通過工具自動生成
- 優(yōu)點：簡單易于實現(xiàn)
- 缺點：性能不佳，二次開發(fā)困難
- 手工編寫
- 優(yōu)點：性能好，代碼清晰易于擴(kuò)展
- 缺點：對開發(fā)人員要求高，需要了解編譯原理
Cobar中也實現(xiàn)了SQL Parser，它在Cobar中的位置可以從它的架構(gòu)圖中看到：
SQL Parser之后是SQL Router，可以推斷出SQL Parser解析出AST的目的是為了分庫分表的路由功能。
Cobar的SQL Parser也經(jīng)歷了三個版本的迭代，本質(zhì)是性能考慮：
第一版：基于JavaCC生成SQL parser，性能較差，優(yōu)化不方便
第二版：仿照ANTLR生成的parser結(jié)構(gòu)手寫，中間對象過多
第三版：基于LL(2)識別器手寫
本文不對SQL Parser做過多的介紹，這篇文章我也仔細(xì)閱讀了幾遍，附上總結(jié)的腦圖：
https://github.com/lkxiaolou/reading/tree/main/xmind
Cobar AST
Cobar中的SQL Parser將SQL解析為AST，為了直觀感受，先舉個例子：
- select id,type from goods as g where type in (select type from type_config where status = 0)
經(jīng)過Cobar SQL Parser后，生成了如下AST對象：
這個AST的根節(jié)點就是select語句，然后每個屬性都是葉子節(jié)點，葉子節(jié)點的屬性再分出葉子節(jié)點。可能有點繞，需要從代碼層面感受。
AST的Node定義如下，這里只有個accept方法，是為了遍歷這棵樹，暫時不管，后面會說到：
- public interface ASTNode {
- void accept(SQLASTVisitor visitor);
- }
實現(xiàn)這個ASTNode主要有這幾個：
- SQLStatement：SQL語句，比如select、update、insert等語句，體現(xiàn)在上圖的DMLSelectStatement
- Expression：表達(dá)式，比如and、or、比較等語句，體現(xiàn)在InExpression、ComparisionEqualsExpression、LiteralNumber、Identifier
- TableReference：table相關(guān)語句，體現(xiàn)在TableReferences、TableRefFactor
以ComparisionEqualsExpression的實現(xiàn)為例
其中1是比較的左右表達(dá)式，2是判斷符，這里是“=”，3是計算該表達(dá)式。
evaluationInternal如何實現(xiàn)?其實表達(dá)式被結(jié)構(gòu)化和窮舉之后這個問題變得簡單，比如這里只需要取左右的數(shù)值，進(jìn)行是否相等的比較即可。
AST操作
有了如上對AST的了解，接下來看對AST的操作，最基本的是遍歷，利用ASTNode的accept，需要實現(xiàn)SQLASTVisitor接口，這個SQLASTVisitor定義如下：
其實是利用了java的多態(tài)，對每種ASTNode都定義了visit方法，遍歷時不同對象對應(yīng)到不同方法上。
比如MySQLOutputASTVisitor可以遍歷AST，將AST還原為SQL輸出，只需要這樣：
- SQLStatement stmt = SQLParserDelegate.parse(sql);
- StringBuilder s = new StringBuilder();
- stmt.accept(new MySQLOutputASTVisitor(s));
- System.out.println(s.toString());
這樣執(zhí)行會輸出
SELECT id, type FROM goods AS G WHERE type IN (SELECT type FROM type_config WHERE status = 0)
SQLParserDelegate.parse(sql)解析出來為DMLSelectStatement對象，它的visit方法實現(xiàn)如下：
- @Override
- public void accept(SQLASTVisitor visitor) {
- visitor.visit(this);
- }
再看MySQLOutputASTVisitor的visit(DMLSelectStatement node)實現(xiàn)：代碼比較長，這里就不貼了，總體思路是遇到葉子節(jié)點就直接按格式存入StringBuilder中，否則繼續(xù)調(diào)用相應(yīng)節(jié)點的accept繼續(xù)遍歷，是一種深度遍歷的思想。
我們可以參考MySQLOutputASTVisitor編寫符合自己需求的遍歷器。
AST的應(yīng)用
分庫分表
Cobar中利用AST可以獲取table名、列名、比較的值進(jìn)行分庫分表，這也是Cobar最重要的功能。
SQL特征生成
除此之外，我了解的AST還可以對原始SQL生成SQL特征，比如原始SQL是這樣：
select id, name, age from user as u where age >= 20
或者是
select id, name, age from user as u where age >= 30
都可以被歸一化為
select id, name, age from user as u where age >= ?
在進(jìn)行SQL慢查詢或其他的統(tǒng)計、針對SQL進(jìn)行限流時非常有用。
危險SQL攔截
線上寫了一條沒有where條件的update或delete，這時可以利用AST進(jìn)行表達(dá)式計算，對沒有where條件和where條件恒為true的SQL進(jìn)行攔截。
最后
本文從SQL AST的來源、結(jié)構(gòu)、遍歷原理、應(yīng)用等方面進(jìn)行介紹，相信看完文章會對SQL AST有了初步的了解，如果想進(jìn)一步了解可以參考Cobar項目中的單元測試進(jìn)行實際的演示感受。
