LFU: do some changes about LFU to find hotkeys

Firstly, use access time to replace the decreas time of LFU.
For function LFUDecrAndReturn,
it should only try to get decremented counter,
not update LFU fields, we will update it in an explicit way.
And we will times halve the counter according to the times of
elapsed time than server.lfu_decay_time.
Everytime a key is accessed, we should update the LFU
including update access time, and increment the counter after
call function LFUDecrAndReturn.
If a key is overwritten, the LFU should be also updated.
Then we can use `OBJECT freq` command to get a key's frequence,
and LFUDecrAndReturn should be called in `OBJECT freq` command
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.

1 files changed, 18 insertions, 13 deletions

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;
 }