前一段时间我在推进一个动态查询服务业务方把筛选条件直接以结构化的方式传给后端后端要把这些条件拼成表达式树再编译成委托塞给数据访问层。量小的时候一切正常等压测一上来CPU 直接被打到 80% 以上——不是查询慢而是卡在表达式树的构建和 Compile 上。那一刻我才真正意识到两件事第一表达式树的构建和编译成本比想象中高得多第二对这个东西做缓存并没有一开始想的“放个字典”那么简单。后来我换了个思路把缓存结构从前缀树的角度重新做了一版效果非常明显。这篇内容就是把我完整的思考过程、踩过的坑、落地的代码细节都整理出来。如果你也在做动态 LINQ、对象映射器、规则引擎、或者任何需要频繁构造和编译表达式树的服务这篇文章大概率能帮你省下不少 CPU。1. 表达式树缓存为什么没有想象中简单1.1 表达式树不是普通对象没法直接当字典键很多人第一反应是缓存嘛搞一个Dictionaryobject, T不就行了。表达式树本身是对象直接用实例做 key 不行吗不行。表达式树内部是一堆对象引用互相连接根节点是一个 LambdaExpression下面挂 BodyBody 里又有 Left、Right、Arguments 之类的子节点。最关键的问题是两个逻辑上完全等价的表达式例如ExpressionFuncUser, bool expr1 u u.Age 18; ExpressionFuncUser, bool expr2 v v.Age 18;它们在运行时创建出来完全不同的对象图。expr1和expr2的引用不相等内部的 MemberExpression、ParameterExpression、ConstantExpression 也全部是独立实例。你用ReferenceEqualityComparer做 key同一个逻辑的表达式也会被当成不同条目缓存命中等于零。有人可能会说那我把表达式树转成字符串存字典不就好了。这个方向是对的但里面藏着很多坑下面单独说。1.2 字符串 Key 方案的三个硬伤字符串方案是网上最常见的做法核心思路就是expr.ToString()或者序列化成某种文本形式然后用这个字符串当 key。我在第一版也是这么干的跑了一段时间后发现三个硬伤。第一个硬伤是ToString()的输出不稳定。表达式树的ToString生成的字符串在不同运行环境下并不是完全等价的。比如常量decimal或double的格式化可能受当前 Culture 影响一元表达式可能会因为括号层级不同产生不一样的输出形式甚至有些自定义表达式节点的ToString行为完全不可控。一旦 key 不稳定同一个表达式在某个线程下生成 key A在另一个线程下生成 key B缓存就形同虚设。第二个硬伤是字符串生成本身的代价。expr.ToString()是一次完整的树遍历每次请求都先遍历整棵树生成字符串再用字符串去字典里查找。这等于把“构建表达式树”的解析成本省了但遍历成本和字符串分配成本全留下了。表达式一复杂字符串长度轻松上千字符字符串比较又得逐字符比对算下来并没有比重新 Compile 快太多。第三个硬伤是字符串 key 的内存浪费。一个表达式转成字符串动不动几百上千字符如果业务请求有几千上万个变体光 key 就吃掉不少内存。而且字符串 key 和表达式树的内部结构完全是两种维度如果你后续想调整匹配规则比如忽略参数名、忽略某些子表达式用字符串做 key 会非常痛苦因为你还得先做字符串解析和正则替换。1.3 缓存命中之后还要考虑编译阶段还有一个很容易被忽略的点缓存的目标到底是什么。如果只缓存“表达式树对象”命中了确实省掉了重新Expression.XXX()一堆方法调用的时间但表达式树被使用的时候往往还要Compile()成委托。Compile()阶段涉及 IL 生成、类型元数据读取、委托构造这部分成本在大多数场景下比“构建表达式树”还高尤其是需要反射访问复杂成员或调用链很长的时候。所以我在设计缓存的时候目标从一开始就不是“缓存表达式树”。而是直接把“同一个结构的表达式”对应的已编译委托缓存下来。这样命中后连Compile()都省了。而表达式树对象本身只是当 key 的匹配依据。这个目标设定决定了后面整个数据结构的选择。2. 前缀树凭什么适合承载表达式树缓存2.1 前缀树的一层对应表达式树的一层前缀树也叫 Trie本质上是一种多叉树。它的特点是根节点不存数据树的每一层对应判定序列中的一环从根到叶子的路径拼起来就是完整的判定序列。和普通字典相比它的最大优势是能自动共享前缀。那这件事和表达式树有什么关系关系很大因为表达式树本身就是一棵树。两棵表达式树如果结构相似它们的前半段路径大概率是重叠的。比如u u.Age 18 v v.Age 18这两棵树从根节点的 Lambda 开始参数类型相同Body 是一个二元比较节点二元节点的 NodeType 都是 GreaterThan左子节点都是访问 User 的 Age 属性右子节点都是常量 18。如果用“节点的类型和特征”组成判定序列那么这两棵树的判定序列从头到尾完全一致自然会在前缀树中走到同一条路径最终命中同一个缓存项。这就是前缀树相比字典的底层优势字典的 key 是整体匹配前缀树的匹配是逐层进行的结构越相似匹配过程中越早汇合天然支持结构共享。2.2 维度序列把树压平成逐层判定要使用前缀树首先得把一棵“树”变成一个“序列”。这个序列不是简单地把所有节点平铺而是要保证父节点的判定特征在序列中一定出现在子节点之前。这样前缀树的每一层对应表达式树中的某一层从根开始逐层对齐。我做了一个叫“维度序列”的东西。树的每个节点转化成一条边Edge一条边包含三个字段节点的表达式类型NodeType比如GreaterThan、MemberAccess、Constant、Parameter。子节点数量ChildCount用来区分同一类型但子结构不同的情况。辅助哈希AuxHash用来细化特征比如成员访问的成员名、方法调用的方法签名、参数的类型、常量值的类型和值哈希。举个具体例子表达式u u.Age 18的维度序列大致是Lambda(参数类型: User, 参数个数: 1) - GreaterThan(子节点: 2) - MemberAccess(User.Age, 子节点: 1) - Parameter(User) - Constant(int, 18)注意我在这里把 Lambda 的参数类型和数量也放进了序列。这一点很重要因为两个表达式即使 Body 完全一样如果参数类型不同语义也不同必须区分开。后续每一步都沿着先序顺序继续展开直到叶子节点。把这个序列放进前缀树里等于给每个表达式建立一条路径。查找时只需要拿着同样方式生成的维度序列从前缀树根节点开始逐层往下走即可。2.3 对照前缀树 vs 字典 vs 表达式比较器这里我简单做一个方案对比方便大家看清为什么最终选了前缀树。方案命中粒度查询复杂度实现成本典型问题字符串作为 key整体匹配O(字符串长度)低ToString 不稳定、字符串分配大、无法忽略参数名引用相等做 key只有同一个实例命中O(1)极低等价表达式无法命中形同虚设规范化后比较结构等价命中O(树规模)高每次比较都遍历全树没有共享前缀树前缀共享O(序列深度)中需要处理规范化、分支膨胀但查找非常快这里的“规范化后比较”是指用微软的表达式比较器一类工具把每个节点逐个比对。如果缓存里存了 1 万条表达式来一个新表达式要依次比对 1 万次每次都是一次完整树遍历。前缀树则是直接按维度序列寻径查一次树的深度也就是表达式树的深度完全不管缓存里有多少条这是数量级上的差异。3. 落地实现节点设计、归一化与增删查3.1 边结构 TrieEdge 与节点结构先定义边。边就是我在 2.2 里说的维度序列中的一个元素。这里我用一个只读结构体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)的组合哈希如果是方法调用就是方法名、声明类型、方法签名的组合哈希如果是常量节点就是常量值的类型哈希加上值本身的哈希。总之辅助哈希的目的是区分“同类型、同子节点个数但语义不同”的节点。接下来是前缀树节点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); } }这个节点的结构很简单每个节点存三个东西子节点字典、是否已有缓存值、缓存下来的表达式和编译委托。3.2 参数重命名与闭包展开这部分是整个方案真正的核心也是我踩坑最多的地方。如果直接拿原始表达式树生成维度序列那么u u.Age 18和v v.Age 18会被判定为两条完全不同的路径因为公共语言运行时会认为u和v是两个不同的 ParameterExpression 实例。所以必须先做“参数归一化”。我实现了一个参数重写器本质是把 Lambda 里出现的所有参数按“第一次出现顺序”统一改名为p0、p1这样的占位符之后再插入前缀树。这样两个逻辑等价但参数名不同的表达式生成的维度序列就完全一致了。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里必须先重写参数节点本身再重写 Body。而且同一个 ParameterExpression 实例可能在 Body 中出现多次VisitParameter里的字典会保证同一个实例始终映射到同一个归一化参数。另一件必须处理的事情是闭包展开。动态查询里经常会写int minAge GetMinAgeFromConfig(); ExpressionFuncUser, bool expr u u.Age minAge;minAge会被编译器捕获成闭包然后在表达式树里体现为一个ConstantExpression这个常量的值是一个编译器生成的闭包对象。问题是每次调用GetMinAgeFromConfig()闭包对象都是新的哪怕minAge的值一模一样表达式树的常量节点引用也不一致缓存照样不命中。解决办法是在参数归一化之前先把闭包里的字段“摊开”成真正的常量值。我用一个自定义的表达式访问器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); } }这段代码的作用是如果发现成员访问的“源”是一个编译器生成闭包就反射读取字段的值。如果是基础类型直接替换成常量节点。这样u.Age minAge就变成了u.Age 3030 这个值直接参与哈希计算闭包对象的版本差异就被消除掉了。这里有个边界必须小心如果闭包字段的值是引用类型而且后面还继续访问它的子成员一层展开就可能不够。比如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 实例引用)那这个实例引用每次可能还是不同。这种情况我目前的处理方法是如果第一层展开后仍然是个比较复杂对象的实例就递归往下展开字段直到遇到基础类型如果递归层数太深就直接放弃缓存该表达式走原来的编译逻辑。这个策略对大多数业务场景已经够用。3.3 插入和查找的完整过程把表达式“洗”干净之后剩下的就是生成维度序列并插入前缀树。我用一个递归函数按先序顺序把整棵表达式树压平为一条边序列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: // 其他不常见节点类型直接按类型哈希走 edges.Add(new TrieEdge(node.NodeType, 0, node.Type.GetHashCode())); break; } }GetValueHash对于值类型直接调GetHashCode()对于字符串也直接用字符串哈希对于其他对象则退回到引用哈希防止把一个大对象序列化进来导致性能劣化。有了边序列之后插入和查找就非常简单了。插入是从根节点开始按边序列挨个走走到哪没有子节点就创建一个直到序列结束然后在终点节点塞入表达式和编译委托。查找则完全一样地走如果中途任一层找不到对应边直接返回未命中。这里我把提交编译委托和查找合并成一个方法public Delegate GetOrCompileTDelegate( ExpressionTDelegate seed, FuncExpressionTDelegate, Delegate compiler) where TDelegate : Delegate { // 1. 闭包展开 var expanded new CaptureExpander().Visit(seed); // 2. 参数归一化 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参数不需要由调用方传内部直接调expression.Compile()就行。我这里留成一个委托参数是为了方便测试时替换各位可以直接写成Compile()。3.4 并发读写的一个可落地方案前缀树和普通字典不一样它不能靠一个简单的 ConcurrentDictionary 就解决并发问题因为一次插入要沿着路径创建多个节点。如果两个线程同时插入同一个前缀路径很容易在中间节点上产生竞争。我用的方案是GetOrAddNode这一步在锁内做双重检查。上面代码里已经体现了if (!current.TryGetNode(edge, out var next)) { lock (current) { next current.GetOrAddNode(edge); } }这里 lock 的对象就是当前节点。因为TrieEdge是只读结构体节点的子节点字典只在插入时修改查找时只读。两个线程同时走到同一节点时都尝试在它的_children里加同一条边但加锁保证了只有一个线程真正创建新节点另一个线程走完锁之后发现已经有了直接复用。对于读多写少的服务里这个锁竞争几乎可以忽略不计。因为它只在“第一次遇到某个边”时才触发后续所有请求都是纯字典读取不碰任何锁。如果你追求极端并发性能可以在每个节点上用一个ReaderWriterLockSlim但就我的实测来看双重检查锁已经足够。还有一点值得注意如果某个分支走完整个序列后发现没有缓存值并发插入还没完成可能会产生重复编译。我目前的策略是拿到终点节点后先看有没有值没有就编译编译结束后再SetValue。在多线程下可能出现同一路径被编译多次的情况但因为后续线程都能复用第一次写入的值所以最多只会多编译几次不会造成正确性问题。如果你接受不了这点可以在终点节点上加一个LazyDelegate做单次初始化效果更好。4. 实测效果、边界情况与两个重要提醒4.1 三套方案的对比数据为了验证这套方案到底值不值得做我写了一个模拟测试生成了 10 万条结构不同但有一定重合度的动态表达式所有表达式都是User类型上的谓词组合包含属性访问、常量比较、字符串匹配、闭包捕获然后分别用无缓存、字符串字典缓存、前缀树缓存跑了一遍。需要说明的是这个测试是为了横向比较方案之间的相对差异不是造数据吹一个绝对数字。不同机器、不同表达式复杂度一定会导致绝对值变化但相对关系是稳定的。方案平均单次总耗时命中率内存占用趋势无缓存每次构建加编译约 1.2ms0每次请求都会产生新对象GC 压力最大字符串 key 字典缓存约 0.35ms能命中但受 ToString 稳定性影响字符串 key 和表达式树都存着中等前缀树缓存委托约 0.08ms结构等价即可命中含参数名无关匹配节点多分支多内存偏高但可控最直观的感受是前缀树方案比字符串方案快了 4 倍左右和完全无缓存比快了 15 倍。字符串方案最大的开销其实不在字典查找而是在每次请求生成ToString()的字符串和后续字符串哈希。前缀树方案省掉这一步而且查询是逐结构走路径走完基本就到底了几乎没什么额外计算。4.2 常量对象引用导致的假不命中前缀树方案有一个非常大的坑第一次跑测试时我花了好长时间才定位出来常量节点的哈希不能用对象引用否则缓存命中率会断崖式下跌。举个例子用户查询City Shanghai每次生成的ConstantExpression都是一个新的string对象。虽然字符串的GetHashCode()是按内容算的所以对于字符串还好。但如果常量是某一个自定义配置对象比如ExpressionFuncUser, bool expr u u.Category currentCategory;其中currentCategory是一个Category对象每次请求从数据库加载出来都是新实例。如果哈希直接currentCategory.GetHashCode()那引用变了哈希就变缓存必然不命中。我的解决办法是在GetValueHash里做一个分支判断只有值类型、字符串、decimal、DateTime、Guid 这类“语义值”参与哈希计算其他对象一律退回“类型哈希”而不是对象哈希。这样即使闭包对象每次都是新实例只要类型相同常量节点就被认为是同一个维度上的后续闭包展开已经把真实值替换成基础类型所以这个退化策略不会造成语义错误。如果业务里确实需要缓存“复杂对象常量值”不同的表达式那就要给这个对象的 “Equals” 和GetHashCode做好值语义或者把它序列化成稳定字符串再参与哈希。否则就老实让缓存失效不要为了追求命中率引入错误风险。4.3 分支膨胀与定期裁剪前缀树也有自己的代价它把大量公共前缀拆成了很多细粒度节点每一条没命中过的分支都会在树里留下永久节点。如果业务表达式变化非常零散缓存分支可能会不成比例地膨胀。我第一次上线时没处理这个问题运行了一周后看内存发现前缀树占用的内存比所有缓存表达式委托加起来还要多。原因是很多请求是“一次性变体”某个表达式只出现过一两次但它在树上留下了一条完整路径这条路径永远不会再被访问。后来我加了一个轻量级计数器每个节点记录最后一次访问的时间戳和命中次数。定时任务每小时扫描一次把所有叶子节点那一侧、访问次数为零、且超过一段时间未访问的分支剪掉。注意裁剪一定要从叶子往上剪不能从中间切否则会把有缓存值的根路径误删。对于大多数业务其实可以先不加裁剪功能但要心里有数如果缓存条目的规模在千万级以上内存控制就会变成主要矛盾。4.4 跨进程一致性提醒还有一个容易踩的坑字符串和哈希值在不同的 .NET 运行时版本之间不具备跨进程一致性。string.GetHashCode()在 .NET Core 3.0 之后开始引入进程内随机化同一个字符串在不同进程里算出来的哈希很可能不一样。PropertyInfo.GetHashCode()也类似它和反射对象的元数据身份绑定不同进程加载同一个类型时返回的哈希不一定相同。所以这种前缀树缓存只能用在进程内缓存场景千万不要把辅助哈希值算好后塞进 Redis 或者其他分布式缓存里再拿去跨进程匹配。如果你真要做分布式表达式缓存那就得先定义一套完全确定性的规范化序列化协议把这个协议作为 key前缀树只负责进程内的快速匹配。序列化的成本会吃掉一部分性能优势所以我的建议是如果分布式是硬需求进程内只缓存编译委托分布式只缓存表达式树的内容别混着用。5. 我的实践体会与后续扩展这套方案我从最初用字符串字典踩坑到后来改成前缀树最大的感受是表达式树这种结构用线性容器去承载是天然不舒服的它本身就是树让缓存结构也贴近树的形态才是顺理成章的事。在这个实现里我每次比对一个节点都不会递归整棵子树而是走一条路径这条路径的长度最多就是表达式树的深度。这也是为什么在表达式数量的规模变大之后前缀树方案的性能曲线依然很平坦而字典方案早就开始肉眼可见地变慢了。如果以后要继续往下做我可能的扩展方向有这么几个一是把边序列生成器从硬编码的 switch 改成基于表达式访问器的可扩展管线方便接入自定义表达式节点二是把节点内的子节点字典在某些高热点分支上替换成固定数组用索引访问代替字典哈希进一步降低单次查找的常数因子三是把闭包展开逻辑做更深层的递归配合类型缓存把任意深度的闭包字段自动替换成值常量这样动态查询的缓存命中率还能再往上走一截。最后说一个很多人会忽略的小技巧处理表达式树之前先调用一次Expression.CanReduce看看节点能不能归约。不少从语法树转换过来的表达式会带有冗余的转换节点如Convert不提前归约的话同样逻辑的表达式会因为是否带转换节点而产生两种维度序列缓存命中率和分支膨胀都会受影响提前归约一次能省很多不必要的麻烦。