簡(jiǎn)介
jodd.cache包中有FIFO配名，LRU，LFU等幾種緩存置換算法的實(shí)現(xiàn)
FIFO -- 先進(jìn)先出
FIFO
- 新訪(fǎng)問(wèn)的數(shù)據(jù)插入FIFO隊(duì)列尾部晋辆，數(shù)據(jù)在FIFO隊(duì)列中順序移動(dòng)
- 淘汰FIFO隊(duì)列頭部的數(shù)據(jù)
LRU -- 最久未使用
LRU
- 新數(shù)據(jù)插入到鏈表頭部
- 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪(fǎng)問(wèn)）渠脉，則將數(shù)據(jù)移到鏈表頭部
- 當(dāng)鏈表滿(mǎn)的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄
LFU -- 最近最少使用
LFU
- 新加入數(shù)據(jù)插入到隊(duì)列尾部（因?yàn)橐糜?jì)數(shù)為1）
- 隊(duì)列中的數(shù)據(jù)被訪(fǎng)問(wèn)后瓶佳，引用計(jì)數(shù)增加芋膘，隊(duì)列重新排序
- 當(dāng)需要淘汰數(shù)據(jù)時(shí)，將已經(jīng)排序的列表最后的數(shù)據(jù)塊刪除
代碼實(shí)現(xiàn)
繼承關(guān)系
UML
-
Cache：緩存接口 -
AbstractCacheMap：抽象類(lèi)，實(shí)現(xiàn)一些公共的邏輯（讀寫(xiě)鎖等） -
LRUCache：LRU替換算法實(shí)現(xiàn) -
LFUCache：LFU替換算法實(shí)現(xiàn) -
FIFOCache：FIFO替換算法實(shí)現(xiàn) -
TimedCache：無(wú)容量限制緩存为朋，但可以通過(guò)定時(shí)任務(wù)清除超時(shí)的對(duì)象
Cache
public interface Cache<K, V> {
/**
* 返回緩存容器的大小限制臂拓，如果為0則為不限制
*/
int limit();
/**
* 返回超時(shí)時(shí)間，如果為0則沒(méi)有超時(shí)
*/
long timeout();
/**
* 使用默認(rèn)超時(shí)時(shí)間（0）添加緩存對(duì)象
*/
void put(K key, V object);
/**
* 使用自定的超時(shí)時(shí)間添加緩存對(duì)象
* 如果緩存容器已經(jīng)滿(mǎn)將調(diào)用purne()方法來(lái)獲得空間
*/
void put(K key, V object, long timeout);
/**
* 根據(jù)鍵從容器中取得緩存對(duì)象
* 如果該對(duì)象已被清除將返回null
*/
V get(K key);
/**
* 從緩存容器中移除對(duì)象并返回移除的對(duì)象的個(gè)數(shù)
*/
int prune();
/**
* 返回緩存容器是否已滿(mǎn)习寸，當(dāng)且僅當(dāng)容器容積有限制的情況下
*/
boolean isFull();
/**
* 從容器中移除一個(gè)對(duì)象
*/
void remove(K key);
/**
* 清空容器
*/
void clear();
/**
* 返回當(dāng)前緩存的對(duì)象的數(shù)量
*/
int size();
/**
* 返回緩存容器是否為空
*/
boolean isEmpty();
/**
* 返回一個(gè)包含容器中緩存對(duì)象的Map對(duì)象
* 期間會(huì)鎖定容器
*/
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; // 最后訪(fǎng)問(wèn)時(shí)間胶惰，供LRU實(shí)現(xiàn)使用
long accessCount; // 訪(fǎng)問(wèn)計(jì)數(shù)，供LFU實(shí)現(xiàn)使用
long ttl; // 對(duì)象超時(shí)時(shí)間, 0 = 沒(méi)有超時(shí)
// 是否過(guò)期
boolean isExpired() {
if (ttl == 0) {
return false;
}
return lastAccess + ttl < System.currentTimeMillis();
}
// 獲得緩存對(duì)象并刷新訪(fǎng)問(wèn)時(shí)間
V2 getObject() {
lastAccess = System.currentTimeMillis();
accessCount++;
return cachedObject;
}
}
// 用于存放緩存的Map霞溪，在實(shí)現(xiàn)類(lèi)中具體實(shí)例化
protected Map<K, CacheObject<K, V>> cacheMap;
// 讀寫(xiě)鎖
private final StampedLock lock = new StampedLock();
// ---------------------------------------------------------------- properties
// 緩存大小
protected int cacheSize; // max cache size, 0 = no limit
public int limit() {
return cacheSize;
}
// 緩存容器默認(rèn)超時(shí)時(shí)間孵滞，默認(rèn)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;
}
// 是否有緩存對(duì)象曾自定義超時(shí)時(shí)間
protected boolean existCustomTimeout;
// 緩存替換時(shí)是否需要對(duì)對(duì)象的存活狀態(tài)進(jìn)行判斷
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);
// 緩存對(duì)象自定義過(guò)超時(shí)時(shí)間
if (timeout != 0) {
existCustomTimeout = true;
}
// 判斷是否達(dá)到緩存容器上限，是的話(huà)觸發(fā)替換（達(dá)到最大容量鸯匹，但鍵值已存在不觸發(fā)坊饶，替換為新對(duì)象）
if (isReallyFull(key)) {
pruneCache();
}
cacheMap.put(key, co);
} finally {
lock.unlockWrite(stamp);
}
}
// ---------------------------------------------------------------- get
// 命中次數(shù)
protected int hitCount;
// 非命中次數(shù)
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;
}
// 判斷是否過(guò)期
if (co.isExpired()) {
// 嘗試獲得寫(xiě)鎖，獲取失敗則釋放讀鎖殴蓬，手動(dòng)獲得讀鎖
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();
}
// 移除過(guò)期對(duì)象
CacheObject<K, V> removedCo = cacheMap.remove(key);
// 觸發(fā)移除后的鉤子函數(shù)(Files Cache用的)
if (removedCo != null) {
onRemove(removedCo.key, removedCo.cachedObject);
}
missCount++;
return null;
}
// 緩存命中匿级，返回對(duì)象
hitCount++;
return co.getObject();
} finally {
lock.unlock(stamp);
}
}
// ---------------------------------------------------------------- prune
// 緩存修剪具體實(shí)現(xiàn)
protected abstract int pruneCache();
public final int prune() {
final long stamp = lock.writeLock();
try {
return pruneCache();
} finally {
lock.unlockWrite(stamp);
}
}
// ---------------------------------------------------------------- common
// 以下方法基本為加鎖訪(fǎng)問(wèn)Map的對(duì)應(yīng)方法
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
// 返回一個(gè)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實(shí)現(xiàn)
// 不自動(dòng)擴(kuò)容，按訪(fǎng)問(wèn)順序排序染厅，達(dá)到容量后移除末尾元素
cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1, 1.0f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return LRUCache.this.removeEldestEntry(size());
}
};
}
/**
* 用來(lái)判斷是否需要移除尾部元素
*/
protected boolean removeEldestEntry(int currentSize) {
if (cacheSize == 0) {
return false;
}
return currentSize > cacheSize;
}
// ---------------------------------------------------------------- prune
// 遍歷緩存map痘绎，移除超時(shí)對(duì)象，返回超時(shí)對(duì)象計(jì)數(shù)
// 如果沒(méi)有定義超時(shí)糟秘，直接返回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();
// 移除超時(shí)對(duì)象简逮，并獲得存活對(duì)象中訪(fǎng)問(wèn)計(jì)數(shù)中最小的對(duì)象==>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;
}
}
}
// 容器沒(méi)滿(mǎn)直接返回
if (!isFull()) {
return count;
}
// 遍歷cache map，移除訪(fǎng)問(wèn)計(jì)數(shù)值等于或小于最小計(jì)數(shù)的對(duì)象
// 以最小計(jì)數(shù)為原點(diǎn)尿赚，重新規(guī)范計(jì)數(shù)器
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作為存儲(chǔ)散庶，不自動(dòng)擴(kuò)容，按插入順序排序
cacheMap = new LinkedHashMap<>(cacheSize + 1, 1.0f, false);
}
// ---------------------------------------------------------------- prune
// 移除過(guò)期元素凌净，如果空間還是不足悲龟，移除最早插入的元素（鏈表尾部）
@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沒(méi)有容量限制，但必須制定緩存對(duì)象的超時(shí)時(shí)間
// 定時(shí)任務(wù)可以根據(jù)元素是否超時(shí)移除元素
public TimedCache(long timeout) {
this.cacheSize = 0;
this.timeout = timeout;
cacheMap = new HashMap<>();
}
// ---------------------------------------------------------------- prune
/**
* 遍歷Map冰寻，移除超時(shí)元素
*/
@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;
/**
* 開(kāi)啟定時(shí)清理
*/
public void schedulePrune(long delay) {
if (pruneTimer != null) {
pruneTimer.cancel();
}
pruneTimer = new Timer();
pruneTimer.schedule(
new TimerTask() {
@Override
public void run() {
prune();
}
}, delay, delay
);
}
/**
* 取消定時(shí)清理
*/
public void cancelPruneSchedule() {
if (pruneTimer != null) {
pruneTimer.cancel();
pruneTimer = null;
}
}
}
}
