點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”

優(yōu)質(zhì)文章，第一時間送達(dá)

本文從源碼層面分析了 redis 的緩存淘汰機(jī)制，并在文章末尾描述使用 Java 實(shí)現(xiàn)的思路，以供參考。

緩存淘汰機(jī)制

一個完整的緩存淘汰機(jī)制需要解決兩個問題：

確定淘汰哪些記錄 ——?淘汰策略
刪除被淘汰的記錄 ——?刪除策略

淘汰策略

緩存能使用的內(nèi)存是有限的，當(dāng)空間不足時，應(yīng)該優(yōu)先淘汰那些將來不再被訪問的數(shù)據(jù)，保留那些將來還會頻繁訪問的數(shù)據(jù)。因此淘汰算法會圍繞?時間局部性?原理進(jìn)行設(shè)計，即：如果一個數(shù)據(jù)正在被訪問，那么在近期很可能會被再次訪問。

為了適應(yīng)緩存讀多寫少的特點(diǎn)，實(shí)際應(yīng)用中會使用哈希表來實(shí)現(xiàn)緩存。當(dāng)需要實(shí)現(xiàn)某種特定的緩存淘汰策略時，需要引入額外的簿記?book keeping?結(jié)構(gòu)。

下面回顧 3 種最常見的緩存淘汰策略。

FIFO (先進(jìn)先出)

　越早進(jìn)入緩存的數(shù)據(jù)，其不再被訪問的可能性越大。
　因此在淘汰緩存時，應(yīng)選擇在內(nèi)存中停留時間最長的緩存記錄。

　使用隊列即可實(shí)現(xiàn)該策略：
　

　優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，適合線性訪問的場景
　缺點(diǎn)：無法適應(yīng)特定的訪問熱點(diǎn)，緩存的命中率差
　簿記開銷：時間?O(1)，空間?O(N)

LRU (最近最少使用)

　一個緩存被訪問后，近期再被訪問的可能性很大。
　可以記錄每個緩存記錄的最近訪問時間，最近未被訪問時間最長的數(shù)據(jù)會被首先淘汰。

　使用鏈表即可實(shí)現(xiàn)該策略：
　

　當(dāng)更新 LRU 信息時，只需調(diào)整指針：
　

　優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，能適應(yīng)訪問熱點(diǎn)
　缺點(diǎn)：對偶發(fā)的訪問敏感，影響命中率
　簿記開銷：時間?O(1)，空間?O(N)

LRU 改進(jìn)

　原始的 LRU 算法緩存的是最近訪問了 1 次的數(shù)據(jù)，因此不能很好地區(qū)分頻繁和不頻繁緩存引用。
　這意味著，部分冷門的低頻數(shù)據(jù)也可能進(jìn)入到緩存，并將原本的熱點(diǎn)記錄擠出緩存。
　為了減少偶發(fā)訪問對緩存的影響，后續(xù)提出的 LRU-K 算法作出了如下改進(jìn)：

在 LRU 簿記的基礎(chǔ)上增加一個歷史隊列?History Queue

當(dāng)記錄訪問次數(shù)小于 K 時，會記錄在歷史隊列中（當(dāng)歷史隊列滿時，可以使用 FIFO 或 LRU 策略進(jìn)行淘汰）
當(dāng)記錄訪問次數(shù)大于等于 K 時，會被從歷史隊列中移出，并記錄到 LRU 緩存中

　K 值越大，緩存命中率越高，但適應(yīng)性差，需要經(jīng)過大量訪問才能將過期的熱點(diǎn)記錄淘汰掉。
　綜合各種因素后，實(shí)踐中常用的是 LRU-2 算法：
　

　優(yōu)點(diǎn)：減少偶發(fā)訪問對緩存命中率的影響
　缺點(diǎn)：需要額外的簿記開銷
　簿記開銷：時間?O(1)，空間?O(N+M)

LFU (最不經(jīng)常使用)

　一個緩存近期內(nèi)訪問頻率越高，其再被訪問的可能性越大。
　可以記錄每個緩存記錄的最近一段時間的訪問頻率，訪問頻率低的數(shù)據(jù)會被首先淘汰。
　
　實(shí)現(xiàn) LFU 的一個簡單方式，是在緩存記錄設(shè)置一個記錄訪問次數(shù)的計數(shù)器，然后將其放入一個小頂堆：
　

　為了保證數(shù)據(jù)的時效性，還要以一定的時間間隔對計數(shù)器進(jìn)行衰減，保證過期的熱點(diǎn)數(shù)據(jù)能夠被及時淘汰：
　

刪除策略

常見刪除策略可以分為以下幾種：

實(shí)時刪除：
　每次增加新的記錄時，立即查找可淘汰的記錄，如果存在則將該記錄從緩存中刪除

優(yōu)點(diǎn)：實(shí)時性好，最節(jié)省內(nèi)存空間
缺點(diǎn)：查找淘汰記錄會影響寫入的效率，需要額外的簿記結(jié)構(gòu)提高查找效率（比如 LRU 中的鏈表）

惰性刪除：
　在緩存中設(shè)置兩個計數(shù)器，一個統(tǒng)計訪問緩存的次數(shù)，一個統(tǒng)計可淘汰記錄的數(shù)量
　每經(jīng)過 N 次訪問后或當(dāng)前可淘汰記錄數(shù)量大于 M，則觸發(fā)一次批量刪除（M 與 N 可調(diào)節(jié)）

優(yōu)點(diǎn)：對正常緩存操作影響小，批量刪除減少維護(hù)開銷
缺點(diǎn)：實(shí)時性較差，偶發(fā)的刪除操作會導(dǎo)致訪問耗時波動

異步刪除：
　設(shè)置一個獨(dú)立的定時器線程，每隔固定的時間觸發(fā)一次批量刪除

優(yōu)點(diǎn)：對正常緩存操作影透明，無額外性能開銷
缺點(diǎn)：需要增加維護(hù)線程，并且需要提前規(guī)劃緩存的負(fù)載，以此決定如何在多個緩存實(shí)例上調(diào)度

redis 實(shí)現(xiàn)

redis 中實(shí)現(xiàn)了 LRU 與 LFU 兩種淘汰策略

為了節(jié)省空間，redis 沒有使用前面描述的簿記結(jié)構(gòu)實(shí)現(xiàn) LRU 或 LFU，而是在?robj?中使用一個 24bits 的空間記錄訪問信息：

#define?LRU_BITS?24

typedef?struct?redisObject?{
????...
????unsigned?lru:LRU_BITS;??/*?LRU?時間?(相對與全局?lru_clock?的時間)?或
?????????????????????????????*?LFU?數(shù)據(jù)?(8bits?記錄訪問頻率，16?bits?記錄訪問時間).?*/
}?robj;

每當(dāng)記錄被命中時，redis 都會更新?robj.lru?作為后面淘汰算法運(yùn)行的依據(jù)：

robj?*lookupKey(redisDb?*db,?robj?*key,?int?flags)?{
????//?...

????//?根據(jù)?maxmemory_policy?選擇不同的更新策略
????if?(server.maxmemory_policy?&?MAXMEMORY_FLAG_LFU)?{
????????updateLFU(val);
????}?else?{
????????val->lru?=?LRU_CLOCK();
????}
}

LFU 與 LRU 的更新關(guān)鍵在于?updateLFU?函數(shù)與?LRU_CLOCK?宏，下面分別進(jìn)行分析。

更新 LRU 時間

當(dāng)時使用 LRU 算法時，robj.lru?記錄的是最近一次訪問的時間戳，可以據(jù)此找出長時間未被訪問的記錄。

為了減少系統(tǒng)調(diào)用，redis 設(shè)置了一個全局的時鐘?server.lruclock?并交由后臺任務(wù)進(jìn)行更新：

#define?LRU_CLOCK_MAX?((1<lru?*/
#define?LRU_CLOCK_RESOLUTION?1000?/*?以毫秒為單位的時鐘精度?*/

/**
?*?server.lruclock?的更新頻率為?1000/server.hz
?*?如果該頻率高于?LRU?時鐘精度，則直接用?server.lruclock
?*?避免調(diào)用?getLRUClock()?產(chǎn)生額外的開銷
?*/
#define?LRU_CLOCK()?((1000/server.hz?<=?LRU_CLOCK_RESOLUTION)???server.lruclock?:?getLRUClock())

unsigned?int?getLRUClock(void)?{
????return?(mstime()/LRU_CLOCK_RESOLUTION)?&?LRU_CLOCK_MAX;
}

計算 LRU 時間方法如下：

unsigned?long?long?estimateObjectIdleTime(robj?*o)?{
????unsigned?long?long?lruclock?=?LRU_CLOCK();
????if?(lruclock?>=?o->lru)?{
????????return?(lruclock?-?o->lru)?*?LRU_CLOCK_RESOLUTION;
????}?else?{
????????//?處理?LRU?時間溢出的情況
????????return?(lruclock?+?(LRU_CLOCK_MAX?-?o->lru))?*
????????????????????LRU_CLOCK_RESOLUTION;
????}
}

當(dāng)LRU_CLOCK_RESOLUTION為 1000ms 時，robj.lru最長可記錄的 LRU 時長為 194 天0xFFFFFF / 3600 / 24。

更新 LFU 計數(shù)

當(dāng)時使用 LFU 算法時，robj.lru?被分為兩部分：16bits 記錄最近一次訪問時間，8bits 用作計數(shù)器

void?updateLFU(robj?*val)?{
????unsigned?long?counter?=?LFUDecrAndReturn(val);?//?衰減計數(shù)
????counter?=?LFULogIncr(counter);?//?增加計數(shù)
????val->lru?=?(LFUGetTimeInMinutes()<<8)?|?counter;?//?更新時間
}

更新訪問時間

前 16bits 用于保存最近一次被訪問的時間：

/**
?*?獲取?UNIX?分鐘時間戳，且只保留最低?16bits
?*?用于表示最近一次衰減時間?LDT?(last?decrement?time)
?*/
unsigned?long?LFUGetTimeInMinutes(void)?{
????return?(server.unixtime/60)?&?65535;
}

增加訪問計數(shù)

后 8bits 是一個對數(shù)計數(shù)器?logarithmic counter，里面保存的是訪問次數(shù)的對數(shù)：

#define?LFU_INIT_VAL?5?

?//?對數(shù)遞增計數(shù)器，最大值為?255
uint8_t?LFULogIncr(uint8_t?counter)?{
????if?(counter?==?255)?return?255;
????double?r?=?(double)rand()/RAND_MAX;
????double?baseval?=?counter?-?LFU_INIT_VAL;
????if?(baseval?????double?p?=?1.0/(baseval*server.lfu_log_factor+1);
????if?(r?????return?counter;
}

當(dāng)?server.lfu_log_factor = 10?時，p = 1/((counter-LFU_INIT_VAL)*server.lfu_log_factor+1)?的增長函數(shù)如圖所示：

使用函數(shù)?rand()?生成的介于 0 與 1 之間隨機(jī)浮點(diǎn)數(shù)?r?符合均勻分布，隨著?counter?的增大，其自增成功的概率迅速降低。

下列表格展示了?counter?在不同?lfu_log_factor?情況下，達(dá)到飽和（255）所需的訪問次數(shù)：

+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
| 0      | 104        | 255        | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 1      | 18         | 49         | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 10     | 10         | 18         | 142        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 100    | 8          | 11         | 49         | 143        | 255        |
+--------+------------+------------+------------+------------+------------+

衰減訪問計數(shù)

同樣的，為了保證過期的熱點(diǎn)數(shù)據(jù)能夠被及時淘汰，redis 使用如下衰減函數(shù)：

//?計算距離上一次衰減的時間?，單位為分鐘
unsigned?long?LFUTimeElapsed(unsigned?long?ldt)?{
????unsigned?long?now?=?LFUGetTimeInMinutes();
????if?(now?>=?ldt)?return?now-ldt;
????return?65535-ldt+now;
}

/**
?*?衰減函數(shù)，返回根據(jù)?LDT?時間戳衰減后的?LFU?計數(shù)
?*?不更新計數(shù)器
?*/
unsigned?long?LFUDecrAndReturn(robj?*o)?{
????unsigned?long?ldt?=?o->lru?>>?8;
????unsigned?long?counter?=?o->lru?&?255;
????/**
????*?衰減因子?server.lfu_decay_time?用于控制計數(shù)器的衰減速度
????*?每過?server.lfu_decay_time?分鐘訪問計數(shù)減?1
????*?默認(rèn)值為?1
????*/
????unsigned?long?num_periods?=?server.lfu_decay_time???LFUTimeElapsed(ldt)?/?server.lfu_decay_time?:?0;
????if?(num_periods)
????????counter?=?(num_periods?>?counter)???0?:?counter?-?num_periods;
????return?counter;
}

16bits 最多能保存的分鐘數(shù)，換算成天數(shù)約為 45 天，因此 LDT 時間戳每隔 45 天就會重置一次。

執(zhí)行刪除

每當(dāng)客戶端執(zhí)行命令產(chǎn)生新數(shù)據(jù)時，redis 會檢查內(nèi)存使用是否超過?maxmemory，如果超過則嘗試根據(jù)?maxmemory_policy?淘汰數(shù)據(jù)：

//?redis?處理命令的主方法，在真正執(zhí)行命令前，會有各種檢查，包括對OOM情況下的處理:
int?processCommand(client?*c)?{

????//?...

????//?設(shè)置了?maxmemory?時，如果有必要，嘗試釋放內(nèi)存(evict)
????if?(server.maxmemory?&&?!server.lua_timedout)?{
????????int?out_of_memory?=?(performEvictions()?==?EVICT_FAIL);
????????
????????//?...

????????//?如果釋放內(nèi)存失敗，并且當(dāng)前將要執(zhí)行的命令不允許OOM（一般是寫入類命令）
????????if?(out_of_memory?&&?reject_cmd_on_oom)?{
????????????rejectCommand(c,?shared.oomerr);?//?向客戶端返回OOM
????????????return?C_OK;
????????}
????}
}

實(shí)際執(zhí)行刪除的是?performEvictions?函數(shù)：

int?performEvictions(void)?{
????//?循環(huán)，嘗試釋放足夠大的內(nèi)存
????while?(mem_freed?????????
????????//?...

????????if?(server.maxmemory_policy?&?(MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU)?||
????????????server.maxmemory_policy?==?MAXMEMORY_VOLATILE_TTL)
????????{

????????????/**
????????????*?redis?使用的是近似?LRU?/?LFU?算法
????????????*?在淘汰對象時不會遍歷所有記錄，而是對記錄進(jìn)行采樣
????????????*?EvictionPoolLRU?被用于臨時存儲應(yīng)該被優(yōu)先淘汰的樣本數(shù)據(jù)
????????????*/
????????????struct?evictionPoolEntry?*pool?=?EvictionPoolLRU;
????????????
????????????//?根據(jù)配置的?maxmemory-policy，拿到一個可以釋放掉的bestkey
????????????while(bestkey?==?NULL)?{
????????????????unsigned?long?total_keys?=?0,?keys;

????????????????//?遍歷所有的?db?實(shí)例
????????????????for?(i?=?0;?i?????????????????????db?=?server.db+i;
????????????????????dict?=?(server.maxmemory_policy?&?MAXMEMORY_FLAG_ALLKEYS)??
????????????????????????????db->dict?:?db->expires;
????????????????????//?根據(jù)?policy?選擇采樣的集合（keyspace?或?expire?set）
????????????????????if?((keys?=?dictSize(dict))?!=?0)?{
????????????????????????//?采樣并填充?pool
????????????????????????evictionPoolPopulate(i,?dict,?db->dict,?pool);
????????????????????????total_keys?+=?keys;
????????????????????}
????????????????}

????????????????//?遍歷?pool?中的記錄，釋放內(nèi)存
????????????????for?(k?=?EVPOOL_SIZE-1;?k?>=?0;?k--)?{
????????????????????if?(pool[k].key?==?NULL)?continue;
????????????????????bestdbid?=?pool[k].dbid;

????????????????????if?(server.maxmemory_policy?&?MAXMEMORY_FLAG_ALLKEYS)?{
????????????????????????de?=?dictFind(server.db[pool[k].dbid].dict,?pool[k].key);
????????????????????}?else?{
????????????????????????de?=?dictFind(server.db[pool[k].dbid].expires,?pool[k].key);
????????????????????}

????????????????????//?將記錄從?pool?中剔除
????????????????????if?(pool[k].key?!=?pool[k].cached)
????????????????????????sdsfree(pool[k].key);
????????????????????pool[k].key?=?NULL;
????????????????????pool[k].idle?=?0;

????????????????????if?(de)?{
????????????????????????//?提取該記錄的?key
????????????????????????bestkey?=?dictGetKey(de);
????????????????????????break;
????????????????????}?else?{
????????????????????????/*?Ghost...?Iterate?again.?*/
????????????????????}
????????????????}
????????????}
????????}

????????//?最終選中了一個?bestkey
????????if?(bestkey)?{

????????????//?如果配置了?lazyfree-lazy-eviction，嘗試異步刪除
????????????if?(server.lazyfree_lazy_eviction)
????????????????dbAsyncDelete(db,keyobj);
????????????else
????????????????dbSyncDelete(db,keyobj);
????????????
????????????//?...

????????}?else?{
????????????goto?cant_free;?/*?nothing?to?free...?*/
????????}
????}
}

負(fù)責(zé)采樣的?evictionPoolPopulate?函數(shù)：

#define?EVPOOL_SIZE?16
#define?EVPOOL_CACHED_SDS_SIZE?255
struct?evictionPoolEntry?{
????unsigned?long?long?idle;????/*?LRU?空閑時間?/?LFU?頻率倒數(shù)（優(yōu)先淘汰該值較大的記錄）?*/
????sds?key;????????????????????/*?參與淘汰篩選的鍵?*/
????sds?cached;?????????????????/*?鍵名緩存?*/
????int?dbid;???????????????????/*?數(shù)據(jù)庫ID?*/
};

//?evictionPool?數(shù)組用于輔助?eviction?操作
static?struct?evictionPoolEntry?*evictionPoolEntry;

/**
?*?在給定的?sampledict?集合中進(jìn)行采樣
?*?并將其中應(yīng)該被淘汰的記錄記錄至?evictionPool
?*/
void?evictionPoolPopulate(int?dbid,?dict?*sampledict,?dict?*keydict,?struct?evictionPoolEntry?*pool)?{
????int?j,?k,?count;
????dictEntry?*samples[server.maxmemory_samples];

????//?從?sampledict?中隨機(jī)獲取?maxmemory_samples?個樣本數(shù)據(jù)
????count?=?dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);

????//?遍歷樣本數(shù)據(jù)
????for?(j?=?0;?j?????????//?根據(jù)?maxmemory_policy?計算樣本空閑時間?idle
????????if?(server.maxmemory_policy?&?MAXMEMORY_FLAG_LRU)?{
????????????idle?=?estimateObjectIdleTime(o);
????????}?else?if?(server.maxmemory_policy?&?MAXMEMORY_FLAG_LFU)?{
????????????idle?=?255-LFUDecrAndReturn(o);
????????}?else?{
????????????//?...
????????}

????????k?=?0;?//?根據(jù)?idle?定位樣本在?evictionPool?中的索引（樣本按照?idle?升序）
????????while?(k?????????
????????if?(k?==?0?&&?pool[EVPOOL_SIZE-1].key?!=?NULL)?{
????????????//?樣本空閑時間不夠長，不參與該輪?eviction
????????????continue;
????????}?else?if?(k?????????????//?樣本對應(yīng)的位置為空，可以直接插入至該位置
????????}?else?{
???????????//?樣本對應(yīng)的位置已被占用，移動其他元素空出該位置
????????}

????????//?...
????????
????????//?將樣本數(shù)據(jù)插入其對應(yīng)的位置?k?
????????int?klen?=?sdslen(key);
????????if?(klen?>?EVPOOL_CACHED_SDS_SIZE)?{
????????????pool[k].key?=?sdsdup(key);
????????}?else?{
???????????//?如果?key?長度不超過?EVPOOL_CACHED_SDS_SIZE，則復(fù)用?sds?對象
????????}
????????pool[k].idle?=?idle;
????????pool[k].dbid?=?dbid;
????}
}

Java 實(shí)現(xiàn)

在了解以上知識后，嘗試使用 Java 實(shí)現(xiàn)?線程安全?的淘汰策略。

確定簿記結(jié)構(gòu)

在一個多線程安全的緩存中，很重要的一點(diǎn)是減少簿記：

一方面避免額外狀態(tài)的維護(hù)開銷
另一方面可以減少系統(tǒng)處于不一致狀態(tài)的邊界情況

因此參考 redis 使用計數(shù)器來記錄訪問模式：

/**
?*?緩存記錄
?*/
public?abstract?class?CacheEntry?{

????//?CAS?Updater
????private?static?final?AtomicLongFieldUpdater
????????????TTL_UPDATER?=?AtomicLongFieldUpdater.newUpdater(CacheEntry.class,?"ttl");

????//?緩存記錄的剩余存活時間（無符號長整數(shù)）
????private?volatile?long?ttl;

????protected?CacheEntry(long?ttl)?{
????????this.ttl?=?ttl;
????}

????public?long?ttl()?{
????????return?ttl;
????}

????//?支持并發(fā)更新?TTL
????public?boolean?casTTL(long?old,?long?ttl)?{
????????return?TTL_UPDATER.compareAndSet(this,?old,?ttl);
????}

}

/**
?*?淘汰策略
?*/
public?interface?EvictStrategy?{

????//?更新緩存記錄的?TTL
????void?updateTTL(CacheEntry?node);

????//?根據(jù)當(dāng)前時間戳，計算緩存記錄的?TTL
????long?weightTTL(CacheEntry?node,?long?now);

}

確定刪除策略

受限于簿記結(jié)構(gòu)，redis 只能通過采樣來規(guī)避大量的遍歷，減少?實(shí)時刪除?策略對主線程的阻塞。
而在對于內(nèi)存限制沒那么嚴(yán)謹(jǐn)?shù)那闆r下，可以使用?懶惰刪除?策略，減少單次請求的開銷：


public?abstract?class?EvictableCache?{

????EvictStrategy?evicting;?//?淘汰策略

????/**
?????*?在讀寫緩存記錄時，更新該記錄的?TTL
?????*?@param?entry?最近被訪問的緩存記錄
?????*/
????void?accessEntry(CacheEntry?entry)?{
????????evicting.updateTTL(entry);
????}

????/**
?????*?批量淘汰緩存
?????*?@param?evictSamples?緩存樣本
?????*?@param?evictNum?最大淘汰數(shù)量
?????*?@return?應(yīng)該被淘汰的記錄
?????*/
????Collection?evictEntries(Iterable?evictSamples,?int?evictNum)?{

????????//?比較兩個?CacheEntry?的?TTL（優(yōu)先淘汰?TTL?較小的記錄）
????????Comparator?comparator?=?new?Comparator()?{
????????????final?long?now?=?System.currentTimeMillis();
????????????public?int?compare(CacheEntry?o1,?CacheEntry?o2)?{
????????????????long?w1?=?evicting.weightTTL(o1,?now);
????????????????long?w2?=?evicting.weightTTL(o2,?now);
????????????????return?-Long.compareUnsigned(w1,?w2);
????????????}
????????};

????????//?使用大頂堆記錄?TTL?最小的?K?個?CacheEntry
????????PriorityQueue?evictPool?=?new?PriorityQueue<>(evictNum,?comparator);

????????Iterator?iterator?=?evictSamples.iterator();
????????while?(iterator.hasNext())?{
????????????CacheEntry?entry?=?iterator.next();
????????????if?(evictPool.size()?????????????????evictPool.add(entry);
????????????}?else?{
????????????????//?如果?CacheEntry?的?TTL?小于堆頂記錄
????????????????//?則彈出堆頂記錄，并將?TTL?更小的記錄放入堆中
????????????????CacheEntry?top?=?evictPool.peek();
????????????????if?(comparator.compare(entry,?top)?????????????????????evictPool.poll();
????????????????????evictPool.add(entry);
????????????????}
????????????}
????????}

????????return?evictPool;
????}
}

實(shí)現(xiàn)淘汰策略

FIFO 策略

/**
?*?FIFO?策略
?*/
public?class?FirstInFirstOut?implements?EvictStrategy?{

????//?計數(shù)器，每發(fā)生一次訪問操作自增?1
????private?final?AtomicLong?counter?=?new?AtomicLong(0);

????//?第一次訪問時才更新?TTL
????public?void?updateTTL(CacheEntry?node)?{
????????node.casTTL(0,?counter.incrementAndGet());
????}

????//?返回第一次被訪問的序號
????public?long?weightTTL(CacheEntry?node,?long?now)?{
????????return?node.ttl();
????}

}

LRU 策略

/**
?*?LRU-2?策略
?*/
public?class?LeastRecentlyUsed?implements?EvictStrategy?{

????//?邏輯時鐘，每發(fā)生一次訪問操作自增?1
????private?final?AtomicLong?clock?=?new?AtomicLong(0);

????/**
?????*?更新?LRU?時間
?????*/
????public?void?updateTTL(CacheEntry?node)?{
????????long?old?=?node.ttl();
????????long?tick?=?clock.incrementAndGet();
????????long?flag?=?old?==?0???Long.MIN_VALUE:?0;
????????//?flag?=?Long.MIN_VALUE?表示放入?History?Queue
????????//?flag?=?0??????????????表示放入?LRU?Cache
????????long?ttl?=?(tick?&?Long.MAX_VALUE)?|?flag;
????????while?((old?&?Long.MAX_VALUE)?????????????old?=?node.ttl();
????????????ttl?=?tick?&?Long.MAX_VALUE;?//?CAS?失敗說明已經(jīng)是二次訪問
????????}
????}

????/**
?????*?根據(jù)?LRU?時間計算?TTL
?????*/
????public?long?weightTTL(CacheEntry?node,?long?now)?{
????????long?ttl?=?node.ttl();
????????return?-1L?-?ttl;
????}

}

LFU 策略

/**
?*?LFU-AgeDecay?策略
?*/
public?class?LeastFrequentlyUsed?implements?EvictStrategy?{

????private?static?final?int?TIMESTAMP_BITS?=?40;?//?40bits?記錄訪問時間戳（保證?34?年不溢出）
????private?static?final?int?FREQUENCY_BITS?=?24;?//?24bits?作為對數(shù)計數(shù)器（可以忽略計數(shù)溢出的情況）

????private?final?long?ERA?=?System.currentTimeMillis();??//?起始時間（記錄相對于該值的時間戳）
????private?final?double?LOG_FACTOR?=?1;??????????????????//?對數(shù)因子
????private?final?TimeUnit?DECAY_UNIT?=?TimeUnit.MINUTES;?//?時間衰減單位

????/**
?????*?更新?LFU?計數(shù)器與訪問時間
?????*?與?redis?不同，更新時不會對計數(shù)進(jìn)行衰減
?????*/
????public?void?updateTTL(CacheEntry?node)?{

????????final?long?now?=?System.currentTimeMillis();

????????long?old?=?node.ttl();
????????long?timestamp?=?old?>>>?FREQUENCY_BITS;
????????long?frequency?=?old?&?(~0L?>>>?TIMESTAMP_BITS);

????????//?計算訪問時間
????????long?elapsed?=?Math.min(~0L?>>>?FREQUENCY_BITS,?now?-?ERA);
????????while?(timestamp?????????????//?增加訪問計數(shù)
????????????double?rand?=?ThreadLocalRandom.current().nextDouble();
????????????if?(1./(frequency?*?LOG_FACTOR?+?1)?>?rand)?{
????????????????frequency++;
????????????????frequency?&=?(~0L?>>>?TIMESTAMP_BITS);
????????????}
????????????//?更新?TTL
????????????long?ttl?=?elapsed?<>>?TIMESTAMP_BITS);
????????????if?(node.casTTL(old,?ttl))?{
????????????????break;
????????????}
????????????old?=?node.ttl();
????????????timestamp?=?old?>>>?FREQUENCY_BITS;
????????????frequency?=?old?&?(~0L?>>>?TIMESTAMP_BITS);
????????}
????}

????/**
?????*?返回衰減后的?LFU?計數(shù)
?????*/
????public?long?weightTTL(CacheEntry?node,?long?now)?{
????????long?ttl?=?node.ttl();
????????long?timestamp?=?ttl?>>>?FREQUENCY_BITS;
????????long?frequency?=?ttl?&?(~0L?>>>?TIMESTAMP_BITS);
????????long?decay?=?DECAY_UNIT.toMinutes(Math.max(now?-?ERA,?timestamp)?-?timestamp);
????????return?frequency?-?decay;
????}

}

至此，對 redis 的淘汰策略分析完畢，后續(xù)將對 redis 的一些其他細(xì)節(jié)進(jìn)行分享，感謝觀看。

鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布

??????

??長按上方微信二維碼?2 秒

感謝點(diǎn)贊支持下哈?

Redis 的緩存淘汰機(jī)制（Eviction）

相關(guān)配置

maxmemory

maxmemory-policy

maxmemory-samples

lazyfree-lazy-eviction