diff options
| -rw-r--r-- | src/db.c | 16 | ||||
| -rw-r--r-- | src/evict.c | 31 | ||||
| -rw-r--r-- | src/object.c | 8 | ||||
| -rw-r--r-- | src/server.h | 3 |
4 files changed, 39 insertions, 19 deletions
@@ -38,6 +38,15 @@ * C-level DB API *----------------------------------------------------------------------------*/ +/* Update LFU when an object is accessed. + * Firstly, decrement the counter if the decrement time is reached. + * Then logarithmically increment the counter, and update the access time. */ +void updateLFU(robj *val) { + unsigned long counter = LFUDecrAndReturn(val); + counter = LFULogIncr(counter); + val->lru = (LFUGetTimeInMinutes()<<8) | counter; +} + /* Low level key lookup API, not actually called directly from commands * implementations that should instead rely on lookupKeyRead(), * lookupKeyWrite() and lookupKeyReadWithFlags(). */ @@ -54,9 +63,7 @@ robj *lookupKey(redisDb *db, robj *key, int flags) { !(flags & LOOKUP_NOTOUCH)) { if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { - unsigned long ldt = val->lru >> 8; - unsigned long counter = LFULogIncr(val->lru & 255); - val->lru = (ldt << 8) | counter; + updateLFU(val); } else { val->lru = LRU_CLOCK(); } @@ -180,6 +187,9 @@ void dbOverwrite(redisDb *db, robj *key, robj *val) { int saved_lru = old->lru; dictReplace(db->dict, key->ptr, val); val->lru = saved_lru; + /* LFU should be not only copied but also updated + * when a key is overwritten. */ + updateLFU(val); } else { dictReplace(db->dict, key->ptr, val); } diff --git a/src/evict.c b/src/evict.c index 0a04ed1bb..55b132123 100644 --- a/src/evict.c +++ b/src/evict.c @@ -60,8 +60,6 @@ struct evictionPoolEntry { static struct evictionPoolEntry *EvictionPoolLRU; -unsigned long LFUDecrAndReturn(robj *o); - /* ---------------------------------------------------------------------------- * Implementation of eviction, aging and LRU * --------------------------------------------------------------------------*/ @@ -302,8 +300,8 @@ unsigned long LFUGetTimeInMinutes(void) { return (server.unixtime/60) & 65535; } -/* Given an object last decrement time, compute the minimum number of minutes - * that elapsed since the last decrement. Handle overflow (ldt greater than +/* 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) { @@ -324,24 +322,31 @@ uint8_t LFULogIncr(uint8_t counter) { return counter; } -/* If the object decrement time is reached, decrement the LFU counter and - * update the decrement time field. Return the object frequency 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. */ -#define LFU_DECR_INTERVAL 1 unsigned long LFUDecrAndReturn(robj *o) { unsigned long ldt = o->lru >> 8; unsigned long counter = o->lru & 255; - if (LFUTimeElapsed(ldt) >= (unsigned long)server.lfu_decay_time && counter) { - if (counter > LFU_INIT_VAL*2) { - counter /= 2; - if (counter < LFU_INIT_VAL*2) counter = LFU_INIT_VAL*2; + long halve_times = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; + if (halve_times > 0 && counter) { + if (halve_times == 1) { + if (counter > LFU_INIT_VAL*2) { + counter /= 2; + if (counter < LFU_INIT_VAL*2) counter = LFU_INIT_VAL*2; + } else { + counter--; + } } else { - counter--; + counter = counter >> halve_times; } - o->lru = (LFUGetTimeInMinutes()<<8) | counter; } return counter; } diff --git a/src/object.c b/src/object.c index 8c33d7ef6..d2f8d53c5 100644 --- a/src/object.c +++ b/src/object.c @@ -1050,10 +1050,14 @@ void objectCommand(client *c) { if ((o = objectCommandLookupOrReply(c,c->argv[2],shared.nullbulk)) == NULL) return; if (!(server.maxmemory_policy & MAXMEMORY_FLAG_LFU)) { - addReplyError(c,"A non-LFU maxmemory policy is selected, access frequency not tracked. Please note that when switching between policies at runtime LRU and LFU data will take some time to adjust."); + addReplyError(c,"An LFU maxmemory policy is not selected, access frequency not tracked. Please note that when switching between policies at runtime LRU and LFU data will take some time to adjust."); return; } - addReplyLongLong(c,o->lru&255); + /* LFUDecrAndReturn should be called + * in case of the key has not been accessed for a long time, + * because we update the access time only + * when the key is read or overwritten. */ + addReplyLongLong(c,LFUDecrAndReturn(o)); } else { addReplyErrorFormat(c, "Unknown subcommand or wrong number of arguments for '%s'. Try OBJECT help", (char *)c->argv[1]->ptr); diff --git a/src/server.h b/src/server.h index aa04344cb..9b7da1d37 100644 --- a/src/server.h +++ b/src/server.h @@ -586,7 +586,7 @@ typedef struct redisObject { 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 decreas time). */ + * and most significant 16 bits access time). */ int refcount; void *ptr; } robj; @@ -1802,6 +1802,7 @@ void evictionPoolAlloc(void); #define LFU_INIT_VAL 5 unsigned long LFUGetTimeInMinutes(void); uint8_t LFULogIncr(uint8_t value); +unsigned long LFUDecrAndReturn(robj *o); /* Keys hashing / comparison functions for dict.c hash tables. */ uint64_t dictSdsHash(const void *key); |