1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#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 LFU_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 counter logarithmically: 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-LFU_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 > LFU_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 sec]\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 = LFU_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. */
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 = LFU_INIT_VAL;
entries[idx].decrtime = to_16bit_minutes(time(NULL));
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;
}
|
