cache 的设计与实现--转载

本文整理自一下两篇博客：http://my.oschina.net/ScottYang/blog/298727http://my.oschina.net/u/866190/blog/188712

Cache简介：

Cache(高速缓存)， 一个在计算机中几乎随时接触的概念。CPU中Cache能极大提高存取数据和指令的时间，让整个存储器(Cache+内存)既有Cache的高速度，又能有内存的大容量；操作系统中的内存page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存，从而提高访问速度。Cache的算法设计常见的有FIFO(first in first out，先进先出)、LRU(least recently used，最近最少使用)和LFU（Least Frequently userd，最不经常使用)。

• LRU(Least Recently Used ，最近最少使用) —— 删除最久没有被使用过的数据

算法根据数据的最近访问记录来淘汰数据，其原理是如果数据最近被访问过，将来被访问的几概率相对比较高，最常见的实现是使用一个链表保存缓存数据，详细具体算法如下：

1. 新数据插入到链表头部；

2. 每当缓存数据命中，则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃；

 

• LFU(Least Frequently Used，最不经常使用) —— 删除使用次数最少的的数据

算法根据数据的历史访问频率来淘汰数据，其原理是如果数据过去被访问次数越多，将来被访问的几概率相对比较高。LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。具体算法如下：

1. 新加入数据插入到队列尾部（因为引用计数为1）； 
2. 队列中的数据被访问后，引用计数增加，队列重新排序； 
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除；

• FIFO(First In First Out ，先进先出)

算法是根据先进先出原理来淘汰数据的，实现上是最简单的一种,具体算法如下：

1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动； 
2. 淘汰FIFO队列头部的数据；

评价一个缓存算法好坏的标准主要有两个，一是命中率要高，二是算法要容易实现。当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。FIFO虽然实现很简单，但是命中率很低，实际上也很少使用这种算法。

---

面试题：Google和百度的面试题都出现了设计一个Cache的题目，什么是Cache，如何设计简单的Cache

• 解题思路：

Cache中的存储空间往往是有限的，当Cache中的存储块被用完，而需要把新的数据Load进Cache的时候，我们就需要设计一种良好的算法来完成数据块的替换。LRU的思想是基于“最近用到的数据被重用的概率比较早用到的大的多”这个设计规则来实现的。

为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满时，淘汰链表最后的位置就是了。 
注： 对于双向链表的使用，基于两个考虑。首先是Cache中块的命中可能是随机的，和Load进来的顺序无关。其次，双向链表插入、删除很快，可以灵活的调整相互间的次序，时间复杂度为O(1)。 
    查找一个链表中元素的时间复杂度是O(n)，每次命中的时候，我们就需要花费O(n)的时间来进行查找，如果不添加其他的数据结构，这个就是我们能实现的最高效率了。目前看来，整个算法的瓶颈就是在查找这里了，怎么样才能提高查找的效率呢？Hash表，对，就是它，数据结构中之所以有它，就是因为它的查找时间复杂度是O(1)。

梳理一下思路：对于Cache的每个数据块，我们设计一个数据结构来储存Cache块的内容，并实现一个双向链表，其中属性next和prev时双向链表的两个指针，key用于存储对象的键值，value用户存储要cache块对象本身。

• Cache的接口：

查询：

• 根据键值查询hashmap，若命中，则返回节点，否则返回null。
• 从双向链表中删除命中的节点，将其重新插入到表头。
• 所有操作的复杂度均为O(1)。

插入：

• 将新的节点关联到Hashmap
• 如果Cache满了，删除双向链表的尾节点，同时删除Hashmap对应的记录
• 将新的节点插入到双向链表中头部

更新：

• 和查询相似

删除：

• 从双向链表和Hashmap中同时删除对应的记录。

 

• 实现方式

    参考实现：Apache jcs

    1）首先我们需要一个双向链表，自然地，我们需要定义双向链表的节点：DoubleLinkListNode，DoubleLinkList

//  双向链表节点
public class DoubleLinkListNode implements Serializable{

    private Object value;
    public DoubleLinkListNode next;
    public DoubleLinkListNode prev;

    DoubleLinkListNode(Object value){
        this.value = value;
    }

    public Object getValue() {
        return value;
    }
}

对于 DoubleLinkList ,我们需要同步对节点的各种读写操作：

public class DoubleLinkList {

	private int size = 0;
	private DoubleLinkListNode first;
	private DoubleLinkListNode last;

	public DoubleLinkList(){
		super();
	}

	// 在链表的尾部的插入一个节点
	public synchronized void addLast(DoubleLinkListNode me){
		if (first == null) {
			first = me;
		}else{
			last.next = me;
			me.prev = last;
		}
		last = me;
		size++;
	}

	// 在链表的头部插入一个节点
	public synchronized void addFirtst(DoubleLinkListNode me){
		if (last == null) {
			last = me;
		}else{
			first.next = me;
			me.prev = first;
		}
		first = me;
		size++;
	}
	// 获取尾节点
	public synchronized DoubleLinkListNode getLast(){
		return last;
	}
	// 获取头结点
	public synchronized DoubleLinkListNode getFirst(){
		return first;
	}
	// 删除链表指定节点（这个节点一定在链表中）
	public synchronized boolean remove(DoubleLinkListNode me){
		if(me.next == null){
			//删除尾节点
			if (me.prev == null) {
				// Make sure it really is the only node before setting head and
                // tail to null. It is possible that we will be passed a node
                // which has already been removed from the list, in which case
                // we should ignore it

                if ( me == first && me == last ){
                    first = last = null;
                }
			} else {
				last = me.prev;
				last.next = null;
				me.prev = null;// gc 回收需要
			}
		}else if(me.prev == null){
			// 头结点
			first = me.next;
			first.prev = null;
			me.next = null;
		}else{
			// 中间节点
			me.prev.next = me.next;
			me.next.prev = me.prev;
			me.prev = me.next = null;
		}

		size--;
		return true;
	}

	// 删除链表所有元素
	// 注意不能只执行 first = last = null,这样会引起 OutOfMemory
	public synchronized boolean removeAll(){
		for(DoubleLinkListNode me=first;me!=null;){
			if (me.prev != null) {
				me.prev = null;
			}
			DoubleLinkListNode next = me.next;
			me = next;
		}
		first = last = null;
		size = 0;
		return true;
	}

	// 删除链表的尾节点
	public synchronized DoubleLinkListNode removeLast(){
		DoubleLinkListNode temp = last;
		if (last != null) {
			remove(last);
		}

		return temp;
	}

	// 将节点 node 移到头部
	public synchronized void makeFirst(DoubleLinkListNode node){
		if (node.prev == null) {
			// already the first node , or not a node
			return;
		}
		node.prev.next = node.next;
		if (node.next == null) {
			// last but the first
			last = node.prev;
			last.next = null;
		}else {
			//neither the last or the first
			node.next.prev = node.prev;
		}

		first.prev = node;
		node.next = first;
		node.prev = null;
		first = node;
	}

	public synchronized int size(){
		return size;
	}
}

    2）双向链表实现了，接着我们需要实现一个自定义的 LRUMap，根据 key 来存储 DoubleLinkListNode。这样我们就可以借助map 的hash 表来查询相对应的值。

·在给出实现之前，我们也许回想到，map 的键值对中，key 自己创建，而 value 就是 DoubleLinkListNode，来实现这个map，在 put 的时候，根据需要调整 cache 的容量即可（LRU 算法）。

如果是这样想得，那我们再反过来想，其实 map 本事就是一个容器，可直接用作 cache，直接使用 Map(Object key,Object value) 比使用 Map(Object key,doubleLinkListNode node)更好，可这样做的时候，就会出现一个问题，当我们需要删除一个对象，准确地说，是删除一个最近最久没有被使用过得对象，这样的操作原始的 map 结果是实现不了的；或许更进一步，你会想到，我们可以 map 里的每一个对象添加一个时间标记，这样在删除的时候，需要遍历每一个对象，找出时间标记为最早的那一个，直接就删除它（这样做，效率会很不好，需要O(n) 的时间）。说道这里，其实就是想说，借助双链表就是为了快速删除最近最久未被使用的对象，所以我们需要搭建一个描述符，来关联 hashMap 和 双联表之间的关系。

• 先实现一个 map 键值对描述符，如下：

public class LRUElementDescriptor extends DoubleLinkListNode {

	private Object key;

	public LRUElementDescriptor(Object key,Object value){
		super(value);
		this.key = key;
	}

	public Object getKey() {
		return key;
	}

	public void setKey(Object key) {
		this.key = key;
	}
}

接着实现一下LRUMap 基本的操作，如下：

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

@SuppressWarnings("unchecked")
public class LRUMap implements Map {

	// 在 LRUMap 里，需要使用到 map，DoubleLinkList
	private DoubleLinkList list = null;
	private Map map = null;

	private int maxSize = -1;	//cache 容量，< 0 时，表示容量不限
	private int chunkSize = 1;	//当cache 溢出时，需要删除对象的个数,最好验证 chunkSize < maxSize

	public LRUMap(){
		list = new DoubleLinkList();
		map = new HashMap();
	}

	public LRUMap(int size){
		this();
		this.maxSize = size;
	}

	public void clear() {
		map.clear();
		list.removeAll();
	}

	public boolean containsKey(Object key) {
		return map.containsKey(key);
	}

	public boolean containsValue(Object value) {
		return map.containsValue(value);
	}

	//返回 key-value 值，注意不是 key-DoubleLinkListNode
	public Set entrySet() {
		Set entries = map.entrySet();
		Set unWraped = new HashSet();
		Iterator it = entries.iterator();
		while (it.hasNext()) {
			Entry pre = (Entry) it.next();
			Entry post = new LRUMapEntry(pre.getKey(),((LRUElementDescriptor)pre.getValue()).getValue());;
			unWraped.add(post);
		}
		return unWraped;
	}

	public Object get(Object key) {
		Object value = null;
		LRUElementDescriptor elem = (LRUElementDescriptor)map.get(key);

		if (elem !=null) {
			value = elem.getValue();
			list.makeFirst(elem);
		}
		return value;
	}

	public boolean isEmpty() {
		return map.size() == 0;
	}

	public Set keySet() {
		return map.keySet();
	}

	public Object put(Object key, Object value) {
		LRUElementDescriptor old = null;

		synchronized (this) {
			addFirst(key, value);

			old = (LRUElementDescriptor) map.put(((LRUElementDescriptor)list.getFirst()).getKey(),list.getFirst());
			// 若已经存在于缓存里，则删除旧的
			if (old != null && ((LRUElementDescriptor)list.getFirst()).getKey().equals(old.getKey())) {
				list.remove(old);
			}
		}
		// 判断是否溢出，若溢出，则删除最后 chunkSize 个元素
		int size = map.size();
		if (this.maxSize >=0 && this.maxSize < size) {
			for(int i = 0;i<chunkSize;i++){
				LRUElementDescriptor last = (LRUElementDescriptor) list.getLast();
				if (last != null) {
					map.remove(last.getKey());
				}else{
					System.err.println("update: remove failed for key:"+last.getKey());
				}
				list.removeLast();
			}
		}

		// Map.put 操作的返回值
		if(old != null){
			return old.getValue();
		}

		return null;
	}

	public synchronized void addFirst (Object key,Object value){
		LRUElementDescriptor elem = new LRUElementDescriptor(key,value);
		list.addFirtst(elem);
	}

	public void putAll(Map source) {
		if (source != null) {
			Set entries = source.entrySet();
			Iterator it = entries.iterator();
			while (it.hasNext()) {
				Entry elem = (Entry) it.next();
				// 这里不是使用 map.put，因为这样 DoubleLinkList 就会失去作用
				this.put(elem.getKey(), elem.getValue());
			}
		}
	}

	public Object remove(Object key) {

		LRUElementDescriptor elem =(LRUElementDescriptor) map.remove(key);
		if (elem != null) {
			list.remove(elem);
			return elem.getValue();
		}
		return null;
	}

	public int size() {
		return map.size();
	}

	// DoubleLinkListNode 的集合
	public Collection values() {
		return map.values();
	}

}

原文：http://peiquan.blog.51cto.com/7518552/1558294