Redis中LRU淘汰策略的深入分析

typedef struct redisObject {
 unsigned type:4;
 unsigned encoding:4;
 unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
       * LFU data (least significant 8 bits frequency
       * and most significant 16 bits access time). */
 int refcount;
 void *ptr;
} robj;

robj *lookupKey(redisDb *db, robj *key, int flags) {
 dictEntry *de = dictFind(db->dict,key->ptr);
 if (de) {
  robj *val = dictGetVal(de);

  /* Update the access time for the ageing algorithm.
   * Don't do it if we have a saving child, as this will trigger
   * a copy on write madness. */
  if (server.rdb_child_pid == -1 &&
   server.aof_child_pid == -1 &&
   !(flags & LOOKUP_NOTOUCH))
  {
   if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    updateLFU(val);
   } else {
    val->lru = LRU_CLOCK();
   }
  }
  return val;
 } else {
  return NULL;
 }
}

/* Return the LRU clock, based on the clock resolution. This is a time
 * in a reduced-bits format that can be used to set and check the
 * object->lru field of redisObject structures. */
unsigned int getLRUClock(void) {
 return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

/* This function is used to obtain the current LRU clock.
 * If the current resolution is lower than the frequency we refresh the
 * LRU clock (as it should be in production servers) we return the
 * precomputed value, otherwise we need to resort to a system call. */
unsigned int LRU_CLOCK(void) {
 unsigned int lruclock;
 if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
  atomicGet(server.lruclock,lruclock);
 } else {
  lruclock = getLRUClock();
 }
 return lruclock;
}

int processCommand(client *c) {

 /* Handle the maxmemory directive.
  *
  * Note that we do not want to reclaim memory if we are here re-entering
  * the event loop since there is a busy Lua script running in timeout
  * condition, to avoid mixing the propagation of scripts with the
  * propagation of DELs due to eviction. */
 if (server.maxmemory && !server.lua_timedout) {
  int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;
  /* freeMemoryIfNeeded may flush slave output buffers. This may result
   * into a slave, that may be the active client, to be freed. */
  if (server.current_client == NULL) return C_ERR;

  /* It was impossible to free enough memory, and the command the client
   * is trying to execute is denied during OOM conditions or the client
   * is in MULTI/EXEC context"htmlcode">

int freeMemoryIfNeeded(void) {
 /* By default replicas should ignore maxmemory
  * and just be masters exact copies. */
 if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;

 size_t mem_reported, mem_tofree, mem_freed;
 mstime_t latency, eviction_latency;
 long long delta;
 int slaves = listLength(server.slaves);

 /* When clients are paused the dataset should be static not just from the
  * POV of clients not being able to write, but also from the POV of
  * expires and evictions of keys not being performed. */
 if (clientsArePaused()) return C_OK;
 if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
  return C_OK;

 mem_freed = 0;

 if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
  goto cant_free; /* We need to free memory, but policy forbids. */

 latencyStartMonitor(latency);
 while (mem_freed < mem_tofree) {
  int j, k, i, keys_freed = 0;
  static unsigned int next_db = 0;
  sds bestkey = NULL;
  int bestdbid;
  redisDb *db;
  dict *dict;
  dictEntry *de;

  if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
   server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
  {
   struct evictionPoolEntry *pool = EvictionPoolLRU;

   while(bestkey == NULL) {
    unsigned long total_keys = 0, keys;

    /* We don't want to make local-db choices when expiring keys,
     * so to start populate the eviction pool sampling keys from
     * every DB. */
    for (i = 0; i < server.dbnum; i++) {
     db = server.db+i;
     dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) "eviction-del",eviction_latency);
   latencyRemoveNestedEvent(latency,eviction_latency);
   delta -= (long long) zmalloc_used_memory();
   mem_freed += delta;
   server.stat_evictedkeys++;
   notifyKeyspaceEvent(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();

   /* Normally our stop condition is the ability to release
    * a fixed, pre-computed amount of memory. However when we
    * are deleting objects in another thread, it's better to
    * check, from time to time, if we already reached our target
    * memory, since the "mem_freed" amount is computed only
    * across the dbAsyncDelete() call, while the thread can
    * release the memory all the time. */
   if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
    if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
     /* Let's satisfy our stop condition. */
     mem_freed = mem_tofree;
    }
   }
  }

  if (!keys_freed) {
   latencyEndMonitor(latency);
   latencyAddSampleIfNeeded("eviction-cycle",latency);
   goto cant_free; /* nothing to free... */
  }
 }
 latencyEndMonitor(latency);
 latencyAddSampleIfNeeded("eviction-cycle",latency);
 return C_OK;

cant_free:
 /* We are here if we are not able to reclaim memory. There is only one
  * last thing we can try: check if the lazyfree thread has jobs in queue
  * and wait... */
 while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
  if (((mem_reported - zmalloc_used_memory()) + mem_freed) >= mem_tofree)
   break;
  usleep(1000);
 }
 return C_ERR;
}

/* This is a wrapper for freeMemoryIfNeeded() that only really calls the
 * function if right now there are the conditions to do so safely:
 *
 * - There must be no script in timeout condition.
 * - Nor we are loading data right now.
 *
 */
int freeMemoryIfNeededAndSafe(void) {
 if (server.lua_timedout || server.loading) return C_OK;
 return freeMemoryIfNeeded();
}


几种淘汰策略maxmemory_policy就是在这个函数里面实现的。
当采用LRU时，可以看到，从0号数据库开始(默认16个)，根据不同的策略，选择redisDb的dict(全部键)或者expires(有过期时间的键)，用来更新候选键池子pool，pool更新策略是evictionPoolPopulate:


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

 count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
 for (j = 0; j < count; j++) {
  unsigned long long idle;
  sds key;
  robj *o;
  dictEntry *de;

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

  /* If the dictionary we are sampling from is not the main
   * dictionary (but the expires one) we need to lookup the key
   * again in the key dictionary to obtain the value object. */
  if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
   if (sampledict != keydict) de = dictFind(keydict, key);
   o = dictGetVal(de);
  }

  /* Calculate the idle time according to the policy. This is called
   * idle just because the code initially handled LRU, but is in fact
   * just a score where an higher score means better candidate. */
  if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
   idle = estimateObjectIdleTime(o);
  } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
   /* When we use an LRU policy, we sort the keys by idle time
    * so that we expire keys starting from greater idle time.
    * However when the policy is an LFU one, we have a frequency
    * estimation, and we want to evict keys with lower frequency
    * first. So inside the pool we put objects using the inverted
    * frequency subtracting the actual frequency to the maximum
    * frequency of 255. */
   idle = 255-LFUDecrAndReturn(o);
  } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
   /* In this case the sooner the expire the better. */
   idle = ULLONG_MAX - (long)dictGetVal(de);
  } else {
   serverPanic("Unknown eviction policy in evictionPoolPopulate()");
  }

  /* Insert the element inside the pool.
   * First, find the first empty bucket or the first populated
   * bucket that has an idle time smaller than our idle time. */
  k = 0;
  while (k < EVPOOL_SIZE &&
    pool[k].key &&
    pool[k].idle < idle) k++;
  if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
   /* Can't insert if the element is < the worst element we have
    * and there are no empty buckets. */
   continue;
  } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
   /* Inserting into empty position. No setup needed before insert. */
  } else {
   /* Inserting in the middle. Now k points to the first element
    * greater than the element to insert. */
   if (pool[EVPOOL_SIZE-1].key == NULL) {
    /* Free space on the right"htmlcode">

/* Given an object returns the min number of milliseconds the object was never
 * requested, using an approximated LRU algorithm. */
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;
 }
}


空闲时间基本就是就是对象的lru和全局的LRU_CLOCK()的差值乘以精度LRU_CLOCK_RESOLUTION，将秒转化为了毫秒。
参考链接



  
Random notes on improving the Redis LRU algorithm
  
Using Redis as an LRU cache

总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。