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