一、引言
在緩存-淘汰策略原理及其實現(xiàn)中茬底，我們提到了常用的LRU和LFU各自的優(yōu)缺點高诺，為了綜合LRU和LFU各自的優(yōu)點，最后演進出了W-TinyLFU算法差购。該算法既能夠應(yīng)對突發(fā)性的流量場景绳锅，又能夠應(yīng)對局部周期性熱點數(shù)據(jù)的場景飒焦。下面我們將詳細講解W-TinyLFU在caffeine中的設(shè)計思想與源碼解析那槽。
W-TinyLFU的總體設(shè)計思想
W-TinyLFU為了平衡訪問頻率和訪問時間新鮮程度兩個維度因素悼沿，盡量
將新鮮的訪問頻率高的緩存項保留在緩存中，將緩存存儲空間分為兩個大的區(qū)域：Window Cache和Main Cache骚灸，
Window Cache是一個標準的LRU Cache糟趾，Main Cache則是一個SLFU（Segmemted LFU）cache，Main Cache進一步劃分為Protected Cache（保護區(qū)）和Probation Cache（考察區(qū)）兩個區(qū)域甚牲，這兩個區(qū)域都是基于LRU的Cache拉讯。
這三個區(qū)域的作用分別是：
- window cache區(qū)域用來存儲剛產(chǎn)生的數(shù)據(jù)；
- Protected Cache則用來存放頻率較高的熱點數(shù)據(jù)鳖藕；
- 介于這兩者之間的，即兼顧了訪問時間和訪問頻率的數(shù)據(jù)則存放于Probation Cache只锭。
W-TinyLFU的算法流程
1著恩、數(shù)據(jù)剛進入時，如果window區(qū)域未滿蜻展，則放入隊尾喉誊；如果緩存?zhèn)€數(shù)超過了window區(qū)域的最大緩存數(shù)，則將元素放入隊首纵顾。
2伍茄、緩存區(qū)域維護
- 首先維護window區(qū)域，如果window區(qū)超過了最大的限制施逾，那么就要把“多出來”的記錄做處理敷矫。取隊首元素，從window中刪除汉额，并且把節(jié)點移動到probation區(qū)域的隊首曹仗。
- 接著維護mainCache區(qū)域。會從probation隊列取出隊首元素victim（剛從window區(qū)域過來的）和隊尾元素candidate（最久未被訪問過的）pk蠕搜，比較頻率大小怎茫，小的元素會被從緩存中刪除。
-
producted 區(qū)域維護：probation中的元素如果被訪問過妓灌，元素則會晉升到producted區(qū)域轨蛤。如果producted區(qū)域元素滿了蜜宪，則根據(jù)lru會淘汰出一個元素進入probgation(不同版本有差別)
整體的淘汰流程如下圖所示：
image.png
總結(jié)
從上面對W-TinyLFU的原理描述可知，caffeine綜合了LFU和LRU的優(yōu)勢祥山，將不同特性的緩存項存入不同的緩存區(qū)域圃验，最近剛產(chǎn)生的緩存項進入Window區(qū)，不會被淘汰枪蘑；訪問頻率高的緩存項進入Protected區(qū)损谦，也不會淘汰；介于這兩者之間的緩存項存在Probation區(qū)岳颇，當緩存空間滿了時照捡，Probation區(qū)的緩存項會根據(jù)訪問頻率判斷是保留還是淘汰；通過這種機制话侧，很好的平衡了訪問頻率和訪問時間新鮮程度兩個維度因素栗精，盡量將新鮮的訪問頻率高的緩存項保留在緩存中。
同時在維護緩存項訪問頻率時瞻鹏，引入計數(shù)器衰減機制（保鮮）悲立，即節(jié)省了存儲資源，也能較好的處理稀疏流量新博、短時超熱點流量等傳統(tǒng)LFU無法很好處理的場景薪夕。
附錄：caffeine源碼
final class AddTask implements Runnable {
final Node<K, V> node;
final int weight;
AddTask(Node<K, V> node, int weight) {
this.weight = weight;
this.node = node;
}
@Override
@GuardedBy("evictionLock")
@SuppressWarnings("FutureReturnValueIgnored")
public void run() {
if (evicts()) {
//當前緩存?zhèn)€數(shù)
long weightedSize = weightedSize();
//設(shè)置當前緩存?zhèn)€數(shù)
setWeightedSize(weightedSize + weight);
//設(shè)置window區(qū)域緩存?zhèn)€數(shù)
setWindowWeightedSize(windowWeightedSize() + weight);
node.setPolicyWeight(node.getPolicyWeight() + weight);
long maximum = maximum();
if (weightedSize >= (maximum >>> 1)) {
// Lazily initialize when close to the maximum
long capacity = isWeighted() ? data.mappingCount() : maximum;
frequencySketch().ensureCapacity(capacity);
}
K key = node.getKey();
if (key != null) {
//更新訪問頻率
frequencySketch().increment(key);
}
setMissesInSample(missesInSample() + 1);
}
// ignore out-of-order write operations
boolean isAlive;
synchronized (node) {
isAlive = node.isAlive();
}
if (isAlive) {
if (expiresAfterWrite()) {
writeOrderDeque().add(node);
}
//如果有驅(qū)逐策略并且當前緩存?zhèn)€數(shù)已經(jīng)大于了window區(qū)域最大的緩存數(shù)，
//則把新來的緩存key放到deque的頭部
if (evicts() && (weight > windowMaximum())) {
accessOrderWindowDeque().offerFirst(node);
} else if (evicts() || expiresAfterAccess()) {
//如果有驅(qū)逐策略（并且當前緩存?zhèn)€數(shù)已經(jīng)小于window區(qū)域最大的緩存
//數(shù)） 或者 設(shè)置了key進入后失效赫悄，則把緩存key放到deque的尾部
accessOrderWindowDeque().offerLast(node);
}
if (expiresVariable()) {
timerWheel().schedule(node);
}
}
// Ensure that in-flight async computation cannot expire (reset on a completion callback)
if (isComputingAsync(node)) {
synchronized (node) {
if (!Async.isReady((CompletableFuture<?>) node.getValue())) {
long expirationTime = expirationTicker().read() + ASYNC_EXPIRY;
setVariableTime(node, expirationTime);
setAccessTime(node, expirationTime);
setWriteTime(node, expirationTime);
}
}
}
}
}
//從window區(qū)淘汰
int evictFromWindow() {
int candidates = 0;
//取window deque的隊首第一個元素（LRU策略原献，最先達到的元素在隊尾，后
//到的元素在其前面）
Node<K, V> node = accessOrderWindowDeque().peek();
//一直循環(huán)： 如果window區(qū)超過了最大的限制埂淮，那么就要把“多出來”的記錄做處理
while (windowWeightedSize() > windowMaximum()) {
// The pending operations will adjust the size to reflect the correct weight
if (node == null) {
break;
}
Node<K, V> next = node.getNextInAccessOrder();
if (node.getPolicyWeight() != 0) {
//設(shè)置 node 的類型： 為觀察類型 probation
node.makeMainProbation();
// 從window區(qū)去掉
accessOrderWindowDeque().remove(node);
//加入到probation queue,相當于把節(jié)點移動到probation區(qū)（開始準備晉升）
accessOrderProbationDeque().add(node);
candidates++;
setWindowWeightedSize(windowWeightedSize() - node.getPolicyWeight());
}
node = next;
}
return candidates;
}
//從mainCache區(qū)淘汰
void evictFromMain(int candidates) {
int victimQueue = PROBATION;
//victim 從probation cache區(qū)域取出隊首元素（window區(qū)域淘汰的）
Node<K, V> victim = accessOrderProbationDeque().peekFirst();
//candidate = 從probation cache區(qū)域取出隊尾元素（最久沒有被訪問過）
Node<K, V> candidate = accessOrderProbationDeque().peekLast();
while (weightedSize() > maximum()) {
(省略部分代碼)
.........
/**
*candidate和victim進行頻率比較姑隅，頻率小的會被從緩存中刪除。
*/
if (admit(candidateKey, victimKey)) {
Node<K, V> evict = victim;
victim = victim.getNextInAccessOrder();
// 刪除 victim 倔撞，從而留下 candidate
evictEntry(evict, RemovalCause.SIZE, 0L);
candidate = candidate.getPreviousInAccessOrder();
} else {
Node<K, V> evict = candidate;
candidate = (candidates > 0)
? candidate.getPreviousInAccessOrder()
: candidate.getNextInAccessOrder();
// 刪除 candidate 讲仰，從而留下 victim
evictEntry(evict, RemovalCause.SIZE, 0L);
}
}
}
