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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
start_server {tags {"hll"}} {
test {HyperLogLog self test passes} {
catch {r pfselftest} e
set e
} {OK}
test {PFADD without arguments creates an HLL value} {
r pfadd hll
r exists hll
} {1}
test {Approximated cardinality after creation is zero} {
r pfcount hll
} {0}
test {PFADD returns 1 when at least 1 reg was modified} {
r pfadd hll a b c
} {1}
test {PFADD returns 0 when no reg was modified} {
r pfadd hll a b c
} {0}
test {PFADD works with empty string (regression)} {
r pfadd hll ""
}
# Note that the self test stresses much better the
# cardinality estimation error. We are testing just the
# command implementation itself here.
test {PFCOUNT returns approximated cardinality of set} {
r del hll
set res {}
r pfadd hll 1 2 3 4 5
lappend res [r pfcount hll]
# Call it again to test cached value invalidation.
r pfadd hll 6 7 8 8 9 10
lappend res [r pfcount hll]
set res
} {5 10}
test {HyperLogLogs are promote from sparse to dense} {
r del hll
r config set hll-sparse-max-bytes 3000
set n 0
while {$n < 100000} {
set elements {}
for {set j 0} {$j < 100} {incr j} {lappend elements [expr rand()]}
incr n 100
r pfadd hll {*}$elements
set card [r pfcount hll]
set err [expr {abs($card-$n)}]
assert {$err < (double($card)/100)*5}
if {$n < 1000} {
assert {[r pfdebug encoding hll] eq {sparse}}
} elseif {$n > 10000} {
assert {[r pfdebug encoding hll] eq {dense}}
}
}
}
test {HyperLogLog sparse encoding stress test} {
for {set x 0} {$x < 1000} {incr x} {
r del hll1 hll2
set numele [randomInt 100]
set elements {}
for {set j 0} {$j < $numele} {incr j} {
lappend elements [expr rand()]
}
# Force dense representation of hll2
r pfadd hll2
r pfdebug todense hll2
r pfadd hll1 {*}$elements
r pfadd hll2 {*}$elements
assert {[r pfdebug encoding hll1] eq {sparse}}
assert {[r pfdebug encoding hll2] eq {dense}}
# Cardinality estimated should match exactly.
assert {[r pfcount hll1] eq [r pfcount hll2]}
}
}
test {Corrupted sparse HyperLogLogs are detected: Additional at tail} {
r del hll
r pfadd hll a b c
r append hll "hello"
set e {}
catch {r pfcount hll} e
set e
} {*INVALIDOBJ*}
test {Corrupted sparse HyperLogLogs are detected: Broken magic} {
r del hll
r pfadd hll a b c
r setrange hll 0 "0123"
set e {}
catch {r pfcount hll} e
set e
} {*WRONGTYPE*}
test {Corrupted sparse HyperLogLogs are detected: Invalid encoding} {
r del hll
r pfadd hll a b c
r setrange hll 4 "x"
set e {}
catch {r pfcount hll} e
set e
} {*WRONGTYPE*}
test {Corrupted dense HyperLogLogs are detected: Wrong length} {
r del hll
r pfadd hll a b c
r setrange hll 4 "\x00"
set e {}
catch {r pfcount hll} e
set e
} {*WRONGTYPE*}
test {Fuzzing dense/sparse encoding: Redis should always detect errors} {
for {set j 0} {$j < 1000} {incr j} {
r del hll
set items {}
set numitems [randomInt 3000]
for {set i 0} {$i < $numitems} {incr i} {
lappend items [expr {rand()}]
}
r pfadd hll {*}$items
# Corrupt it in some random way.
for {set i 0} {$i < 5} {incr i} {
set len [r strlen hll]
set pos [randomInt $len]
set byte [randstring 1 1 binary]
r setrange hll $pos $byte
# Don't modify more bytes 50% of times
if {rand() < 0.5} break
}
# Use the hyperloglog to check if it crashes
# Redis in some way.
catch {
r pfcount hll
}
}
}
test {PFADD, PFCOUNT, PFMERGE type checking works} {
r set foo bar
catch {r pfadd foo 1} e
assert_match {*WRONGTYPE*} $e
catch {r pfcount foo} e
assert_match {*WRONGTYPE*} $e
catch {r pfmerge bar foo} e
assert_match {*WRONGTYPE*} $e
catch {r pfmerge foo bar} e
assert_match {*WRONGTYPE*} $e
}
test {PFMERGE results on the cardinality of union of sets} {
r del hll hll1 hll2 hll3
r pfadd hll1 a b c
r pfadd hll2 b c d
r pfadd hll3 c d e
r pfmerge hll hll1 hll2 hll3
r pfcount hll
} {5}
test {PFCOUNT multiple-keys merge returns cardinality of union #1} {
r del hll1 hll2 hll3
for {set x 1} {$x < 10000} {incr x} {
r pfadd hll1 "foo-$x"
r pfadd hll2 "bar-$x"
r pfadd hll3 "zap-$x"
set card [r pfcount hll1 hll2 hll3]
set realcard [expr {$x*3}]
set err [expr {abs($card-$realcard)}]
assert {$err < (double($card)/100)*5}
}
}
test {PFCOUNT multiple-keys merge returns cardinality of union #2} {
r del hll1 hll2 hll3
set elements {}
for {set x 1} {$x < 10000} {incr x} {
for {set j 1} {$j <= 3} {incr j} {
set rint [randomInt 20000]
r pfadd hll$j $rint
lappend elements $rint
}
}
set realcard [llength [lsort -unique $elements]]
set card [r pfcount hll1 hll2 hll3]
set err [expr {abs($card-$realcard)}]
assert {$err < (double($card)/100)*5}
}
test {PFDEBUG GETREG returns the HyperLogLog raw registers} {
r del hll
r pfadd hll 1 2 3
llength [r pfdebug getreg hll]
} {16384}
test {PFADD / PFCOUNT cache invalidation works} {
r del hll
r pfadd hll a b c
r pfcount hll
assert {[r getrange hll 15 15] eq "\x00"}
r pfadd hll a b c
assert {[r getrange hll 15 15] eq "\x00"}
r pfadd hll 1 2 3
assert {[r getrange hll 15 15] eq "\x80"}
}
}
|
