简介
jodd.cache包中有FIFO，LRU，LFU等几种缓存置换算法的实现
FIFO -- 先进先出
FIFO
- 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动
- 淘汰FIFO队列头部的数据
LRU -- 最久未使用
LRU
- 新数据插入到链表头部
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
- 当链表满的时候，将链表尾部的数据丢弃
LFU -- 最近最少使用
LFU
- 新加入数据插入到队列尾部（因为引用计数为1）
- 队列中的数据被访问后，引用计数增加，队列重新排序
- 当需要淘汰数据时，将已经排序的列表最后的数据块删除
代码实现
继承关系
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;
}
}
}
}
