简单的java缓存实现
简单的java缓存实现
温佐镜 发表于4年前
简单的java缓存实现
  • 发表于 4年前
  • 阅读 12880
  • 收藏 57
  • 点赞 12
  • 评论 8
摘要: 缓存淘汰算法LRU、LFU、FIFO

提到缓存,不得不提就是缓存算法(淘汰算法),常见算法有LRU、LFU和FIFO等算法,每种算法各有各的优势和缺点及适应环境。

1、LRU(Least Recently Used ,最近最少使用)
算法根据数据的最近访问记录来淘汰数据,其原理是如果数据最近被访问过,将来被访问的几概率相对比较高,最常见的实现是使用一个链表保存缓存数据,详细具体算法如下:
1. 新数据插入到链表头部;
2. 每当缓存数据命中,则将数据移到链表头部;
3. 当链表满的时候,将链表尾部的数据丢弃;


2、LFU(Least Frequently Used,最不经常使用)
算法根据数据的历史访问频率来淘汰数据,其原理是如果数据过去被访问次数越多,将来被访问的几概率相对比较高。LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。
具体算法如下:
1. 新加入数据插入到队列尾部(因为引用计数为1);
2. 队列中的数据被访问后,引用计数增加,队列重新排序;
3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除;


3、FIFO(First In First Out ,先进先出)
算法是根据先进先出原理来淘汰数据的,实现上是最简单的一种,具体算法如下:
1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动;
2. 淘汰FIFO队列头部的数据;


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

基于现有jdk类库,我们可以很容易实现上面的缓存算法

首先定义缓存接口类


/**
 * 缓存接口
 * @author Wen
 *
 */
public interface Cache<K,V> {
	/**
	 * 返回当前缓存的大小
	 * 
	 * @return  
	 */
	int size();
	
	/**
	 * 返回默认存活时间
	 * 
	 * @return
	 */
	long getDefaultExpire();
	
	/**
	 * 向缓存添加value对象,其在缓存中生存时间为默认值
	 * 
	 * @param key
	 * @param value
	 */
	void put(K key ,V value) ;
	
	/**
	 * 向缓存添加value对象,并指定存活时间
	 * @param key
	 * @param value
	 * @param expire  过期时间
	 */
	void put(K key ,V value , long expire ) ;
	
	/**
	 * 查找缓存对象
	 * @param key
	 * @return
	 */
	V get(K key);
	
	/**
	 * 淘汰对象
	 * 
	 * @return  被删除对象大小
	 */
	int eliminate();
	
	/**
	 * 缓存是否已经满
	 * @return
	 */
	boolean isFull();

	/**
	 * 删除缓存对象
	 * 
	 * @param key
	 */
	void remove(K key);

	/**
	 * 清除所有缓存对象
	 */
	void clear();

	/**
	 * 返回缓存大小
	 * 
	 * @return  
	 */
	int getCacheSize();

	/**
	 * 缓存中是否为空
	 */
	boolean isEmpty();

}



基本实现抽象类



import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 默认实现
 */
public abstract class AbstractCacheMap<K,V> implements Cache<K,V> {

	class CacheObject<K2,V2> {
		CacheObject(K2 key, V2 value, long ttl) {
			this.key = key;
			this.cachedObject = value;
			this.ttl = ttl;
			this.lastAccess = System.currentTimeMillis();
		}

		final K2 key;
		final V2 cachedObject;
		long lastAccess;		// 最后访问时间
		long accessCount;		// 访问次数
		long ttl;				// 对象存活时间(time-to-live)

		boolean isExpired() {
			if (ttl == 0) {
				return false;
			}
			return lastAccess + ttl < System.currentTimeMillis();
		}
		V2 getObject() {
			lastAccess = System.currentTimeMillis();
			accessCount++;
			return cachedObject;
		}
    }

	protected Map<K,CacheObject<K,V>> cacheMap;

	private final ReentrantReadWriteLock cacheLock = new ReentrantReadWriteLock();
	private final Lock readLock = cacheLock.readLock();
	private final Lock writeLock = cacheLock.writeLock();



	protected int cacheSize;      // 缓存大小 , 0 -> 无限制
	
	protected  boolean existCustomExpire ; //是否设置默认过期时间
	
	public int getCacheSize() {
		return cacheSize;
	}

	protected long defaultExpire;     // 默认过期时间, 0 -> 永不过期
	
	public AbstractCacheMap(int cacheSize ,long defaultExpire){
		this.cacheSize  = cacheSize ;
		this.defaultExpire  = defaultExpire ;
	}

	
	public long getDefaultExpire() {
		return defaultExpire;
	}


	protected boolean isNeedClearExpiredObject(){
		return defaultExpire > 0 || existCustomExpire ;
	}

	
	public void put(K key, V value) {
		put(key, value, defaultExpire );
	}


	public void put(K key, V value, long expire) {
		writeLock.lock();

		try {
			CacheObject<K,V> co = new CacheObject<K,V>(key, value, expire);
			if (expire != 0) {
				existCustomExpire = true;
			}
			if (isFull()) {
				eliminate() ;
			}
			cacheMap.put(key, co);
		}
		finally {
			writeLock.unlock();
		}
	}



	/**
	 * {@inheritDoc}
	 */
	public V get(K key) {
		readLock.lock();

		try {
			CacheObject<K,V> co = cacheMap.get(key);
			if (co == null) {
				return null;
			}
			if (co.isExpired() == true) {
				cacheMap.remove(key);
				return null;
			}

			return co.getObject();
		}
		finally {
			readLock.unlock();
		}
	}
	
	public final int eliminate() {
		writeLock.lock();
		try {
			return eliminateCache();
		}
		finally {
			writeLock.unlock();
		}
	}
	
	/**
	 * 淘汰对象具体实现
	 * 
	 * @return
	 */
	protected abstract int eliminateCache(); 


	
	public boolean isFull() {
		if (cacheSize == 0) {//o -> 无限制
			return false;
		}
		return cacheMap.size() >= cacheSize;
	}

	
	public void remove(K key) {
		writeLock.lock();
		try {
			cacheMap.remove(key);
		}
		finally {
			writeLock.unlock();
		}
	}

	
	public void clear() {
		writeLock.lock();
		try {
			cacheMap.clear();
		}
		finally {
			writeLock.unlock();
		}
	}

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

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



LRU缓存实现类



import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LRU  实现
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> extends AbstractCacheMap<K, V> {

	public LRUCache(int cacheSize, long defaultExpire) {
		
		super(cacheSize , defaultExpire) ;

		//linkedHash已经实现LRU算法 是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置
		this.cacheMap = new LinkedHashMap<K, CacheObject<K, V>>( cacheSize +1 , 1f,true ) {

			@Override
			protected boolean removeEldestEntry(
					Map.Entry<K, CacheObject<K, V>> eldest) {

				return LRUCache.this.removeEldestEntry(eldest);
			}

		};
	}

	private boolean removeEldestEntry(Map.Entry<K, CacheObject<K, V>> eldest) {

		if (cacheSize == 0)
			return false;

		return size() > cacheSize;
	}

	/**
	 * 只需要实现清除过期对象就可以了,linkedHashMap已经实现LRU
	 */
	@Override
	protected int eliminateCache() {

		if(!isNeedClearExpiredObject()){ return 0 ;}
		
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
			}
		}
		
		return count;
	}

}



LFU实现类



import java.util.HashMap;
import java.util.Iterator;

//LFU实现
public class LFUCache<K,V> extends AbstractCacheMap<K, V> {
	

	public LFUCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new HashMap<K, CacheObject<K,V>>(cacheSize+1) ;
	}

	/**
	 * 实现删除过期对象 和 删除访问次数最少的对象 
	 * 
	 */
	@Override
	protected int eliminateCache() {
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		long minAccessCount = Long.MAX_VALUE  ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
				continue ;
			}else{
				minAccessCount  = Math.min(cacheObject.accessCount , minAccessCount)  ;
			}
		}
		
		if(count > 0 ) return count ;
		
		if(minAccessCount != Long.MAX_VALUE ){
			
			iterator = cacheMap.values().iterator();
			
			while(iterator.hasNext()){
				CacheObject<K, V> cacheObject = iterator.next();
				
				cacheObject.accessCount  -=  minAccessCount ;
				
				if(cacheObject.accessCount <= 0 ){
					iterator.remove();
					count++ ;
				}
				
			}
			
		}
		
		return count;
	}

}



FIFO实现类



import java.util.Iterator;
import java.util.LinkedHashMap;
/**
 * FIFO实现
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class FIFOCache<K, V> extends AbstractCacheMap<K, V> {

	public FIFOCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
	}

	@Override
	protected int eliminateCache() {

		int count = 0;
		K firstKey = null;

		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		while (iterator.hasNext()) {
			CacheObject<K, V> cacheObject = iterator.next();

			if (cacheObject.isExpired()) {
				iterator.remove();
				count++;
			} else {
				if (firstKey == null)
					firstKey = cacheObject.key;
			}
		}

		if (firstKey != null && isFull()) {//删除过期对象还是满,继续删除链表第一个
			cacheMap.remove(firstKey);
		}

		return count;
	}

}




共有 人打赏支持
粉丝 11
博文 32
码字总数 11554
评论 (8)
kidbei
学习了
蓝杖奥利奥
学习了,但是有个小问题,LinkedHashMap中的get操作并不是一个纯读操作,会导致双向链表的顺序改变,使用ReentrantReadWriteLock读写锁还是会有get时的线程安全问题,不知道博主有没有解决这个问题?
yuweic
新手,学习了,谢谢前辈的分享!!!
祥林会跟你远走高飞
这个代码就是jodd.cache包下面的
反正不管
FIFO实现类中,14行:
cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
这里使用LinkedHashMap是什么原因呢?
温佐镜

引用来自“反正不管”的评论

FIFO实现类中,14行:
cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
这里使用LinkedHashMap是什么原因呢?
迭代遍历LinkedHashMap(内部维护一个双向链表)时,取得“键值对”的顺序是插入次序,或者是最近最少使用的次序,其中一个构造函数 LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) ,其中accessOrder=false就是按插入顺序访问,符合FIFO特性
anjieanzhi
请问博主如何构建defaultExpire这个参数呢?
狂奔的牛牛

引用来自“祥林会跟你远走高飞”的评论

这个代码就是jodd.cache包下面的
你说的对
×
温佐镜
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: