summaryrefslogtreecommitdiffstats
path: root/utils/lru
diff options
context:
space:
mode:
Diffstat (limited to 'utils/lru')
-rw-r--r--utils/lru/README19
-rw-r--r--utils/lru/lfu-simulation.c158
-rw-r--r--utils/lru/test-lru.rb223
3 files changed, 400 insertions, 0 deletions
diff --git a/utils/lru/README b/utils/lru/README
new file mode 100644
index 0000000..f043b29
--- /dev/null
+++ b/utils/lru/README
@@ -0,0 +1,19 @@
+The test-lru.rb program can be used in order to check the behavior of the
+Redis approximated LRU algorithm against the theoretical output of true
+LRU algorithm.
+
+In order to use the program you need to recompile Redis setting the define
+REDIS_LRU_CLOCK_RESOLUTION to 1, by editing the file server.h.
+This allows to execute the program in a fast way since the 1 ms resolution
+is enough for all the objects to have a different enough time stamp during
+the test.
+
+The program is executed like this:
+
+ ruby test-lru.rb /tmp/lru.html
+
+You can optionally specify a number of times to run, so that the program
+will output averages of different runs, by adding an additional argument.
+For instance in order to run the test 10 times use:
+
+ ruby test-lru.rb /tmp/lru.html 10
diff --git a/utils/lru/lfu-simulation.c b/utils/lru/lfu-simulation.c
new file mode 100644
index 0000000..60105e5
--- /dev/null
+++ b/utils/lru/lfu-simulation.c
@@ -0,0 +1,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;
+}
+
diff --git a/utils/lru/test-lru.rb b/utils/lru/test-lru.rb
new file mode 100644
index 0000000..d511e20
--- /dev/null
+++ b/utils/lru/test-lru.rb
@@ -0,0 +1,223 @@
+require 'rubygems'
+require 'redis'
+
+$runs = []; # Remember the error rate of each run for average purposes.
+$o = {}; # Options set parsing arguments
+
+def testit(filename)
+ r = Redis.new
+ r.config("SET","maxmemory","2000000")
+ if $o[:ttl]
+ r.config("SET","maxmemory-policy","volatile-ttl")
+ else
+ r.config("SET","maxmemory-policy","allkeys-lru")
+ end
+ r.config("SET","maxmemory-samples",5)
+ r.config("RESETSTAT")
+ r.flushall
+
+ html = ""
+ html << <<EOF
+ <html>
+ <body>
+ <style>
+ .box {
+ width:5px;
+ height:5px;
+ float:left;
+ margin: 1px;
+ }
+
+ .old {
+ border: 1px black solid;
+ }
+
+ .new {
+ border: 1px green solid;
+ }
+
+ .otherdb {
+ border: 1px red solid;
+ }
+
+ .ex {
+ background-color: #666;
+ }
+ </style>
+ <pre>
+EOF
+
+ # Fill the DB up to the first eviction.
+ oldsize = r.dbsize
+ id = 0
+ while true
+ id += 1
+ begin
+ r.set(id,"foo")
+ rescue
+ break
+ end
+ newsize = r.dbsize
+ break if newsize == oldsize # A key was evicted? Stop.
+ oldsize = newsize
+ end
+
+ inserted = r.dbsize
+ first_set_max_id = id
+ html << "#{r.dbsize} keys inserted.\n"
+
+ # Access keys sequentially, so that in theory the first part will be expired
+ # and the latter part will not, according to perfect LRU.
+
+ if $o[:ttl]
+ STDERR.puts "Set increasing expire value"
+ (1..first_set_max_id).each{|id|
+ r.expire(id,1000+id)
+ STDERR.print(".") if (id % 150) == 0
+ }
+ else
+ STDERR.puts "Access keys sequentially"
+ (1..first_set_max_id).each{|id|
+ r.get(id)
+ sleep 0.001
+ STDERR.print(".") if (id % 150) == 0
+ }
+ end
+ STDERR.puts
+
+ # Insert more 50% keys. We expect that the new keys will rarely be expired
+ # since their last access time is recent compared to the others.
+ #
+ # Note that we insert the first 100 keys of the new set into DB1 instead
+ # of DB0, so that we can try how cross-DB eviction works.
+ half = inserted/2
+ html << "Insert enough keys to evict half the keys we inserted.\n"
+ add = 0
+
+ otherdb_start_idx = id+1
+ otherdb_end_idx = id+100
+ while true
+ add += 1
+ id += 1
+ if id >= otherdb_start_idx && id <= otherdb_end_idx
+ r.select(1)
+ r.set(id,"foo")
+ r.select(0)
+ else
+ r.set(id,"foo")
+ end
+ break if r.info['evicted_keys'].to_i >= half
+ end
+
+ html << "#{add} additional keys added.\n"
+ html << "#{r.dbsize} keys in DB.\n"
+
+ # Check if evicted keys respect LRU
+ # We consider errors from 1 to N progressively more serious as they violate
+ # more the access pattern.
+
+ errors = 0
+ e = 1
+ error_per_key = 100000.0/first_set_max_id
+ half_set_size = first_set_max_id/2
+ maxerr = 0
+ (1..(first_set_max_id/2)).each{|id|
+ if id >= otherdb_start_idx && id <= otherdb_end_idx
+ r.select(1)
+ exists = r.exists(id)
+ r.select(0)
+ else
+ exists = r.exists(id)
+ end
+ if id < first_set_max_id/2
+ thiserr = error_per_key * ((half_set_size-id).to_f/half_set_size)
+ maxerr += thiserr
+ errors += thiserr if exists
+ elsif id >= first_set_max_id/2
+ thiserr = error_per_key * ((id-half_set_size).to_f/half_set_size)
+ maxerr += thiserr
+ errors += thiserr if !exists
+ end
+ }
+ errors = errors*100/maxerr
+
+ STDERR.puts "Test finished with #{errors}% error! Generating HTML on stdout."
+
+ html << "#{errors}% error!\n"
+ html << "</pre>"
+ $runs << errors
+
+ # Generate the graphical representation
+ (1..id).each{|id|
+ # Mark first set and added items in a different way.
+ c = "box"
+ if id >= otherdb_start_idx && id <= otherdb_end_idx
+ c << " otherdb"
+ elsif id <= first_set_max_id
+ c << " old"
+ else
+ c << " new"
+ end
+
+ # Add class if exists
+ if id >= otherdb_start_idx && id <= otherdb_end_idx
+ r.select(1)
+ exists = r.exists(id)
+ r.select(0)
+ else
+ exists = r.exists(id)
+ end
+
+ c << " ex" if exists
+ html << "<div title=\"#{id}\" class=\"#{c}\"></div>"
+ }
+
+ # Close HTML page
+
+ html << <<EOF
+ </body>
+ </html>
+EOF
+
+ f = File.open(filename,"w")
+ f.write(html)
+ f.close
+end
+
+def print_avg
+ avg = ($runs.reduce {|a,b| a+b}) / $runs.length
+ puts "#{$runs.length} runs, AVG is #{avg}"
+end
+
+if ARGV.length < 1
+ STDERR.puts "Usage: ruby test-lru.rb <html-output-filename> [--runs <count>] [--ttl]"
+ STDERR.puts "Options:"
+ STDERR.puts " --runs <count> Execute the test <count> times."
+ STDERR.puts " --ttl Set keys with increasing TTL values"
+ STDERR.puts " (starting from 1000 seconds) in order to"
+ STDERR.puts " test the volatile-lru policy."
+ exit 1
+end
+
+filename = ARGV[0]
+$o[:numruns] = 1
+
+# Options parsing
+i = 1
+while i < ARGV.length
+ if ARGV[i] == '--runs'
+ $o[:numruns] = ARGV[i+1].to_i
+ i+= 1
+ elsif ARGV[i] == '--ttl'
+ $o[:ttl] = true
+ else
+ STDERR.puts "Unknown option #{ARGV[i]}"
+ exit 1
+ end
+ i+= 1
+end
+
+$o[:numruns].times {
+ testit(filename)
+ print_avg if $o[:numruns] != 1
+}