锁定老帖子 主题:缓存策略之LRU实现(基于双链表实现)
精华帖 (11) :: 良好帖 (0) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2010-06-15
最后修改:2010-06-17
缓存在应用中的作用,相信不用多说,对性能是具有质的提升的,而目前的缓存策略常用的FIFO,LRU等等。 今天来探讨一下 LRU这种缓存策略的底层原理与实现。
首先,来看看LRU的定义: Least recently used. 可以理解为, 最少使用的被淘汰。
今天主要来讨论基于双链表的LRU算法的实现, 在讨论之前,我们需要了解一下,传统LRU算法的实现,与其的弊端。
传统意义的LRU算法是为每一个Cache对象设置一个计数器,每次Cache命中则给计数器+1,而Cache用完,需要淘汰旧内容,放置新内容时,就查看所有的计数器,并将最少使用的内容替换掉。 它的弊端很明显,如果Cache的数量少,问题不会很大, 但是如果Cache的空间过大,达到10W或者100W以上,一旦需要淘汰,则需要遍历所有计算器,其性能与资源消耗是巨大的。效率也就非常的慢了。
基于这样的情况,所有就有新的LRU算法的实现----基于双链表 的LRU实现。 它的原理: 将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。 这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而想链表后面移动,链表尾则表示最近最少使用的Cache。 当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。
上面说了这么多的理论, 下面用代码来实现一个LRU策略的缓存。 我们用一个对象来表示Cache,并实现双链表,
public class LRUCache { /** * 链表节点 * @author Administrator * */ class CacheNode { …… } private int cacheSize;//缓存大小 private Hashtable nodes;//缓存容器 private int currentSize;//当前缓存对象数量 private CacheNode first;//(实现双链表)链表头 private CacheNode last;//(实现双链表)链表尾 }
下面给出完整的实现,这个类也被Tomcat所使用( org.apache.tomcat.util.collections.LRUCache),但是在tomcat6.x版本中,已经被弃用,使用另外其他的缓存类来替代它。
public class LRUCache { /** * 链表节点 * @author Administrator * */ class CacheNode { CacheNode prev;//前一节点 CacheNode next;//后一节点 Object value;//值 Object key;//键 CacheNode() { } } public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable(i);//缓存容器 } /** * 获取缓存中对象 * @param key * @return */ public Object get(Object key) { CacheNode node = (CacheNode) nodes.get(key); if (node != null) { moveToHead(node); return node.value; } else { return null; } } /** * 添加缓存 * @param key * @param value */ public void put(Object key, Object value) { CacheNode node = (CacheNode) nodes.get(key); if (node == null) { //缓存容器是否已经超过大小. if (currentSize >= cacheSize) { if (last != null)//将最少使用的删除 nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new CacheNode(); } node.value = value; node.key = key; //将最新使用的节点放到链表头,表示最新使用的. moveToHead(node); nodes.put(key, node); } /** * 将缓存删除 * @param key * @return */ public Object remove(Object key) { CacheNode node = (CacheNode) nodes.get(key); if (node != null) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (last == node) last = node.prev; if (first == node) first = node.next; } return node; } public void clear() { first = null; last = null; } /** * 删除链表尾部节点 * 表示 删除最少使用的缓存对象 */ private void removeLast() { //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象) if (last != null) { if (last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } /** * 移动到链表头,表示这个节点是最新使用过的 * @param node */ private void moveToHead(CacheNode node) { if (node == first) return; if (node.prev != null) node.prev.next = node.next; if (node.next != null) node.next.prev = node.prev; if (last == node) last = node.prev; if (first != null) { node.next = first; first.prev = node; } first = node; node.prev = null; if (last == null) last = first; } private int cacheSize; private Hashtable nodes;//缓存容器 private int currentSize; private CacheNode first;//链表头 private CacheNode last;//链表尾 }
PS: 首先感谢各位给帖子投票的朋友, 不管你是投的新手贴,还是精华帖,都是对我的鼓励, 对于帖子中大量谈到的并发问题,这个实现在写之前确实是没有考虑的。 帖子的本意只是向不清楚LRU实现的朋友,展示这种算法的实现而已,并非是专门讲并发性问题的。 对于帖子中谈到的并发问题, 稍后有时间,我会写一个稍微完善一点的实现,贴出来, 到时候,再跟大家探讨探讨。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2010-06-15
这种模型是理论上有的并且使用在缓存技术上面,还是你自己想的?
|
|
返回顶楼 | |
发表时间:2010-06-15
beneo 写道 这种模型是理论上有的并且使用在缓存技术上面,还是你自己想的?
很多缓存都是这种模型,例如ehcache |
|
返回顶楼 | |
发表时间:2010-06-15
sky3380 写道 beneo 写道 这种模型是理论上有的并且使用在缓存技术上面,还是你自己想的?
很多缓存都是这种模型,例如ehcache 是的,很多缓存都有这样的缓存策略,比如Ibatis中的缓存策略就有……,还有楼上说的ehcache。 |
|
返回顶楼 | |
发表时间:2010-06-15
可以看看commons-beanutils里的一个基于SequenceHashmap的实现
|
|
返回顶楼 | |
发表时间:2010-06-16
Zahir 写道 可以看看commons-beanutils里的一个基于SequenceHashmap的实现
thanks,我会去看看 |
|
返回顶楼 | |
发表时间:2010-06-16
我看这缓存实现没有带锁?
|
|
返回顶楼 | |
发表时间:2010-06-16
对这个没什么研究
不过从字面意义上来说 Least recently used 最近被使用和最多被使用就是不一样的好吧…… 最近被使用不一定是最多被使用 在清理缓存的时候有一定偶然性 |
|
返回顶楼 | |
发表时间:2010-06-16
这么做的话,淘汰旧数据的效率是高了,可是每次检索时的开销增加了,不知道楼主测试过这个影响没?
|
|
返回顶楼 | |
发表时间:2010-06-16
的确每次用的时候检索速度增加了并且也增加了维护链表的代价。
|
|
返回顶楼 | |