redis 數據刪除策略和逐出算法

redis 數據刪除策略和逐出算法

數據存儲和有效期

redis 工作流程中,過期的數據並不需要馬上就要執行刪除操作。因為這些刪不刪除只是一種狀態表示,可以異步的去處理,在不忙的時候去把這些不緊急的刪除操作做了,從而保證 redis 的高效

數據的存儲

在redis中數據的存儲不僅僅需要保存數據本身還要保存數據的生命周期,也就是過期時間。在redis 中 數據的存儲結構如下圖:

獲取有效期

Redis是一種內存級數據庫,所有數據均存放在內存中,內存中的數據可以通過TTL指令獲取其狀態

刪除策略

在內存佔用與CPU佔用之間尋找一種平衡,顧此失彼都會造成整體redis性能的下降,甚至引發服務器宕機或內存泄漏。

定時刪除

創建一個定時器,當key設置過期時間,且過期時間到達時,由定時器任務立即執行對鍵的刪除操作

優點

節約內存,到時就刪除,快速釋放掉不必要的內存佔用

缺點

CPU壓力很大,無論CPU此時負載多高,均佔用CPU,會影響redis服務器響應時間和指令吞吐量

總結

用處理器性能換取存儲空間

惰性刪除

數據到達過期時間,不做處理。等下次訪問該數據,如果未過期,返回數據。發現已經過期,刪除,返回不存在。這樣每次讀寫數據都需要檢測數據是否已經到達過期時間。也就是惰性刪除總是在數據的讀寫時發生的。

expireIfNeeded函數

對所有的讀寫命令進行檢查,檢查操作的對象是否過期。過期就刪除返回過期,不過期就什麼也不做~。

執行數據寫入過程中,首先通過expireIfNeeded函數對寫入的key進行過期判斷。

/*
 * 為執行寫入操作而取出鍵 key 在數據庫 db 中的值。
 *
 * 和 lookupKeyRead 不同,這個函數不會更新服務器的命中/不命中信息。
 *
 * 找到時返回值對象,沒找到返回 NULL 。
 */
robj *lookupKeyWrite(redisDb *db, robj *key) {

    // 刪除過期鍵
    expireIfNeeded(db,key);

    // 查找並返回 key 的值對象
    return lookupKey(db,key);
}

執行數據讀取過程中,首先通過expireIfNeeded函數對寫入的key進行過期判斷。

/*
 * 為執行讀取操作而取出鍵 key 在數據庫 db 中的值。
 *
 * 並根據是否成功找到值,更新服務器的命中/不命中信息。
 *
 * 找到時返回值對象,沒找到返回 NULL 。
 */
robj *lookupKeyRead(redisDb *db, robj *key) {
    robj *val;

    // 檢查 key 釋放已經過期
    expireIfNeeded(db,key);

    // 從數據庫中取出鍵的值
    val = lookupKey(db,key);

    // 更新命中/不命中信息
    if (val == NULL)
        server.stat_keyspace_misses++;
    else
        server.stat_keyspace_hits++;

    // 返回值
    return val;
}

執行過期動作expireIfNeeded其實內部做了三件事情,分別是:

  • 查看key判斷是否過期
  • 向slave節點傳播執行過期key的動作併發送事件通知
  • 刪除過期key
/*
 * 檢查 key 是否已經過期,如果是的話,將它從數據庫中刪除。
 *
 * 返回 0 表示鍵沒有過期時間,或者鍵未過期。
 *
 * 返回 1 表示鍵已經因為過期而被刪除了。
 */
int expireIfNeeded(redisDb *db, robj *key) {

    // 取出鍵的過期時間
    mstime_t when = getExpire(db,key);
    mstime_t now;

    // 沒有過期時間
    if (when < 0) return 0; /* No expire for this key */

    /* Don't expire anything while loading. It will be done later. */
    // 如果服務器正在進行載入,那麼不進行任何過期檢查
    if (server.loading) return 0;

    // 當服務器運行在 replication 模式時
    // 附屬節點並不主動刪除 key
    // 它只返回一個邏輯上正確的返回值
    // 真正的刪除操作要等待主節點發來刪除命令時才執行
    // 從而保證數據的同步
    if (server.masterhost != NULL) return now > when;

    // 運行到這裏,表示鍵帶有過期時間,並且服務器為主節點

    /* Return when this key has not expired */
    // 如果未過期,返回 0
    if (now <= when) return 0;

    /* Delete the key */
    server.stat_expiredkeys++;

    // 向 AOF 文件和附屬節點傳播過期信息
    propagateExpire(db,key);

    // 發送事件通知
    notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
        "expired",key,db->id);

    // 將過期鍵從數據庫中刪除
    return dbDelete(db,key);
}

判斷key是否過期的數據結構是db->expires,也就是通過expires的數據結構判斷數據是否過期。
內部獲取過期時間並返回。

/*
 * 返回字典中包含鍵 key 的節點
 *
 * 找到返回節點,找不到返回 NULL
 *
 * T = O(1)
 */
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    // 字典(的哈希表)為空
    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */

    // 如果條件允許的話,進行單步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 計算鍵的哈希值
    h = dictHashKey(d, key);
    // 在字典的哈希表中查找這個鍵
    // T = O(1)
    for (table = 0; table <= 1; table++) {

        // 計算索引值
        idx = h & d->ht[table].sizemask;

        // 遍歷給定索引上的鏈表的所有節點,查找 key
        he = d->ht[table].table[idx];
        // T = O(1)
        while(he) {

            if (dictCompareKeys(d, key, he->key))
                return he;

            he = he->next;
        }

        // 如果程序遍歷完 0 號哈希表,仍然沒找到指定的鍵的節點
        // 那麼程序會檢查字典是否在進行 rehash ,
        // 然後才決定是直接返回 NULL ,還是繼續查找 1 號哈希表
        if (!dictIsRehashing(d)) return NULL;
    }

    // 進行到這裏時,說明兩個哈希表都沒找到
    return NULL;
}

優點

節約CPU性能,發現必須刪除的時候才刪除。

缺點

內存壓力很大,出現長期佔用內存的數據。

總結

用存儲空間換取處理器性能

定期刪除

周期性輪詢redis庫中時效性數據,採用隨機抽取的策略,利用過期數據佔比的方式刪除頻度。

優點

CPU性能佔用設置有峰值,檢測頻度可自定義設置

內存壓力不是很大,長期佔用內存的冷數據會被持續清理

缺點

需要周期性抽查存儲空間

定期刪除詳解

redis的定期刪除是通過定時任務實現的,也就是定時任務會循環調用serverCron方法。然後定時檢查過期數據的方法是databasesCron。定期刪除的一大特點就是考慮了定時刪除過期數據會佔用cpu時間,所以每次執行databasesCron的時候會限制cpu的佔用不超過25%。真正執行刪除的是 activeExpireCycle方法。

時間事件

對於持續運行的服務器來說, 服務器需要定期對自身的資源和狀態進行必要的檢查和整理, 從而讓服務器維持在一個健康穩定的狀態, 這類操作被統稱為常規操作(cron job

在 Redis 中, 常規操作由 redis.c/serverCron() 實現, 它主要執行以下操作

1 更新服務器的各類統計信息,比如時間、內存佔用、數據庫佔用情況等。

2 清理數據庫中的過期鍵值對。

3 對不合理的數據庫進行大小調整。

4 關閉和清理連接失效的客戶端。

5 嘗試進行 AOF 或 RDB 持久化操作。

6 如果服務器是主節點的話,對附屬節點進行定期同步。

7 如果處於集群模式的話,對集群進行定期同步和連接測試。

因為 serverCron() 需要在 Redis 服務器運行期間一直定期運行, 所以它是一個循環時間事件: serverCron() 會一直定期執行,直到服務器關閉為止。

在 Redis 2.6 版本中, 程序規定 serverCron() 每秒運行 10 次, 平均每 100 毫秒運行一次。 從 Redis 2.8 開始, 用戶可以通過修改 hz選項來調整 serverCron() 的每秒執行次數, 具體信息請參考 redis.conf 文件中關於 hz 選項的說明

查看hz

way1 : config get hz  # "hz" "10"
way2 : info server  # server.hz 10

serverCron()

serverCron()會定期的執行,在serverCron()執行中會調用databasesCron() 方法(serverCron()還做了其他很多事情,但是現在不討論,只談刪除策略)

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    // 略去多無關代碼

    /* We need to do a few operations on clients asynchronously. */
    // 檢查客戶端,關閉超時客戶端,並釋放客戶端多餘的緩衝區
    clientsCron();

    /* Handle background operations on Redis databases. */
    // 對數據庫執行各種操作
    databasesCron();   /* !我們關注的方法! */

databasesCron()

databasesCron() 中 調用了 activeExpireCycle()方法,來對過期的數據進行處理。(在這裏還會做一些其他操作~ 調整數據庫大小,主動和漸進式rehash)

// 對數據庫執行刪除過期鍵,調整大小,以及主動和漸進式 rehash
void databasesCron(void) {

    // 判斷是否是主服務器 如果是 執行主動過期鍵清除
    if (server.active_expire_enabled && server.masterhost == NULL)
        // 清除模式為 CYCLE_SLOW ,這個模式會盡量多清除過期鍵
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

    // 在沒有 BGSAVE 或者 BGREWRITEAOF 執行時,對哈希表進行 rehash
    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
        static unsigned int resize_db = 0;
        static unsigned int rehash_db = 0;
        unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
        unsigned int j;

        /* Don't test more DBs than we have. */
        // 設定要測試的數據庫數量
        if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;

        /* Resize */
        // 調整字典的大小
        for (j = 0; j < dbs_per_call; j++) {
            tryResizeHashTables(resize_db % server.dbnum);
            resize_db++;
        }

        /* Rehash */
        // 對字典進行漸進式 rehash
        if (server.activerehashing) {
            for (j = 0; j < dbs_per_call; j++) {
                int work_done = incrementallyRehash(rehash_db % server.dbnum);
                rehash_db++;
                if (work_done) {
                    /* If the function did some work, stop here, we'll do
                     * more at the next cron loop. */
                    break;
                }
            }
        }
    }
}

activeExpireCycle()

大致流程如下

1 遍歷指定個數的db(默認的 16 )進行刪除操作

2 針對每個db隨機獲取過期數據每次遍歷不超過指定數量(如20),發現過期數據並進行刪除。

3 如果有多於25%的keys過期,重複步驟 2

除了主動淘汰的頻率外,Redis對每次淘汰任務執行的最大時長也有一個限定,這樣保證了每次主動淘汰不會過多阻塞應用請求,以下是這個限定計算公式:

#define ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 25 /* CPU max % for keys collection */ ``... ``timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;

也就是每次執行時間的25%用於過期數據刪除。

void activeExpireCycle(int type) {
    // 靜態變量,用來累積函數連續執行時的數據
    static unsigned int current_db = 0; /* Last DB tested. */
    static int timelimit_exit = 0;      /* Time limit hit in previous call? */
    static long long last_fast_cycle = 0; /* When last fast cycle ran. */

    unsigned int j, iteration = 0;
    // 默認每次處理的數據庫數量
    unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
    // 函數開始的時間
    long long start = ustime(), timelimit;

    // 快速模式
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        // 如果上次函數沒有觸發 timelimit_exit ,那麼不執行處理
        if (!timelimit_exit) return;
        // 如果距離上次執行未夠一定時間,那麼不執行處理
        if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
        // 運行到這裏,說明執行快速處理,記錄當前時間
        last_fast_cycle = start;
    }

    /* 
     * 一般情況下,函數只處理 REDIS_DBCRON_DBS_PER_CALL 個數據庫,
     * 除非:
     *
     * 1) 當前數據庫的數量小於 REDIS_DBCRON_DBS_PER_CALL
     * 2) 如果上次處理遇到了時間上限,那麼這次需要對所有數據庫進行掃描,
     *     這可以避免過多的過期鍵佔用空間
     */
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;

    // 函數處理的微秒時間上限
    // ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 默認為 25 ,也即是 25 % 的 CPU 時間
    timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;

    // 如果是運行在快速模式之下
    // 那麼最多只能運行 FAST_DURATION 微秒 
    // 默認值為 1000 (微秒)
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */

    // 遍曆數據庫
    for (j = 0; j < dbs_per_call; j++) {
        int expired;
        // 指向要處理的數據庫
        redisDb *db = server.db+(current_db % server.dbnum);

        // 為 DB 計數器加一,如果進入 do 循環之後因為超時而跳出
        // 那麼下次會直接從下個 DB 開始處理
        current_db++;

        do {
            unsigned long num, slots;
            long long now, ttl_sum;
            int ttl_samples;

            /* If there is nothing to expire try next DB ASAP. */
            // 獲取數據庫中帶過期時間的鍵的數量
            // 如果該數量為 0 ,直接跳過這個數據庫
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            // 獲取數據庫中鍵值對的數量
            slots = dictSlots(db->expires);
            // 當前時間
            now = mstime();

            // 這個數據庫的使用率低於 1% ,掃描起來太費力了(大部分都會 MISS)
            // 跳過,等待字典收縮程序運行
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;

            /* 
             * 樣本計數器
             */
            // 已處理過期鍵計數器
            expired = 0;
            // 鍵的總 TTL 計數器
            ttl_sum = 0;
            // 總共處理的鍵計數器
            ttl_samples = 0;

            // 每次最多只能檢查 LOOKUPS_PER_LOOP 個鍵
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

            // 開始遍曆數據庫
            while (num--) {
                dictEntry *de;
                long long ttl;

                // 從 expires 中隨機取出一個帶過期時間的鍵
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                // 計算 TTL
                ttl = dictGetSignedIntegerVal(de)-now;
                // 如果鍵已經過期,那麼刪除它,並將 expired 計數器增一
                if (activeExpireCycleTryExpire(db,de,now)) expired++;
                if (ttl < 0) ttl = 0;
                // 累積鍵的 TTL
                ttl_sum += ttl;
                // 累積處理鍵的個數
                ttl_samples++;
            }

            /* Update the average TTL stats for this database. */
            // 為這個數據庫更新平均 TTL 統計數據
            if (ttl_samples) {
                // 計算當前平均值
                long long avg_ttl = ttl_sum/ttl_samples;
                
                // 如果這是第一次設置數據庫平均 TTL ,那麼進行初始化
                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                /* Smooth the value averaging with the previous one. */
                // 取數據庫的上次平均 TTL 和今次平均 TTL 的平均值
                db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
            }

            // 我們不能用太長時間處理過期鍵,
            // 所以這個函數執行一定時間之後就要返回

            // 更新遍歷次數
            iteration++;

            // 每遍歷 16 次執行一次
            if ((iteration & 0xf) == 0 && /* check once every 16 iterations. */
                (ustime()-start) > timelimit)
            {
                // 如果遍歷次數正好是 16 的倍數
                // 並且遍歷的時間超過了 timelimit
                // 那麼斷開 timelimit_exit
                timelimit_exit = 1;
            }

            // 已經超時了,返回
            if (timelimit_exit) return;

            // 如果已刪除的過期鍵占當前總數據庫帶過期時間的鍵數量的 25 %
            // 那麼不再遍歷
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
}

hz調大將會提高Redis主動淘汰的頻率,如果你的Redis存儲中包含很多冷數據佔用內存過大的話,可以考慮將這個值調大,但Redis作者建議這個值不要超過100。我們實際線上將這個值調大到100,觀察到CPU會增加2%左右,但對冷數據的內存釋放速度確實有明顯的提高(通過觀察keyspace個數和used_memory大小)。

可以看出timelimit和server.hz是一個倒數的關係,也就是說hz配置越大,timelimit就越小。換句話說是每秒鐘期望的主動淘汰頻率越高,則每次淘汰最長佔用時間就越短。這裏每秒鐘的最長淘汰佔用時間是固定的250ms(1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/100),而淘汰頻率和每次淘汰的最長時間是通過hz參數控制的。

因此當redis中的過期key比率沒有超過25%之前,提高hz可以明顯提高掃描key的最小個數。假設hz為10,則一秒內最少掃描200個key(一秒調用10次*每次最少隨機取出20個key),如果hz改為100,則一秒內最少掃描2000個key;另一方面,如果過期key比率超過25%,則掃描key的個數無上限,但是cpu時間每秒鐘最多佔用250ms。

當REDIS運行在主從模式時,只有主結點才會執行上述這兩種過期刪除策略,然後把刪除操作”del key”同步到從結點。

if (server.active_expire_enabled && server.masterhost == NULL)  // 判斷是否是主節點 從節點不需要執行activeExpireCycle()函數。
        // 清除模式為 CYCLE_SLOW ,這個模式會盡量多清除過期鍵
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

隨機個數

redis.config.ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 決定每次循環從數據庫 expire中隨機挑選值的個數

逐出算法

如果不限制 reids 對內存使用的限制,它將會使用全部的內存。可以通過 config.memory 來指定redis 對內存的使用量 。

下面是redis 配置文件中的說明

 543 # Set a memory usage limit to the specified amount of bytes.
 544 # When the memory limit is reached Redis will try to remove keys
 545 # according to the eviction policy selected (see maxmemory-policy).
 546 #
 547 # If Redis can't remove keys according to the policy, or if the policy is
 548 # set to 'noeviction', Redis will start to reply with errors to commands
 549 # that would use more memory, like SET, LPUSH, and so on, and will continue
 550 # to reply to read-only commands like GET.
 551 #
 552 # This option is usually useful when using Redis as an LRU or LFU cache, or to
 553 # set a hard memory limit for an instance (using the 'noeviction' policy).
 554 #
 555 # WARNING: If you have replicas attached to an instance with maxmemory on,
 556 # the size of the output buffers needed to feed the replicas are subtracted
 557 # from the used memory count, so that network problems / resyncs will
 558 # not trigger a loop where keys are evicted, and in turn the output
 559 # buffer of replicas is full with DELs of keys evicted triggering the deletion
 560 # of more keys, and so forth until the database is completely emptied.
 561 #
 562 # In short... if you have replicas attached it is suggested that you set a lower
 563 # limit for maxmemory so that there is some free RAM on the system for replica
 564 # output buffers (but this is not needed if the policy is 'noeviction').
 
將內存使用限制設置為指定的字節。當已達到內存限制Redis將根據所選的逐出策略(請參閱maxmemory策略)嘗試刪除數據。

如果Redis無法根據逐出策略移除密鑰,或者策略設置為“noeviction”,Redis將開始對使用更多內存的命令(如set、LPUSH等)進行錯誤回復,並將繼續回復只讀命令,如GET。

當將Redis用作LRU或LFU緩存或設置實例的硬內存限制(使用“noeviction”策略)時,此選項通常很有用。

警告:如果將副本附加到啟用maxmemory的實例,則將從已用內存計數中減去饋送副本所需的輸出緩衝區的大小,這樣,網絡問題/重新同步將不會觸發收回密鑰的循環,而副本的輸出緩衝區將充滿收回的密鑰增量,從而觸發刪除更多鍵,依此類推,直到數據庫完全清空。

簡而言之。。。如果附加了副本,建議您設置maxmemory的下限,以便系統上有一些空閑RAM用於副本輸出緩衝區(但如果策略為“noeviction”,則不需要此限制)。

驅逐策略的配置

Maxmemery-policy volatile-lru

當前已用內存超過 maxmemory 限定時,觸發主動清理策略

易失數據清理

volatile-lru:只對設置了過期時間的key進行LRU(默認值)

volatile-random:隨機刪除即將過期key

volatile-ttl : 刪除即將過期的

volatile-lfu:挑選最近使用次數最少的數據淘汰

全部數據清理

allkeys-lru : 刪除lru算法的key

allkeys-lfu:挑選最近使用次數最少的數據淘汰

allkeys-random:隨機刪除

禁止驅逐

(Redis 4.0 默認策略)

noeviction : 永不過期,返回錯誤當mem_used內存已經超過maxmemory的設定,對於所有的讀寫請求都會觸發redis.c/freeMemoryIfNeeded(void)函數以清理超出的內存。注意這個清理過程是阻塞的,直到清理出足夠的內存空間。所以如果在達到maxmemory並且調用方還在不斷寫入的情況下,可能會反覆觸發主動清理策略,導致請求會有一定的延遲。

清理時會根據用戶配置的maxmemory-policy來做適當的清理(一般是LRU或TTL),這裏的LRU或TTL策略並不是針對redis的所有key,而是以配置文件中的maxmemory-samples個key作為樣本池進行抽樣清理。

maxmemory-samples在redis-3.0.0中的默認配置為5,如果增加,會提高LRU或TTL的精準度,redis作者測試的結果是當這個配置為10時已經非常接近全量LRU的精準度了,並且增加maxmemory-samples會導致在主動清理時消耗更多的CPU時間,建議:

1 盡量不要觸發maxmemory,最好在mem_used內存佔用達到maxmemory的一定比例后,需要考慮調大hz以加快淘汰,或者進行集群擴容。

2 如果能夠控制住內存,則可以不用修改maxmemory-samples配置;如果Redis本身就作為LRU cache服務(這種服務一般長時間處於maxmemory狀態,由Redis自動做LRU淘汰),可以適當調大maxmemory-samples。

這裏提一句,實際上redis根本就不會準確的將整個數據庫中最久未被使用的鍵刪除,而是每次從數據庫中隨機取5個鍵並刪除這5個鍵里最久未被使用的鍵。上面提到的所有的隨機的操作實際上都是這樣的,這個5可以用過redis的配置文件中的maxmemeory-samples參數配置。

數據逐出策略配置依據

使用INFO命令輸出監控信息,查詢緩存int和miss的次數,根據業務需求調優Redis配置。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※產品缺大量曝光嗎?你需要的是一流包裝設計!