Redis中LFU算法的深入分析

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;

      16 bits   8 bits   +----------------+--------+   + Last decr time | LOG_C |   +----------------+--------+

lfu-log-factor 10lfu-decay-time 1

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;  }}

/* Update LFU when an object is accessed. * Firstly, decrement the counter if the decrement time is reached. * Then logarithmically increment the counter, and update the access time. */void updateLFU(robj *val) {  unsigned long counter = LFUDecrAndReturn(val);  counter = LFULogIncr(counter);  val->lru = (LFUGetTimeInMinutes()<<8) | counter;}

/* If the object decrement time is reached decrement the LFU counter but * do not update LFU fields of the object, we update the access time * and counter in an explicit way when the object is really accessed. * And we will times halve the counter according to the times of * elapsed time than server.lfu_decay_time. * Return the object frequency counter. * * This function is used in order to scan the dataset for the best object * to fit: as we check for the candidate, we incrementally decrement the * counter of the scanned objects if needed. */unsigned long LFUDecrAndReturn(robj *o) {  unsigned long ldt = o->lru >> 8;  unsigned long counter = o->lru & 255;  unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;  if (num_periods)    counter = (num_periods > counter) ? 0 : counter - num_periods;  return counter;}

/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */unsigned long LFUGetTimeInMinutes(void) {  return (server.unixtime/60) & 65535;}/* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */unsigned long LFUTimeElapsed(unsigned long ldt) {  unsigned long now = LFUGetTimeInMinutes();  if (now >= ldt) return now-ldt;  return 65535-ldt+now;}

/* Logarithmically increment a counter. The greater is the current counter value * the less likely is that it gets really implemented. Saturate it at 255. */uint8_t LFULogIncr(uint8_t counter) {  if (counter == 255) return 255;  double r = (double)rand()/RAND_MAX;  double baseval = counter - LFU_INIT_VAL;  if (baseval < 0) baseval = 0;  double p = 1.0/(baseval*server.lfu_log_factor+1);  if (r < p) counter++;  return counter;}

robj *createObject(int type, void *ptr) {  robj *o = zmalloc(sizeof(*o));  o->type = type;  o->encoding = OBJ_ENCODING_RAW;  o->ptr = ptr;  o->refcount = 1;  /* Set the LRU to the current lruclock (minutes resolution), or   * alternatively the LFU counter. */  if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;  } else {    o->lru = LRU_CLOCK();  }  return o;}

    if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||      server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)

    } 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);