#define LRU_BITS 24
struct redisServer {
       pid_t pid; /* Main process pid. */
       char *configfile; /* Absolute config file path, or NULL */
       …..
       unsigned lruclock:LRU_BITS; /* Clock for LRU eviction */
       ...
};

#define REDIS_LRU_BITS 24
typedef struct redisObject {
     unsigned type:4;
     unsigned encoding:4;
    // 从这里看出, 这个字段在不同淘汰策略下, 存的内容是不一样的
     unsigned lru:LRU_BITS; /* LRU time (relative to server.lruclock) or
                             * LFU data (least significant 8 bits frequency
                             * and most significant 16 bits decreas time). */
     int refcount;
     void *ptr;
} robj

robj *lookupKey(redisDb *db, robj *key, int flags) {
    ...
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { //如果配置的是lfu方式，则更新lfu
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();//否则按lru方式更新
            }
    ...
}

/* 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. */
// server.unixtime是Redis缓存的Unix时间戳
// 可以看出使用的Unix的分钟时间戳，取模2^16
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) {
  // 获取系统当前的LFU time
  unsigned long now = LFUGetTimeInMinutes();
  // 如果now >= ldt 直接取差值  
  if (now >= ldt) return now-ldt;
  // 如果now < ldt 增加上65535
  // 注意Redis 认为折返就只有一次折返，多次折返也是一次，我思考了很久感觉这个应该是可以接受的，本身Redis的淘汰算法就带有随机性  
  return 65535-ldt+now;
}

-- 用于调整Logistic Counter的增长速度，lfu-log-factor值越大，Logistic Counter增长越慢。
lfu-log-factor 10
-- 用于调整Logistic Counter的衰减速度，它是一个以分钟为单位的数值，默认值为1,；lfu-decay-time值越大，衰减越慢。
lfu-decay-time 1

/* 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) {
  // Logistic Counter最大值为255  
  if (counter == 255) return 255;
  // 取一个0~1的随机数r  
  double r = (double)rand()/RAND_MAX;
  // counter减去LFU_INIT_VAL （LFU_INIT_VAL为每个key的Logistic Counter初始值，默认为5）
  double baseval = counter - LFU_INIT_VAL;
  // 如果衰减之后已经小于5了，那么baseval < 0取0
  if (baseval < 0) baseval = 0;
  // lfu-log-factor在这里被使用
  // 可以看出如果lfu_log_factor的值越大，p越小
  // r < p的概率就越小，Logistic Counter增加的概率就越小（因此lfu_log_factor越大增长越缓慢）
  double p = 1.0/(baseval*server.lfu_log_factor+1);
  if (r < p) counter++;
  return 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) {
  // 获取lru的高16位，也就是ldt
  unsigned long ldt = o->lru >> 8;  
  // 获取lru的低8位，也就是logc  
  unsigned long counter = o->lru & 255;
  // 根据配置的lfu-decay-time计算Logistic Counter需要衰减的值
  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;
}

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. */
        // 空闲时间的计算方式 LRU 、 LFU 、最快过期的可以 三种过期策略下 都是不同的
        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;
        // 在这里判断 池中某一个key的空闲时间是否小于 当前key的空闲时间
        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? Insert at k shifting
                 * all the elements from k to end to the right. */

                /* Save SDS before overwriting. */
                sds cached = pool[EVPOOL_SIZE-1].cached;
                memmove(pool+k+1,pool+k,
                    sizeof(pool[0])*(EVPOOL_SIZE-k-1));
                pool[k].cached = cached;
            } else {
                /* No free space on right? Insert at k-1 */
                k--;
                /* Shift all elements on the left of k (included) to the
                 * left, so we discard the element with smaller idle time. */
                sds cached = pool[0].cached; /* Save SDS before overwriting. */
                if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);
                memmove(pool,pool+1,sizeof(pool[0])*k);
                pool[k].cached = cached;
            }
        }

        /* Try to reuse the cached SDS string allocated in the pool entry,
         * because allocating and deallocating this object is costly
         * (according to the profiler, not my fantasy. Remember:
         * premature optimizbla bla bla bla. */
        int klen = sdslen(key);
        if (klen > EVPOOL_CACHED_SDS_SIZE) {
            pool[k].key = sdsdup(key);
        } else {
            memcpy(pool[k].cached,key,klen+1);
            sdssetlen(pool[k].cached,klen);
            pool[k].key = pool[k].cached;
        }
        pool[k].idle = idle;
        pool[k].dbid = dbid;
    }
}