首页 > 代码库 > JAVA缓存简单的实现思路

JAVA缓存简单的实现思路

提到缓存,不得不提就是缓存算法(淘汰算法),常见算法有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;    } }

 

JAVA缓存简单的实现思路