【IT168技术文档】

转载自Jeff Zhao的博客

    终于到了这个系列的最后一篇文章了，这个系列的文章本是许多话题的基础，却拖了那么长时间还没有完结。这篇文章主要讨论五种缓存方式各自的优劣，以及他们的性能关键在什么地方，如果要进行改进又有什么可选方案。在这个问题上，老赵的思考可能会有遗漏，如果您有任何补充，也请不吝指出。

　SimpleKeyCache

　SimpleKeyCache是最直接的缓存方案：将表达式树进行完整编码，将其转化为一个少有的字符串，然后作为Key存放到字典中。

　从上一篇文章的实验来看，无论从耗时还是对GC造成的压力上来说，SimpleKeyCache都是五种缓存方案中最差的。这一点倒很容易理解。因为在.NET中拼接字符串是一种相对来说消耗巨大的操作。而将一个表达式树进行完整编码，势必要将它的各种信息都存放到字符串中。此时您就会发现，例如表达式树的每个节点中的Type或MemberInfo信息会占用较大的空间，同时一颗表达式树内部的节点数量也可能比较可观。两者相辅相成，使得构造一个字符串的代价就非常显著了。

　不过，SimpleKeyCache的优点是什么呢？它的优点就在于，它是五种缓存方案中唯一“能够任意重现”的方案。也就是说，无论是在哪台机器上，无论是哪一次启动，相同表达式树的编码结果是不变的。这也是实现“分布式存储”的必要条件。之前文章中所提到的各种缓存方案都是在单个进程内实现的，因此只要在程序启动之后某些必要信息不会改变（例如某个对象的GetHashCode调用结果）即可。但是在分布是存储环境中，会出现多个进程多台机器，如果它们产生的“键”无法保持不变，就无法使用相同表达式树进行可持续的通信了。

　如果您真的在“分布式存储”环境，或是其他需要“稳定”特性的场景下（例如把一个表达式树存入数据库）使用表达式树作为标识符，那么您可以选择的做法可能是优化编码方案了。例如，您可以把最终的字符串进行分段，在header中写入Type对象的信息并为它指定一个简短的表识符，这样在字符串的body里就可以省去对大量数据的重复了。

　不过，复杂的编码也可能带来额外的运算开销，对于性能不一定会带来好处。因此，在得出确定的结论之前，一定要对实现进行性能评测，不用感觉，而是用数据说话。

　PrefixTreeCache

　PrefixTreeCache使用了前缀树作为存储数据结构。它将表达式树转化为一个单一序列，并使用Hashtable来作为前缀树的单个节点，形成了一个粗略的表达式树。

　与SimpleKeyCache相比，PrefixTreeCache省去了大量的字符串拼接操作，节省了客观的内存占用，因此在GC上与前者相比有了非常明显的改善。但是从结果上看，其性能并不如理论上来的高。老赵认为这是因为我们的实现过于粗糙导致的。.NET类库中的Hashtable性能应该很难进一步提到（因为从代码上看并没有发现明显需要优化的地方——老赵是指只读环境中），因此我们只能设法优化自己的实现。

　我们在表达式树的每一层进行查询时会根据当前节点的信息构造一个匿名对象，并作为Key去Hashtable中进行查询。大量的匿名对象造成了GC压力在五种缓存中仅仅落后SimpleKeyCache，而遥遥领先于其余三种方案。从编译器自动生成的类型上看，其GetHashCode方法和Equals方法的实现并没有明显的性能方面问题。因此我们优化的着眼点，似乎只有在对Hashtable的查询次数上了。

　我们的实现中对于Hashtable的查询次数的确太多。为了编程方便，每一个节点至少会对有两次查询，因此一个拥有20个节点的表达式（这个数量并不多）就会进行40次以上的查询。对于PrefixTreeCache，我们需要设法减少Hashtable的查询次数。例如，我们其实完全可以把每一个节点的查询次数简化到1次。更进一步，我们可以设法把两个节点并作一个进行查询，就好比传统前缀树实现中的优化方式一样。只是这样做的话编程就变得非常复杂了。

　PrefixTreeCache的实现似乎并没有太大优化的余地，而它的性能也不是太好。因此，老赵目前还想不到什么情况下适合使用这种存储方案。