1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5
6 #ifndef GFLAGS
7 #include <cstdio>
main()8 int main() {
9 fprintf(stderr, "Please install gflags to run this test... Skipping...\n");
10 return 0;
11 }
12 #else
13
14 #include <algorithm>
15 #include <atomic>
16 #include <cinttypes>
17 #include <functional>
18 #include <memory>
19 #include <thread>
20 #include <vector>
21
22 #include "dynamic_bloom.h"
23 #include "logging/logging.h"
24 #include "memory/arena.h"
25 #include "port/port.h"
26 #include "test_util/testharness.h"
27 #include "test_util/testutil.h"
28 #include "util/gflags_compat.h"
29 #include "util/stop_watch.h"
30
31 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
32
33 DEFINE_int32(bits_per_key, 10, "");
34 DEFINE_int32(num_probes, 6, "");
35 DEFINE_bool(enable_perf, false, "");
36
37 namespace ROCKSDB_NAMESPACE {
38
39 struct KeyMaker {
40 uint64_t a;
41 uint64_t b;
42
43 // Sequential, within a hash function block
SeqROCKSDB_NAMESPACE::KeyMaker44 inline Slice Seq(uint64_t i) {
45 a = i;
46 return Slice(reinterpret_cast<char *>(&a), sizeof(a));
47 }
48 // Not quite sequential, varies across hash function blocks
NonseqROCKSDB_NAMESPACE::KeyMaker49 inline Slice Nonseq(uint64_t i) {
50 a = i;
51 b = i * 123;
52 return Slice(reinterpret_cast<char *>(this), sizeof(*this));
53 }
KeyROCKSDB_NAMESPACE::KeyMaker54 inline Slice Key(uint64_t i, bool nonseq) {
55 return nonseq ? Nonseq(i) : Seq(i);
56 }
57 };
58
59 class DynamicBloomTest : public testing::Test {};
60
TEST_F(DynamicBloomTest,EmptyFilter)61 TEST_F(DynamicBloomTest, EmptyFilter) {
62 Arena arena;
63 DynamicBloom bloom1(&arena, 100, 2);
64 ASSERT_TRUE(!bloom1.MayContain("hello"));
65 ASSERT_TRUE(!bloom1.MayContain("world"));
66
67 DynamicBloom bloom2(&arena, CACHE_LINE_SIZE * 8 * 2 - 1, 2);
68 ASSERT_TRUE(!bloom2.MayContain("hello"));
69 ASSERT_TRUE(!bloom2.MayContain("world"));
70 }
71
TEST_F(DynamicBloomTest,Small)72 TEST_F(DynamicBloomTest, Small) {
73 Arena arena;
74 DynamicBloom bloom1(&arena, 100, 2);
75 bloom1.Add("hello");
76 bloom1.Add("world");
77 ASSERT_TRUE(bloom1.MayContain("hello"));
78 ASSERT_TRUE(bloom1.MayContain("world"));
79 ASSERT_TRUE(!bloom1.MayContain("x"));
80 ASSERT_TRUE(!bloom1.MayContain("foo"));
81
82 DynamicBloom bloom2(&arena, CACHE_LINE_SIZE * 8 * 2 - 1, 2);
83 bloom2.Add("hello");
84 bloom2.Add("world");
85 ASSERT_TRUE(bloom2.MayContain("hello"));
86 ASSERT_TRUE(bloom2.MayContain("world"));
87 ASSERT_TRUE(!bloom2.MayContain("x"));
88 ASSERT_TRUE(!bloom2.MayContain("foo"));
89 }
90
TEST_F(DynamicBloomTest,SmallConcurrentAdd)91 TEST_F(DynamicBloomTest, SmallConcurrentAdd) {
92 Arena arena;
93 DynamicBloom bloom1(&arena, 100, 2);
94 bloom1.AddConcurrently("hello");
95 bloom1.AddConcurrently("world");
96 ASSERT_TRUE(bloom1.MayContain("hello"));
97 ASSERT_TRUE(bloom1.MayContain("world"));
98 ASSERT_TRUE(!bloom1.MayContain("x"));
99 ASSERT_TRUE(!bloom1.MayContain("foo"));
100
101 DynamicBloom bloom2(&arena, CACHE_LINE_SIZE * 8 * 2 - 1, 2);
102 bloom2.AddConcurrently("hello");
103 bloom2.AddConcurrently("world");
104 ASSERT_TRUE(bloom2.MayContain("hello"));
105 ASSERT_TRUE(bloom2.MayContain("world"));
106 ASSERT_TRUE(!bloom2.MayContain("x"));
107 ASSERT_TRUE(!bloom2.MayContain("foo"));
108 }
109
NextNum(uint32_t num)110 static uint32_t NextNum(uint32_t num) {
111 if (num < 10) {
112 num += 1;
113 } else if (num < 100) {
114 num += 10;
115 } else if (num < 1000) {
116 num += 100;
117 } else {
118 num = num * 26 / 10;
119 }
120 return num;
121 }
122
TEST_F(DynamicBloomTest,VaryingLengths)123 TEST_F(DynamicBloomTest, VaryingLengths) {
124 KeyMaker km;
125
126 // Count number of filters that significantly exceed the false positive rate
127 int mediocre_filters = 0;
128 int good_filters = 0;
129 uint32_t num_probes = static_cast<uint32_t>(FLAGS_num_probes);
130
131 fprintf(stderr, "bits_per_key: %d num_probes: %d\n", FLAGS_bits_per_key,
132 num_probes);
133
134 // NB: FP rate impact of 32-bit hash is noticeable starting around 10M keys.
135 // But that effect is hidden if using sequential keys (unique hashes).
136 for (bool nonseq : {false, true}) {
137 const uint32_t max_num = FLAGS_enable_perf ? 40000000 : 400000;
138 for (uint32_t num = 1; num <= max_num; num = NextNum(num)) {
139 uint32_t bloom_bits = 0;
140 Arena arena;
141 bloom_bits = num * FLAGS_bits_per_key;
142 DynamicBloom bloom(&arena, bloom_bits, num_probes);
143 for (uint64_t i = 0; i < num; i++) {
144 bloom.Add(km.Key(i, nonseq));
145 ASSERT_TRUE(bloom.MayContain(km.Key(i, nonseq)));
146 }
147
148 // All added keys must match
149 for (uint64_t i = 0; i < num; i++) {
150 ASSERT_TRUE(bloom.MayContain(km.Key(i, nonseq)));
151 }
152
153 // Check false positive rate
154 int result = 0;
155 for (uint64_t i = 0; i < 30000; i++) {
156 if (bloom.MayContain(km.Key(i + 1000000000, nonseq))) {
157 result++;
158 }
159 }
160 double rate = result / 30000.0;
161
162 fprintf(stderr,
163 "False positives (%s keys): "
164 "%5.2f%% @ num = %6u, bloom_bits = %6u\n",
165 nonseq ? "nonseq" : "seq", rate * 100.0, num, bloom_bits);
166
167 if (rate > 0.0125)
168 mediocre_filters++; // Allowed, but not too often
169 else
170 good_filters++;
171 }
172 }
173
174 fprintf(stderr, "Filters: %d good, %d mediocre\n", good_filters,
175 mediocre_filters);
176 ASSERT_LE(mediocre_filters, good_filters / 25);
177 }
178
TEST_F(DynamicBloomTest,perf)179 TEST_F(DynamicBloomTest, perf) {
180 KeyMaker km;
181 StopWatchNano timer(Env::Default());
182 uint32_t num_probes = static_cast<uint32_t>(FLAGS_num_probes);
183
184 if (!FLAGS_enable_perf) {
185 return;
186 }
187
188 for (uint32_t m = 1; m <= 8; ++m) {
189 Arena arena;
190 const uint32_t num_keys = m * 8 * 1024 * 1024;
191 fprintf(stderr, "testing %" PRIu32 "M keys\n", m * 8);
192
193 DynamicBloom std_bloom(&arena, num_keys * 10, num_probes);
194
195 timer.Start();
196 for (uint64_t i = 1; i <= num_keys; ++i) {
197 std_bloom.Add(km.Seq(i));
198 }
199
200 uint64_t elapsed = timer.ElapsedNanos();
201 fprintf(stderr, "dynamic bloom, avg add latency %3g\n",
202 static_cast<double>(elapsed) / num_keys);
203
204 uint32_t count = 0;
205 timer.Start();
206 for (uint64_t i = 1; i <= num_keys; ++i) {
207 if (std_bloom.MayContain(km.Seq(i))) {
208 ++count;
209 }
210 }
211 ASSERT_EQ(count, num_keys);
212 elapsed = timer.ElapsedNanos();
213 assert(count > 0);
214 fprintf(stderr, "dynamic bloom, avg query latency %3g\n",
215 static_cast<double>(elapsed) / count);
216 }
217 }
218
TEST_F(DynamicBloomTest,concurrent_with_perf)219 TEST_F(DynamicBloomTest, concurrent_with_perf) {
220 uint32_t num_probes = static_cast<uint32_t>(FLAGS_num_probes);
221
222 uint32_t m_limit = FLAGS_enable_perf ? 8 : 1;
223
224 uint32_t num_threads = 4;
225 std::vector<port::Thread> threads;
226
227 // NB: Uses sequential keys for speed, but that hides the FP rate
228 // impact of 32-bit hash, which is noticeable starting around 10M keys
229 // when they vary across hashing blocks.
230 for (uint32_t m = 1; m <= m_limit; ++m) {
231 Arena arena;
232 const uint32_t num_keys = m * 8 * 1024 * 1024;
233 fprintf(stderr, "testing %" PRIu32 "M keys\n", m * 8);
234
235 DynamicBloom std_bloom(&arena, num_keys * 10, num_probes);
236
237 std::atomic<uint64_t> elapsed(0);
238
239 std::function<void(size_t)> adder([&](size_t t) {
240 KeyMaker km;
241 StopWatchNano timer(Env::Default());
242 timer.Start();
243 for (uint64_t i = 1 + t; i <= num_keys; i += num_threads) {
244 std_bloom.AddConcurrently(km.Seq(i));
245 }
246 elapsed += timer.ElapsedNanos();
247 });
248 for (size_t t = 0; t < num_threads; ++t) {
249 threads.emplace_back(adder, t);
250 }
251 while (threads.size() > 0) {
252 threads.back().join();
253 threads.pop_back();
254 }
255
256 fprintf(stderr,
257 "dynamic bloom, avg parallel add latency %3g"
258 " nanos/key\n",
259 static_cast<double>(elapsed) / num_threads / num_keys);
260
261 elapsed = 0;
262 std::function<void(size_t)> hitter([&](size_t t) {
263 KeyMaker km;
264 StopWatchNano timer(Env::Default());
265 timer.Start();
266 for (uint64_t i = 1 + t; i <= num_keys; i += num_threads) {
267 bool f = std_bloom.MayContain(km.Seq(i));
268 ASSERT_TRUE(f);
269 }
270 elapsed += timer.ElapsedNanos();
271 });
272 for (size_t t = 0; t < num_threads; ++t) {
273 threads.emplace_back(hitter, t);
274 }
275 while (threads.size() > 0) {
276 threads.back().join();
277 threads.pop_back();
278 }
279
280 fprintf(stderr,
281 "dynamic bloom, avg parallel hit latency %3g"
282 " nanos/key\n",
283 static_cast<double>(elapsed) / num_threads / num_keys);
284
285 elapsed = 0;
286 std::atomic<uint32_t> false_positives(0);
287 std::function<void(size_t)> misser([&](size_t t) {
288 KeyMaker km;
289 StopWatchNano timer(Env::Default());
290 timer.Start();
291 for (uint64_t i = num_keys + 1 + t; i <= 2 * num_keys; i += num_threads) {
292 bool f = std_bloom.MayContain(km.Seq(i));
293 if (f) {
294 ++false_positives;
295 }
296 }
297 elapsed += timer.ElapsedNanos();
298 });
299 for (size_t t = 0; t < num_threads; ++t) {
300 threads.emplace_back(misser, t);
301 }
302 while (threads.size() > 0) {
303 threads.back().join();
304 threads.pop_back();
305 }
306
307 fprintf(stderr,
308 "dynamic bloom, avg parallel miss latency %3g"
309 " nanos/key, %f%% false positive rate\n",
310 static_cast<double>(elapsed) / num_threads / num_keys,
311 false_positives.load() * 100.0 / num_keys);
312 }
313 }
314
315 } // namespace ROCKSDB_NAMESPACE
316
main(int argc,char ** argv)317 int main(int argc, char** argv) {
318 ::testing::InitGoogleTest(&argc, argv);
319 ParseCommandLineFlags(&argc, &argv, true);
320
321 return RUN_ALL_TESTS();
322 }
323
324 #endif // GFLAGS
325