redis evict.cメモリ淘汰メカニズムのソースコード分析


周知のように、redisはメモリデータベースであり、すべてのキー値ペアがメモリに格納されています.データが多くなるとメモリが
新しいキー値ペアを保存するのに十分なスペースがあるように、いくつかのキー値ペアを淘汰します.redisでserverを設定.maxmemory
メモリの使用を限定する(server.maxmemoryは0、メモリを制限しない)、serverに到達する.maxmemoryは淘汰メカニズムをトリガーします.redis
主に6種類の淘汰戦略を提供します.
1)volatile-lru:有効期限が設定されているデータセット(server.db[i].expires)から、最も最近使用したデータの除外を選択
2)volatile-lfu:有効期限が設定されているデータセット(server.db[i].expires)から、最近最も使用されていないデータを選択します.
3)volatile-ttl:有効期限が設定されているデータセット(server.db[i].expires)から有効期限が切れるデータを選択します.
4)volatile-random:有効期限が設定されているデータセット(server.db[i].expires)から任意のデータ除外を選択
4)allkeys-lru:データセット(server.db[i].dict)から最近最も使用されているデータ淘汰を選択
5)allkeys-lfu:データセット(server.db[i].dict)から最近最も使用されていないデータの淘汰を選択
6)allkeys-random:データセット(server.db[i].dict)から任意にデータ淘汰を選択
7)no-enviction(駆逐):駆逐禁止データ
redisは、クライアントのコマンドを実行するたびに、使用メモリがserverを超えるかどうかをチェックする.maxmemoryは、超えると淘汰データを行います.
int processCommand(client *c) {
	……//server.maxmemory 0,         
	if (server.maxmemory) {
	//    ,      
        int retval = freeMemoryIfNeeded();
        ……
    }
    ……
}
int freeMemoryIfNeeded(void) {
    mem_reported = zmalloc_used_memory();//  redis    
    if (mem_reported <= server.maxmemory) return C_OK; 
    mem_used = mem_reported;
    if (slaves) {
        listRewind(server.slaves,&li);
        while((ln = listNext(&li))) {
            ……//  slaves output   
        }
    }//aof         
    if (server.aof_state != AOF_OFF) {
        mem_used -= sdslen(server.aof_buf);
        mem_used -= aofRewriteBufferSize();
    }
    /* Check if we are still over the memory limit. */
    if (mem_used <= server.maxmemory) return C_OK;
    /* Compute how much memory we need to free. */
    mem_tofree = mem_used - server.maxmemory;
    mem_freed = 0;
    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        goto cant_free; /*        */
    //      
    while (mem_freed < mem_tofree) {
    	……
    	sds bestkey = NULL;
        if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
            server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
        {   //  ttl  lru    
            struct evictionPoolEntry *pool = EvictionPoolLRU;
            while(bestkey == NULL) {
                unsigned long total_keys = 0, keys;
                for (i = 0; i < server.dbnum; i++) {
                    db = server.db+i;
                    dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?
                            db->dict : db->expires;
                    if ((keys = dictSize(dict)) != 0) {
                        evictionPoolPopulate(i, dict, db->dict, pool);
                        //pool       evictionPool
                    }
                }/* evictionPool                        */
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;
                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                        de = dictFind(server.db[pool[k].dbid].dict,
                            pool[k].key);
                    } else {
                        de = dictFind(server.db[pool[k].dbid].expires,
                            pool[k].key);
                    }
                    ……
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        /* Ghost... Iterate again. */
                    }
                }
            }
        }
        else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
                 server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
        {   /*  db->dict  db->expires             */
            for (i = 0; i < server.dbnum; i++) {
                j = (++next_db) % server.dbnum;
                db = server.db+j;
                dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ?
                        db->dict : db->expires;
                if (dictSize(dict) != 0) {
                    de = dictGetRandomKey(dict);
                    bestkey = dictGetKey(de);
                    bestdbid = j;
                    break;
                }
            }
        }//        
        if (bestkey) {
            db = server.db+bestdbid;
            robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
            propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
            delta = (long long) zmalloc_used_memory();
            if (server.lazyfree_lazy_eviction)
                dbAsyncDelete(db,keyobj);
            else
                dbSyncDelete(db,keyobj);
            delta -= (long long) zmalloc_used_memory();
            mem_freed += delta;
            server.stat_evictedkeys++;
            decrRefCount(keyobj);
            keys_freed++;
            if (slaves) flushSlavesOutputBuffers();
        }

    }
    return C_OK;
cant_free://           
    while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
        if (((mem_reported - zmalloc_used_memory()) + mem_freed) >= mem_tofree)
            break;
        usleep(1000);
    }
    return C_ERR;
}

淘汰メカニズムに従ってランダムに選択したキー値ペアからキー値ペアを選択してevictionPoolを構築する
1)LRUデータ淘汰メカニズム:データセットでランダムにいくつかのキー値ペアを選択し、lruの最大の一部のキー値ペアを選択してevictionPoolを構築する.
2)LFUデータ淘汰メカニズム:データセットでランダムにいくつかのキー値ペアを選択し、lfuの最小のキー値ペアの一部を選択してevictionPoolを構築する.
3)TTLデータ淘汰メカニズム:有効期限を設定したデータセットからランダムにいくつかのキー値ペアを選択し、TTLの最大の一部のキー値ペアを選択してevictionPoolを構築する.
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];
    //    sampledict       
    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
    for (j = 0; j < count; j++) {
        de = samples[j];
        key = dictGetKey(de);
        if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
            if (sampledict != keydict) de = dictFind(keydict, key);
            o = dictGetVal(de);
        }        
        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            idle = estimateObjectIdleTime(o);//LRU  ,  lru 
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            idle = 255-LFUDecrAndReturn(o);//LFU  ,  lfu 
        } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
            idle = ULLONG_MAX - (long)dictGetVal(de);//TTL  ,  ttl 
        }
        k = 0;
        //  idle           pool(       ),    idle   EVPOOL_SIZE 
        while (k < EVPOOL_SIZE &&pool[k].key &&pool[k].idle < idle) 
        	k++;
        if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
            continue;
        } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
            /* Inserting into empty position. No setup needed before insert. */
        } else {
            if (pool[EVPOOL_SIZE-1].key == NULL) {
                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 {
                k--;
                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;
            }
        }
        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;
    }
}