各位讀者朋友大家好，我是薯?xiàng)l，好久沒更文章，不知還有多少讀者記得這個(gè)號(hào)，這篇文章寫的有點(diǎn)精分，如果你有耐心看完本文，可以翻翻留言區(qū)，我會(huì)發(fā)個(gè)新年紅包。

業(yè)務(wù)背景

如果是本號(hào)老讀者，可能知道我是做數(shù)據(jù)系統(tǒng)的，作為一個(gè)在線數(shù)據(jù)服務(wù)組，我們這邊承接的需求是小而多的。我在一家打車公司上班，運(yùn)營大佬們認(rèn)為不同用戶在不同場景下有不同打車需求，設(shè)計(jì)出來很多子品類。于是我們組會(huì)承接這樣一類需求：計(jì)算用戶不同品類的各種實(shí)時(shí)單量，如：快車呼單量、拼車完單量。

這樣的需求，一般處理流程是這樣的：

描述一下這個(gè)圖：用戶在訂單流轉(zhuǎn)狀態(tài)關(guān)鍵節(jié)點(diǎn)發(fā)生動(dòng)作時(shí)，系統(tǒng)會(huì)發(fā)一個(gè)MQ消息讓供其他系統(tǒng)消費(fèi)。其他系統(tǒng)通過一個(gè)明確的據(jù)口徑判斷這條msg是否符合當(dāng)前業(yè)務(wù)邏輯，進(jìn)而存db或是丟棄。比如一個(gè)需求要計(jì)算：拼車完單量，一個(gè)靠譜的拼車rd告訴你口徑是：

If aa.bb.cc == 1  // 說明是多車型發(fā)單 
  Unmarshal(bb.cc.ee) 
  看type是否為 4  
else  // 單車型發(fā)單 
 Unmarshal(bb.cc.ff) 
  看type是否為 4  
(type = 4 的是拼車) 

你對(duì)著這個(gè)口徑，訂閱mq，寫數(shù)據(jù)提取和訂單判斷的邏輯，整個(gè)流程寫代碼1小時(shí)，自測一小時(shí)，由于你們機(jī)器太多，上線花了1整天，整體研發(fā)效率還行。

第二天，產(chǎn)品又給你提了個(gè)需求，想計(jì)算拼車的發(fā)單量，你又去找對(duì)應(yīng)業(yè)務(wù)線的開發(fā)同學(xué)尋求一個(gè)取數(shù)口徑，然后重復(fù)上面的過程。

第三天，產(chǎn)品上線了，效果不錯(cuò)，數(shù)據(jù)漲了3個(gè)點(diǎn)，老板非常開心，在周會(huì)上讓PM講兩句他的心路歷程，PM同學(xué)重點(diǎn)感謝了老板的栽培，然后輕描淡寫的說了產(chǎn)品的底層邏輯和關(guān)鍵抓手。而他的幾個(gè)精明的同事都get到了抓手是你，于是連夜趕PRD，要求你這個(gè)抓手把他們負(fù)責(zé)品類的各種實(shí)時(shí)單量全給抓出來。

第四天，你崩潰了，因?yàn)槟闶盏?個(gè)PM并行的8個(gè)單量需求，正當(dāng)你奮筆疾書再次準(zhǔn)備重復(fù)上述流程時(shí)，你睿智的老板告訴你這樣做有不妥之處：來一個(gè)坑填一個(gè)蘿卜是小農(nóng)時(shí)代的做法，現(xiàn)在都21世紀(jì)了，時(shí)代變了，讓你想一種通用解決方案，讓系統(tǒng)走向工業(yè)時(shí)代!

你似懂非懂點(diǎn)了點(diǎn)頭，查了各種CSDN、博客園、知乎、github，又在技術(shù)交流群各種@群里大佬有沒有遇到這種場景。一番折騰后終于有了頭緒，于是你高興的向老板匯報(bào)：老板，我懂了，這個(gè)場景可以用JPATH + Expression Eval來解決!這樣一來，再來新的需求只需要寫在db里插入倆表達(dá)式就可以了，20個(gè)需求提過來也不用怕。

你的老板微笑著點(diǎn)了點(diǎn)頭，看了一眼自己手上的勞力士，有意無意的晃了晃，說：小伙子很上道，自己也琢磨出解法了，趕緊設(shè)計(jì)方案，爭取本周上線，盡快拿到業(yè)務(wù)結(jié)果，到時(shí)候升職加薪少不了你的!

實(shí)現(xiàn)方案

這個(gè)系統(tǒng)的核心需求有兩點(diǎn)：

1. 數(shù)據(jù)提取
2. 規(guī)則判斷

數(shù)據(jù)提取即ETL，把mq的msg中關(guān)鍵信息提取出來，提取之后可能還需要簡單處理一下(比如msg中事件時(shí)間是timestamp，你想轉(zhuǎn)化為RFC3339格式) ，這里可以用JPATH 做數(shù)據(jù)提取 (如果你寫過爬蟲，一定知道用xpath去提取HTML中的node消息，jpath就是json數(shù)據(jù)的提取規(guī)則)。配置一個(gè)ETL rule，如圖所示：

然后是數(shù)據(jù)規(guī)則判斷，即題目中提到的規(guī)則引擎，我們這里使用 開源庫govaluate，比如上面拼車完單的例子，我們可以配置這樣的規(guī)則：

cc == 1 ? ( in(4, ee)? 1:0 ) : ( ff ==4 ? 1:0) 

govaluate會(huì)把這個(gè)表達(dá)式構(gòu)建出一顆ast，然后輸入?yún)?shù)進(jìn)行求值(是不是回憶起來了編譯原理?)。接下來讓我們研究一下這個(gè)庫~

govaluate介紹與使用注意

govaluate支持對(duì)C風(fēng)格的算數(shù)/字符串的表達(dá)式進(jìn)行求值。比如這些例子(例子來源于evaluation_test.go):

1. 100 ^ (23 * (2 | 5)) 
2. 5 < 10 && 1 < 5 
3. (foo == true) || (bar == true) // foo、bar為變量 
4. theft && period == 24 ? 60     // theft、period為變量 

這個(gè)庫幾乎支持你能想象到的任何表達(dá)式，有興趣可以去這個(gè)test文件。除此之外它支持拓展UDF， 你可以自己寫一些函數(shù)支持你的定制業(yè)務(wù)邏輯，它還支持執(zhí)行類方法，更多信息可以看README。

當(dāng)我們需要使用它時(shí)，只需要這幾行代碼

expression, err := govaluate.NewEvaluableExpression("foo > 0"); 
 
parameters := make(map[string]interface{}, 8) 
parameters["foo"] = -1; 
 
result, err := expression.Evaluate(parameters); 
// result is now set to "false", the bool value. 

通過這個(gè)demo我們可以看到它的api被設(shè)計(jì)成了兩步， 第一步NewEvaluableExpression的功能主要是把表達(dá)式拓展為一顆AST，Evaluate的主要功能是把用戶參數(shù)填入ast求值。。舉個(gè)例子：比如1 + foo + 4 * boo這個(gè)表達(dá)式，在兩個(gè)階段分別做的事情是這樣：

那么生產(chǎn)項(xiàng)目代碼中直接把這兩步抄進(jìn)去就可以了嗎?顯然不是。通過觀察就可以發(fā)現(xiàn)， 第一步構(gòu)造ast依賴的表達(dá)式其實(shí)是可以預(yù)先確定的，且表達(dá)式一般不會(huì)變化，沒有必要用戶每次傳一個(gè)api就構(gòu)造一顆ast然后求值?？梢园驯磉_(dá)式存入db，在項(xiàng)目啟動(dòng)or更新配置時(shí)加載到內(nèi)存中， 比如搞一個(gè)map[string]*EvaluableExpression, 把不同表達(dá)式的ast進(jìn)行cache，這樣用戶每次請(qǐng)求時(shí)只需遍歷ast進(jìn)行求值。

預(yù)編譯所帶來的收益很顯著，尤其是在你表達(dá)式比較復(fù)雜的情況下。我對(duì)foo > 2? 1:0這個(gè)表達(dá)式分別做了現(xiàn)編譯和預(yù)編譯的benchmark，結(jié)果如下：

現(xiàn)編譯

(現(xiàn)編譯 構(gòu)建ast占用62.3%的cpu開銷，而eval只占2%)

預(yù)編譯

(預(yù)編譯省掉了構(gòu)建ast的成本，節(jié)約了大量cpu資源) 建議大家如果使用這個(gè)庫，有條件要用預(yù)編譯版本。

govaluate 原理

看起來govaluate很有意思， 接下來讓我們挖一下它的源碼。首先來看第一階段，把表達(dá)式拓展為AST時(shí)的邏輯，我簡單畫了一張圖：

下面以1 + foo + 4 * boo為例，parserToken后，我們可以得到一堆token:

checkBalance沒啥好說的，核心功能就看小括號(hào)是否成對(duì)出現(xiàn)：

而checkExpressionSyntax階段主要是check token之間是否符合預(yù)設(shè)規(guī)則，核心是這個(gè)函數(shù)：

這個(gè)函數(shù)會(huì)check當(dāng)前的token是否是上一個(gè)token的合法值，合法值是預(yù)設(shè)的，比如NUMERIC的合法值是后面這些：

接下來的 optimizeTokens 函數(shù)沒啥好說的，主要就是編譯一下正則。

比較有意思的是planStages這個(gè)步驟。planStages這個(gè)大步驟內(nèi)部大概分成了planTokens、reorderStages、elideLiterals這三個(gè)小步驟，下面來一一介紹：

planTokens

這個(gè)函數(shù)寫的讓我大開眼界，首先它用func做不同運(yùn)算符的優(yōu)先級(jí)計(jì)算，原理是func接收struct作為參數(shù)，而參數(shù)中的next為這個(gè)函數(shù)連接的下一個(gè)優(yōu)先級(jí)的func。

這個(gè)func優(yōu)先級(jí)打印出來是這樣的：

有了運(yùn)算符優(yōu)先級(jí)之后，對(duì)于具體的節(jié)點(diǎn)，會(huì)繼續(xù)看節(jié)點(diǎn)類型，比如是func，accesser還是valueType，valueType的節(jié)點(diǎn)對(duì)于不同的詳細(xì)類型也有不同策略，比如數(shù)字節(jié)點(diǎn)會(huì)構(gòu)建一個(gè)Node，而小括號(hào)節(jié)點(diǎn)會(huì)直接parser下一個(gè)token來構(gòu)建優(yōu)先級(jí)更高的樹。

對(duì)于不同的運(yùn)算符，在這個(gè)函數(shù)鏈上會(huì)下沉構(gòu)建出優(yōu)先級(jí)比較高的節(jié)點(diǎn)，保證符合數(shù)學(xué)計(jì)算的規(guī)律。

reorderStages

這里主要把a(bǔ)st重排序，讓ast由普通tree變成avl tree，樹旋轉(zhuǎn)的代碼寫的特別騷氣，比如1 + foo + 4 * boo 這個(gè)表達(dá)式，planToken執(zhí)行完后，會(huì)變成這樣一顆樹：

重排序的過程是把相同優(yōu)先級(jí)的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，第一步是交換左右節(jié)點(diǎn)：

第二步是LL左旋：

這樣就平衡了，一個(gè)非常騷氣的算法。

elideLiterals

這個(gè)步驟是看葉子節(jié)點(diǎn)是否為LITERAL，比如這棵樹：

在這個(gè)階段，各個(gè)子節(jié)點(diǎn)會(huì)進(jìn)行dfs計(jì)算直接變成：

至此第一階段的邏輯梳理完畢。而第二個(gè)階段Evaluate的主要功能是把用戶參數(shù)填入ast，進(jìn)行求值。這個(gè)過程比較簡單，本文不在贅述。

govaluate 不足

govaluate 看起來很美好，真的是這樣嗎?其實(shí)不然，這個(gè)項(xiàng)目最后一次commit是2017年，距今已經(jīng)6年了。我們?cè)谑褂闷陂g也發(fā)現(xiàn)了很多小bug和代碼優(yōu)美度欠缺的地方。下面來簡單列舉幾個(gè)：

弱類型

govaluate所有數(shù)字類型都是被解析為float64進(jìn)行計(jì)算的，這么玩寫代碼爽了，但是當(dāng)你用1+2+9做表達(dá)式時(shí)，可能會(huì)得到一個(gè)類型為fload64的interface{}結(jié)果。

函數(shù)限制

govaluate的函數(shù)有的返回值無法繼續(xù)做運(yùn)算。比如這個(gè)case：

看起來沒有任何問題，但是執(zhí)行會(huì)報(bào)錯(cuò)： 

參數(shù)會(huì)去除轉(zhuǎn)義符

比如這段代碼： 

理論上結(jié)果應(yīng)該含有轉(zhuǎn)義符，實(shí)際上結(jié)果是: 

實(shí)際上是這段代碼搞的鬼，代碼比較簡單，就不解釋了。

奇奇怪怪的代碼

1. this關(guān)鍵字：這個(gè)就不舉例子了，這個(gè)庫里所有方法的接收者都是this，被官方建議熏陶過的我，看的我著實(shí)蛋疼...
2. 雙重否定表肯定：token解析階段有這樣的代碼，不知道作者為啥要搞個(gè)雙重否定，我的話，會(huì)用一個(gè)isQuote代替。
3. 

govaluate改進(jìn)

作為一個(gè)17年后就沒更新過的項(xiàng)目， 也不知道作者還會(huì)不會(huì)維護(hù)。業(yè)務(wù)發(fā)展是不等人，govaluate對(duì)于我們服務(wù)來說并不能滿足需求，很多時(shí)候用起來比較別扭，所以我基于我們的場景對(duì)于govaluate做了一些定制改造。我個(gè)人還是非常喜歡這個(gè)庫的，于是把代碼fork了一份，加了個(gè)eplus后綴，改造了上面那幾個(gè)匪夷所思的問題。并加了個(gè)比較定制化的feature：type promotion。

這個(gè)聽起來比較唬人， 其實(shí)就是支持更弱類型的表達(dá)式運(yùn)算，比如我的庫支持：'2' -1, '4' * 3，要支持這種功能，核心需要改兩種地方：

1. 第一種地方是typeCheck。比如subStage會(huì)check兩個(gè)字節(jié)點(diǎn)必須是float64類型， 我們要支持string operator num， 可以把typeCheck擴(kuò)大為可以是chek node是否為 floatOrStr。
2. 第二種地方是OpeatorOperate。前面我們把String類型也放進(jìn)來讓它支持計(jì)算了，但是在go里str和float終究是無法計(jì)算的， 所以到了計(jì)算階段需要做一個(gè)type promotion，即把string類型轉(zhuǎn)化為數(shù)字類型之后再計(jì)算。

總結(jié)與反思

總結(jié)

govaluate在我心中還是有一些不完美的地方，我們這里用它也是因?yàn)轫?xiàng)目初期就引入了這個(gè)庫，在大量的線上用例使用后要遷移這個(gè)庫成本巨大， 對(duì)于用的不爽的地方只能改了。如果讀者朋友有需求， 可以看一下市面上其他的表達(dá)式開源庫， 比如gval。當(dāng)然，如果你的場景比較復(fù)雜， 需要很多if else 或者for循環(huán)，那簡單的規(guī)則引擎可能滿足不了你的需求，此時(shí)可以考慮內(nèi)嵌個(gè)更完整的腳本庫或者嵌入lua， 不過這樣就更復(fù)雜了， 慎重考慮把這樣的東西直接放在db里面， 后期不好維護(hù)。

反思

govaluate這個(gè)庫對(duì)我有很多啟發(fā)，最主要就是表達(dá)式的預(yù)編譯可以節(jié)省大量CPU開銷，組內(nèi)某個(gè)項(xiàng)目目前的運(yùn)行方式是隨著請(qǐng)求現(xiàn)編譯，構(gòu)建執(zhí)行計(jì)劃dag圖，理論上如果能預(yù)編譯，請(qǐng)求到來只是對(duì)于對(duì)應(yīng)param訪問存儲(chǔ)，可以節(jié)省大量CPU開銷。

跳脫出govaluate本身，我們系統(tǒng)選擇JPATH + Expr做數(shù)據(jù)提取和條件描述做需求，本質(zhì)上是因?yàn)檫@邊的mq數(shù)據(jù)是JSON格式，JSON有一定的局限性，描述數(shù)據(jù)沒啥問題，但是描述條件就比較困難了，理論上如果用XML這種技能描述條件，又能描述數(shù)據(jù)的交互形式，那我們可能會(huì)構(gòu)建一個(gè)完全不同的系統(tǒng)。

最后稍微打個(gè)廣告吧， 如果你也想使用govaluate，又有一些定制化的需求，歡迎star我的庫然后提個(gè)issue， 我想試著維護(hù)一個(gè)開源庫， 嘿嘿。