简介

jodd.cache包中有FIFO，LRU，LFU等几种缓存置换算法的实现

FIFO -- 先进先出

FIFO

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

LRU -- 最久未使用

LRU

1. 新数据插入到链表头部
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
3. 当链表满的时候，将链表尾部的数据丢弃

LFU -- 最近最少使用

LFU

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

代码实现

继承关系

UML

• Cache：缓存接口
• AbstractCacheMap：抽象类，实现一些公共的逻辑（读写锁等）
• LRUCache：LRU替换算法实现
• LFUCache：LFU替换算法实现
• FIFOCache：FIFO替换算法实现
• TimedCache：无容量限制缓存，但可以通过定时任务清除超时的对象

Cache

public interface Cache<K, V> {

    /**
     * 返回缓存容器的大小限制，如果为0则为不限制
     */
    int limit();

    /**
     * 返回超时时间，如果为0则没有超时
     */
    long timeout();

    /**
     * 使用默认超时时间（0）添加缓存对象
     */
    void put(K key, V object);

    /**
     * 使用自定的超时时间添加缓存对象
     * 如果缓存容器已经满将调用purne()方法来获得空间
     */
    void put(K key, V object, long timeout);

    /**
     * 根据键从容器中取得缓存对象
     * 如果该对象已被清除将返回null
     */
    V get(K key);

    /**
     * 从缓存容器中移除对象并返回移除的对象的个数
     */
    int prune();

    /**
     * 返回缓存容器是否已满，当且仅当容器容积有限制的情况下
     */
    boolean isFull();

    /**
     * 从容器中移除一个对象
     */
    void remove(K key);

    /**
     * 清空容器
     */
    void clear();

    /**
     * 返回当前缓存的对象的数量
     */
    int size();

    /**
     * 返回缓存容器是否为空
     */
    boolean isEmpty();

    /**
     * 返回一个包含容器中缓存对象的Map对象
     * 期间会锁定容器
     */
    Map<K, V> snapshot();
}

AbstractCacheMap

public abstract class AbstractCacheMap<K, V> implements Cache<K, V> {
    // Cache Entry
    class CacheObject<K2, V2> {
        CacheObject(K2 key, V2 object, long ttl) {
            this.key = key;
            this.cachedObject = object;
            this.ttl = ttl;
            this.lastAccess = System.currentTimeMillis();
        }

        final K2 key;
        final V2 cachedObject;
        long lastAccess;        // 最后访问时间，供LRU实现使用
        long accessCount;        // 访问计数，供LFU实现使用
        long ttl;                // 对象超时时间, 0 = 没有超时

        // 是否过期
        boolean isExpired() {
            if (ttl == 0) {
                return false;
            }
            return lastAccess + ttl < System.currentTimeMillis();
        }

        // 获得缓存对象并刷新访问时间
        V2 getObject() {
            lastAccess = System.currentTimeMillis();
            accessCount++;
            return cachedObject;
        }
    }

    // 用于存放缓存的Map，在实现类中具体实例化
    protected Map<K, CacheObject<K, V>> cacheMap;
    // 读写锁
    private final StampedLock lock = new StampedLock();

    // ---------------------------------------------------------------- properties
    // 缓存大小
    protected int cacheSize;      // max cache size, 0 = no limit

    public int limit() {
        return cacheSize;
    }

    // 缓存容器默认超时时间，默认0
    protected long timeout;     // default timeout, 0 = no timeout

    /**
     * Returns default cache timeout or <code>0</code> if it is not set.
     * Timeout can be set individually for each object.
     */
    public long timeout() {
        return timeout;
    }

    // 是否有缓存对象曾自定义超时时间
    protected boolean existCustomTimeout;

    // 缓存替换时是否需要对对象的存活状态进行判断
    protected boolean isPruneExpiredActive() {
        return (timeout != 0) || existCustomTimeout;
    }


    // ---------------------------------------------------------------- put


    public void put(K key, V object) {
        put(key, object, timeout);
    }


    public void put(K key, V object, long timeout) {
        final long stamp = lock.writeLock();

        try {
            CacheObject<K, V> co = new CacheObject<>(key, object, timeout);
            // 缓存对象自定义过超时时间
            if (timeout != 0) {
                existCustomTimeout = true;
            }
            // 判断是否达到缓存容器上限，是的话触发替换（达到最大容量，但键值已存在不触发，替换为新对象）
            if (isReallyFull(key)) {
                pruneCache();
            }
            cacheMap.put(key, co);
        } finally {
            lock.unlockWrite(stamp);
        }
    }


    // ---------------------------------------------------------------- get

    // 命中次数
    protected int hitCount;
    // 非命中次数
    protected int missCount;

    /**
     * Returns hit count.
     */
    public int getHitCount() {
        return hitCount;
    }

    /**
     * Returns miss count.
     */
    public int getMissCount() {
        return missCount;
    }

    public V get(K key) {
        long stamp = lock.readLock();

        try {
            CacheObject<K, V> co = cacheMap.get(key);
            if (co == null) {
                missCount++;
                return null;
            }
            // 判断是否过期
            if (co.isExpired()) {
                // 尝试获得写锁，获取失败则释放读锁，手动获得读锁
                final long newStamp = lock.tryConvertToWriteLock(stamp);

                if (newStamp != 0L) {
                    stamp = newStamp;
                    // lock is upgraded to write lock
                } else {
                    // manually upgrade lock to write lock
                    lock.unlockRead(stamp);
                    stamp = lock.writeLock();
                }
                // 移除过期对象
                CacheObject<K, V> removedCo = cacheMap.remove(key);
                // 触发移除后的钩子函数(Files Cache用的)
                if (removedCo != null) {
                    onRemove(removedCo.key, removedCo.cachedObject);
                }

                missCount++;
                return null;
            }
            // 缓存命中，返回对象
            hitCount++;
            return co.getObject();
        } finally {
            lock.unlock(stamp);
        }
    }

    // ---------------------------------------------------------------- prune

    // 缓存修剪具体实现
    protected abstract int pruneCache();

    public final int prune() {
        final long stamp = lock.writeLock();
        try {
            return pruneCache();
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    // ---------------------------------------------------------------- common
    // 以下方法基本为加锁访问Map的对应方法
    public boolean isFull() {
        if (cacheSize == 0) {
            return false;
        }
        return cacheMap.size() >= cacheSize;
    }

    protected boolean isReallyFull(K key) {
        if (cacheSize == 0) {
            return false;
        }
        if (cacheMap.size() >= cacheSize) {
            return !cacheMap.containsKey(key);
        } else {
            return false;
        }
    }

    public void remove(K key) {
        final long stamp = lock.writeLock();
        try {
            CacheObject<K, V> co = cacheMap.remove(key);
            if (co != null) {
                onRemove(co.key, co.cachedObject);
            }
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    public void clear() {
        final long stamp = lock.writeLock();
        try {
            cacheMap.clear();
        } finally {
            lock.unlockWrite(stamp);
        }
    }

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

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

    @Override
    // 返回一个cache map的拷贝
    public Map<K, V> snapshot() {
        final long stamp = lock.writeLock();
        try {
            Map<K, V> map = new HashMap<>(cacheMap.size());
            cacheMap.forEach((key, cacheValue) -> map.put(key, cacheValue.getObject()));
            return map;
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    // ---------------------------------------------------------------- protected

    /**
     * Callback called on item removal. The cache is still locked.
     */
    protected void onRemove(K key, V cachedObject) {
    }

}

LRUCache

public class LRUCache<K, V> extends AbstractCacheMap<K, V> {

    public LRUCache(int cacheSize) {
        this(cacheSize, 0);
    }

    /**
     * Creates a new LRU cache.
     */
    public LRUCache(int cacheSize, long timeout) {
        this.cacheSize = cacheSize;
        this.timeout = timeout;
        // cacheMap使用LinkedHashMap实现
        // 不自动扩容，按访问顺序排序，达到容量后移除末尾元素
        cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1, 1.0f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return LRUCache.this.removeEldestEntry(size());
            }
        };
    }

    /**
     * 用来判断是否需要移除尾部元素
     */
    protected boolean removeEldestEntry(int currentSize) {
        if (cacheSize == 0) {
            return false;
        }
        return currentSize > cacheSize;
    }

    // ---------------------------------------------------------------- prune

    // 遍历缓存map，移除超时对象，返回超时对象计数
    // 如果没有定义超时，直接返回0
    @Override
    protected int pruneCache() {
        if (!isPruneExpiredActive()) {
            return 0;
        }
        int count = 0;
        Iterator<CacheObject<K, V>> values = cacheMap.values().iterator();
        while (values.hasNext()) {
            CacheObject<K, V> co = values.next();
            if (co.isExpired()) {
                values.remove();
                onRemove(co.key, co.cachedObject);
                count++;
            }
        }
        return count;
    }
}

LFUCache

public class LFUCache<K, V> extends AbstractCacheMap<K, V> {

    public LFUCache(int maxSize) {
        this(maxSize, 0);
    }

    public LFUCache(int maxSize, long timeout) {
        this.cacheSize = maxSize;
        this.timeout = timeout;
        cacheMap = new HashMap<>(maxSize + 1);
    }

    // ---------------------------------------------------------------- prune

    /**
     * Prunes expired and, if cache is still full, the LFU element(s) from the cache.
     * On LFU removal, access count is normalized to value which had removed object.
     * Returns the number of removed objects.
     */
    @Override
    protected int pruneCache() {
        int count = 0;
        CacheObject<K, V> comin = null;

        // remove expired items and find cached object with minimal access count
        Iterator<CacheObject<K, V>> values = cacheMap.values().iterator();
        // 移除超时对象，并获得存活对象中访问计数中最小的对象==>comin
        while (values.hasNext()) {
            CacheObject<K, V> co = values.next();
            if (co.isExpired()) {
                values.remove();
                onRemove(co.key, co.cachedObject);
                count++;
                continue;
            }

            if (comin == null) {
                comin = co;
            } else {
                if (co.accessCount < comin.accessCount) {
                    comin = co;
                }
            }
        }

        // 容器没满直接返回
        if (!isFull()) {
            return count;
        }

        // 遍历cache map，移除访问计数值等于或小于最小计数的对象
        // 以最小计数为原点，重新规范计数器
        if (comin != null) {
            long minAccessCount = comin.accessCount;

            values = cacheMap.values().iterator();
            while (values.hasNext()) {
                CacheObject<K, V> co = values.next();
                co.accessCount -= minAccessCount;
                if (co.accessCount <= 0) {
                    values.remove();
                    onRemove(co.key, co.cachedObject);
                    count++;
                }
            }
        }
        return count;
    }
}

FIFOCache

public class FIFOCache<K, V> extends AbstractCacheMap<K, V> {
    
        public FIFOCache(int cacheSize) {
            this(cacheSize, 0);
        }
    
        /**
         * Creates a new LRU cache.
         */
        public FIFOCache(int cacheSize, long timeout) {
            this.cacheSize = cacheSize;
            this.timeout = timeout;
            // 依旧使用LinkedHashMap作为存储，不自动扩容，按插入顺序排序
            cacheMap = new LinkedHashMap<>(cacheSize + 1, 1.0f, false);
        }
    
    
        // ---------------------------------------------------------------- prune
    
        // 移除过期元素，如果空间还是不足，移除最早插入的元素（链表尾部）
        @Override
        protected int pruneCache() {
            int count = 0;
            CacheObject<K,V> first = null;
            Iterator<CacheObject<K,V>> values = cacheMap.values().iterator();
            while (values.hasNext()) {
                CacheObject<K,V> co = values.next();
                if (co.isExpired()) {
                    values.remove();
                    count++;
                }
                if (first == null) {
                    first = co;
                }
            }
            if (isFull()) {
                if (first != null) {
                    cacheMap.remove(first.key);
                    count++;
                }
            }
            return count;
        }
    }
}

TimedCache

public class TimedCache<K, V> extends AbstractCacheMap<K, V> {
        // TimedCache没有容量限制，但必须制定缓存对象的超时时间
        // 定时任务可以根据元素是否超时移除元素
        public TimedCache(long timeout) {
            this.cacheSize = 0;
            this.timeout = timeout;
            cacheMap = new HashMap<>();
        }
    
        // ---------------------------------------------------------------- prune
    
        /**
         * 遍历Map，移除超时元素
         */
        @Override
        protected int pruneCache() {
            int count = 0;
            Iterator<CacheObject<K,V>> values = cacheMap.values().iterator();
            while (values.hasNext()) {
                CacheObject co = values.next();
                if (co.isExpired()) {
                    values.remove();
                    count++;
                }
            }
            return count;
        }
    
    
        // ---------------------------------------------------------------- auto prune
    
        protected Timer pruneTimer;
    
        /**
         * 开启定时清理
         */
        public void schedulePrune(long delay) {
            if (pruneTimer != null) {
                pruneTimer.cancel();
            }
            pruneTimer = new Timer();
            pruneTimer.schedule(
                    new TimerTask() {
                        @Override
                        public void run() {
                            prune();
                        }
                    }, delay, delay
            );
        }
    
        /**
         * 取消定时清理
         */
        public void cancelPruneSchedule() {
            if (pruneTimer != null) {
                pruneTimer.cancel();
                pruneTimer = null;
            }
        }    
    }
}