作者： 程式設計師薯條 來源：薯條的程式設計修養
各位讀者朋友大家好，我是薯條，好久沒更文章，不知還有多少讀者記得這個號，這篇文章寫的有點精分，如果你有耐心看完本文，可以翻翻留言區，我會發個新年紅包。
業務背景
如果是本號老讀者，可能知道我是做資料系統的，作為一個線上資料服務組，我們這邊承接的需求是小而多的。我在一家打車公司上班，運營大佬們認為不同使用者在不同場景下有不同打車需求，設計出來很多子品類。於是我們組會承接這樣一類需求：計算使用者不同品類的各種實時單量，如：快車呼單量、拼車完單量。
這樣的需求，一般處理流程是這樣的：
描述一下這個圖：使用者在訂單流轉狀態關鍵節點發生動作時，系統會發一個MQ訊息讓供其他系統消費。其他系統透過一個明確的據口徑判斷這條msg是否符合當前業務邏輯，進而存db或是丟棄。比如一個需求要計算：拼車完單量，一個靠譜的拼車rd告訴你口徑是：
If aa.bb.cc == 1 // 說明是多車型發單
Unmarshal(bb.cc.ee)
看type是否為 4
else // 單車型發單
Unmarshal(bb.cc.ff)
看type是否為 4
(type = 4 的是拼車) 你對著這個口徑，訂閱mq，寫資料提取和訂單判斷的邏輯，整個流程寫程式碼1小時，自測一小時，由於你們機器太多，上線花了1整天，整體研發效率還行。
第二天，產品又給你提了個需求，想計算拼車的發單量，你又去找對應業務線的開發同學尋求一個取數口徑，然後重複上面的過程。
第三天，產品上線了，效果不錯，資料漲了3個點，老闆非常開心，在週會上讓PM講兩句他的心路歷程，PM同學重點感謝了老闆的栽培，然後輕描淡寫的說了產品的底層邏輯和關鍵抓手。而他的幾個精明的同事都get到了抓手是你，於是連夜趕PRD，要求你這個抓手把他們負責品類的各種實時單量全給抓出來。
第四天，你崩潰了，因為你收到4個PM並行的8個單量需求，正當你奮筆疾書再次準備重複上述流程時，你睿智的老闆告訴你這樣做有不妥之處：來一個坑填一個蘿蔔是小農時代的做法，現在都21世紀了，時代變了，讓你想一種通用解決方案，讓系統走向工業時代!
你似懂非懂點了點頭，查了各種CSDN、部落格園、知乎、github，又在技術交流群各種@群裡大佬有沒有遇到這種場景。一番折騰後終於有了頭緒，於是你高興的向老闆彙報：老闆，我懂了，這個場景可以用JPATH + Expression Eval來解決!這樣一來，再來新的需求只需要寫在db裡插入倆表示式就可以了，20個需求提過來也不用怕。
你的老闆微笑著點了點頭，看了一眼自己手上的勞力士，有意無意的晃了晃，說：小夥子很上道，自己也琢磨出解法了，趕緊設計方案，爭取本週上線，儘快拿到業務結果，到時候升職加薪少不了你的!
實現方案
這個系統的核心需求有兩點：
- 資料提取
- 規則判斷
資料提取即ETL，把mq的msg中關鍵資訊提取出來，提取之後可能還需要簡單處理一下(比如msg中事件時間是timestamp，你想轉化為RFC3339格式) ，這裡可以用JPATH 做資料提取 (如果你寫過爬蟲，一定知道用xpath去提取HTML中的node訊息，jpath就是json資料的提取規則)。配置一個ETL rule，如圖所示：
然後是資料規則判斷，即題目中提到的規則引擎，我們這裡使用 開源庫govaluate，比如上面拼車完單的例子，我們可以配置這樣的規則：
cc == 1 ? ( in(4, ee)? 1:0 ) : ( ff ==4 ? 1:0) govaluate會把這個表示式構建出一顆ast，然後輸入引數進行求值(是不是回憶起來了編譯原理?)。接下來讓我們研究一下這個庫~
govaluate介紹與使用注意
govaluate支援對C風格的算數/字串的表示式進行求值。比如這些例子(例子來源於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為變數 這個庫幾乎支援你能想象到的任何表示式，有興趣可以去這個test檔案。除此之外它支援拓展UDF， 你可以自己寫一些函式支援你的定製業務邏輯，它還支援執行類方法，更多資訊可以看README。
當我們需要使用它時，只需要這幾行程式碼
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. 透過這個demo我們可以看到它的api被設計成了兩步， 第一步NewEvaluableExpression的功能主要是把表示式拓展為一顆AST，Evaluate的主要功能是把使用者引數填入ast求值。。舉個例子：比如1 + foo + 4 * boo這個表示式，在兩個階段分別做的事情是這樣：
那麼生產專案程式碼中直接把這兩步抄進去就可以了嗎?顯然不是。透過觀察就可以發現， 第一步構造ast依賴的表示式其實是可以預先確定的，且表示式一般不會變化，沒有必要使用者每次傳一個api就構造一顆ast然後求值。可以把表示式存入db，在專案啟動or更新配置時載入到記憶體中， 比如搞一個map[string]*EvaluableExpression, 把不同表示式的ast進行cache，這樣使用者每次請求時只需遍歷ast進行求值。
預編譯所帶來的收益很顯著，尤其是在你表示式比較複雜的情況下。我對foo > 2? 1:0這個表示式分別做了現編譯和預編譯的benchmark，結果如下：
現編譯
(現編譯 構建ast佔用62.3%的cpu開銷，而eval只佔2%)
預編譯
(預編譯省掉了構建ast的成本，節約了大量cpu資源) 建議大家如果使用這個庫，有條件要用預編譯版本。
govaluate 原理
看起來govaluate很有意思， 接下來讓我們挖一下它的原始碼。首先來看第一階段，把表示式拓展為AST時的邏輯，我簡單畫了一張圖：
下面以1 + foo + 4 * boo為例，parserToken後，我們可以得到一堆token:
checkBalance沒啥好說的，核心功能就看小括號是否成對出現：
而checkExpressionSyntax階段主要是check token之間是否符合預設規則，核心是這個函式：
這個函式會check當前的token是否是上一個token的合法值，合法值是預設的，比如NUMERIC的合法值是後面這些：
接下來的 optimizeTokens 函式沒啥好說的，主要就是編譯一下正則。
比較有意思的是planStages這個步驟。planStages這個大步驟內部大概分成了planTokens、reorderStages、elideLiterals這三個小步驟，下面來一一介紹：
planTokens
這個函式寫的讓我大開眼界，首先它用func做不同運算子的優先順序計算，原理是func接收struct作為引數，而引數中的next為這個函式連線的下一個優先順序的func。
這個func優先順序打印出來是這樣的：
有了運算子優先順序之後，對於具體的節點，會繼續看節點型別，比如是func，accesser還是valueType，valueType的節點對於不同的詳細型別也有不同策略，比如數字節點會構建一個Node，而小括號節點會直接parser下一個token來構建優先順序更高的樹。
對於不同的運算子，在這個函式鏈上會下沉構建出優先順序比較高的節點，保證符合數學計算的規律。
reorderStages
這裡主要把ast重排序，讓ast由普通tree變成avl tree，樹旋轉的程式碼寫的特別騷氣，比如1 + foo + 4 * boo 這個表示式，planToken執行完後，會變成這樣一顆樹：
重排序的過程是把相同優先順序的節點進行旋轉，第一步是交換左右節點：
第二步是LL左旋：
這樣就平衡了，一個非常騷氣的演算法。
elideLiterals
這個步驟是看葉子節點是否為LITERAL，比如這棵樹：
在這個階段，各個子節點會進行dfs計算直接變成：
至此第一階段的邏輯梳理完畢。而第二個階段Evaluate的主要功能是把使用者引數填入ast，進行求值。這個過程比較簡單，本文不在贅述。
govaluate 不足
govaluate 看起來很美好，真的是這樣嗎?其實不然，這個專案最後一次commit是2017年，距今已經6年了。我們在使用期間也發現了很多小bug和程式碼優美度欠缺的地方。下面來簡單列舉幾個：
弱型別
govaluate所有數字型別都是被解析為float64進行計算的，這麼玩寫程式碼爽了，但是當你用1+2+9做表示式時，可能會得到一個型別為fload64的interface{}結果。
函式限制
govaluate的函式有的返回值無法繼續做運算。比如這個case：
看起來沒有任何問題，但是執行會報錯：
引數會去除轉義符
比如這段程式碼：
理論上結果應該含有轉義符，實際上結果是:
實際上是這段程式碼搞的鬼，程式碼比較簡單，就不解釋了。
奇奇怪怪的程式碼
- this關鍵字：這個就不舉例子了，這個庫裡所有方法的接收者都是this，被官方建議薰陶過的我，看的我著實蛋疼...
- 雙重否定表肯定：token解析階段有這樣的程式碼，不知道作者為啥要搞個雙重否定，我的話，會用一個isQuote代替。
govaluate改進
作為一個17年後就沒更新過的專案， 也不知道作者還會不會維護。業務發展是不等人，govaluate對於我們服務來說並不能滿足需求，很多時候用起來比較彆扭，所以我基於我們的場景對於govaluate做了一些定製改造。我個人還是非常喜歡這個庫的，於是把程式碼fork了一份，加了個eplus字尾，改造了上面那幾個匪夷所思的問題。並加了個比較定製化的feature：type promotion。
這個聽起來比較唬人， 其實就是支援更弱型別的表示式運算，比如我的庫支援：'2' -1, '4' * 3，要支援這種功能，核心需要改兩種地方：
- 第一種地方是typeCheck。比如subStage會check兩個位元組點必須是float64型別， 我們要支援string operator num， 可以把typeCheck擴大為可以是chek node是否為 floatOrStr。
- 第二種地方是OpeatorOperate。前面我們把String型別也放進來讓它支援計算了，但是在go裡str和float終究是無法計算的， 所以到了計算階段需要做一個type promotion，即把string型別轉化為數字型別之後再計算。
總結與反思
總結
govaluate在我心中還是有一些不完美的地方，我們這裡用它也是因為專案初期就引入了這個庫，在大量的線上用例使用後要遷移這個庫成本巨大， 對於用的不爽的地方只能改了。如果讀者朋友有需求， 可以看一下市面上其他的表示式開源庫， 比如gval。當然，如果你的場景比較複雜， 需要很多if else 或者for迴圈，那簡單的規則引擎可能滿足不了你的需求，此時可以考慮內嵌個更完整的指令碼庫或者嵌入lua， 不過這樣就更復雜了， 慎重考慮把這樣的東西直接放在db裡面， 後期不好維護。
反思
govaluate這個庫對我有很多啟發，最主要就是表示式的預編譯可以節省大量CPU開銷，組內某個專案目前的執行方式是隨著請求現編譯，構建執行計劃dag圖，理論上如果能預編譯，請求到來只是對於對應param訪問儲存，可以節省大量CPU開銷。
跳脫出govaluate本身，我們系統選擇JPATH + Expr做資料提取和條件描述做需求，本質上是因為這邊的mq資料是JSON格式，JSON有一定的侷限性，描述資料沒啥問題，但是描述條件就比較困難了，理論上如果用XML這種技能描述條件，又能描述資料的互動形式，那我們可能會構建一個完全不同的系統。
最後稍微打個廣告吧， 如果你也想使用govaluate，又有一些定製化的需求，歡迎star我的庫然後提個issue， 我想試著維護一個開源庫， 嘿嘿。
