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 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 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配置。