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 10
lfu-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 "htmlcode">

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


具体是当前时间转化成分钟数后取低16 bits，然后计算与ldt的差值now-ldt。当ldt > now时，默认为过了一个周期(16 bits，最大65535)，取值65535-ldt+now。
然后用差值与配置lfu_decay_time相除，LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去n个lfu_decay_time，则将counter减少n，counter - num_periods。
增长LFULogIncr


增长函数LFULogIncr如下：


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


counter并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。counter最大值为255。取一个0-1之间的随机数r与p比较，当r<p时，才增加counter，这和比特币中控制产出的策略类似。p取决于当前counter值与lfu_log_factor因子，counter值与lfu_log_factor因子越大，p越小，r<p的概率也越小，counter增长的概率也就越小。增长情况如下：

+--------+------------+------------+------------+------------+------------+

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

+--------+------------+------------+------------+------------+------------+



可见counter增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter增长的越来越慢。
新生key策略


另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter，createObject:


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


counter会被初始化为LFU_INIT_VAL，默认5。
pool


pool算法就与LRU算法一致了：


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


计算idle时有所不同：


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


使用了255-LFUDecrAndReturn(o)当做排序的依据。
参考链接



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

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