关于redis Key淘汰策略的实现方法

// 处理客户端的每个命令，都会调用这个函数
int processCommand(redisClient *c) {
  ... ...
  /* Handle the maxmemory directive.
   *
   * First we try to free some memory if possible (if there are volatile
   * keys in the dataset). If there are not the only thing we can do
   * is returning an error. */
  // 以上意思是：若存在可以删除的key，就释放一些内存，若不存在，给客户端返回一个错误。
  if (server.maxmemory) {               // 若maxmemory不为0，则调用以下函数，释放其中一些key
    int retval = freeMemoryIfNeeded();   // 根据配置策略删除key
    if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {  // 若出错，就终止处理命令，把错误返回给客户端
      flagTransaction(c);
      addReply(c, shared.oomerr);
      return REDIS_OK;
    }
  }
  ... ...
}

int freeMemoryIfNeeded(void) {
  size_t mem_used, mem_tofree, mem_freed;
  int slaves = listLength(server.slaves);
  mstime_t latency;


  /* Remove the size of slaves output buffers and AOF buffer from the
   * count of used memory. */
  mem_used = zmalloc_used_memory();
  if (slaves) {
    listIter li;
    listNode *ln;


    listRewind(server.slaves,&li);
    while((ln = listNext(&li))) {
      redisClient *slave = listNodeValue(ln);
      unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
      if (obuf_bytes > mem_used)
        mem_used = 0;
      else
        mem_used -= obuf_bytes;
    }
  }
  if (server.aof_state != REDIS_AOF_OFF) {
    mem_used -= sdslen(server.aof_buf);
    mem_used -= aofRewriteBufferSize();
  }


  /* Check if we are over the memory limit. */
  // 检查目前系统是否超过内存的限制
  if (mem_used <= server.maxmemory) return REDIS_OK;


  if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
    return REDIS_ERR; /* We need to free memory, but policy forbids. */


  /* Compute how much memory we need to free. */
  mem_tofree = mem_used - server.maxmemory;
  mem_freed = 0;
  latencyStartMonitor(latency);
  while (mem_freed < mem_tofree) {
    int j, k, keys_freed = 0;
    // 遍历16个数据库


    for (j = 0; j < server.dbnum; j++) {
      long bestval = 0; /* just to prevent warning */
      sds bestkey = NULL;
      struct dictEntry *de;
      redisDb *db = server.db+j;
      dict *dict;


      // 这里要注意，若是ALLKEYS_xx策略，则直接在对应库结构的dict中查找key。
      // 若是非ALLKEYS_xx策略，也就是可能是 volatile-xxx等策略，操作的库结构将设置成expires结构。


      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
      {
        // 若设置了
        dict = server.db[j].dict;
      } else {
        dict = server.db[j].expires;
      }
      // 若数据库的大小为0，说明没有key存在，继续在下一个数据库中查找
      if (dictSize(dict) == 0) continue;


... ... 


}

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
 
However since Redis 3.0 (that is currently in beta) the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.
What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:

maxmemory-samples 5

The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.

int freeMemoryIfNeeded(void) {
  size_t mem_used, mem_tofree, mem_freed;
  int slaves = listLength(server.slaves);
  mstime_t latency;


  /* Remove the size of slaves output buffers and AOF buffer from the
   * count of used memory. */
  mem_used = zmalloc_used_memory(); // 计算目前使用的内存大小，要排除slave和AOF使用的buffer大小
  if (slaves) { //遍历slaves链表，减去slave使用的内存数量
    listIter li;
    listNode *ln;


    listRewind(server.slaves,&li);
    while((ln = listNext(&li))) {
      redisClient *slave = listNodeValue(ln);
      unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
      if (obuf_bytes > mem_used)
        mem_used = 0;
      else
        mem_used -= obuf_bytes;
    }
  }
  if (server.aof_state != REDIS_AOF_OFF) { //减去AOF使用的内存大小
    mem_used -= sdslen(server.aof_buf);
    mem_used -= aofRewriteBufferSize();
  }


  /* Check if we are over the memory limit. */ //检查是否达到设置的内存上限
  if (mem_used <= server.maxmemory) return REDIS_OK;
  // 不释放内存
  if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
    return REDIS_ERR; /* We need to free memory, but policy forbids. */


  /* Compute how much memory we need to free. */ //计算要释放的内存量
  mem_tofree = mem_used - server.maxmemory;
  mem_freed = 0;
  latencyStartMonitor(latency);
  while (mem_freed < mem_tofree) { //已经释放的内存小于要释放的内存量
    int j, k, keys_freed = 0;


    for (j = 0; j < server.dbnum; j++) { //遍历所有数据库开始释放内存
      long bestval = 0; /* just to prevent warning */
      sds bestkey = NULL;
      struct dictEntry *de;
      redisDb *db = server.db+j;
      dict *dict;


       // 这一步要先选择淘汰取值的数据库的dict
      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
      { //若maxmemory-policy的值是LRU或RANDOM时，直接在主数据库中进行淘汰
        dict = server.db[j].dict;
      } else { // 其他策略，在已经设置了终止时间的key中间进行淘汰。
        dict = server.db[j].expires;
      }
      if (dictSize(dict) == 0) continue; //当前数据库没有数据跳过


      /* volatile-random and allkeys-random policy */ //若是RANDOM策略中的一个
      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
        server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
      {
        de = dictGetRandomKey(dict);
        bestkey = dictGetKey(de);
      }


      /* volatile-lru and allkeys-lru policy */// 若删除策略是LRU策略中的一个
      else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
      {
        // 根据配置文件中maxmemory_samples的值，决定做几次选择，删除的key要从这些key中选出来。
        for (k = 0; k < server.maxmemory_samples; k++) {
          sds thiskey;
          long thisval;
          robj *o;


          // 从库中随机选取一个key-value结构(dictEntry类型)的节点
          de = dictGetRandomKey(dict);
          thiskey = dictGetKey(de); // // 从该节点中获取key的字符串地址
          /* When policy is volatile-lru we need an additional lookup
           * to locate the real key, as dict is set to db->expires. */
          // 若最大内存删除策略是volatile-lru，则需要从db中查找thiskey。
          // 若是VOLATILE-xx策略，则目前操作的库的存储结构是expires，此时需要从dict中找到该key
          if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            de = dictFind(db->dict, thiskey);
          // 获取key de的value值
          o = dictGetVal(de);
          // 查看该key的剩下的生存时间
          thisval = estimateObjectIdleTime(o);


          /* Higher idle time is better candidate for deletion */
          // 每次都从遍历的几个Key中选出lru最长的key。
          // 那么如何更新key的lru值呢？每次查找该key的时候就会更新该key的lru值，该值是系统的时间戳。
          if (bestkey == NULL || thisval > bestval) {
            bestkey = thiskey;
            bestval = thisval;
          }
        }
      }


      /* volatile-ttl */
      else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
        for (k = 0; k < server.maxmemory_samples; k++) {
          sds thiskey;
          long thisval;


          de = dictGetRandomKey(dict);
          thiskey = dictGetKey(de);
          thisval = (long) dictGetVal(de);


          /* Expire sooner (minor expire unix timestamp) is better
           * candidate for deletion */
          if (bestkey == NULL || thisval < bestval) {
            bestkey = thiskey;
            bestval = thisval;
          }
        }
      }


      ... ...
      // 到这里，要删除的最优key已经选出来了。现在进入删除阶段。
      // 不论哪种策略，只要选出了最优key，就会执行以下删除流程。


      /* Finally remove the selected key. */
      if (bestkey) {
        long long delta;


        robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
        propagateExpire(db,keyobj);
        /* We compute the amount of memory freed by dbDelete() alone.
         * It is possible that actually the memory needed to propagate
         * the DEL in AOF and replication link is greater than the one
         * we are freeing removing the key, but we can't account for
         * that otherwise we would never exit the loop.
         *
         * AOF and Output buffer memory will be freed eventually so
         * we only care about memory used by the key space. */
        // 删除该bestkey对应的key-value值。注意这里既要从dict中删除，还要从expires中删除。
        delta = (long long) zmalloc_used_memory();
        dbDelete(db,keyobj);
        delta -= (long long) zmalloc_used_memory();
        mem_freed += delta;
        server.stat_evictedkeys++;
        notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
          keyobj, db->id);
        decrRefCount(keyobj);
        keys_freed++;


        /* When the memory to free starts to be big enough, we may
         * start spending so much time here that is impossible to
         * deliver data to the slaves fast enough, so we force the
         * transmission here inside the loop. */
        if (slaves) flushSlavesOutputBuffers();
      }
    }
    if (!keys_freed) {
      latencyEndMonitor(latency);
      latencyAddSampleIfNeeded("eviction-cycle",latency);
      return REDIS_ERR; /* nothing to free... */
    }
  }
  latencyEndMonitor(latency);
  latencyAddSampleIfNeeded("eviction-cycle",latency);
  return REDIS_OK;
}