前一段時(shí)間我在推進(jìn)一個(gè)動(dòng)態(tài)查詢服務(wù)業(yè)務(wù)方把篩選條件直接以結(jié)構(gòu)化的方式傳給后端后端要把這些條件拼成表達(dá)式樹(shù)再編譯成委托塞給數(shù)據(jù)訪問(wèn)層。量小的時(shí)候一切正常等壓測(cè)一上來(lái)CPU 直接被打到 80% 以上——不是查詢慢而是卡在表達(dá)式樹(shù)的構(gòu)建和 Compile 上。那一刻我才真正意識(shí)到兩件事第一表達(dá)式樹(shù)的構(gòu)建和編譯成本比想象中高得多第二對(duì)這個(gè)東西做緩存并沒(méi)有一開(kāi)始想的“放個(gè)字典”那么簡(jiǎn)單。后來(lái)我換了個(gè)思路把緩存結(jié)構(gòu)從前綴樹(shù)的角度重新做了一版效果非常明顯。這篇內(nèi)容就是把我完整的思考過(guò)程、踩過(guò)的坑、落地的代碼細(xì)節(jié)都整理出來(lái)。如果你也在做動(dòng)態(tài) LINQ、對(duì)象映射器、規(guī)則引擎、或者任何需要頻繁構(gòu)造和編譯表達(dá)式樹(shù)的服務(wù)這篇文章大概率能幫你省下不少 CPU。1. 表達(dá)式樹(shù)緩存為什么沒(méi)有想象中簡(jiǎn)單1.1 表達(dá)式樹(shù)不是普通對(duì)象沒(méi)法直接當(dāng)字典鍵很多人第一反應(yīng)是緩存嘛搞一個(gè)Dictionaryobject, T不就行了。表達(dá)式樹(shù)本身是對(duì)象直接用實(shí)例做 key 不行嗎不行。表達(dá)式樹(shù)內(nèi)部是一堆對(duì)象引用互相連接根節(jié)點(diǎn)是一個(gè) LambdaExpression下面掛 BodyBody 里又有 Left、Right、Arguments 之類(lèi)的子節(jié)點(diǎn)。最關(guān)鍵的問(wèn)題是兩個(gè)邏輯上完全等價(jià)的表達(dá)式例如ExpressionFuncUser, bool expr1 u u.Age 18; ExpressionFuncUser, bool expr2 v v.Age 18;它們?cè)谶\(yùn)行時(shí)創(chuàng)建出來(lái)完全不同的對(duì)象圖。expr1和expr2的引用不相等內(nèi)部的 MemberExpression、ParameterExpression、ConstantExpression 也全部是獨(dú)立實(shí)例。你用ReferenceEqualityComparer做 key同一個(gè)邏輯的表達(dá)式也會(huì)被當(dāng)成不同條目緩存命中等于零。有人可能會(huì)說(shuō)那我把表達(dá)式樹(shù)轉(zhuǎn)成字符串存字典不就好了。這個(gè)方向是對(duì)的但里面藏著很多坑下面單獨(dú)說(shuō)。1.2 字符串 Key 方案的三個(gè)硬傷字符串方案是網(wǎng)上最常見(jiàn)的做法核心思路就是expr.ToString()或者序列化成某種文本形式然后用這個(gè)字符串當(dāng) key。我在第一版也是這么干的跑了一段時(shí)間后發(fā)現(xiàn)三個(gè)硬傷。第一個(gè)硬傷是ToString()的輸出不穩(wěn)定。表達(dá)式樹(shù)的ToString生成的字符串在不同運(yùn)行環(huán)境下并不是完全等價(jià)的。比如常量decimal或double的格式化可能受當(dāng)前 Culture 影響一元表達(dá)式可能會(huì)因?yàn)槔ㄌ?hào)層級(jí)不同產(chǎn)生不一樣的輸出形式甚至有些自定義表達(dá)式節(jié)點(diǎn)的ToString行為完全不可控。一旦 key 不穩(wěn)定同一個(gè)表達(dá)式在某個(gè)線程下生成 key A在另一個(gè)線程下生成 key B緩存就形同虛設(shè)。第二個(gè)硬傷是字符串生成本身的代價(jià)。expr.ToString()是一次完整的樹(shù)遍歷每次請(qǐng)求都先遍歷整棵樹(shù)生成字符串再用字符串去字典里查找。這等于把“構(gòu)建表達(dá)式樹(shù)”的解析成本省了但遍歷成本和字符串分配成本全留下了。表達(dá)式一復(fù)雜字符串長(zhǎng)度輕松上千字符字符串比較又得逐字符比對(duì)算下來(lái)并沒(méi)有比重新 Compile 快太多。第三個(gè)硬傷是字符串 key 的內(nèi)存浪費(fèi)。一個(gè)表達(dá)式轉(zhuǎn)成字符串動(dòng)不動(dòng)幾百上千字符如果業(yè)務(wù)請(qǐng)求有幾千上萬(wàn)個(gè)變體光 key 就吃掉不少內(nèi)存。而且字符串 key 和表達(dá)式樹(shù)的內(nèi)部結(jié)構(gòu)完全是兩種維度如果你后續(xù)想調(diào)整匹配規(guī)則比如忽略參數(shù)名、忽略某些子表達(dá)式用字符串做 key 會(huì)非常痛苦因?yàn)槟氵€得先做字符串解析和正則替換。1.3 緩存命中之后還要考慮編譯階段還有一個(gè)很容易被忽略的點(diǎn)緩存的目標(biāo)到底是什么。如果只緩存“表達(dá)式樹(shù)對(duì)象”命中了確實(shí)省掉了重新Expression.XXX()一堆方法調(diào)用的時(shí)間但表達(dá)式樹(shù)被使用的時(shí)候往往還要Compile()成委托。Compile()階段涉及 IL 生成、類(lèi)型元數(shù)據(jù)讀取、委托構(gòu)造這部分成本在大多數(shù)場(chǎng)景下比“構(gòu)建表達(dá)式樹(shù)”還高尤其是需要反射訪問(wèn)復(fù)雜成員或調(diào)用鏈很長(zhǎng)的時(shí)候。所以我在設(shè)計(jì)緩存的時(shí)候目標(biāo)從一開(kāi)始就不是“緩存表達(dá)式樹(shù)”。而是直接把“同一個(gè)結(jié)構(gòu)的表達(dá)式”對(duì)應(yīng)的已編譯委托緩存下來(lái)。這樣命中后連Compile()都省了。而表達(dá)式樹(shù)對(duì)象本身只是當(dāng) key 的匹配依據(jù)。這個(gè)目標(biāo)設(shè)定決定了后面整個(gè)數(shù)據(jù)結(jié)構(gòu)的選擇。2. 前綴樹(shù)憑什么適合承載表達(dá)式樹(shù)緩存2.1 前綴樹(shù)的一層對(duì)應(yīng)表達(dá)式樹(shù)的一層前綴樹(shù)也叫 Trie本質(zhì)上是一種多叉樹(shù)。它的特點(diǎn)是根節(jié)點(diǎn)不存數(shù)據(jù)樹(shù)的每一層對(duì)應(yīng)判定序列中的一環(huán)從根到葉子的路徑拼起來(lái)就是完整的判定序列。和普通字典相比它的最大優(yōu)勢(shì)是能自動(dòng)共享前綴。那這件事和表達(dá)式樹(shù)有什么關(guān)系關(guān)系很大因?yàn)楸磉_(dá)式樹(shù)本身就是一棵樹(shù)。兩棵表達(dá)式樹(shù)如果結(jié)構(gòu)相似它們的前半段路徑大概率是重疊的。比如u u.Age 18 v v.Age 18這兩棵樹(shù)從根節(jié)點(diǎn)的 Lambda 開(kāi)始參數(shù)類(lèi)型相同Body 是一個(gè)二元比較節(jié)點(diǎn)二元節(jié)點(diǎn)的 NodeType 都是 GreaterThan左子節(jié)點(diǎn)都是訪問(wèn) User 的 Age 屬性右子節(jié)點(diǎn)都是常量 18。如果用“節(jié)點(diǎn)的類(lèi)型和特征”組成判定序列那么這兩棵樹(shù)的判定序列從頭到尾完全一致自然會(huì)在前綴樹(shù)中走到同一條路徑最終命中同一個(gè)緩存項(xiàng)。這就是前綴樹(shù)相比字典的底層優(yōu)勢(shì)字典的 key 是整體匹配前綴樹(shù)的匹配是逐層進(jìn)行的結(jié)構(gòu)越相似匹配過(guò)程中越早匯合天然支持結(jié)構(gòu)共享。2.2 維度序列把樹(shù)壓平成逐層判定要使用前綴樹(shù)首先得把一棵“樹(shù)”變成一個(gè)“序列”。這個(gè)序列不是簡(jiǎn)單地把所有節(jié)點(diǎn)平鋪而是要保證父節(jié)點(diǎn)的判定特征在序列中一定出現(xiàn)在子節(jié)點(diǎn)之前。這樣前綴樹(shù)的每一層對(duì)應(yīng)表達(dá)式樹(shù)中的某一層從根開(kāi)始逐層對(duì)齊。我做了一個(gè)叫“維度序列”的東西。樹(shù)的每個(gè)節(jié)點(diǎn)轉(zhuǎn)化成一條邊Edge一條邊包含三個(gè)字段節(jié)點(diǎn)的表達(dá)式類(lèi)型NodeType比如GreaterThan、MemberAccess、Constant、Parameter。子節(jié)點(diǎn)數(shù)量ChildCount用來(lái)區(qū)分同一類(lèi)型但子結(jié)構(gòu)不同的情況。輔助哈希AuxHash用來(lái)細(xì)化特征比如成員訪問(wèn)的成員名、方法調(diào)用的方法簽名、參數(shù)的類(lèi)型、常量值的類(lèi)型和值哈希。舉個(gè)具體例子表達(dá)式u u.Age 18的維度序列大致是Lambda(參數(shù)類(lèi)型: User, 參數(shù)個(gè)數(shù): 1) - GreaterThan(子節(jié)點(diǎn): 2) - MemberAccess(User.Age, 子節(jié)點(diǎn): 1) - Parameter(User) - Constant(int, 18)注意我在這里把 Lambda 的參數(shù)類(lèi)型和數(shù)量也放進(jìn)了序列。這一點(diǎn)很重要因?yàn)閮蓚€(gè)表達(dá)式即使 Body 完全一樣如果參數(shù)類(lèi)型不同語(yǔ)義也不同必須區(qū)分開(kāi)。后續(xù)每一步都沿著先序順序繼續(xù)展開(kāi)直到葉子節(jié)點(diǎn)。把這個(gè)序列放進(jìn)前綴樹(shù)里等于給每個(gè)表達(dá)式建立一條路徑。查找時(shí)只需要拿著同樣方式生成的維度序列從前綴樹(shù)根節(jié)點(diǎn)開(kāi)始逐層往下走即可。2.3 對(duì)照前綴樹(shù) vs 字典 vs 表達(dá)式比較器這里我簡(jiǎn)單做一個(gè)方案對(duì)比方便大家看清為什么最終選了前綴樹(shù)。方案命中粒度查詢復(fù)雜度實(shí)現(xiàn)成本典型問(wèn)題字符串作為 key整體匹配O(字符串長(zhǎng)度)低ToString 不穩(wěn)定、字符串分配大、無(wú)法忽略參數(shù)名引用相等做 key只有同一個(gè)實(shí)例命中O(1)極低等價(jià)表達(dá)式無(wú)法命中形同虛設(shè)規(guī)范化后比較結(jié)構(gòu)等價(jià)命中O(樹(shù)規(guī)模)高每次比較都遍歷全樹(shù)沒(méi)有共享前綴樹(shù)前綴共享O(序列深度)中需要處理規(guī)范化、分支膨脹但查找非?？爝@里的“規(guī)范化后比較”是指用微軟的表達(dá)式比較器一類(lèi)工具把每個(gè)節(jié)點(diǎn)逐個(gè)比對(duì)。如果緩存里存了 1 萬(wàn)條表達(dá)式來(lái)一個(gè)新表達(dá)式要依次比對(duì) 1 萬(wàn)次每次都是一次完整樹(shù)遍歷。前綴樹(shù)則是直接按維度序列尋徑查一次樹(shù)的深度也就是表達(dá)式樹(shù)的深度完全不管緩存里有多少條這是數(shù)量級(jí)上的差異。3. 落地實(shí)現(xiàn)節(jié)點(diǎn)設(shè)計(jì)、歸一化與增刪查3.1 邊結(jié)構(gòu) TrieEdge 與節(jié)點(diǎn)結(jié)構(gòu)先定義邊。邊就是我在 2.2 里說(shuō)的維度序列中的一個(gè)元素。這里我用一個(gè)只讀結(jié)構(gòu)體public readonly struct TrieEdge : IEquatableTrieEdge { public ExpressionType NodeType { get; } public int ChildCount { get; } public int AuxHash { get; } public TrieEdge(ExpressionType nodeType, int childCount, int auxHash) { NodeType nodeType; ChildCount childCount; AuxHash auxHash; } public bool Equals(TrieEdge other) { return NodeType other.NodeType ChildCount other.ChildCount AuxHash other.AuxHash; } public override int GetHashCode() { unchecked { var hash (int)NodeType; hash (hash * 397) ^ ChildCount; hash (hash * 397) ^ AuxHash; return hash; } } }AuxHash 具體怎么算邏輯不一樣。拿成員訪問(wèn)舉例訪問(wèn)User.Age輔助哈希就是nameof(Age)和聲明類(lèi)型typeof(User)的組合哈希如果是方法調(diào)用就是方法名、聲明類(lèi)型、方法簽名的組合哈希如果是常量節(jié)點(diǎn)就是常量值的類(lèi)型哈希加上值本身的哈希?？傊o助哈希的目的是區(qū)分“同類(lèi)型、同子節(jié)點(diǎn)個(gè)數(shù)但語(yǔ)義不同”的節(jié)點(diǎn)。接下來(lái)是前綴樹(shù)節(jié)點(diǎn)public class ExpressionTrieNode { private readonly DictionaryTrieEdge, ExpressionTrieNode _children new(); public bool HasCachedValue { get; private set; } public LambdaExpression CachedExpression { get; private set; } public Delegate CachedDelegate { get; private set; } public bool TryGetValue(out Delegate compiledDelegate) { compiledDelegate null; if (!HasCachedValue) return false; compiledDelegate CachedDelegate; return true; } public void SetValue(LambdaExpression expression, Delegate compiledDelegate) { HasCachedValue true; CachedExpression expression; CachedDelegate compiledDelegate; } public ExpressionTrieNode GetOrAddNode(TrieEdge edge) { if (_children.TryGetValue(edge, out var existing)) return existing; var newNode new ExpressionTrieNode(); _children.Add(edge, newNode); return newNode; } public bool TryGetNode(TrieEdge edge, out ExpressionTrieNode node) { return _children.TryGetValue(edge, out node); } }這個(gè)節(jié)點(diǎn)的結(jié)構(gòu)很簡(jiǎn)單每個(gè)節(jié)點(diǎn)存三個(gè)東西子節(jié)點(diǎn)字典、是否已有緩存值、緩存下來(lái)的表達(dá)式和編譯委托。3.2 參數(shù)重命名與閉包展開(kāi)這部分是整個(gè)方案真正的核心也是我踩坑最多的地方。如果直接拿原始表達(dá)式樹(shù)生成維度序列那么u u.Age 18和v v.Age 18會(huì)被判定為兩條完全不同的路徑因?yàn)楣舱Z(yǔ)言運(yùn)行時(shí)會(huì)認(rèn)為u和v是兩個(gè)不同的 ParameterExpression 實(shí)例。所以必須先做“參數(shù)歸一化”。我實(shí)現(xiàn)了一個(gè)參數(shù)重寫(xiě)器本質(zhì)是把 Lambda 里出現(xiàn)的所有參數(shù)按“第一次出現(xiàn)順序”統(tǒng)一改名為p0、p1這樣的占位符之后再插入前綴樹(shù)。這樣兩個(gè)邏輯等價(jià)但參數(shù)名不同的表達(dá)式生成的維度序列就完全一致了。public class ParameterNormalizer : ExpressionVisitor { private readonly DictionaryParameterExpression, ParameterExpression _map new(); protected override Expression VisitParameter(ParameterExpression node) { if (!_map.TryGetValue(node, out var normalized)) { normalized Expression.Parameter(node.Type, $p{_map.Count}); _map[node] normalized; } return normalized; } protected override Expression VisitLambdaT(ExpressionT node) { var body Visit(node.Body); var parameters node.Parameters.Select(p (ParameterExpression)VisitParameter(p)).ToArray(); return Expression.Lambda(body, parameters); } }注意VisitLambda里必須先重寫(xiě)參數(shù)節(jié)點(diǎn)本身再重寫(xiě) Body。而且同一個(gè) ParameterExpression 實(shí)例可能在 Body 中出現(xiàn)多次VisitParameter里的字典會(huì)保證同一個(gè)實(shí)例始終映射到同一個(gè)歸一化參數(shù)。另一件必須處理的事情是閉包展開(kāi)。動(dòng)態(tài)查詢里經(jīng)常會(huì)寫(xiě)int minAge GetMinAgeFromConfig(); ExpressionFuncUser, bool expr u u.Age minAge;minAge會(huì)被編譯器捕獲成閉包然后在表達(dá)式樹(shù)里體現(xiàn)為一個(gè)ConstantExpression這個(gè)常量的值是一個(gè)編譯器生成的閉包對(duì)象。問(wèn)題是每次調(diào)用GetMinAgeFromConfig()閉包對(duì)象都是新的哪怕minAge的值一模一樣表達(dá)式樹(shù)的常量節(jié)點(diǎn)引用也不一致緩存照樣不命中。解決辦法是在參數(shù)歸一化之前先把閉包里的字段“攤開(kāi)”成真正的常量值。我用一個(gè)自定義的表達(dá)式訪問(wèn)器public class CaptureExpander : ExpressionVisitor { protected override Expression VisitMember(MemberExpression node) { if (node.Expression is ConstantExpression constant) { var declaringType node.Member.DeclaringType; if (declaringType ! null declaringType.IsDefined(typeof(CompilerGeneratedAttribute), false)) { object value node.Member switch { FieldInfo field field.GetValue(constant.Value), PropertyInfo property property.GetValue(constant.Value), _ null }; if (value ! null (value.GetType().IsPrimitive || value is string || value is decimal || value is DateTime || value is Guid)) { return Expression.Constant(value, node.Type); } } } return base.VisitMember(node); } }這段代碼的作用是如果發(fā)現(xiàn)成員訪問(wèn)的“源”是一個(gè)編譯器生成閉包就反射讀取字段的值。如果是基礎(chǔ)類(lèi)型直接替換成常量節(jié)點(diǎn)。這樣u.Age minAge就變成了u.Age 3030 這個(gè)值直接參與哈希計(jì)算閉包對(duì)象的版本差異就被消除掉了。這里有個(gè)邊界必須小心如果閉包字段的值是引用類(lèi)型而且后面還繼續(xù)訪問(wèn)它的子成員一層展開(kāi)就可能不夠。比如u u.Address.City Shanghaiu.Address是 User 對(duì)象的成員不涉及閉包沒(méi)問(wèn)題但string prefix ...; u u.Name.StartsWith(prefix)里面的 prefix 是閉包字段展開(kāi)成常量后可以直接匹配。對(duì)于SomeConfig config ...; u u.Age config.MinAge閉包展開(kāi)只做一層的話會(huì)把config展開(kāi)成Constant(config 實(shí)例引用)那這個(gè)實(shí)例引用每次可能還是不同。這種情況我目前的處理方法是如果第一層展開(kāi)后仍然是個(gè)比較復(fù)雜對(duì)象的實(shí)例就遞歸往下展開(kāi)字段直到遇到基礎(chǔ)類(lèi)型如果遞歸層數(shù)太深就直接放棄緩存該表達(dá)式走原來(lái)的編譯邏輯。這個(gè)策略對(duì)大多數(shù)業(yè)務(wù)場(chǎng)景已經(jīng)夠用。3.3 插入和查找的完整過(guò)程把表達(dá)式“洗”干凈之后剩下的就是生成維度序列并插入前綴樹(shù)。我用一個(gè)遞歸函數(shù)按先序順序把整棵表達(dá)式樹(shù)壓平為一條邊序列private static void AppendEdges(Expression node, ListTrieEdge edges) { switch (node) { case LambdaExpression lambda: { var hash 17; foreach (var p in lambda.Parameters) hash HashCode.Combine(hash, p.Type); edges.Add(new TrieEdge(ExpressionType.Lambda, lambda.Parameters.Count 1, hash)); AppendEdges(lambda.Body, edges); break; } case BinaryExpression binary: edges.Add(new TrieEdge(binary.NodeType, 2, 0)); AppendEdges(binary.Left, edges); AppendEdges(binary.Right, edges); break; case UnaryExpression unary: edges.Add(new TrieEdge(unary.NodeType, 1, 0)); AppendEdges(unary.Operand, edges); break; case MemberExpression member: { int childCount member.Expression null ? 0 : 1; var hash HashCode.Combine(member.Member.Name, member.Member.DeclaringType); edges.Add(new TrieEdge(ExpressionType.MemberAccess, childCount, hash)); if (member.Expression ! null) AppendEdges(member.Expression, edges); break; } case MethodCallExpression call: { int childCount (call.Object null ? 0 : 1) call.Arguments.Count; var hash HashCode.Combine(call.Method.Name, call.Method.DeclaringType, call.Method.GetParameters().Length); edges.Add(new TrieEdge(ExpressionType.Call, childCount, hash)); if (call.Object ! null) AppendEdges(call.Object, edges); foreach (var arg in call.Arguments) AppendEdges(arg, edges); break; } case ConstantExpression constant: { int valueHash GetValueHash(constant.Value); int hash HashCode.Combine(constant.Type, valueHash); edges.Add(new TrieEdge(ExpressionType.Constant, 0, hash)); break; } case ParameterExpression parameter: edges.Add(new TrieEdge(ExpressionType.Parameter, 0, parameter.Type.GetHashCode())); break; default: // 其他不常見(jiàn)節(jié)點(diǎn)類(lèi)型直接按類(lèi)型哈希走 edges.Add(new TrieEdge(node.NodeType, 0, node.Type.GetHashCode())); break; } }GetValueHash對(duì)于值類(lèi)型直接調(diào)GetHashCode()對(duì)于字符串也直接用字符串哈希對(duì)于其他對(duì)象則退回到引用哈希防止把一個(gè)大對(duì)象序列化進(jìn)來(lái)導(dǎo)致性能劣化。有了邊序列之后插入和查找就非常簡(jiǎn)單了。插入是從根節(jié)點(diǎn)開(kāi)始按邊序列挨個(gè)走走到哪沒(méi)有子節(jié)點(diǎn)就創(chuàng)建一個(gè)直到序列結(jié)束然后在終點(diǎn)節(jié)點(diǎn)塞入表達(dá)式和編譯委托。查找則完全一樣地走如果中途任一層找不到對(duì)應(yīng)邊直接返回未命中。這里我把提交編譯委托和查找合并成一個(gè)方法public Delegate GetOrCompileTDelegate( ExpressionTDelegate seed, FuncExpressionTDelegate, Delegate compiler) where TDelegate : Delegate { // 1. 閉包展開(kāi) var expanded new CaptureExpander().Visit(seed); // 2. 參數(shù)歸一化 var normalized new ParameterNormalizer().Visit(expanded); // 3. 生成邊序列 var edges new ListTrieEdge(); AppendEdges(normalized, edges); // 4. 前綴樹(shù)查找/插入 ExpressionTrieNode current _root; foreach (var edge in edges) { if (!current.TryGetNode(edge, out var next)) { lock (current) { next current.GetOrAddNode(edge); } } current next; } if (current.TryGetValue(out var cachedDelegate)) return cachedDelegate; var compiled compiler(normalized as ExpressionTDelegate); current.SetValue(normalized as LambdaExpression, compiled); return compiled; }實(shí)際項(xiàng)目中compiler參數(shù)不需要由調(diào)用方傳內(nèi)部直接調(diào)expression.Compile()就行。我這里留成一個(gè)委托參數(shù)是為了方便測(cè)試時(shí)替換各位可以直接寫(xiě)成Compile()。3.4 并發(fā)讀寫(xiě)的一個(gè)可落地方案前綴樹(shù)和普通字典不一樣它不能靠一個(gè)簡(jiǎn)單的 ConcurrentDictionary 就解決并發(fā)問(wèn)題因?yàn)橐淮尾迦胍刂窂絼?chuàng)建多個(gè)節(jié)點(diǎn)。如果兩個(gè)線程同時(shí)插入同一個(gè)前綴路徑很容易在中間節(jié)點(diǎn)上產(chǎn)生競(jìng)爭(zhēng)。我用的方案是GetOrAddNode這一步在鎖內(nèi)做雙重檢查。上面代碼里已經(jīng)體現(xiàn)了if (!current.TryGetNode(edge, out var next)) { lock (current) { next current.GetOrAddNode(edge); } }這里 lock 的對(duì)象就是當(dāng)前節(jié)點(diǎn)。因?yàn)門(mén)rieEdge是只讀結(jié)構(gòu)體節(jié)點(diǎn)的子節(jié)點(diǎn)字典只在插入時(shí)修改查找時(shí)只讀。兩個(gè)線程同時(shí)走到同一節(jié)點(diǎn)時(shí)都嘗試在它的_children里加同一條邊但加鎖保證了只有一個(gè)線程真正創(chuàng)建新節(jié)點(diǎn)另一個(gè)線程走完鎖之后發(fā)現(xiàn)已經(jīng)有了直接復(fù)用。對(duì)于讀多寫(xiě)少的服務(wù)里這個(gè)鎖競(jìng)爭(zhēng)幾乎可以忽略不計(jì)。因?yàn)樗辉凇暗谝淮斡龅侥硞€(gè)邊”時(shí)才觸發(fā)后續(xù)所有請(qǐng)求都是純字典讀取不碰任何鎖。如果你追求極端并發(fā)性能可以在每個(gè)節(jié)點(diǎn)上用一個(gè)ReaderWriterLockSlim但就我的實(shí)測(cè)來(lái)看雙重檢查鎖已經(jīng)足夠。還有一點(diǎn)值得注意如果某個(gè)分支走完整個(gè)序列后發(fā)現(xiàn)沒(méi)有緩存值并發(fā)插入還沒(méi)完成可能會(huì)產(chǎn)生重復(fù)編譯。我目前的策略是拿到終點(diǎn)節(jié)點(diǎn)后先看有沒(méi)有值沒(méi)有就編譯編譯結(jié)束后再SetValue。在多線程下可能出現(xiàn)同一路徑被編譯多次的情況但因?yàn)楹罄m(xù)線程都能復(fù)用第一次寫(xiě)入的值所以最多只會(huì)多編譯幾次不會(huì)造成正確性問(wèn)題。如果你接受不了這點(diǎn)可以在終點(diǎn)節(jié)點(diǎn)上加一個(gè)LazyDelegate做單次初始化效果更好。4. 實(shí)測(cè)效果、邊界情況與兩個(gè)重要提醒4.1 三套方案的對(duì)比數(shù)據(jù)為了驗(yàn)證這套方案到底值不值得做我寫(xiě)了一個(gè)模擬測(cè)試生成了 10 萬(wàn)條結(jié)構(gòu)不同但有一定重合度的動(dòng)態(tài)表達(dá)式所有表達(dá)式都是User類(lèi)型上的謂詞組合包含屬性訪問(wèn)、常量比較、字符串匹配、閉包捕獲然后分別用無(wú)緩存、字符串字典緩存、前綴樹(shù)緩存跑了一遍。需要說(shuō)明的是這個(gè)測(cè)試是為了橫向比較方案之間的相對(duì)差異不是造數(shù)據(jù)吹一個(gè)絕對(duì)數(shù)字。不同機(jī)器、不同表達(dá)式復(fù)雜度一定會(huì)導(dǎo)致絕對(duì)值變化但相對(duì)關(guān)系是穩(wěn)定的。方案平均單次總耗時(shí)命中率內(nèi)存占用趨勢(shì)無(wú)緩存每次構(gòu)建加編譯約 1.2ms0每次請(qǐng)求都會(huì)產(chǎn)生新對(duì)象GC 壓力最大字符串 key 字典緩存約 0.35ms能命中但受 ToString 穩(wěn)定性影響字符串 key 和表達(dá)式樹(shù)都存著中等前綴樹(shù)緩存委托約 0.08ms結(jié)構(gòu)等價(jià)即可命中含參數(shù)名無(wú)關(guān)匹配節(jié)點(diǎn)多分支多內(nèi)存偏高但可控最直觀的感受是前綴樹(shù)方案比字符串方案快了 4 倍左右和完全無(wú)緩存比快了 15 倍。字符串方案最大的開(kāi)銷(xiāo)其實(shí)不在字典查找而是在每次請(qǐng)求生成ToString()的字符串和后續(xù)字符串哈希。前綴樹(shù)方案省掉這一步而且查詢是逐結(jié)構(gòu)走路徑走完基本就到底了幾乎沒(méi)什么額外計(jì)算。4.2 常量對(duì)象引用導(dǎo)致的假不命中前綴樹(shù)方案有一個(gè)非常大的坑第一次跑測(cè)試時(shí)我花了好長(zhǎng)時(shí)間才定位出來(lái)常量節(jié)點(diǎn)的哈希不能用對(duì)象引用否則緩存命中率會(huì)斷崖式下跌。舉個(gè)例子用戶查詢City Shanghai每次生成的ConstantExpression都是一個(gè)新的string對(duì)象。雖然字符串的GetHashCode()是按內(nèi)容算的所以對(duì)于字符串還好。但如果常量是某一個(gè)自定義配置對(duì)象比如ExpressionFuncUser, bool expr u u.Category currentCategory;其中currentCategory是一個(gè)Category對(duì)象每次請(qǐng)求從數(shù)據(jù)庫(kù)加載出來(lái)都是新實(shí)例。如果哈希直接currentCategory.GetHashCode()那引用變了哈希就變緩存必然不命中。我的解決辦法是在GetValueHash里做一個(gè)分支判斷只有值類(lèi)型、字符串、decimal、DateTime、Guid 這類(lèi)“語(yǔ)義值”參與哈希計(jì)算其他對(duì)象一律退回“類(lèi)型哈希”而不是對(duì)象哈希。這樣即使閉包對(duì)象每次都是新實(shí)例只要類(lèi)型相同常量節(jié)點(diǎn)就被認(rèn)為是同一個(gè)維度上的后續(xù)閉包展開(kāi)已經(jīng)把真實(shí)值替換成基礎(chǔ)類(lèi)型所以這個(gè)退化策略不會(huì)造成語(yǔ)義錯(cuò)誤。如果業(yè)務(wù)里確實(shí)需要緩存“復(fù)雜對(duì)象常量值”不同的表達(dá)式那就要給這個(gè)對(duì)象的 “Equals” 和GetHashCode做好值語(yǔ)義或者把它序列化成穩(wěn)定字符串再參與哈希。否則就老實(shí)讓緩存失效不要為了追求命中率引入錯(cuò)誤風(fēng)險(xiǎn)。4.3 分支膨脹與定期裁剪前綴樹(shù)也有自己的代價(jià)它把大量公共前綴拆成了很多細(xì)粒度節(jié)點(diǎn)每一條沒(méi)命中過(guò)的分支都會(huì)在樹(shù)里留下永久節(jié)點(diǎn)。如果業(yè)務(wù)表達(dá)式變化非常零散緩存分支可能會(huì)不成比例地膨脹。我第一次上線時(shí)沒(méi)處理這個(gè)問(wèn)題運(yùn)行了一周后看內(nèi)存發(fā)現(xiàn)前綴樹(shù)占用的內(nèi)存比所有緩存表達(dá)式委托加起來(lái)還要多。原因是很多請(qǐng)求是“一次性變體”某個(gè)表達(dá)式只出現(xiàn)過(guò)一兩次但它在樹(shù)上留下了一條完整路徑這條路徑永遠(yuǎn)不會(huì)再被訪問(wèn)。后來(lái)我加了一個(gè)輕量級(jí)計(jì)數(shù)器每個(gè)節(jié)點(diǎn)記錄最后一次訪問(wèn)的時(shí)間戳和命中次數(shù)。定時(shí)任務(wù)每小時(shí)掃描一次把所有葉子節(jié)點(diǎn)那一側(cè)、訪問(wèn)次數(shù)為零、且超過(guò)一段時(shí)間未訪問(wèn)的分支剪掉。注意裁剪一定要從葉子往上剪不能從中間切否則會(huì)把有緩存值的根路徑誤刪。對(duì)于大多數(shù)業(yè)務(wù)其實(shí)可以先不加裁剪功能但要心里有數(shù)如果緩存條目的規(guī)模在千萬(wàn)級(jí)以上內(nèi)存控制就會(huì)變成主要矛盾。4.4 跨進(jìn)程一致性提醒還有一個(gè)容易踩的坑字符串和哈希值在不同的 .NET 運(yùn)行時(shí)版本之間不具備跨進(jìn)程一致性。string.GetHashCode()在 .NET Core 3.0 之后開(kāi)始引入進(jìn)程內(nèi)隨機(jī)化同一個(gè)字符串在不同進(jìn)程里算出來(lái)的哈希很可能不一樣。PropertyInfo.GetHashCode()也類(lèi)似它和反射對(duì)象的元數(shù)據(jù)身份綁定不同進(jìn)程加載同一個(gè)類(lèi)型時(shí)返回的哈希不一定相同。所以這種前綴樹(shù)緩存只能用在進(jìn)程內(nèi)緩存場(chǎng)景千萬(wàn)不要把輔助哈希值算好后塞進(jìn) Redis 或者其他分布式緩存里再拿去跨進(jìn)程匹配。如果你真要做分布式表達(dá)式緩存那就得先定義一套完全確定性的規(guī)范化序列化協(xié)議把這個(gè)協(xié)議作為 key前綴樹(shù)只負(fù)責(zé)進(jìn)程內(nèi)的快速匹配。序列化的成本會(huì)吃掉一部分性能優(yōu)勢(shì)所以我的建議是如果分布式是硬需求進(jìn)程內(nèi)只緩存編譯委托分布式只緩存表達(dá)式樹(shù)的內(nèi)容別混著用。5. 我的實(shí)踐體會(huì)與后續(xù)擴(kuò)展這套方案我從最初用字符串字典踩坑到后來(lái)改成前綴樹(shù)最大的感受是表達(dá)式樹(shù)這種結(jié)構(gòu)用線性容器去承載是天然不舒服的它本身就是樹(shù)讓緩存結(jié)構(gòu)也貼近樹(shù)的形態(tài)才是順理成章的事。在這個(gè)實(shí)現(xiàn)里我每次比對(duì)一個(gè)節(jié)點(diǎn)都不會(huì)遞歸整棵子樹(shù)而是走一條路徑這條路徑的長(zhǎng)度最多就是表達(dá)式樹(shù)的深度。這也是為什么在表達(dá)式數(shù)量的規(guī)模變大之后前綴樹(shù)方案的性能曲線依然很平坦而字典方案早就開(kāi)始肉眼可見(jiàn)地變慢了。如果以后要繼續(xù)往下做我可能的擴(kuò)展方向有這么幾個(gè)一是把邊序列生成器從硬編碼的 switch 改成基于表達(dá)式訪問(wèn)器的可擴(kuò)展管線方便接入自定義表達(dá)式節(jié)點(diǎn)二是把節(jié)點(diǎn)內(nèi)的子節(jié)點(diǎn)字典在某些高熱點(diǎn)分支上替換成固定數(shù)組用索引訪問(wèn)代替字典哈希進(jìn)一步降低單次查找的常數(shù)因子三是把閉包展開(kāi)邏輯做更深層的遞歸配合類(lèi)型緩存把任意深度的閉包字段自動(dòng)替換成值常量這樣動(dòng)態(tài)查詢的緩存命中率還能再往上走一截。最后說(shuō)一個(gè)很多人會(huì)忽略的小技巧處理表達(dá)式樹(shù)之前先調(diào)用一次Expression.CanReduce看看節(jié)點(diǎn)能不能歸約。不少?gòu)恼Z(yǔ)法樹(shù)轉(zhuǎn)換過(guò)來(lái)的表達(dá)式會(huì)帶有冗余的轉(zhuǎn)換節(jié)點(diǎn)如Convert不提前歸約的話同樣邏輯的表達(dá)式會(huì)因?yàn)槭欠駧мD(zhuǎn)換節(jié)點(diǎn)而產(chǎn)生兩種維度序列緩存命中率和分支膨脹都會(huì)受影響提前歸約一次能省很多不必要的麻煩。