关于LRU命中算法的改进想法

    LRU最近最久未使用的淘汰，这是现阶段应用最广泛的cache命中算法。现阶段应用的LRU算法一般是基于双链表实现的，这个算法的好处是，在查找cache和查找淘汰页面的复杂度都是O(1)，只要cache空间足够大，这个命中率是相当不错的。原理如下：
    整个cache是放在一个HashMap中，页面有key和value值，同时将Cache的所有位置都用双连表连接起来，当一个页面被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，如果是新加入的Cache那么就直接加到链表头中。
    如此循环，在多次查找命中和淘汰后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最久未使用的Cache。当需要替换页面的时候，链表的最后位置就是最应该被淘汰的位置，算法就只需要淘汰链表最后页面。
    下面是tomcat所使用的一个LRU算法：

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;//链表尾
}

    上几周，我导师和我谈了下关于LRU算法的改进，由上我们可以知道，LRU是没有计数功能的，也就是说如果我一个页面是处于一种周期性访问的性质，而每次这个页面到来访问cache的时候它已经被淘汰了，但是其实它是属于周期性经常访问的页面内容，下面举个实例：
    比如我设cache的大小是8，而来的页面内容是1，2，1，4，5，5，7，8，9，10，11，1，12，13，5，14，15，16，17，20，1，3，18，5
如果是上面这种情况，你会发现cache命中次数为2。很悲剧的一种情况，但是很可能常见，好了下面我们来探讨下我改进这个LRU算法的思想：
    既然LRU没有计数功能，那么我们就给它一个计数参数，但是我们要保证查找cache和查找淘汰页面的复杂度都是小于O(n)的，不然代价会太高了。好我先在建立一个HashMap的时候除了key和value，再增加一个count。初始的时候cache中没有页面，如果是新加入的Cache那么就直接加到链表头中。同时count=0+200，当一个页面被命中之后，还是和上面规则一样将通过调整链表的指向，将该位置调整到链表头的位置，同时count=count+200。
    如此循环，但是替换规则次数要调整了，（不然要count做什么呢 哈哈）。替换规则是这样的，我们设定一个K=3的参数，每次没有命中的页面需要替换页面的时候，我们就去比较链表最后的k个页面count值最小的页面，然后把新的页面加在链表的最前面，把最后面k个页面中count值最小的页面淘汰了。
    基于这个规则我们在来看上面那个例子，你会发现cache命中次数为6了。当然只是一个特例还没有大规模测试，同时你会提出一个问题，很有可能有情况就是开始一个页面的访问次数特别多，然后count值很高如果这样是不是这个页面就没办法淘汰了，也许后来它根本就不被访问的。恩！我也这么想的，所以继续改进，在有count后我们还要设定一个规则，就是衰减规则。我们不能让count一成不变，根据我们cache访问的特点。我们可以在设定一个p值，这个p值是每次访问的衰减率，也就是每次访问我们自动对cache里面页面所有的count值减去一p的衰减值，这样如果它之后久久不被访问，那么它也会马上被淘汰。
    （如有建议请跟帖，如有错误请指正，第一次发博客@.@）

评论

1 楼 mht19840918 2010-08-30  

没有考虑线程同步问题！