1 #include <stdio.h>
2 #include <time.h>
3 #include <stdint.h>
4 #include <stdlib.h>
5 
6 int decr_every = 1;
7 int keyspace_size = 1000000;
8 time_t switch_after = 30; /* Switch access pattern after N seconds. */
9 
10 struct entry {
11     /* Field that the LFU Redis implementation will have (we have
12      * 24 bits of total space in the object->lru field). */
13     uint8_t counter;    /* Logarithmic counter. */
14     uint16_t decrtime;  /* (Reduced precision) time of last decrement. */
15 
16     /* Fields only useful for visualization. */
17     uint64_t hits;      /* Number of real accesses. */
18     time_t ctime;       /* Key creation time. */
19 };
20 
21 #define to_16bit_minutes(x) ((x/60) & 65535)
22 #define COUNTER_INIT_VAL 5
23 
24 /* Compute the difference in minutes between two 16 bit minutes times
25  * obtained with to_16bit_minutes(). Since they can wrap around if
26  * we detect the overflow we account for it as if the counter wrapped
27  * a single time. */
minutes_diff(uint16_t now,uint16_t prev)28 uint16_t minutes_diff(uint16_t now, uint16_t prev) {
29     if (now >= prev) return now-prev;
30     return 65535-prev+now;
31 }
32 
33 /* Increment a couter logaritmically: the greatest is its value, the
34  * less likely is that the counter is really incremented.
35  * The maximum value of the counter is saturated at 255. */
log_incr(uint8_t counter)36 uint8_t log_incr(uint8_t counter) {
37     if (counter == 255) return counter;
38     double r = (double)rand()/RAND_MAX;
39     double baseval = counter-COUNTER_INIT_VAL;
40     if (baseval < 0) baseval = 0;
41     double limit = 1.0/(baseval*10+1);
42     if (r < limit) counter++;
43     return counter;
44 }
45 
46 /* Simulate an access to an entry. */
access_entry(struct entry * e)47 void access_entry(struct entry *e) {
48     e->counter = log_incr(e->counter);
49     e->hits++;
50 }
51 
52 /* Return the entry LFU value and as a side effect decrement the
53  * entry value if the decrement time was reached. */
scan_entry(struct entry * e)54 uint8_t scan_entry(struct entry *e) {
55     if (minutes_diff(to_16bit_minutes(time(NULL)),e->decrtime)
56         >= decr_every)
57     {
58         if (e->counter) {
59             if (e->counter > COUNTER_INIT_VAL*2) {
60                 e->counter /= 2;
61             } else {
62                 e->counter--;
63             }
64         }
65         e->decrtime = to_16bit_minutes(time(NULL));
66     }
67     return e->counter;
68 }
69 
70 /* Print the entry info. */
show_entry(long pos,struct entry * e)71 void show_entry(long pos, struct entry *e) {
72     char *tag = "normal       ";
73 
74     if (pos >= 10 && pos <= 14) tag = "new no access";
75     if (pos >= 15 && pos <= 19) tag = "new accessed ";
76     if (pos >= keyspace_size -5) tag= "old no access";
77 
78     printf("%ld] <%s> frequency:%d decrtime:%d [%lu hits | age:%ld sec]\n",
79         pos, tag, e->counter, e->decrtime, (unsigned long)e->hits,
80             time(NULL) - e->ctime);
81 }
82 
main(void)83 int main(void) {
84     time_t start = time(NULL);
85     time_t new_entry_time = start;
86     time_t display_time = start;
87     struct entry *entries = malloc(sizeof(*entries)*keyspace_size);
88     long j;
89 
90     /* Initialize. */
91     for (j = 0; j < keyspace_size; j++) {
92         entries[j].counter = COUNTER_INIT_VAL;
93         entries[j].decrtime = to_16bit_minutes(start);
94         entries[j].hits = 0;
95         entries[j].ctime = time(NULL);
96     }
97 
98     while(1) {
99         time_t now = time(NULL);
100         long idx;
101 
102         /* Scan N random entries (simulates the eviction under maxmemory). */
103         for (j = 0; j < 3; j++) {
104             scan_entry(entries+(rand()%keyspace_size));
105         }
106 
107         /* Access a random entry: use a power-law access pattern up to
108          * 'switch_after' seconds. Then revert to flat access pattern. */
109         if (now-start < switch_after) {
110             /* Power law. */
111             idx = 1;
112             while((rand() % 21) != 0 && idx < keyspace_size) idx *= 2;
113             if (idx > keyspace_size) idx = keyspace_size;
114             idx = rand() % idx;
115         } else {
116             /* Flat. */
117             idx = rand() % keyspace_size;
118         }
119 
120         /* Never access entries between position 10 and 14, so that
121          * we simulate what happens to new entries that are never
122          * accessed VS new entries which are accessed in positions
123          * 15-19.
124          *
125          * Also never access last 5 entry, so that we have keys which
126          * are never recreated (old), and never accessed. */
127         if ((idx < 10 || idx > 14) && (idx < keyspace_size-5))
128             access_entry(entries+idx);
129 
130         /* Simulate the addition of new entries at positions between
131          * 10 and 19, a random one every 10 seconds. */
132         if (new_entry_time <= now) {
133             idx = 10+(rand()%10);
134             entries[idx].counter = COUNTER_INIT_VAL;
135             entries[idx].decrtime = to_16bit_minutes(time(NULL));
136             entries[idx].hits = 0;
137             entries[idx].ctime = time(NULL);
138             new_entry_time = now+10;
139         }
140 
141         /* Show the first 20 entries and the last 20 entries. */
142         if (display_time != now) {
143             printf("=============================\n");
144             printf("Current minutes time: %d\n", (int)to_16bit_minutes(now));
145             printf("Access method: %s\n",
146                 (now-start < switch_after) ? "power-law" : "flat");
147 
148             for (j = 0; j < 20; j++)
149                 show_entry(j,entries+j);
150 
151             for (j = keyspace_size-20; j < keyspace_size; j++)
152                 show_entry(j,entries+j);
153             display_time = now;
154         }
155     }
156     return 0;
157 }
158 
159