LFU: Simulation of the algorithm planned for Redis.

We have 24 total bits of space in each object in order to implement
an LFU (Least Frequently Used) eviction policy.

We split the 24 bits into two fields:

      8 bits      16 bits
    +--------+----------------+
    | LOG_C  | Last decr time |
    +--------+----------------+

LOG_C is a logarithmic counter that provides an indication of the access
frequency. However this field must also be deceremented otherwise what used
to be a frequently accessed key in the past, will remain ranked like that
forever, while we want the algorithm to adapt to access pattern changes.

So the remaining 16 bits are used in order to store the "decrement time",
a reduced-precision unix time (we take 16 bits of the time converted
in minutes since we don't care about wrapping around) where the LOG_C
counter is halved if it has an high value, or just decremented if it
has a low value.

New keys don't start at zero, in order to have the ability to collect
some accesses before being trashed away, so they start at COUNTER_INIT_VAL.
The logaritmic increment performed on LOG_C takes care of COUNTER_INIT_VAL
when incrementing the key, so that keys starting at COUNTER_INIT_VAL
(or having a smaller value) have a very high chance of being incremented
on access.

The simulation starts with a power-law access pattern, and later converts
into a flat access pattern in order to see how the algorithm adapts.
Currenty the decrement operation period is 1 minute, however note that
it is not guaranteed that each key will be scanned 1 time every minute,
so the actual frequency can be lower. However under high load, we access
3/5 keys every newly inserted key (because of how Redis eviction works).

This is a work in progress at this point to evaluate if this works well.

1 files changed, 163 insertions, 0 deletions

diff --git a/utils/lru/lfu-simulation.c b/utils/lru/lfu-simulation.c
new file mode 100644
index 000000000..ebfc434ac
--- /dev/null
+++ b/utils/lru/lfu-simulation.c
@@ -0,0 +1,163 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+int decr_every = 1;
+int keyspace_size = 1000000;
+time_t switch_after = 30; /* Switch access pattern after N seconds. */
+
+struct entry {
+    /* Field that the LFU Redis implementation will have (we have
+     * 24 bits of total space in the object->lru field). */
+    uint8_t counter;    /* Logarithmic counter. */
+    uint16_t decrtime;  /* (Reduced precision) time of last decrement. */
+
+    /* Fields only useful for visualization. */
+    uint64_t hits;      /* Number of real accesses. */
+    time_t ctime;       /* Key creation time. */
+};
+
+#define to_16bit_minutes(x) ((x/60) & 65535)
+#define COUNTER_INIT_VAL 5
+
+/* Compute the difference in minutes between two 16 bit minutes times
+ * obtained with to_16bit_minutes(). Since they can wrap around if
+ * we detect the overflow we account for it as if the counter wrapped
+ * a single time. */
+uint16_t minutes_diff(uint16_t now, uint16_t prev) {
+    if (now >= prev) return now-prev;
+    return 65535-prev+now;
+}
+
+/* Increment a couter logaritmically: the greatest is its value, the
+ * less likely is that the counter is really incremented.
+ * The maximum value of the counter is saturated at 255. */
+uint8_t log_incr(uint8_t counter) {
+    if (counter == 255) return counter;
+    double r = (double)rand()/RAND_MAX;
+    double baseval = counter-COUNTER_INIT_VAL;
+    if (baseval < 0) baseval = 0;
+    double limit = 1.0/(baseval*10+1);
+    if (r < limit) counter++;
+    return counter;
+}
+
+/* Simulate an access to an entry. */
+void access_entry(struct entry *e) {
+    e->counter = log_incr(e->counter);
+    e->hits++;
+}
+
+/* Return the entry LFU value and as a side effect decrement the
+ * entry value if the decrement time was reached. */
+uint8_t scan_entry(struct entry *e) {
+    if (minutes_diff(to_16bit_minutes(time(NULL)),e->decrtime)
+        >= decr_every)
+    {
+        if (e->counter) {
+            if (e->counter > COUNTER_INIT_VAL*2) {
+                e->counter /= 2;
+            } else {
+                e->counter--;
+            }
+        }
+        e->decrtime = to_16bit_minutes(time(NULL));
+    }
+    return e->counter;
+}
+
+/* Print the entry info. */
+void show_entry(long pos, struct entry *e) {
+    char *tag = "normal       ";
+
+    if (pos >= 10 && pos <= 14) tag = "new no access";
+    if (pos >= 15 && pos <= 19) tag = "new accessed ";
+    if (pos >= keyspace_size -5) tag= "old no access";
+
+    printf("%ld] <%s> frequency:%d decrtime:%d [%lu hits | age:%ld seconds]\n",
+        pos, tag, e->counter, e->decrtime, (unsigned long)e->hits,
+            time(NULL) - e->ctime);
+}
+
+int main(void) {
+    time_t start = time(NULL);
+    time_t new_entry_time = start;
+    time_t display_time = start;
+    struct entry *entries = malloc(sizeof(*entries)*keyspace_size);
+    long j;
+
+    /* Initialize. */
+    for (j = 0; j < keyspace_size; j++) {
+        entries[j].counter = COUNTER_INIT_VAL;
+        entries[j].decrtime = to_16bit_minutes(start);
+        entries[j].hits = 0;
+        entries[j].ctime = time(NULL);
+    }
+
+    while(1) {
+        time_t now = time(NULL);
+        long idx;
+
+        /* Scan N random entries (simulates the eviction under maxmemory). */
+        for (j = 0; j < 3; j++) {
+            scan_entry(entries+(rand()%keyspace_size));
+        }
+
+        /* Access a random entry: use a power-law access pattern up to
+         * 'switch_after' seconds. Then revert to flat access pattern. */
+        if (now-start < switch_after) {
+            /* Power law. */
+            #if 0
+            idx = keyspace_size;
+            while(rand() % 2 && idx > 1) idx /= 2;
+            idx = rand() % idx;
+            #endif
+            idx = 1;
+            while((rand() % 21) != 0 && idx < keyspace_size) idx *= 2;
+            if (idx > keyspace_size) idx = keyspace_size;
+            idx = rand() % idx;
+        } else {
+            /* Flat. */
+            idx = rand() % keyspace_size;
+        }
+
+        /* Never access entries between position 10 and 14, so that
+         * we simulate what happens to new entries that are never
+         * accessed VS new entries which are accessed in positions
+         * 15-19.
+         *
+         * Also never access last 5 entry, so that we have keys which
+         * are never recreated (old), and never accessed. */
+        if ((idx < 10 || idx > 14) && (idx < keyspace_size-5))
+            access_entry(entries+idx);
+
+        /* Simulate the addition of new entries at positions between
+         * 10 and 19, a random one every 10 seconds. */
+        if (new_entry_time == now) {
+            idx = 10+(rand()%10);
+            entries[idx].counter = COUNTER_INIT_VAL;
+            entries[idx].decrtime = to_16bit_minutes(start);
+            entries[idx].hits = 0;
+            entries[idx].ctime = time(NULL);
+            new_entry_time = now+10;
+        }
+
+        /* Show the first 20 entries and the last 20 entries. */
+        if (display_time != now) {
+            printf("=============================\n");
+            printf("Current minutes time: %d\n", (int)to_16bit_minutes(now));
+            printf("Access method: %s\n",
+                (now-start < switch_after) ? "power-law" : "flat");
+
+            for (j = 0; j < 20; j++)
+                show_entry(j,entries+j);
+
+            for (j = keyspace_size-20; j < keyspace_size; j++)
+                show_entry(j,entries+j);
+            display_time = now;
+        }
+    }
+    return 0;
+}
+