主頁 > 知識(shí)庫 > 詳解Redis 緩存刪除機(jī)制(源碼解析)

詳解Redis 緩存刪除機(jī)制(源碼解析)

刪除的范圍

過期的 key
在內(nèi)存滿了的情況下，如果繼續(xù)執(zhí)行 set 等命令，且所有 key 都沒有過期，那么會(huì)按照緩存淘汰策略選中的 key

過期刪除

redis 中設(shè)置了過期時(shí)間的 key 會(huì)單獨(dú)存儲(chǔ)一份

typedef struct redisDb {
 dict *dict;   // 所有的鍵值對(duì)
 dict *expires;  //設(shè)置了過期時(shí)間的鍵值對(duì)
 // ...
} redisDb;

設(shè)置有效期

Redis 中有 4 個(gè)命令可以給 key 設(shè)置過期時(shí)間，分別是 expire pexpire expireat pexpireat

設(shè)置相對(duì)時(shí)間

expire key> ttl>：將 key 值的過期時(shí)間設(shè)置為 ttl 秒。

// src/expire.c

/* EXPIRE key seconds */
void expireCommand(client *c) {
 expireGenericCommand(c,mstime(),UNIT_SECONDS);
}

pexpire key> ttl>：將 key 值的過期時(shí)間設(shè)置為 ttl 毫秒。

// src/expire.c

/* PEXPIRE key milliseconds */
void pexpireCommand(client *c) {
 expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);
}

設(shè)置絕對(duì)時(shí)間

expireat key> timestamp>：將 key 值的過期時(shí)間設(shè)置為指定的 timestamp 秒數(shù)。

// src/expire.c

/* EXPIREAT key time */
void expireatCommand(client *c) {
 expireGenericCommand(c,0,UNIT_SECONDS);
}

pexpireat key> timestamp>：將 key 值的過期時(shí)間設(shè)置為指定的 timestamp 毫秒數(shù)。

// src/expire.c

/* PEXPIREAT key ms_time */
void pexpireatCommand(client *c) {
 expireGenericCommand(c,0,UNIT_MILLISECONDS);
}

以上 4 種方法最終都會(huì)調(diào)用下面的通用函數(shù) expireGenericCommand ：

// src/expire.c

void expireGenericCommand(client *c, long long basetime, int unit) {
 robj *key = c->argv[1], *param = c->argv[2];
 
 // 獲取數(shù)據(jù)對(duì)象
 long long when;
 if (getLongLongFromObjectOrReply(c, param, when, NULL) != C_OK)
  return;

 // 將時(shí)間轉(zhuǎn)化成以 ms 為單位
 if (unit == UNIT_SECONDS) when *= 1000;
 when += basetime;
 // 在 master 節(jié)點(diǎn)上，如果設(shè)置的過期時(shí)間小于當(dāng)前時(shí)間，那么將命令轉(zhuǎn)化成 DEL 指令
 if (when = mstime()  !server.loading  !server.masterhost) {
  robj *aux;

  int deleted = server.lazyfree_lazy_expire ? dbAsyncDelete(c->db,key) :
             dbSyncDelete(c->db,key);
  // ...
  // 將刪除命令同步給 slave 和 AOF
  // ...
 } else {
  // 設(shè)置過期時(shí)間
  setExpire(c,c->db,key,when);
  // ...
  // 構(gòu)造返回值和發(fā)布對(duì)象更新消息
  // ...
  return;
 }
}

設(shè)置過期時(shí)間的操作由 setExpire 執(zhí)行，他將 dictEntry 的 union v 中的 s64 設(shè)為過期時(shí)間

// src/db.c

void setExpire(client *c, redisDb *db, robj *key, long long when) {
 dictEntry *kde, *de;

 // 找出 db->dict 中對(duì)應(yīng)的存儲(chǔ)對(duì)象，這里的查詢和用 get 查詢數(shù)據(jù)是邏輯一樣，通過 hashFunc(key)  sizemask 
 // 找到 bucket 后在鏈表中遍歷
 kde = dictFind(db->dict,key->ptr);
 // 找出 db->expires 中對(duì)應(yīng)的存儲(chǔ)對(duì)象，如果沒有則新建一個(gè)
 de = dictAddOrFind(db->expires,dictGetKey(kde));
 // 
 dictSetSignedIntegerVal(de,when);
 // ...
}

#define dictSetSignedIntegerVal(entry, _val_) \

 do { (entry)->v.s64 = _val_; } while(0)

db->expires 中存儲(chǔ)的 dictEntry 表示的是過期 key 和過期時(shí)間，存儲(chǔ)過期時(shí)間的 v 是一個(gè) union ，可見在 redis 中不同使用場景或不同編碼下 v 的意義不同

typedef struct dictEntry {
 void *key;
 union {
  void *val;
  uint64_t u64;
  int64_t s64;
  double d;
 } v;
 struct dictEntry *next;
} dictEntry;

查詢過期時(shí)間

ttl key 返回 key 剩余過期秒數(shù)。

// src/expire.c

/* TTL key */
void ttlCommand(client *c) {
 ttlGenericCommand(c, 0);
}

pttl key 返回 key 剩余過期的毫秒數(shù)。

// src/expire.c

/* PTTL key */
void pttlCommand(client *c) {
 ttlGenericCommand(c, 1);
}

以上 2 種查看方式最終都會(huì)調(diào)用下面的通用函數(shù) ttlGenericCommand ：

// src/expire.c

/* Implements TTL and PTTL */
void ttlGenericCommand(client *c, int output_ms) {
 // ...
 // key 不存在時(shí)報(bào)錯(cuò)
 // ...
 
 // 獲取過期時(shí)間，如果沒有過期時(shí)間則
 expire = getExpire(c->db,c->argv[1]);
 if (expire != -1) {
  ttl = expire-mstime();
  if (ttl  0) ttl = 0;
 }
 
 if (ttl == -1) {
  addReplyLongLong(c,-1);
 } else {
  // 根據(jù)指定的單位返回結(jié)果，以秒為單位時(shí)向上取整
  addReplyLongLong(c,output_ms ? ttl : ((ttl+500)/1000));
 }
}

獲取過期時(shí)間的操作由 getExpire 執(zhí)行，在 db->expires 中查詢到對(duì)象后，獲取 union v 中的成員 s64

// src/expire.c

// 返回過期時(shí)間的絕對(duì)時(shí)間
long long getExpire(redisDb *db, robj *key) {
 dictEntry *de;

 // 查詢對(duì)象
 if (dictSize(db->expires) == 0 ||
  // 如果返回為 NULL 表示沒有設(shè)置過期時(shí)間，向上返回 -1
  (de = dictFind(db->expires,key->ptr)) == NULL) return -1;
 
 // 獲取 v.s64
 return dictGetSignedIntegerVal(de);
}

#define dictGetSignedIntegerVal(he) ((he)->v.s64)

過期策略

Redis 綜合使用惰性刪除和定期掃描實(shí)現(xiàn)

惰性刪除

每次訪問時(shí)會(huì)調(diào)用 expireIfNeeded 判斷 key 是否過期，如果過期就刪除該鍵，否則返回鍵對(duì)應(yīng)的值。單獨(dú)使用這種策略可能會(huì)浪費(fèi)很多內(nèi)存。

// src/db.c

int expireIfNeeded(redisDb *db, robj *key) {
 mstime_t when = getExpire(db,key);
 mstime_t now;
 
 // 沒有設(shè)置過期時(shí)間，直接返回
 if (when  0) return 0;

 // 從硬盤中加載數(shù)據(jù)時(shí)不執(zhí)行過期操作
 if (server.loading) return 0;

 // 參考 GitHub Issue #1525
 // 對(duì)于 master，在執(zhí)行 Lua Script 的過程中，可能會(huì)用某個(gè) key 是否存在當(dāng)作判斷條件
 // 為了避免一個(gè)腳本中前后條件不一致，將當(dāng)前時(shí)間強(qiáng)制設(shè)為腳本開始時(shí)間 
 now = server.lua_caller ? server.lua_time_start : mstime();

 // 對(duì)于 slave，返回此時(shí) key 是否已過期，但不執(zhí)行后續(xù)刪除操作
 if (server.masterhost != NULL) return now > when;

 // key 未過期
 if (now = when) return 0;

 // 統(tǒng)計(jì)過期 key 的個(gè)數(shù)
 server.stat_expiredkeys++;
 // 向所有的 slave 和 AOF 文件寫入一條 DEL 指令
 propagateExpire(db,key,server.lazyfree_lazy_expire);
 // 向 keyspace channel 中發(fā)布一條 key 過期的消息
 notifyKeyspaceEvent(NOTIFY_EXPIRED,
  "expired",key,db->id);
 // 根據(jù)配置決定是同步刪除還是異步刪除（僅刪除引用，由后臺(tái)線程執(zhí)行物理刪除）
 return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
           dbSyncDelete(db,key);
}

特殊處理

在 master 節(jié)點(diǎn)執(zhí)行 Lua 腳本時(shí)

參考 GitHub Issue #1525，對(duì)于 master，在執(zhí)行 Lua Script 的過程中，可能會(huì)用某個(gè) key 是否存在當(dāng)作判斷條件。為了避免一個(gè)腳本中前后條件不一致，將當(dāng)前時(shí)間強(qiáng)制設(shè)為腳本開始時(shí)間。
例如多次執(zhí)行如下 Lua 腳本 /tmp/myscript.lua 出現(xiàn)的結(jié)果可能不一致

-- /tmp/myscript.lua

if redis.call("exists",KEYS[1]) == 1
then
 redis.call("incr","mycounter")
end

if redis.call("exists",KEYS[1]) == 1
then
 return redis.call("incr","mycounter")
end

具體復(fù)現(xiàn)操作可以參考下面的 bash 腳本：

while [ 1 ]
do
 redis-cli set x foo px 100 > /dev/null
 sleep 0.092
 redis-cli --eval /tmp/myscript.lua x > /dev/null
 sleep 0.1
 redis-cli get mycounter
 redis-cli -p 6380 get mycounter
done

對(duì)于 slave 節(jié)點(diǎn)

在 slave 節(jié)點(diǎn)上，key 的刪除操作由 master 發(fā)來的 DEL 執(zhí)行，因此這里只返回是否過期的結(jié)果給客戶端，而不執(zhí)行刪除操作

正在從 RDB 和 AOF 讀取數(shù)據(jù)時(shí)跳過這個(gè)步驟

定期掃描

系統(tǒng)每隔一段時(shí)間就定期掃描一次，發(fā)現(xiàn)過期的鍵就進(jìn)行刪除。單獨(dú)使用這種策略可能出現(xiàn)鍵已經(jīng)過期但沒有刪除的情況
Redis 默認(rèn)每 100ms 執(zhí)行一次（通過 hz 參數(shù)配置，執(zhí)行周期為 1s/hz）過期掃描。由于 redisDb 中設(shè)置了過期時(shí)間的 key 會(huì)單獨(dú)存儲(chǔ)，所以不會(huì)出現(xiàn)掃描所有 key 的情況
具體步驟由 activeExpireCycle 函數(shù)執(zhí)行

activeExpireCycle、incrementallyRehash 等后臺(tái)操作都是由 databasesCron 觸發(fā)的

void activeExpireCycle(int type) {
 // ...
 
 // 依次遍歷各個(gè) db
 for (j = 0; j  dbs_per_call  timelimit_exit == 0; j++) {
  int expired;
  redisDb *db = server.db+(current_db % server.dbnum);

  // 記錄下一個(gè)執(zhí)行的 db，這樣如果因?yàn)槌瑫r(shí)意外退出，下次可以繼續(xù)從這個(gè) db 開始，
  // 從而在所有 db 上均勻執(zhí)行清除操作
  current_db++;

  do {
   // ...
   // 跳過沒有設(shè)置過期時(shí)間的 key 等不需要執(zhí)行的情況
   // ...

   // 抽樣個(gè)數(shù)，默認(rèn)為 20
   if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
    num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

   // 從設(shè)置了過期時(shí)間的 key 中隨機(jī)抽取 20 個(gè)
   while (num--) {
    dictEntry *de;
    long long ttl;

    // 隨機(jī)挑選 dict 中的一個(gè) key
    if ((de = dictGetRandomKey(db->expires)) == NULL) break;
    ttl = dictGetSignedIntegerVal(de)-now;
    // 執(zhí)行刪除，具體刪除操作和惰性刪除中類似
    if (activeExpireCycleTryExpire(db,de,now)) expired++;
    // ...
   }
   // ...
   // 更新統(tǒng)計(jì)數(shù)據(jù)等操作
   // ...
  // 如果每次刪除的 key 超過了樣本數(shù)的 25%，說明過期鍵占的比例較高，需要再重復(fù)執(zhí)行依次
  } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
 }
 // ...
}

隨機(jī)抽樣由 dictGetRandomKey 執(zhí)行

// src/dict.c

/* Return a random entry from the hash table. Useful to
 * implement randomized algorithms */
dictEntry *dictGetRandomKey(dict *d)
{
 dictEntry *he, *orighe;
 unsigned long h;
 int listlen, listele;

 // 沒有數(shù)據(jù)，返回為 NULL，外層函數(shù)接收到 NULL 后會(huì)中斷過期操作的執(zhí)行
 if (dictSize(d) == 0) return NULL;
 // 根據(jù) rehashidx 參數(shù)判斷是否正在執(zhí)行 rehash，如果正在執(zhí)行，
 // 則先執(zhí)行 rehash 中的一個(gè)步驟
 if (dictIsRehashing(d)) _dictRehashStep(d);
 
 if (dictIsRehashing(d)) {
  do {
   // 正在執(zhí)行 rehash，所以兩個(gè) ht 中的對(duì)象都要考慮
   //
   // 由于正在執(zhí)行 rehash，所以可以肯定 ht[0] 中下標(biāo)小于等于 rehashidx 的 bucket
   // 肯定沒有數(shù)據(jù)，所以只從 ht[0] 中大于 rehashidx 的 bucket 和 ht[1] 中抽取
   h = d->rehashidx + (random() % (d->ht[0].size +
           d->ht[1].size -
           d->rehashidx));
   he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
          d->ht[0].table[h];
  // 取到空 bucket 時(shí)重試
  } while(he == NULL);
 } else {
  do {
   // 參考寫入 ht 時(shí)計(jì)算下標(biāo)的規(guī)則 hashFunc(key)  sizemake
   // 這里 random()  sizemask 是隨機(jī)取一個(gè)下標(biāo)
   h = random()  d->ht[0].sizemask;
   he = d->ht[0].table[h];
  // 取到空 bucket 時(shí)重試
  } while(he == NULL);
 }
 
 // 到這一步 he 是 ht[n] 中某個(gè) bucket 中完整的鏈表
 // 所以還要從這個(gè)鏈表中隨機(jī)取一個(gè)對(duì)象
 
 // 遍歷計(jì)算整個(gè)鏈表的長度
 listlen = 0;
 orighe = he;
 while(he) {
  he = he->next;
  listlen++;
 }
 // 隨機(jī)取鏈表中某個(gè)對(duì)象的下標(biāo)
 listele = random() % listlen;
 he = orighe;
 // 重新遍歷鏈表獲取指定下標(biāo)的對(duì)象
 while(listele--) he = he->next;
 return he;
}

緩存淘汰

配置最大內(nèi)存限制

在 redis.conf 中配置

redis server 啟動(dòng)時(shí)加載配置文件和命令行參數(shù)中的 maxmemory ，存入 Server 對(duì)象的 maxmemory 字段
main 中在 redis server 啟動(dòng)時(shí)執(zhí)行初始化等操作，其中會(huì)執(zhí)行加載配置文件的 loadServerConfig 函數(shù)

// src/server.c
int main(int argc, char **argv) {
 // ..
 // 加載配置
 loadServerConfig(configfile,options);
 // ..
 // 警告過小的配置
 if (server.maxmemory > 0  server.maxmemory  1024*1024) {
  serverLog(LL_WARNING,"WARNING: You specified a maxmemory value that is less than 1MB (current value is %llu bytes). Are you sure this is what you really want?", server.maxmemory);
 }
}

loadServerConfig 中將配置文件、stdin、命令行參數(shù)加載到 config 字符串中，然后調(diào)用 loadServerConfigFromString

// src/config.c
void loadServerConfig(char *filename, char *options) {
 sds config = sdsempty();
 char buf[CONFIG_MAX_LINE+1];
 
 // 加載配置文件
 if (filename) {
  FILE *fp;

  // 啟動(dòng)命令為 ./redis-server - 則從 stdin 中讀取，需要用 C-D> 觸發(fā) EOF
  if (filename[0] == '-'  filename[1] == '\0') {
   fp = stdin;
  } else {
  // 第一個(gè)參數(shù)不是 -，則嘗試打開這個(gè)參數(shù)指定的文件
   if ((fp = fopen(filename,"r")) == NULL) {
    serverLog(LL_WARNING,
     "Fatal error, can't open config file '%s'", filename);
    exit(1);
   }
  }
  // 將配置文件中的每一行追加到 config 中
  while(fgets(buf,CONFIG_MAX_LINE+1,fp) != NULL)
   config = sdscat(config,buf);
  if (fp != stdin) fclose(fp);
 }
 // 添加其他選項(xiàng)，例如 ./redis-server --port 8080 后面的參數(shù)，直接加到 config 中
 if (options) {
  config = sdscat(config,"\n");
  config = sdscat(config,options);
 }
 loadServerConfigFromString(config);
 sdsfree(config);
}

loadServerConfigFromString 從上一步中的 config 字符串中逐行讀取配置，并寫入 server 對(duì)象

// src/config.c
void loadServerConfigFromString(char *config) {
 // ...
 
 // 按行讀取配置文件
 lines = sdssplitlen(config,strlen(config),"\n",1,totlines);
 for (i = 0; i  totlines; i++) {
 // 跳過無效的配置和注釋
  // ...
  argv = sdssplitargs(lines[i],argc);
  
  // 將配置命令轉(zhuǎn)化成小寫
  sdstolower(argv[0]);

  // 根據(jù)配置命令初始化配置，strcasecmp 比較
  if (!strcasecmp(argv[0],"timeout")  argc == 2) {
   server.maxidletime = atoi(argv[1]);
   if (server.maxidletime  0) {
    err = "Invalid timeout value"; goto loaderr;
   }
  // ...
  } else if (!strcasecmp(argv[0],"maxmemory")  argc == 2) {
   // memtoll 將字符串形式的配置轉(zhuǎn)化成對(duì)應(yīng)的 long long 值
   // 例如 1kb -> 1024
   server.maxmemory = memtoll(argv[1],NULL);
  }
 }
}

使用 CONFIG SET 命令配置

Redis Server 接收到客戶端的 CONFIG SET 命令后調(diào)用 configSetCommand 函數(shù)
服務(wù)端接收到命令時(shí)將命令和參數(shù)存入 Redis Server 的 argc 和 argv

argc: 4
argv: 0  1 2   3
  config set maxmemory 10mb

動(dòng)態(tài)配置 maxmemory 后會(huì)立即嘗試觸發(fā)內(nèi)存回收，而修改其他內(nèi)存相關(guān)配置(例如: maxmemory_policy)時(shí)不會(huì)觸發(fā)

if (0) {
 // ...
} config_set_memory_field("maxmemory",server.maxmemory) {
 // 配置不為 0，表示之前限制過內(nèi)存
 if (server.maxmemory) {
  if (server.maxmemory  zmalloc_used_memory()) {
   serverLog(LL_WARNING,"WARNING: the new maxmemory value set via CONFIG SET is smaller than the current memory usage. This will result in keys eviction and/or inability to accept new write commands depending on the maxmemory-policy.");
  }
  freeMemoryIfNeeded();
 }
 // ...
}

32 位機(jī)器的內(nèi)存限制

對(duì)于 64 位機(jī)器，將 maxmemory 設(shè)置為 0 表示不限制內(nèi)存，但由于 32 位尋址空間最多只有 4 GB，所以默認(rèn)內(nèi)存限制設(shè)為 3 GB，緩存淘汰策略設(shè)為 noeviction

// src/server.c
// ...
if (server.arch_bits == 32  server.maxmemory == 0) {
 serverLog(LL_WARNING,"Warning: 32 bit instance detected but no memory limit set. Setting 3 GB maxmemory limit with 'noeviction' policy now.");
 server.maxmemory = 3072LL*(1024*1024); /* 3 GB */
 server.maxmemory_policy = MAXMEMORY_NO_EVICTION;
 }

淘汰策略

淘汰策略使用 CONFIG SET maxmemory-policy 配置

默認(rèn)：

**noeviction: **內(nèi)存滿了后對(duì)于 set 等命令直接返回錯(cuò)誤

針對(duì)所有 key：

allkeys-lru: 在所有 key 的范圍內(nèi)使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
**allkeys-lfu: **在所有 key 的范圍內(nèi)使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
**allkeys-random: **在所有 key 的范圍內(nèi)隨機(jī)執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)

針對(duì)設(shè)置了過期時(shí)間的 key：

**volatile-lru: **在設(shè)置了過期時(shí)間的 key 中使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
**volatile-lfu: **在設(shè)置了過期時(shí)間的 key 中使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
**volatile-random: **在設(shè)置了過期時(shí)間的 key 中隨機(jī)執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
**volatile-ttl: **刪除即將過期的 key，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)

Redis 在執(zhí)行淘汰之前會(huì)計(jì)算部分對(duì)象的 idle 值，使用不同淘汰策略時(shí)計(jì)算 idle 值的方法也不同， idle 值越大表示這個(gè)值越需要優(yōu)先刪除。

下面主要介紹 LRU 和 LFU 中 idle 值的計(jì)算方法

LRU 淘汰策略

抽樣刪除，樣本數(shù)量通過 CONFIG SET maxmemory-samples 100 控制，對(duì)應(yīng) RedisObject 中的 maxmemory_samples 參數(shù)，抽樣數(shù)量越多和傳統(tǒng)的 LRU 算法越接近

優(yōu)化策略

為了避免傳統(tǒng)的 LRU 算法通常使用 hashmap + 鏈表實(shí)現(xiàn)帶來的開銷，Redis 進(jìn)行了如下優(yōu)化：

RedisObject 結(jié)構(gòu)中設(shè)置了一個(gè) lru 字段，用來記錄數(shù)據(jù)的訪問時(shí)間戳，而不是每次調(diào)整對(duì)象在鏈表中的位置

typedef struct redisObject {
 // 對(duì)象類型
 unsigned type:4;
 // 對(duì)象編碼
 unsigned encoding:4;
 // LRU 算法和 LFU 算法公用 lru 這個(gè)字段
 // 
 // LRU_BITS 默認(rèn)為 24，因此最大只能存儲(chǔ) 194 天的時(shí)間戳,
 // 創(chuàng)建對(duì)象時(shí)會(huì)寫入這個(gè)字段，訪問對(duì)象時(shí)會(huì)更新這個(gè)字段，
 // 超過之后再從 0 開始計(jì)算
 unsigned lru:LRU_BITS;
 int refcount;
 void *ptr;
} robj;

使用抽樣數(shù)組代替鏈表，后續(xù)在候選集合中根據(jù) lru 字段值的大小進(jìn)行篩選，避免了鏈表帶來的開銷。候選集合中的對(duì)象用 evictionPoolEntry 表示

struct evictionPoolEntry {
 unsigned long long idle; // 用于淘汰排序，在不同算法中意義不同
 sds key; // 鍵的名字
 // ...
};

計(jì)算方法

全局對(duì)象 lru_clock 記錄了當(dāng)前的 unix 時(shí)間戳，由 serverCron 調(diào)用 updateCachedTime 默認(rèn)每 100 ms 更新一次。更新頻率與 hz 參數(shù)有關(guān)， 1s/hz 即為更新間隔時(shí)間。
LRU_CLOCK_RESOLUTION 的值為 1000，因此使用 LRU_CLOCK 函數(shù)獲取 lru_clock 時(shí)，如果每秒更新頻率在 1 次以上，會(huì)使用全局變量中緩存的 lrulcock

unsigned int LRU_CLOCK(void) {
 unsigned int lruclock;
 if (1000/server.hz = LRU_CLOCK_RESOLUTION) {
  atomicGet(server.lruclock,lruclock);
 } else {
  lruclock = getLRUClock();
 }
 return lruclock;
}

如果更新頻率不到每秒 1 次，則會(huì)用函數(shù) getLRUClock 實(shí)時(shí)計(jì)算 lruclock

unsigned int getLRUClock(void) {
 // mstime() 獲取 unix 時(shí)間戳，單位時(shí)毫秒
 // 除以 LRU_CLOCK_RESOLUTION(值為 1000)，將時(shí)間戳轉(zhuǎn)化為秒
 return (mstime()/LRU_CLOCK_RESOLUTION)  LRU_CLOCK_MAX;
}

其中 LRU_CLOCK_MAX 表示 lru_clock 最大的可能值，這個(gè)值與 redisObject 中 lru 最大的可能值一樣，定義如下：

#define LRU_CLOCK_MAX ((1LRU_BITS)-1)

所以最終比較時(shí) lru_clock 和 robj.lru 的值都在 [0, LRU_CLOCK_MAX] 的范圍內(nèi)。
從邏輯上講，當(dāng)前時(shí)間戳應(yīng)該永遠(yuǎn)大于上次訪問的時(shí)間戳 ,因此正常的計(jì)算規(guī)則應(yīng)該是 lru_clock-robj.lru 。
但是由于 lru_clock 和 robj.lru 是當(dāng)前時(shí)間戳取模后的值，所以可能出現(xiàn) lru_clock 小于 robj.lru 的情況，所以這種情況下計(jì)算規(guī)則應(yīng)該改為 lru_clock+194天-robj.lru
但是對(duì)于 lru_clock 和 robj.lru 間隔超過 194 天的情況仍然無法判斷，所以更能存在刪除不準(zhǔn)確的情況。
將上述的邏輯組合起來就是 LRU 算法下獲取 idle 值的函數(shù):

// src/evict.c

// 以秒為精度計(jì)算對(duì)象距離上一次訪問的間隔時(shí)間，然后轉(zhuǎn)化成毫秒返回
unsigned long long estimateObjectIdleTime(robj *o) {
 unsigned long long lruclock = LRU_CLOCK();
 if (lruclock >= o->lru) {
  return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
 } else {
  return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
     LRU_CLOCK_RESOLUTION;
 }
}

在 Redis 3.0 中，當(dāng)取樣數(shù)量設(shè)為 10 時(shí)，已經(jīng)和傳統(tǒng)的 LRU 算法效果很接近了

LFU 淘汰策略

LFU 算法復(fù)用 robj.lru 字段，將這個(gè) 24 bit 的字段拆分成了兩部分：

ldt(last decrement time，單位：分鐘)：lru 字段的前 16bit，表示數(shù)據(jù)的訪問時(shí)間戳，最多只能存儲(chǔ) 45 天。
counter 值：lru 字段的后 8bit，表示數(shù)據(jù)的訪問頻率

遞增策略

counter 能表示的最大值是 255，因此 counter 與訪問次數(shù)不能是線性關(guān)系，這里采用的計(jì)算步驟如下：

隨機(jī)取 0 到 1 之間的隨機(jī)數(shù) r
比較 r 與 1/((counter-LFU_INIT_VAL)*lfu_log_factor+1) 的大小，其中 LFU_INIT_VAL 是常量，默認(rèn)為 5，lfu_log_factor 是可配置參數(shù)，默認(rèn)為 10
如果 r 小則 counter 增加 1，否則 counter 不變

實(shí)現(xiàn)代碼如下：

uint8_t LFULogIncr(uint8_t counter) {
 // counter 值已經(jīng)到達(dá)了 255，不能再增加，直接返回
 if (counter == 255) return 255;
 double r = (double)rand()/RAND_MAX;
 double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL 值為 5
 if (baseval  0) baseval = 0;
 double p = 1.0/(baseval*server.lfu_log_factor+1);
 if (r  p) counter++;
 return counter;
}

訪問次數(shù)與 counter 值之間大概是對(duì)數(shù)關(guān)系，counter 值越大，增速越低

// https://redis.io/topics/lru-cache

+--------+------------+------------+------------+------------+------------+
| 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  |
+--------+------------+------------+------------+------------+------------+

衰減策略

除了訪問對(duì)象時(shí) counter 需要增加，對(duì)于一段時(shí)間內(nèi)沒有訪問的對(duì)象還要相應(yīng)地減少 counter 值，遞減的速率由 lfu-decay-time 參數(shù)控制。
counter 衰減步驟如下：

取當(dāng)前時(shí)間戳（單位：分鐘）的低 16 位記為 now ，計(jì)算與 ldt 的差值。這里與 LRU 算法中計(jì)算 lru_clock 和 robj.lru 時(shí)可能出現(xiàn)一樣的問題，由于 ldt 最多只能表示 45 天，所以如果距離對(duì)象上次訪問超過 45 天，則無法準(zhǔn)確計(jì)算訪問的時(shí)間間隔

unsigned long LFUDecrAndReturn(robj *o) {
 // 取高 16 位
 unsigned long ldt = o->lru >> 8;
 // 取低 8 位
 unsigned long counter = o->lru  255;
 // 如果 lfu_decay_time 為 0，則步修改 counter，否則將 counter 減少 LFUTimeElapsed(ldt)/lfu_decay_time
 unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
 if (num_periods)
  // 保證 counter 的最小值位 0
  counter = (num_periods > counter) ? 0 : counter - num_periods;
 return counter;
}

// 計(jì)算距離上次訪問的間隔時(shí)間
unsigned long LFUTimeElapsed(unsigned long ldt) {
 // 取當(dāng)前時(shí)間戳（單位：分鐘）
 unsigned long now = LFUGetTimeInMinutes();
 // 計(jì)算時(shí)間差
 if (now >= ldt) return now-ldt;
 return 65535-ldt+now;
}

// 獲取當(dāng)前時(shí)間戳，以分鐘為單位，取低 8 位
unsigned long LFUGetTimeInMinutes(void) {
 return (server.unixtime/60)  65535;
}

如果 lfu_decay_time 為 0，則步修改 counter，否則將 counter 減少 LFUTimeElapsed(ldt)/lfu_decay_time

例如，在 lfu_decay_time 為 1 的情況下，如果有 N 分鐘沒有訪問這個(gè)對(duì)象，那么 counter 值減 N
每次訪問一個(gè)對(duì)象時(shí)都會(huì)調(diào)用 updateLFU 更新 counter 的值：

void updateLFU(robj *val) {
 unsigned long counter = LFUDecrAndReturn(val);
 counter = LFULogIncr(counter);
 val->lru = (LFUGetTimeInMinutes()8) | counter;
}

執(zhí)行淘汰

當(dāng) Redis 需要淘汰一批數(shù)據(jù)時(shí)，會(huì)調(diào)用 evictionPoolPopulate 獲取一批待刪除對(duì)象，根據(jù)設(shè)置的淘汰范圍的不同，會(huì)決定傳遞給 evictionPoolPopulate 的 sampledict 參數(shù)是存有全部數(shù)據(jù)的 db->dict 還是只有設(shè)置了過期時(shí)間的數(shù)據(jù)的 db->expires

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
 int j, k, count;
 dictEntry *samples[server.maxmemory_samples];

 // 隨機(jī)獲取 server.maxmemory_samples 個(gè)對(duì)象，寫入 samples 中
 count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
 // 遍歷每個(gè)對(duì)象
 for (j = 0; j  count; j++) {
  // ...
  // 初始化
  // ...

  de = samples[j];
  key = dictGetKey(de);

  // 如果獲取樣本的字典不是 db->dict（還可能是 db->expires），并且不是按 volatile-ttl 淘汰
  // 那么還要將對(duì)象轉(zhuǎn)化成數(shù)據(jù)字典中對(duì)應(yīng)的對(duì)象，然后取其值
  if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
   if (sampledict != keydict) de = dictFind(keydict, key);
   
   // #define dictGetVal(he) ((he)->v.val)
   // 這里還是利用 union 的特性，如果是 db->dict 中的元素，返回的是鍵的值
   // 如果是 db->expires 中的元素，返回的是過期時(shí)間
   o = dictGetVal(de);
  }

  // 按各算法計(jì)算 idle 分值，idle 越大的越應(yīng)該被先淘汰
  //
  // 如果使用 LRU 淘汰算法，則計(jì)算對(duì)象的空閑時(shí)間
  if (server.maxmemory_policy  MAXMEMORY_FLAG_LRU) {
   idle = estimateObjectIdleTime(o);
  // 使用 LFU 淘汰算法，
  } else if (server.maxmemory_policy  MAXMEMORY_FLAG_LFU) {
   idle = 255-LFUDecrAndReturn(o);
  // 使用 volatile-ttl 算法，用 ULLONG_MAX 減去過期時(shí)間作為分值
  } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
   idle = ULLONG_MAX - (long)dictGetVal(de);
  } else {
   serverPanic("Unknown eviction policy in evictionPoolPopulate()");
  }

  k = 0;
  // 與原 pool 中的 idle 值進(jìn)行比較，找出應(yīng)該比當(dāng)前對(duì)象先淘汰出去的對(duì)象
  while (k  EVPOOL_SIZE 
    pool[k].key 
    pool[k].idle  idle) k++;
  if (k == 0  pool[EVPOOL_SIZE-1].key != NULL) {
   // 沒有發(fā)現(xiàn)更需要被淘汰的對(duì)象，并且 pool 中也沒有多余的位置
   // 那么當(dāng)前對(duì)象仍然留在 samples 中
   continue;
  } else if (k  EVPOOL_SIZE  pool[k].key == NULL) {
   // 沒有發(fā)現(xiàn)更需要被淘汰的對(duì)象，但 pool 中有多余的位置
   // 于是將這個(gè)對(duì)象插入 pool 中
  } else {
   //     當(dāng)前對(duì)象
   //      |
   //      V
   // Pool: [ 0 1 2 3 ...k-1 k ... EVPOOL_SIZE-1]
   // 為了保證 pool 中的數(shù)據(jù)按 idle 從小到大排列，這里將當(dāng)前對(duì)象插入第 k 個(gè)對(duì)象后面的位置
   if (pool[EVPOOL_SIZE-1].key == NULL) {
    // pool 的右邊還有空余的位置，因此將從第 k 個(gè)開始后面的元素整體后移
    memmove(pool+k+1,pool+k,
     sizeof(pool[0])*(EVPOOL_SIZE-k-1));
   } else {
    // pool 的右邊沒有空余的位置了，那么將 pool 中前 k 個(gè)元素整體左移
    sds cached = pool[0].cached;
    memmove(pool,pool+1,sizeof(pool[0])*k);
   }
  }
  // ...
  // 將當(dāng)前對(duì)象的屬性賦值到下標(biāo)為 k 的元素
  // ...
 }
}

完成上述操作后，pool 中剩下的就是新篩選出來的最需要淘汰的對(duì)象了。

在 freeMemoryIfNeeded 中會(huì)調(diào)用 evictionPoolPopulate 來篩選需要淘汰的對(duì)象，每次刪除一個(gè)，直到釋放了足夠的內(nèi)存。如果始終無法達(dá)到內(nèi)存需求，則會(huì)報(bào)錯(cuò)。

到此這篇關(guān)于Redis 緩存刪除機(jī)制(源碼解析)的文章就介紹到這了,更多相關(guān)Redis 緩存刪除內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

Java手動(dòng)實(shí)現(xiàn)Redis的LRU緩存機(jī)制
淺談redis緩存在項(xiàng)目中的使用
詳解redis緩存與數(shù)據(jù)庫一致性問題解決
手動(dòng)實(shí)現(xiàn)Redis的LRU緩存機(jī)制示例詳解
淺談MySQL與redis緩存的同步方案
使用 Redis 緩存實(shí)現(xiàn)點(diǎn)贊和取消點(diǎn)贊的示例代碼
Redis 緩存實(shí)現(xiàn)存儲(chǔ)和讀取歷史搜索關(guān)鍵字的操作方法
SpringCache 分布式緩存的實(shí)現(xiàn)方法(規(guī)避redis解鎖的問題)
詳解緩存穿透擊穿雪崩解決方案

標(biāo)簽：仙桃銅川崇左湖南湘潭黃山蘭州衡水

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《詳解Redis 緩存刪除機(jī)制(源碼解析)》，本文關(guān)鍵詞；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。