diff options
author | antirez <antirez@gmail.com> | 2016-07-18 18:17:57 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2016-07-18 18:17:59 +0200 |
commit | 6416ab19d0bd51fa90c17d856baebd581a7d991c (patch) | |
tree | 2b9e02663e70d040e29506fb93f83fabc736eba5 /src/evict.c | |
parent | dbce190ad018fc757d9c494952531db31eaac700 (diff) | |
download | redis-6416ab19d0bd51fa90c17d856baebd581a7d991c.tar.gz |
LFU: Use the LRU pool for the LFU algorithm.
Verified to have better real world performances with power-law access
patterns because of the data accumulated across calls.
Diffstat (limited to 'src/evict.c')
-rw-r--r-- | src/evict.c | 61 |
1 files changed, 25 insertions, 36 deletions
diff --git a/src/evict.c b/src/evict.c index 3025b3e9b..d791415a5 100644 --- a/src/evict.c +++ b/src/evict.c @@ -43,11 +43,15 @@ * Entries inside the eviciton pool are taken ordered by idle time, putting * greater idle times to the right (ascending order). * + * When an LFU policy is used instead, a reverse frequency indication is used + * instead of the idle time, so that we still evict by larger value (larger + * inverse frequency means to evict keys with the least frequent accesses). + * * Empty entries have the key pointer set to NULL. */ #define EVPOOL_SIZE 16 #define EVPOOL_CACHED_SDS_SIZE 255 struct evictionPoolEntry { - unsigned long long idle; /* Object idle time. */ + unsigned long long idle; /* Object idle time (inverse frequency for LFU) */ sds key; /* Key name. */ sds cached; /* Cached SDS object for key name. */ int dbid; /* Key DB number. */ @@ -55,6 +59,8 @@ struct evictionPoolEntry { static struct evictionPoolEntry *EvictionPoolLRU; +unsigned long LFUDecrAndReturn(robj *o); + /* ---------------------------------------------------------------------------- * Implementation of eviction, aging and LRU * --------------------------------------------------------------------------*/ @@ -158,7 +164,18 @@ void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evic * again in the key dictionary to obtain the value object. */ if (sampledict != keydict) de = dictFind(keydict, key); o = dictGetVal(de); - idle = estimateObjectIdleTime(o); + if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) { + idle = estimateObjectIdleTime(o); + } else { + /* 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); + } /* Insert the element inside the pool. * First, find the first empty bucket or the first populated @@ -361,7 +378,7 @@ int freeMemoryIfNeeded(void) { dict *dict; dictEntry *de; - if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) { + if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU)) { struct evictionPoolEntry *pool = EvictionPoolLRU; while(bestkey == NULL) { @@ -372,7 +389,8 @@ int freeMemoryIfNeeded(void) { * every DB. */ for (i = 0; i < server.dbnum; i++) { db = server.db+i; - dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU) ? + dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU || + server.maxmemory_policy == MAXMEMORY_ALLKEYS_LFU) ? db->dict : db->expires; if ((keys = dictSize(dict)) != 0) { evictionPoolPopulate(i, dict, db->dict, pool); @@ -386,7 +404,9 @@ int freeMemoryIfNeeded(void) { if (pool[k].key == NULL) continue; bestdbid = pool[k].dbid; - if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU) { + if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU || + server.maxmemory_policy == MAXMEMORY_ALLKEYS_LFU) + { de = dictFind(server.db[pool[k].dbid].dict, pool[k].key); } else { @@ -469,37 +489,6 @@ int freeMemoryIfNeeded(void) { } } - /* allkeys-lfu and volatile-lfu */ - else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { - long bestfreq = 0; /* Initialized to avoid warning. */ - - for (i = 0; i < server.dbnum; i++) { - j = (++next_db) % server.dbnum; - db = server.db+j; - dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LFU) ? - db->dict : db->expires; - if (dictSize(dict) != 0) { - for (k = 0; k < server.maxmemory_samples; k++) { - sds thiskey; - long thisfreq; - - de = dictGetRandomKey(dict); - thiskey = dictGetKey(de); - robj *o = dictFetchValue(db->dict,thiskey); - thisfreq = LFUDecrAndReturn(o); - - /* Keys with a smaller access frequency are - * better candidates for deletion */ - if (bestkey == NULL || thisfreq < bestfreq) { - bestkey = thiskey; - bestfreq = thisfreq; - bestdbid = j; - } - } - } - } - } - /* Finally remove the selected key. */ if (bestkey) { db = server.db+bestdbid; |