关于LRU缓存的实现算法讨论

关于LRU缓存的实现算法讨论2011-09-30 cnblogs 蛙蛙业务模型

读、写、删的比例大致是7:3:1，至少要支持500w条缓存，平均每条缓存6k，要求设计一套性能比较好的缓存算法。

算法分析

不考虑MemCached，Velocity等现成的key-value缓存方案，也不考虑脱离.NET gc自己管理内存,不考虑随机读取数据及顺序读取数据的场景，目前想到的有如下几种LRU缓存方案

算法	分析
SortedDictionary	.NET自带的，内部用二叉搜索树（应该不是普通树，至少是做过优化的树）实现的，检索为O （log n），比普通的Dictionay（O（1））慢一点。插入和删除都是O（log n），而且插入和删除，会实时排序。但是.NET 2.0的这个类没有First属性
Dictionary + PriorityQueue	Dictionay可以保证检索是O（1）；优先队列可以保证插入和删除都为O（log n）；但是优先队列删除指定的项不支持（至少我找到的优先队列不支持），所以在删除缓存的时候不知道咋实现
Dictionay + Binary heap	二叉堆也是优先队列，分析应该同上，我没有详细评估。
b树	查找，删除，插入效率都很好，数据库都用它，但实现复杂，写一个没有BUG的B树几乎不可能。有人提到stl:map是自顶向下的红黑树，查找，删除，插入都是O（log n），但咱不懂c++，没做详细测试。
Dictionay + List	Dict用来检索； List用来排序；检索、添加、删除都没问题，只有在清空的时候需要执行List的排序方法，这时候缓存条目比较多的话，可能比较慢。
Dictionay + LinkedList	Dict用来检索； LinkedList的添加和删除都是O（1），添加缓存时在链表头加节点，获取缓存时把特定节点移动（先删除特定节点（O（n）），再到头部添加节点（O（1）））到头，缓存满地时候截断掉尾部的一些节点。

目前几种方案在多线程下应该都需要加锁，不太好设计无锁的方案，下面这个链接是一个支持多线程的方案，但原理至今没搞特明白

A High Performance Multi-Threaded LRU Cache

http://www.codeproject.com/KB/recipes/LRUCache.aspx