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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
require 'rubygems'
require 'redis'
$runs = []; # Remember the error rate of each run for average purposes.
def testit(filename)
r = Redis.new
r.config("SET","maxmemory","2000000")
r.config("SET","maxmemory-policy","allkeys-lru")
r.config("SET","maxmemory-samples",10)
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
r.set(id,"foo")
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"
# Access keys sequentially, so that in theory the first part will be expired
# and the latter part will not, according to perfect LRU.
STDERR.puts "Access keys sequentially"
(1..first_set_max_id).each{|id|
r.get(id)
sleep 0.001
STDERR.print(".") if (id % 150) == 0
}
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"
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."
html << "#{r.dbsize} keys in DB"
# 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!"
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> [num-runs]"
exit 1
end
filename = ARGV[0]
numruns = 1
numruns = ARGV[1].to_i if ARGV.length == 2
numruns.times {
testit(filename)
print_avg if numruns != 1
}
|
