summaryrefslogtreecommitdiff
path: root/utils/lru/test-lru.rb
blob: dadc6d5057ac72ce40c41bd2a572e676b1417c9d (plain)
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
}