File manager - Edit - /home/newsbmcs.com/public_html/static/img/logo/lru.zip
Back
PK ��Z��� READMEnu �[��� 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 PK ��ZŇI � � test-lru.rbnu �[��� 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 } PK ��Z�� � � lfu-simulation.cnu �[��� #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 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 = 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. */ 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(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; } PK ��Z��� READMEnu �[��� PK ��ZŇI � � 9 test-lru.rbnu �[��� PK ��Z�� � � lfu-simulation.cnu �[��� PK � .
| ver. 1.4 |
Github
|
.
| PHP 8.2.28 | Generation time: 0.02 |
proxy
|
phpinfo
|
Settings