diff options
Diffstat (limited to 'utils/lru')
| -rw-r--r-- | utils/lru/README | 19 | ||||
| -rw-r--r-- | utils/lru/lfu-simulation.c | 158 | ||||
| -rw-r--r-- | utils/lru/test-lru.rb | 223 |
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 +} |