Redis內存回收:LRU算法

//去掉一些過期的KEYS
for (j = 0; j < server.dbnum; j++) {
    redisDb *db = server.db+j;
    int num = dictSize(db->expires);//計算hash表中過期Key的數目
    if (num) {
        time_t now = time(NULL);
        //#define REDIS_EXPIRELOOKUPS_PER_CRON 100
        if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
            num = REDIS_EXPIRELOOKUPS_PER_CRON;
        //循環100次，從過期Hash表中隨機挑選出100個Key,判斷Key是否過期，如果過期了，執行刪除操作
        while (num--) {
            dictEntry *de;
            time_t t;
            //隨機獲取Key值(db->expires里面存儲的均是即將過期的Keys)
            if ((de = dictGetRandomKey(db->expires)) == NULL) break;
            t = (time_t) dictGetEntryVal(de);
            if (now > t) {
                //不僅要從存放過期keys的Hash表中刪除數據，還要從存放實際數據的Hash表中刪除數據
                deleteKey(db,dictGetEntryKey(de));
            }
        }
    }
}

typedef struct redisDb {
    dict *dict;//用來存放實際Key->Value數據的位置 
    dict *expires;//用于記錄Key的過期時間 
    int id;//表示選擇的是第幾個redis庫
} redisDb;

# maxmemory <bytes>

# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached. You can select among five behaviors:
# 
# volatile-lru -> remove the key with an expire set using an LRU algorithm
# allkeys-lru -> remove any key accordingly to the LRU algorithm
# volatile-random -> remove a random key with an expire set
# allkeys-random -> remove a random key, any key
# volatile-ttl -> remove the key with the nearest expire time (minor TTL)
# noeviction -> don't expire at all, just return an error on write operations
# 
# Note: with any of the above policies, Redis will return an error on write
#       operations, when there are not suitable keys for eviction.
#
#       At the date of writing this commands are: set setnx setex append
#       incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
#       sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
#       zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
#       getset mset msetnx exec sort
#
# The default is:
#
# maxmemory-policy noeviction

# LRU and minimal TTL algorithms are not precise algorithms but approximated
# algorithms (in order to save memory), so you can tune it for speed or
# accuracy. For default Redis will check five keys and pick the one that was
# used less recently, you can change the sample size using the following
# configuration directive.
#
# The default of 5 produces good enough results. 10 Approximates very closely
# true LRU but costs a bit more CPU. 3 is very fast but not very accurate.
#
# maxmemory-samples 5

#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
        //存放的對象類型 
    unsigned type:4;
    //內容編碼 
    unsigned encoding:4;
    //與server.lruclock的時間差值 
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */\
    //引用計數算法使用的引用計數器
    int refcount;
    //數據指針
    void *ptr;
} robj;

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    .....
    run_with_period(100) trackOperationsPerSecond();

    /* We have just REDIS_LRU_BITS bits per object for LRU information.
     * So we use an (eventually wrapping) LRU clock.
     *
     * Note that even if the counter wraps it's not a big problem,
     * everything will still work but some object will appear younger
     * to Redis. However for this to happen a given object should never be
     * touched for all the time needed to the counter to wrap, which is
     * not likely.
     *
     * Note that you can change the resolution altering the
     * REDIS_LRU_CLOCK_RESOLUTION define. */
    server.lruclock = getLRUClock();
    ....
    return 1000/server.hz;
}

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = REDIS_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    //很關鍵的一步，Redis中創建的每一個對象，都記錄下該對象的LRU時鐘
    /* Set the LRU to the current lruclock (minutes resolution). */
    o->lru = LRU_CLOCK();
    return o;
}

#define LRU_CLOCK() ((1000/server.hz <= REDIS_LRU_CLOCK_RESOLUTION) ? server.lruclock : getLRUClock())

            //不同的策略，操作的數據集不同
            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
            {
                dict = server.db[j].dict;
            } else {//操作的是設置了過期時間的key集
                dict = server.db[j].expires;
            }
            if (dictSize(dict) == 0) continue;

            /* volatile-random and allkeys-random policy */
            //隨機選擇進行淘汰
            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)
            {
                struct evictionPoolEntry *pool = db->eviction_pool;

                while(bestkey == NULL) {
                    //選擇隨機樣式，并從樣本中作用LRU算法選擇需要淘汰的數據
                    evictionPoolPopulate(dict, db->dict, db->eviction_pool);
                    /* Go backward from best to worst element to evict. */
                    for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                        if (pool[k].key == NULL) continue;
                        de = dictFind(dict,pool[k].key);
                        sdsfree(pool[k].key);
                        //將pool+k+1之后的元素向前平移一個單位
                        memmove(pool+k,pool+k+1,
                            sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
                        /* Clear the element on the right which is empty
                         * since we shifted one position to the left.  */
                        pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
                        pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
                        //選擇了需要淘汰的數據
                        if (de) {
                            bestkey = dictGetKey(de);
                            break;
                        } else {
                            /* Ghost... */
                            continue;
                        }
                    }
                }
            }

#define EVICTION_SAMPLES_ARRAY_SIZE 16
void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    //EVICTION_SAMPLES_ARRAY_SIZE最大樣本數，默認16
    dictEntry *_samples[EVICTION_SAMPLES_ARRAY_SIZE];
    dictEntry **samples;
    //如果我們在配置文件中配置的samples小于16，則直接使用EVICTION_SAMPLES_ARRAY_SIZE
    if (server.maxmemory_samples <= EVICTION_SAMPLES_ARRAY_SIZE) {
        samples = _samples;
    } else {
        samples = zmalloc(sizeof(samples[0])*server.maxmemory_samples);
    }

#if 1 /* Use bulk get by default. */
    //從樣本集中隨機獲取server.maxmemory_samples個數據，存放在
    count = dictGetRandomKeys(sampledict,samples,server.maxmemory_samples);
#else
    count = server.maxmemory_samples;
    for (j = 0; j < count; j++) samples[j] = dictGetRandomKey(sampledict);
#endif

    for (j = 0; j < count; j++) {
        unsigned long long idle;
        sds key;
        robj *o;
        dictEntry *de;
        de = samples[j];
        key = dictGetKey(de);
        if (sampledict != keydict) de = dictFind(keydict, key);
        o = dictGetVal(de);
        //計算LRU時間
        idle = estimateObjectIdleTime(o);
        k = 0;
        //選擇de在pool中的正確位置,按升序進行排序,升序的依據是其idle時間
        while (k < REDIS_EVICTION_POOL_SIZE &&
               pool[k].key &&
               pool[k].idle < idle) k++;
        if (k == 0 && pool[REDIS_EVICTION_POOL_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 < REDIS_EVICTION_POOL_SIZE && pool[k].key == NULL) {
            /* Inserting into empty position. No setup needed before insert. */
        } else {
            //移動元素，memmove,還有空間可以插入新元素
            if (pool[REDIS_EVICTION_POOL_SIZE-1].key == NULL) {
                memmove(pool+k+1,pool+k,
                    sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
            } 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. */
                //以下操作突出了第K個位置
                sdsfree(pool[0].key);
                memmove(pool,pool+1,sizeof(pool[0])*k);
            }
        }
        //在第K個位置插入
        pool[k].key = sdsdup(key);
        pool[k].idle = idle;
    }
    //執行到此之后，pool中存放的就是按idle time升序排序
    if (samples != _samples) zfree(samples);
}

//精略估計LRU時間 
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
    } else {//這種情況一般不會發生，發生時證明redis中鍵的保存時間已經wrap了
        return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
                    REDIS_LRU_CLOCK_RESOLUTION;
    }
}