過期刪除策略的深度剖析

Redis 可以對 key 設(shè)置過期時(shí)間的，為了防止過期的key長期占用內(nèi)存，需要相應(yīng)的過期刪除策略將過期的key刪除

基礎(chǔ)操作

Redis設(shè)置過期時(shí)間

• setex key1 5 value1：創(chuàng)建記錄的時(shí)候指定過期時(shí)間，設(shè)置key1在5秒后過期

其實(shí)Redis這是一種基于創(chuàng)建時(shí)間來判定是否過期的機(jī)制，也即常規(guī)上說的TTL策略，當(dāng)設(shè)定了過期時(shí)間之后不管有沒有被使用都會(huì)到期被強(qiáng)制清理掉。但有很多場景下也會(huì)期望數(shù)據(jù)能夠按照TTI（指定時(shí)間未使用再過期）的方式來過期清理，如用戶鑒權(quán)場景：

假設(shè)用戶登錄系統(tǒng)后生成token并存儲(chǔ)到Redis中，指定token有效期30分鐘，那么如果用戶一直在使用系統(tǒng)的時(shí)候突然時(shí)間到了然后退出要求重新登錄，這個(gè)體驗(yàn)感就會(huì)很差。正確的預(yù)期應(yīng)該是用戶連續(xù)操作的時(shí)候就不要退出登錄，只有連續(xù)30分鐘沒有操作的時(shí)候才過期處理。

略有遺憾的是，Redis并不支持按照TTI機(jī)制來做數(shù)據(jù)過期處理。但是作為補(bǔ)償，Redis提供了一個(gè)重新設(shè)定某個(gè)key值過期時(shí)間的方法，可以通過expire方法來實(shí)現(xiàn)指定key的續(xù)期操作，以一種曲線救國的方式滿足訴求。

實(shí)現(xiàn)緩存續(xù)期

• expire <key> <n>：設(shè)置 key 在 n 秒后過期，比如 expire key 100 表示設(shè)置 key 在 100 秒后過期；
• pexpire <key> <n>：設(shè)置 key 在 n 毫秒后過期，比如 pexpire key2 100000 表示設(shè)置 key2 在 100000 毫秒（100 秒）后過期。
• expireat <key> <n>：設(shè)置 key 在某個(gè)時(shí)間戳（精確到秒）之后過期，比如 expireat key3 1683187646 表示 key3 在時(shí)間戳 1683187646 后過期（精確到秒）；
• pexpireat <key> <n>：設(shè)置 key 在某個(gè)時(shí)間戳（精確到毫秒）之后過期，比如 pexpireat key4 1683187660972 表示 key4 在時(shí)間戳 1683187660972 后過期（精確到毫秒）

對于上面說的用戶token續(xù)期的訴求，可以這樣來操作：

用戶首次登錄成功后，會(huì)生成一個(gè)token令牌，然后將令牌與用戶信息存儲(chǔ)到redis中，設(shè)定30分鐘有效期。 每次請求接口中攜帶token來鑒權(quán)，每次get請求的時(shí)候，就重新通過expire操作將token的過期時(shí)間重新設(shè)定為30分鐘。 持續(xù)30分鐘無請求后，此條token緩存信息過期失效。同樣實(shí)現(xiàn)了TTI的效果。

ttl查看過期時(shí)間

# 查看 key1 過期時(shí)間還剩多少
> ttl key
(integer) 56

# 取消 key 的過期時(shí)間
> persist key
(integer) 1

//永不過期返回-1
> ttl key
(integer) -1

如何判斷過期時(shí)間

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* 鍵值對的過期時(shí)間 */
 //……
} redisDb;

dict是hash表

• *dict是鍵值對，指向的是數(shù)據(jù)庫中保存的具體的key value對象，key是String類型，value是具體的數(shù)據(jù)類型
• *expires是過期字典，key與*dict中的key一致，value則是一個(gè) long long 類型的整數(shù)，這個(gè)整數(shù)保存了 key 的過期時(shí)間；

過期字典的數(shù)據(jù)結(jié)構(gòu)如下圖所示：

圖片

簡單地總結(jié)來說就是，設(shè)置了失效時(shí)間的key和具體的失效時(shí)間全部都維護(hù)在 expires 這個(gè)字典表中。未設(shè)置失效時(shí)間的key不會(huì)出現(xiàn)在expires字典表中。

所以當(dāng)查詢一個(gè) key 時(shí)，Redis 首先檢查該 key 是否存在于expires過期字典中：

1. 如果不在，則正常讀取鍵值；
2. 如果存在，則會(huì)獲取該 key 的過期時(shí)間，然后與當(dāng)前系統(tǒng)時(shí)間進(jìn)行比對，如果比系統(tǒng)時(shí)間大，那就沒有過期，否則判定該 key 已過期。

過期刪除策略

定時(shí)刪除

在設(shè)置key的過期時(shí)間的同時(shí)，為該key創(chuàng)建一個(gè)定時(shí)器，讓定時(shí)器在key的過期時(shí)間來臨時(shí)，對key進(jìn)行刪除。

優(yōu)點(diǎn)：保證內(nèi)存被盡快釋放，對內(nèi)存友好

缺點(diǎn)：若過期key很多，刪除這些key會(huì)占用很多的CPU時(shí)間，在CPU時(shí)間緊張的情況下，CPU不能把所有的時(shí)間用來做要緊的事兒，還需要去花時(shí)間刪除這些key，定時(shí)器的創(chuàng)建耗時(shí)，若為每一個(gè)設(shè)置過期時(shí)間的key創(chuàng)建一個(gè)定時(shí)器（將會(huì)有大量的定時(shí)器產(chǎn)生），性能影響嚴(yán)重。對CPU不友好

結(jié)論：此方法基本上沒人用

惰性刪除

過期的key并不一定會(huì)馬上刪除，還會(huì)占用著內(nèi)存。 當(dāng)你真正查詢這個(gè)key時(shí)，redis會(huì)檢查一下，這個(gè)設(shè)置了過期時(shí)間的key是否過期了? 如果過期了就會(huì)刪除，返回空。這就是惰性刪除。

優(yōu)點(diǎn)：刪除操作只發(fā)生在從數(shù)據(jù)庫取出key的時(shí)候發(fā)生，而且只刪除當(dāng)前key，所以對CPU時(shí)間的占用是比較少的,對 CPU友好

缺點(diǎn)：若大量的key在超出超時(shí)時(shí)間后，很久一段時(shí)間內(nèi)，都沒有被獲取過，那么可能發(fā)生內(nèi)存泄露。對內(nèi)存不友好

定期刪除

每隔一段時(shí)間，程序就對數(shù)據(jù)庫進(jìn)行一次檢查，刪除里面的過期鍵，至于要?jiǎng)h除多少過期鍵，以及要檢查多少個(gè)數(shù)據(jù)庫，由算法決定

優(yōu)點(diǎn)：通過限制刪除操作執(zhí)行的時(shí)長和頻率，來減少刪除操作對 CPU 的影響，同時(shí)也能刪除一部分過期的數(shù)據(jù)減少了過期鍵對空間的無效占用。

缺點(diǎn)：

• 內(nèi)存清理方面沒有定時(shí)刪除效果好，同時(shí)沒有惰性刪除使用的系統(tǒng)資源少。
• 難以確定刪除操作執(zhí)行的時(shí)長和頻率。如果執(zhí)行的太頻繁，定期刪除策略變得和定時(shí)刪除策略一樣，對CPU不友好；如果執(zhí)行的太少，那又和惰性刪除一樣了，過期 key 占用的內(nèi)存不能及時(shí)得到釋放

Redis的過期刪除策略

redis實(shí)際使用的過期鍵刪除策略是定期刪除策略和惰性刪除策略：

• 定期刪除策略：redis 會(huì)將每個(gè)設(shè)置了過期時(shí)間的 key 放入到一個(gè)獨(dú)立的字典中，以后會(huì)定時(shí)遍歷這個(gè)字典來刪除到期的 key。
• 惰性刪除策略：只有當(dāng)訪問某個(gè)key時(shí)，才判斷這個(gè)key是否已過期，如果已經(jīng)過期，則從實(shí)例中刪除

定時(shí)刪除是集中處理，惰性刪除是零散處理。

定期刪除策略

Redis內(nèi)部維護(hù)一個(gè)定時(shí)任務(wù)，默認(rèn)每秒進(jìn)行10次(也就是每隔100毫秒一次)過期掃描，過期掃描不會(huì)遍歷過期字典中所有的 key，而是采用了一種簡單的貪心策略。

1. 從過期字典中隨機(jī)取出20個(gè)key
2. 刪除這 20 個(gè) key 中已經(jīng)過期的 key；
3. 如果這20個(gè)key中過期key的比例超過了25%，則重復(fù)步驟1

為了保證過期掃描不會(huì)出現(xiàn)循環(huán)過度，導(dǎo)致線程卡死現(xiàn)象，算法還增加了掃描時(shí)間的上限，默認(rèn)不會(huì)超過 25ms。

為什么key集中過期時(shí)，其它key的讀寫效率會(huì)降低？

Redis的定期刪除策略是在Redis主線程中執(zhí)行的，也就是說如果在執(zhí)行定期刪除的過程中，出現(xiàn)了需要大量刪除過期key的情況，那么在業(yè)務(wù)訪問時(shí)，必須等這個(gè)定期刪除任務(wù)執(zhí)行結(jié)束，才可以處理業(yè)務(wù)請求。此時(shí)就會(huì)出現(xiàn)，業(yè)務(wù)訪問延時(shí)增大的問題，最大延遲為25毫秒。

為了盡量避免這個(gè)問題，在設(shè)置過期時(shí)間時(shí)，可以給過期時(shí)間設(shè)置一個(gè)隨機(jī)范圍，避免同一時(shí)刻過期。

惰性刪除策略

int expireIfNeeded(redisDb *db, robj *key, int flags) {
 //檢查是否開啟惰性刪除策略
    if (server.lazy_expire_disabled) return 0;
    if (!keyIsExpired(db,key)) return 0;//檢查key是否過期，沒過期不用刪除
 
 //……
 
    //刪除失效key
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

int keyIsExpired(redisDb *db, robj *key) {
    //假如Redis服務(wù)器正在從RDB文件中加載數(shù)據(jù)，暫時(shí)不進(jìn)行失效主鍵的刪除，直接返回0
    if (server.loading) return 0;
 
 //獲取主鍵的失效時(shí)間 get當(dāng)前時(shí)間-創(chuàng)建時(shí)間>ttl
    mstime_t when = getExpire(db,key);
    mstime_t now;
 
 //假如失效時(shí)間為負(fù)數(shù)，說明該主鍵未設(shè)置失效時(shí)間(失效時(shí)間默認(rèn)為-1)，直接返回0 
    if (when < 0) return 0; /* No expire for this key */

    now = commandTimeSnapshot();

    //如果以上條件都不滿足，就將主鍵的失效時(shí)間與當(dāng)前時(shí)間進(jìn)行對比，如果發(fā)現(xiàn)指定的key還未失效就返回0
    return now > when;
}

過期key對持久化的影響

RDB：

• 生成rdb文件：生成時(shí)，程序會(huì)對key進(jìn)行檢查，過期key不放入rdb文件。
• 載入rdb文件：載入時(shí)，如果以主服務(wù)器模式運(yùn)行，程序會(huì)對文件中保存的key進(jìn)行檢查，未過期的key會(huì)被載入到數(shù)據(jù)庫中，而過期key則會(huì)忽略；如果以從服務(wù)器模式運(yùn)行，無論鍵過期與否，均會(huì)載入數(shù)據(jù)庫中，過期key會(huì)通過與主服務(wù)器同步而刪除。

AOF：

• 當(dāng)服務(wù)器以AOF持久化模式運(yùn)行時(shí)，如果數(shù)據(jù)庫中的某個(gè)key已經(jīng)過期，但它還沒有被惰性刪除或者定期刪除，那么AOF文件不會(huì)因?yàn)檫@個(gè)過期key而產(chǎn)生任何影響
• 當(dāng)過期key被惰性刪除或者定期刪除之后，程序會(huì)向AOF文件追加一條DEL命令，來顯示的記錄被該key已經(jīng)發(fā)被刪除
• 在執(zhí)行AOF重寫的過程中，程序會(huì)對數(shù)據(jù)庫中的key進(jìn)行檢查，已過期的key不會(huì)被保存到重寫后的AOF文件中

主從復(fù)制：當(dāng)服務(wù)器運(yùn)行在復(fù)制模式下時(shí)，從服務(wù)器的過期刪除動(dòng)作由主服務(wù)器控制：

• 主服務(wù)器在刪除一個(gè)過期key后，會(huì)顯式地向所有從服務(wù)器發(fā)送一個(gè)del命令，告知從服務(wù)器刪除這個(gè)過期key;
• 從服務(wù)器在執(zhí)行客戶端發(fā)送的讀命令時(shí)，即使碰到過期key也不會(huì)將過期key刪除，而是繼續(xù)像處理未過期的key一樣來處理過期key;
• 從服務(wù)器只有在接到主服務(wù)器發(fā)來的del命令后，才會(huì)刪除過期key。

內(nèi)存淘汰策略

過期刪除策略，是刪除已過期的 key，而當(dāng) Redis 的運(yùn)行內(nèi)存已經(jīng)超過 Redis 設(shè)置的最大內(nèi)存之后，則會(huì)使用內(nèi)存淘汰策略刪除符合條件的 key，以此來保障 Redis 高效的運(yùn)行。這兩個(gè)機(jī)制雖然都是做刪除的操作，但是觸發(fā)的條件和使用的策略都是不同的。

• 數(shù)據(jù)過期，是符合業(yè)務(wù)預(yù)期的一種數(shù)據(jù)刪除機(jī)制，為記錄設(shè)定過期時(shí)間，過期后從緩存中移除。
• 數(shù)據(jù)淘汰，是一種“有損自?！钡?/span>降級(jí)策略，是業(yè)務(wù)預(yù)期之外的一種數(shù)據(jù)刪除手段。指的是所存儲(chǔ)的數(shù)據(jù)沒達(dá)到過期時(shí)間，但緩存空間滿了，對于新的數(shù)據(jù)想要加入內(nèi)存時(shí)，為了避免OOM而需要執(zhí)行的一種應(yīng)對策略。

基礎(chǔ)操作

設(shè)置 Redis 最大運(yùn)行內(nèi)存

在配置文件redis.conf 中，可以通過參數(shù) maxmemory <bytes> 來設(shè)定最大內(nèi)存，當(dāng)數(shù)據(jù)內(nèi)存達(dá)到 maxmemory 時(shí)，便會(huì)觸發(fā)redis的內(nèi)存淘汰策略

不進(jìn)行數(shù)據(jù)淘汰

noeviction：不會(huì)淘汰任何數(shù)據(jù)。

當(dāng)使用的內(nèi)存空間超過 maxmemory 值時(shí)，也不會(huì)淘汰任何數(shù)據(jù)，但是再有寫請求時(shí)，則返回OOM錯(cuò)誤。

進(jìn)行數(shù)據(jù)淘汰

• volatile-lru：針對設(shè)置了過期時(shí)間的key，使用lru算法進(jìn)行淘汰。
• allkeys-lru：針對所有key使用lru算法進(jìn)行淘汰。
• volatile-lfu：針對設(shè)置了過期時(shí)間的key，使用lfu算法進(jìn)行淘汰。
• allkeys-lfu：針對所有key使用lfu算法進(jìn)行淘汰。
• volatile-random：針對設(shè)置了過期時(shí)間的key中使用隨機(jī)淘汰的方式進(jìn)行淘汰。
• allkeys-random：針對所有key使用隨機(jī)淘汰機(jī)制進(jìn)行淘汰。
• volatile-ttl：針對設(shè)置了過期時(shí)間的key，越早過期的越先被淘汰。

Redis對隨機(jī)淘汰和LRU策略進(jìn)行的更精細(xì)化的實(shí)現(xiàn)，支持將淘汰目標(biāo)范圍細(xì)分為全部數(shù)據(jù)和設(shè)有過期時(shí)間的數(shù)據(jù)，這種策略相對更為合理一些。因?yàn)橐话阍O(shè)置了過期時(shí)間的數(shù)據(jù)，本身就具備可刪除性，將其直接淘汰對業(yè)務(wù)不會(huì)有邏輯上的影響；而沒有設(shè)置過期時(shí)間的數(shù)據(jù)，通常是要求常駐內(nèi)存的，往往是一些配置數(shù)據(jù)或者是一些需要當(dāng)做白名單含義使用的數(shù)據(jù)（比如用戶信息，如果用戶信息不在緩存里，則說明用戶不存在），這種如果強(qiáng)行將其刪除，可能會(huì)造成業(yè)務(wù)層面的一些邏輯異常。

Redis的內(nèi)存淘汰算法

操作系統(tǒng)本身有其內(nèi)存淘汰算法，針對內(nèi)存頁面淘汰，詳情請看 內(nèi)存的頁面置換算法^[1]

LRU 算法

LRU（ Least Recently Used，最近最少使用）淘汰算法：是一種常用的頁面置換算法，也就是說最久沒有使用的緩存將會(huì)被淘汰。

傳統(tǒng)的LRU 是基于鏈表結(jié)構(gòu)實(shí)現(xiàn)的，鏈表中的元素按照操作順序從前往后排列，最新操作的key會(huì)被移動(dòng)到表頭，當(dāng)需要進(jìn)行內(nèi)存淘汰時(shí)，只需要?jiǎng)h除鏈表尾部的元素即可，因?yàn)殒湵砦膊康脑鼐痛碜罹梦幢皇褂玫脑亍?/span>

但是傳統(tǒng)的LRU算法存在兩個(gè)問題：

• 需要用鏈表管理所有的緩存數(shù)據(jù)，這會(huì)帶來額外的空間開銷；
• 當(dāng)有數(shù)據(jù)被訪問時(shí)，需要在鏈表上把該數(shù)據(jù)移動(dòng)到頭端，如果有大量數(shù)據(jù)被訪問，就會(huì)帶來很多鏈表元素的移動(dòng)操作，會(huì)很耗時(shí)，進(jìn)而會(huì)降低 Redis 緩存性能。

Redis 使用的是一種近似 LRU 算法，目的是為了更好的節(jié)約內(nèi)存，它的實(shí)現(xiàn)方式是給現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)添加一個(gè)額外的字段，用于記錄此key的最后一次訪問時(shí)間。Redis 內(nèi)存淘汰時(shí)，會(huì)使用隨機(jī)采樣的方式來淘汰數(shù)據(jù)，它是隨機(jī)取 5 個(gè)值 (此值可配置) ，然后淘汰一個(gè)最少訪問的key，之后把剩下的key暫存到一個(gè)池子中，繼續(xù)隨機(jī)取出一批key，并與之前池子中的key比較，再淘汰一個(gè)最少訪問的key。以此循環(huán)，直到內(nèi)存降到maxmemory之下。

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; //記錄 Key 的最后被訪問時(shí)間
    int refcount;
    void *ptr;
};

在 LRU 算法中，Redis 對象頭的 24 bits 的 lru 字段是用來記錄 key 的訪問時(shí)間戳，因此在 LRU 模式下，Redis可以根據(jù)對象頭中的 lru 字段記錄的值，來比較最后一次 key 的訪問時(shí)間長，從而淘汰最久未被使用的 key。

但是 LRU 算法有一個(gè)問題，無法解決緩存污染問題，比如應(yīng)用一次讀取了大量的數(shù)據(jù)，而這些數(shù)據(jù)只會(huì)被讀取這一次，那么這些數(shù)據(jù)會(huì)留存在 Redis 緩存中很長一段時(shí)間，造成緩存污染。Redis利用LFU解決這個(gè)問題

LFU 算法

最不常用的算法是根據(jù)總訪問次數(shù)來淘汰數(shù)據(jù)的，它的核心思想是“如果數(shù)據(jù)過去被訪問多次，那么將來被訪問的頻率也更高”。

Redis 的 LFU 算法也是通過 robj 對象的 lru 字段來保存 Key 的訪問頻率的，LFU 算法把  lru 字段分為兩部分，如下圖：

圖片

• 0 ~ 7 位：用于保存 Key 的訪問頻率計(jì)數(shù)器。
• 8 ~ 23 位：用于保存當(dāng)前時(shí)間（以分鐘計(jì)算）。

由于訪問頻率計(jì)數(shù)器只有8個(gè)位，所以取值范圍為 0 ~ 255，如果每訪問 Key 都增加 1，那么很快就用完，LFU 算法也就不起效果了。所以 Redis 使用了一種比較復(fù)雜的算法了計(jì)算訪問頻率，算法如下：

1. 先按照上次訪問距離當(dāng)前的時(shí)長，來對 logc 進(jìn)行衰減；
2. 然后，再按照一定概率增加 logc 的值

具體為：

1. 在每次 key 被訪問時(shí)，會(huì)先對 訪問頻率 做一個(gè)衰減操作，衰減的值跟前后訪問時(shí)間的差距有關(guān)系，如果上一次訪問的時(shí)間與這一次訪問的時(shí)間差距很大，那么衰減的值就越大，這樣實(shí)現(xiàn)的 LFU 算法是根據(jù)訪問頻率來淘汰數(shù)據(jù)的，而不只是訪問次數(shù)。訪問頻率需要考慮 key 的訪問是多長時(shí)間段內(nèi)發(fā)生的。key 的先前訪問距離當(dāng)前時(shí)間越長，那么這個(gè) key 的訪問頻率相應(yīng)地也就會(huì)降低，這樣被淘汰的概率也會(huì)更大。
2. 對 訪問頻率 做完衰減操作后，就開始對 訪問頻率 進(jìn)行增加操作，增加操作并不是單純的 + 1，而是根據(jù)概率增加，如果 訪問頻率 越大的 key，它的 訪問頻率 就越難再增加。

訪問頻率衰減算法：原理就是，Key 越久沒被訪問，衰減的程度就越大。

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;// 獲取 Key 最后訪問時(shí)間(單位為分鐘)
    unsigned long counter = o->lru & 255;// 獲取 Key 訪問頻率計(jì)數(shù)器的值
 // 下面是計(jì)算要衰減的數(shù)量
 // LFUTimeElapsed 函數(shù)用于獲取 Key 沒被訪問的時(shí)間(單位為分鐘)
  // lfu_decay_time 是衰減的力度，通過配置項(xiàng) lfu-decay-time 設(shè)置，值越大，衰減力度越小
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
 // 對訪問頻率計(jì)數(shù)器進(jìn)行衰減操作
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

從 LFUDecrAndReturn 函數(shù)可知，lfu-decay-time 設(shè)置越大，衰減的力度就越小。如果 lfu-decay-time 設(shè)置為1，并且 Key 在 10 分鐘內(nèi)沒被訪問的話，按算法可知，訪問頻率計(jì)數(shù)器就會(huì)被衰減10。

訪問頻率增加算法：

uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;// 獲取隨機(jī)數(shù)r
    double baseval = counter - LFU_INIT_VAL;// 計(jì)數(shù)器舊值
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);// 根據(jù)計(jì)數(shù)器舊值與影響因子來計(jì)算出p
    if (r < p) counter++;// 如果 p 大于 r, 那么對計(jì)數(shù)器進(jìn)行加以操作
    return counter;
}

LFU 算法更新 lru 字段和LRU 算法更新lru字段都是在 lookupKey 函數(shù)中完成的

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    robj *val = NULL;
    if (de) {
        val = dictGetVal(de);
       //……
    }

    if (val) {
       //……
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {// 如果配置的是LFU淘汰算法
                updateLFU(val);// 更新LFU算法的統(tǒng)計(jì)信息
            } else {// 如果配置的是LRU淘汰算法
                val->lru = LRU_CLOCK();// 更新 Key 最后被訪問時(shí)間
            }
        }

       //……
    } else {
        //……
    }

    return val;
}

參考資料

[1] 內(nèi)存的頁面置換算法: https://www.seven97.top/cs-basics/operating-system/memorypagereplacementalgorithm.html