什么是缓存以及它的实现算法 2015.05.05

原文：http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html

什么是缓存

缓存就是存贮使用频繁数据的临时地方，因为取原始数据的代价太大，所以它可以获取的更快一些

Cache算法

• Least Frequently Used(LFU)
  计算每个缓存对象被使用的频率，然后把最不常用的缓存对象踢走 实现code:

  public synchronized Object getElement(Object key){
  	Object obj;
  	obj=table.get(key);
  	if(obj!=null){
  		CacheElement cacheElement=(CacheElement)obj;
  		element.setHitCount(element.getHitCount()+1));
  		return element.getObjectValue();
  	}
  	reteurn null;
  }
  public final synchronized void addElement(Object key,Object value){
  	Object obj;
  	obj=table.get(key);
  	if(obj!=null){
  		//Just replace the value
  		CacheElement cacheElement;
  		cacheElement=(CacheElement)obj;
  		cacheElement.setObjectKey(key);
  		cacheElement.setObjectValue(value);
  		return;
  	}
  	if(!isFull()){
  		index=numEntries;
  		++numEntries;
  	}else{
  		CacheElement cacheElement=removeLfuElement();
  		index=cacheElement.getIndex();
  		table.remove(cacheElement.getObjectKey());
  	}
  	cache[index].setObjectKey(key);
  	cache[index].setObjectValue(value);
  	cache[index].setIndex(index);
  	table.put(key,cache[index]);
  }
  public CacheElement remvoeLfuElement(){
  	CacheElement[] elements=getElementsFromTable();
  	CacheElement leastElement=leastHit(elements);
  	return leastElement;
  }
  //把hitCount最低的元素找出来，然后删除，给新进得缓存元素留位置
  public static CacheElement leastHit(CacheElement[] elements){
  	CacheElement lowestElement=null;
  	for(int i=0;i<elementes.length,i++){
  		CacheElement element=elements[i];
  		if(lowestElement==null){
  			lowestElement=element;
  		}else{
  			if(element.getHitCount() < lowestElement.getHitCount()){
  				lowestElement=element;
  			}
  		}
  	}
  	return lowestElement;
  }
  

• Least Recently User(LRU)：把最近最少使用的缓存对象踢走，它的实现有两种方式：array和LinkedHashMap
  注：1、LRU算法会把新的对象放在缓存的顶部，当缓存达到容量极限，它就会把底部的对象踢走(它会把最新被访问的缓存对象放到缓存池的顶部)，所以，经常被读取的环境对象就会一直呆在缓冲池的顶部，下列代码的逻辑如LUR算法描述一样，把再次用到的缓存提取到最前面，而每次删除的都是最后面的元素实现code

private void moveToFront(int index){
	int nextIndex,prevIndex;
	if(head!=index){
		nextIndex=next[index];
		prevIndex=prev[index];
		/**
		* Only the head has a prev entry that is an invalid index
		* so we don't check
		*/
		next[prevIndex]=nextIndex;
		/**
		* make sure index is valid,If it isn't,we're at the tail
		* and don't set prev[next]
		*/
		if(nextIndex >=0)
			prev[nextIndex]=prevIndex;
		else
			tail=prevIndex;
		prev[index]=-1;
		next[index]=head;
		prev[head]=index;
		head=index;
	}
}
public final synchronized void addElement(Object key,Object value){
	int index;Object obj;
	obj=table.get(key);
	if(obj!=null){
		CacheElement entry;
		//Just replace the value,but move it to the front
		entry=(CacheElement)obj;
		entry.setObjectKey(key);
		entry.setObjectValue(value);
		moveToFront(entry.getIndex());
		return ;
	}
	//If we haven't filled the cache yet,place in next available
	// spot and move to front
	if(!isFull()){
		if(numEntries > 0){
			prev[numEntires]=tail;
			next[_numEntries]=-1;
			moveToFront(numEntries);
		}
		++numEntries;
	}else{
		// We replace the tail of the list
		table.remove(cache[tail].getObjectKey());
		moveToFront(tail);
	}
	cache[head].setObjectKey(key);
	cache[head].setObjectValue(value);
	table.put(key,cache[head]);
}

• Least Recently Used2(LRU2)[LRU的升级版]
  我叫最近最少使用twice,我会把被两次访问过的对象放入缓存池，让缓存池慢了之后，我会把有两次最少使用的缓存对象踢走，因为需要跟着对象两次，访问负载就会随着缓存池的增加而增加，如果把我用在大容量的缓冲池中，我就会有问题，另外，我还需要跟踪不在缓存池中的对象，因为他们还没有被第二次读取，我采用的是adoptive to access模式
• Two Queues(2Q)[LRU的升级版]
  我把被访问的数据放到LRU的缓存中，如果这个对象再次被访问，我就把它移动到第二个、更大的LUR缓存中，我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3，当缓存的访问负载是固定的时候，把LRU换成LRU2，就比增加缓存的容量更好，这种机制使得我比LRU2更好，我采用的时adoptive to access模式
• Adaptive Replacement Cache（ARC）
  有人说我是介于LRU和LFU之间，为了提高效果，我是由2各LRU组成，第一个也就是L1，包含的对象是最近只被使用过一次的，第二个LRU也就是L2，包含的时最近使用过两次的对象，因此，L1放的是新的对象，L2放的是常用的对象。
• Most Recently Used(MRU)
  我和LRU相反，我会移除最近最多被使用的对象，为什么呢？因为当一次访问过来的时候，有些事情是无法预测的，并且在缓存系统中找出最近最少使用的对象是一项时间复杂度非常高的运算。我是数据库中常见的缓存算法，每当一次缓存记录的使用，我会把它放到栈的顶端，当栈满的时候，我就会把栈顶得对象换成新进来的对象
• First in First out (FIFO)
  我是先进先出，是一个低负载的算法，并且对缓存对象的管理要求不高，我通过一个队列去跟踪所有缓存对象，最近最常使用的缓存对象放到后面，而更早的缓存对象放在前面，当缓存容量满时，排在前面的缓存对象会被踢走，然后把新的缓存对象加进去。

public final synchronized void addElement(Object key,Object value){
	int index;
	Object obj;
	obj=talbe.get(key);
	if(obj!=null){
		//Just replace the value
		CacheElement cacheElement;
	    cacheElement=(CacheElement)obj;
	    cacheElement.setObjectKey(key);
	    cacheElement.setObjectValue(value);
		return ;
	}
	//if we haven't filled the cache yet,put it at the end
	if(!isFull()){
		index=numEntries;
		++numEntries;
	}else{
		//otherwise,replace the current pointer
		index=current;
		//in order to make Circular FIFO
		if(++current >= cache.length){
			current=0
		}
		table.remove(cache[index].getObjectKey());
	}
	cache[index].setObjectKey(key);
	cache[index].setObjectValue(value);
	table.put(key,cache[index]);
}

• Second Chance
  大家好，我是 second chance，我是通过 FIFO 修改而来的，被大家叫做 second chance 缓存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本。我和FIFO 一样也是在观察队列的前端，但是与FIFO的立刻踢出不同，我会检查即将要被踢出的对象有没有之前被使用过的标志（1一个 bit 表示），没有没有被使用过，我就把他踢出；否则，我会把这个标志位清除，然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时，由于他已经没有这个标志位了，所以我立刻就把他踢开了。我在速度上比 FIFO 快
• CLock
  我是 Clock，一个更好的 FIFO，也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部，但是也可以达到 second chance 的效果,我持有一个装有缓存对象的环形列表，头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时，我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0，我会直接用新的缓存对象替代这个缓存对象；如果标志位是1，我会把头指针递增，然后重复这个过程，知道新的缓存对象能够被放入。我比 second chance 更快
• Random Cache
  我是随机缓存，我随意的替换缓存实体，没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为，我随意的去处缓存实体。我比 FIFO 机制好，在某些情况下，我甚至比 LRU 好，但是，通常LRU都会比我好code:

public final synchronized void addElement(Object key,Object value){
	int index;
	Object obj;
	obj=talbe.get(key);
	if(obj!=null){
		//Just replace the value
		CacheElement cacheElement;
	    cacheElement=(CacheElement)obj;
	    cacheElement.setObjectKey(key);
	    cacheElement.setObjectValue(value);
		return ;
	}
	//if we haven't filled the cache yet,put it at the end
	if(!isFull()){
		index=numEntries;
		++numEntries;
	}else{
		//otherwise,replace a random entry
		index=(this)(cache.length * random.netFloat());
		table.remove(cache[index].getObjectKey());
	}
	cache[index].setObjectKey(key);
	cache[index].setObjectValue(value);
	table.put(key,cache[index]);
}

缓存算法使用的公共基础代码

• 缓存实体(拥有缓存的key和value)

public class CacheElement{
	private Object objectValue;
	private Object objectKey;
	private int index;
	private int hitCount;
	//getters and setters
	...
}

• 添加缓存实体（用来检查缓存元素是否在缓存中了，如果是，我们就替换它，否则，我们就具体看看每个缓存算法的实现）

public final synchronized void addElement(Object key,Object value){
	int index;
	Object obj;
	//get the entry from the table
	obj=table.get(key);
	//if we have the entry already in our talbe
	//then get it and replace only its value
	get the entry from the tableObj=table.get(key);
	if(obj!=null){
	CacheElement cacheElement;
	cacheElement=(CacheElement)obj;
	cacheElement.setObjectKey(key);
	cacheElement.setObjectValue(value);
	return ;
	}
}

我们已经看到LFU和LRU缓存算法的实现，至于如何实现，采用数组还是LinkedHashMap,都由你决定，一般小的缓存容量用数组，大得用LinkedHashMap。