Redis深度歷險(xiǎn)-淘汰策略

Redis是內(nèi)存型數(shù)據(jù)庫，在系統(tǒng)中如果占用內(nèi)存超過物理內(nèi)存就會(huì)出現(xiàn)磁盤swap，這種操作就會(huì)導(dǎo)致性能急劇下降，所以才會(huì)出現(xiàn)淘汰策略

Redis配置

Redis允許用戶配置使用的最大內(nèi)存和超過最大內(nèi)存時(shí)的處理策略

maxmemory：用于設(shè)置最大使用的內(nèi)存

maxmemory-policy：超過最大內(nèi)存時(shí)的處理策略

• noeviction：禁止寫入操作、允許讀取和刪除操作，這是默認(rèn)配置
• volatile-lru：淘汰設(shè)置了過期時(shí)間的key，最少使用的key會(huì)被釋放掉
• volatile-lfu：淘汰設(shè)置了過期時(shí)間的key，某段時(shí)間內(nèi)使用頻率最少的key會(huì)被釋放掉
• volatile-ttl：淘汰設(shè)置了過期時(shí)間的key，剩余壽命ttl最少的key會(huì)被釋放掉
• volatile-random：淘汰設(shè)置了過期時(shí)間中的隨機(jī)key
• allkeys-lru：與volatile-lru類似，只是面向所有key
• allkeys-lfu：與volatile-lfu類似，只是面向所有key
• allkeys-random：與volatile-random類似，只是面向所有的key

Redis實(shí)現(xiàn)

Redis對象結(jié)構(gòu)體

typedef struct redisObject {
    //數(shù)據(jù)類型，redis提供的5種類型
    unsigned type:4;
    //這種類型的底層實(shí)現(xiàn)方式，比如有序集合底層會(huì)使用鏈表或者壓縮列表實(shí)現(xiàn)
    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). */
    //元素的引用計(jì)數(shù)
    int refcount;
    //元素的數(shù)據(jù)
    void *ptr;
} robj;

這里主要需要關(guān)注的是lru字段，共24位

• 如果使用的是lru相關(guān)算法，則記錄的是最后訪問時(shí)間
• 如果使用的是lfu相關(guān)算法，則高16位記錄的是上次訪問時(shí)間（單位為分）、低8位記錄的是某段時(shí)間的使用頻次

lru算法

Redis實(shí)現(xiàn)的是一種類似LRU的算法，主要是完全按照LRU的實(shí)現(xiàn)需要對現(xiàn)有數(shù)據(jù)結(jié)構(gòu)做改造同時(shí)會(huì)消耗很多內(nèi)存

1. 為每個(gè)key添加一個(gè)24bit的字段，用于存儲(chǔ)最后訪問的時(shí)間戳
2. 隨機(jī)采樣出N個(gè)key，淘汰掉最舊的key
3. 將隨機(jī)采樣剩下的key放入到淘汰池中（一個(gè)數(shù)組）
4. 淘汰后內(nèi)存依舊超出maxmemory，隨機(jī)采樣出N個(gè)key與淘汰池?cái)?shù)據(jù)融合，淘汰掉最舊的key
5. 繼續(xù)3、4步驟，直到空間小于maxmemory

Redis的淘汰過程是一個(gè)阻塞的過程，直到清理出足夠的空間；如果內(nèi)存達(dá)到maxmemory的限制并且客戶端還在不停的寫入，可能會(huì)導(dǎo)致反復(fù)出發(fā)清理策略，導(dǎo)致請求延遲
淘汰池的大小由maxmemory-samples配置來控制，設(shè)置為5-10之間即可

lfu算法

配置

• lfu-log-factor：設(shè)置計(jì)數(shù)器counter的增長速度，越小增長越快
• lfu-decay-time：設(shè)置計(jì)數(shù)器counter的減少速度，以分鐘為單位，越小下降越快

lfu計(jì)數(shù)減少算法

void updateLFU(robj *val) {
    //將訪問計(jì)數(shù)取出來
    unsigned long counter = LFUDecrAndReturn(val);
    //計(jì)數(shù)增長
    counter = LFULogIncr(counter);
    //將訪問計(jì)數(shù)設(shè)置到redisobj中
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

unsigned long LFUDecrAndReturn(robj *o) {
    //分別取出上一次的訪問時(shí)間以及訪問計(jì)數(shù)
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    //每超過lfu_decay_time的時(shí)間counter計(jì)數(shù)就需要減少一
    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;
}

//以分鐘為單位計(jì)算出上次訪問到現(xiàn)在的時(shí)間
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now;
}
//以分鐘為單位， 再對65535取模
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}

隨著時(shí)間的推移lfu計(jì)數(shù)應(yīng)該是會(huì)降低的，但是直到下次更新lfu時(shí)才會(huì)重新計(jì)算

lfu計(jì)數(shù)增長算法

uint8_t LFULogIncr(uint8_t counter) {
    //最大的counter訪問計(jì)數(shù)就是255（8）位
    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;
}

Redis內(nèi)部使用了一種隨機(jī)算法1.0/(baseval*server.lfu_log_factor+1)，不過大體上的規(guī)律是隨著訪問次數(shù)的增大增長速率降低

新生key

lfu算法會(huì)有一個(gè)問題就是新生key可能很快被淘汰掉，所以會(huì)特意設(shè)置一個(gè)訪問時(shí)間

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;

    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        //新生的時(shí)候會(huì)設(shè)置一個(gè)默認(rèn)值（5）
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}