// 處理客戶端的每個命令，都會調(diào)用這個函數(shù)
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，就釋放一些內(nèi)存，若不存在，給客戶端返回一個錯誤。
  if (server.maxmemory) {               // 若maxmemory不為0，則調(diào)用以下函數(shù)，釋放其中一些key
    int retval = freeMemoryIfNeeded();   // 根據(jù)配置策略刪除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. */
  // 檢查目前系統(tǒng)是否超過內(nèi)存的限制
  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個數(shù)據(jù)庫


    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策略，則直接在對應(yīng)庫結(jié)構(gòu)的dict中查找key。
      // 若是非ALLKEYS_xx策略，也就是可能是 volatile-xxx等策略，操作的庫結(jié)構(gòu)將設(shè)置成expires結(jié)構(gòu)。


      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
      {
        // 若設(shè)置了
        dict = server.db[j].dict;
      } else {
        dict = server.db[j].expires;
      }
      // 若數(shù)據(jù)庫的大小為0，說明沒有key存在，繼續(xù)在下一個數(shù)據(jù)庫中查找
      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(); // 計算目前使用的內(nèi)存大小，要排除slave和AOF使用的buffer大小
  if (slaves) { //遍歷slaves鏈表，減去slave使用的內(nèi)存數(shù)量
    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使用的內(nèi)存大小
    mem_used -= sdslen(server.aof_buf);
    mem_used -= aofRewriteBufferSize();
  }


  /* Check if we are over the memory limit. */ //檢查是否達(dá)到設(shè)置的內(nèi)存上限
  if (mem_used = server.maxmemory) return REDIS_OK;
  // 不釋放內(nèi)存
  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. */ //計算要釋放的內(nèi)存量
  mem_tofree = mem_used - server.maxmemory;
  mem_freed = 0;
  latencyStartMonitor(latency);
  while (mem_freed  mem_tofree) { //已經(jīng)釋放的內(nèi)存小于要釋放的內(nèi)存量
    int j, k, keys_freed = 0;


    for (j = 0; j  server.dbnum; j++) { //遍歷所有數(shù)據(jù)庫開始釋放內(nèi)存
      long bestval = 0; /* just to prevent warning */
      sds bestkey = NULL;
      struct dictEntry *de;
      redisDb *db = server.db+j;
      dict *dict;


       // 這一步要先選擇淘汰取值的數(shù)據(jù)庫的dict
      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
      { //若maxmemory-policy的值是LRU或RANDOM時，直接在主數(shù)據(jù)庫中進(jìn)行淘汰
        dict = server.db[j].dict;
      } else { // 其他策略，在已經(jīng)設(shè)置了終止時間的key中間進(jìn)行淘汰。
        dict = server.db[j].expires;
      }
      if (dictSize(dict) == 0) continue; //當(dāng)前數(shù)據(jù)庫沒有數(shù)據(jù)跳過


      /* 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)
      {
        // 根據(jù)配置文件中maxmemory_samples的值，決定做幾次選擇，刪除的key要從這些key中選出來。
        for (k = 0; k  server.maxmemory_samples; k++) {
          sds thiskey;
          long thisval;
          robj *o;


          // 從庫中隨機選取一個key-value結(jié)構(gòu)(dictEntry類型)的節(jié)點
          de = dictGetRandomKey(dict);
          thiskey = dictGetKey(de); // // 從該節(jié)點中獲取key的字符串地址
          /* When policy is volatile-lru we need an additional lookup
           * to locate the real key, as dict is set to db->expires. */
          // 若最大內(nèi)存刪除策略是volatile-lru，則需要從db中查找thiskey。
          // 若是VOLATILE-xx策略，則目前操作的庫的存儲結(jié)構(gòu)是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值，該值是系統(tǒng)的時間戳。
          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;
          }
        }
      }


      ... ...
      // 到這里，要刪除的最優(yōu)key已經(jīng)選出來了?，F(xiàn)在進(jìn)入刪除階段。
      // 不論哪種策略，只要選出了最優(yōu)key，就會執(zhí)行以下刪除流程。


      /* 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對應(yīng)的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;
}