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