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 #if !defined(GFLAGS) || defined(ROCKSDB_LITE)
7 #include <cstdio>
main()8 int main() {
9 fprintf(stderr, "filter_bench requires gflags and !ROCKSDB_LITE\n");
10 return 1;
11 }
12 #else
13
14 #include <cinttypes>
15 #include <iostream>
16 #include <sstream>
17 #include <vector>
18
19 #include "memory/arena.h"
20 #include "port/port.h"
21 #include "port/stack_trace.h"
22 #include "rocksdb/system_clock.h"
23 #include "table/block_based/filter_policy_internal.h"
24 #include "table/block_based/full_filter_block.h"
25 #include "table/block_based/mock_block_based_table.h"
26 #include "table/plain/plain_table_bloom.h"
27 #include "util/cast_util.h"
28 #include "util/gflags_compat.h"
29 #include "util/hash.h"
30 #include "util/random.h"
31 #include "util/stderr_logger.h"
32 #include "util/stop_watch.h"
33
34 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
35 using GFLAGS_NAMESPACE::RegisterFlagValidator;
36 using GFLAGS_NAMESPACE::SetUsageMessage;
37
38 DEFINE_uint32(seed, 0, "Seed for random number generators");
39
40 DEFINE_double(working_mem_size_mb, 200,
41 "MB of memory to get up to among all filters, unless "
42 "m_keys_total_max is specified.");
43
44 DEFINE_uint32(average_keys_per_filter, 10000,
45 "Average number of keys per filter");
46
47 DEFINE_double(vary_key_count_ratio, 0.4,
48 "Vary number of keys by up to +/- vary_key_count_ratio * "
49 "average_keys_per_filter.");
50
51 DEFINE_uint32(key_size, 24, "Average number of bytes for each key");
52
53 DEFINE_bool(vary_key_alignment, true,
54 "Whether to vary key alignment (default: at least 32-bit "
55 "alignment)");
56
57 DEFINE_uint32(vary_key_size_log2_interval, 5,
58 "Use same key size 2^n times, then change. Key size varies from "
59 "-2 to +2 bytes vs. average, unless n>=30 to fix key size.");
60
61 DEFINE_uint32(batch_size, 8, "Number of keys to group in each batch");
62
63 DEFINE_double(bits_per_key, 10.0, "Bits per key setting for filters");
64
65 DEFINE_double(m_queries, 200, "Millions of queries for each test mode");
66
67 DEFINE_double(m_keys_total_max, 0,
68 "Maximum total keys added to filters, in millions. "
69 "0 (default) disables. Non-zero overrides working_mem_size_mb "
70 "option.");
71
72 DEFINE_bool(use_full_block_reader, false,
73 "Use FullFilterBlockReader interface rather than FilterBitsReader");
74
75 DEFINE_bool(use_plain_table_bloom, false,
76 "Use PlainTableBloom structure and interface rather than "
77 "FilterBitsReader/FullFilterBlockReader");
78
79 DEFINE_bool(new_builder, false,
80 "Whether to create a new builder for each new filter");
81
82 DEFINE_uint32(impl, 0,
83 "Select filter implementation. Without -use_plain_table_bloom:"
84 "0 = legacy full Bloom filter, 1 = block-based Bloom filter, "
85 "2 = format_version 5 Bloom filter, 3 = Ribbon128 filter. With "
86 "-use_plain_table_bloom: 0 = no locality, 1 = locality.");
87
88 DEFINE_bool(net_includes_hashing, false,
89 "Whether query net ns/op times should include hashing. "
90 "(if not, dry run will include hashing) "
91 "(build times always include hashing)");
92
93 DEFINE_bool(optimize_filters_for_memory, false,
94 "Setting for BlockBasedTableOptions::optimize_filters_for_memory");
95
96 DEFINE_bool(quick, false, "Run more limited set of tests, fewer queries");
97
98 DEFINE_bool(best_case, false, "Run limited tests only for best-case");
99
100 DEFINE_bool(allow_bad_fp_rate, false, "Continue even if FP rate is bad");
101
102 DEFINE_bool(legend, false,
103 "Print more information about interpreting results instead of "
104 "running tests");
105
106 DEFINE_uint32(runs, 1, "Number of times to rebuild and run benchmark tests");
107
_always_assert_fail(int line,const char * file,const char * expr)108 void _always_assert_fail(int line, const char *file, const char *expr) {
109 fprintf(stderr, "%s: %d: Assertion %s failed\n", file, line, expr);
110 abort();
111 }
112
113 #define ALWAYS_ASSERT(cond) \
114 ((cond) ? (void)0 : ::_always_assert_fail(__LINE__, __FILE__, #cond))
115
116 #ifndef NDEBUG
117 // This could affect build times enough that we should not include it for
118 // accurate speed tests
119 #define PREDICT_FP_RATE
120 #endif
121
122 using ROCKSDB_NAMESPACE::Arena;
123 using ROCKSDB_NAMESPACE::BlockContents;
124 using ROCKSDB_NAMESPACE::BloomFilterPolicy;
125 using ROCKSDB_NAMESPACE::BloomHash;
126 using ROCKSDB_NAMESPACE::BuiltinFilterBitsBuilder;
127 using ROCKSDB_NAMESPACE::CachableEntry;
128 using ROCKSDB_NAMESPACE::EncodeFixed32;
129 using ROCKSDB_NAMESPACE::FastRange32;
130 using ROCKSDB_NAMESPACE::FilterBitsReader;
131 using ROCKSDB_NAMESPACE::FilterBuildingContext;
132 using ROCKSDB_NAMESPACE::FullFilterBlockReader;
133 using ROCKSDB_NAMESPACE::GetSliceHash;
134 using ROCKSDB_NAMESPACE::GetSliceHash64;
135 using ROCKSDB_NAMESPACE::Lower32of64;
136 using ROCKSDB_NAMESPACE::ParsedFullFilterBlock;
137 using ROCKSDB_NAMESPACE::PlainTableBloomV1;
138 using ROCKSDB_NAMESPACE::Random32;
139 using ROCKSDB_NAMESPACE::Slice;
140 using ROCKSDB_NAMESPACE::static_cast_with_check;
141 using ROCKSDB_NAMESPACE::StderrLogger;
142 using ROCKSDB_NAMESPACE::mock::MockBlockBasedTableTester;
143
144 struct KeyMaker {
KeyMakerKeyMaker145 KeyMaker(size_t avg_size)
146 : smallest_size_(avg_size -
147 (FLAGS_vary_key_size_log2_interval >= 30 ? 2 : 0)),
148 buf_size_(avg_size + 11), // pad to vary key size and alignment
149 buf_(new char[buf_size_]) {
150 memset(buf_.get(), 0, buf_size_);
151 assert(smallest_size_ > 8);
152 }
153 size_t smallest_size_;
154 size_t buf_size_;
155 std::unique_ptr<char[]> buf_;
156
157 // Returns a unique(-ish) key based on the given parameter values. Each
158 // call returns a Slice from the same buffer so previously returned
159 // Slices should be considered invalidated.
GetKeyMaker160 Slice Get(uint32_t filter_num, uint32_t val_num) {
161 size_t start = FLAGS_vary_key_alignment ? val_num % 4 : 0;
162 size_t len = smallest_size_;
163 if (FLAGS_vary_key_size_log2_interval < 30) {
164 // To get range [avg_size - 2, avg_size + 2]
165 // use range [smallest_size, smallest_size + 4]
166 len += FastRange32(
167 (val_num >> FLAGS_vary_key_size_log2_interval) * 1234567891, 5);
168 }
169 char * data = buf_.get() + start;
170 // Populate key data such that all data makes it into a key of at
171 // least 8 bytes. We also don't want all the within-filter key
172 // variance confined to a contiguous 32 bits, because then a 32 bit
173 // hash function can "cheat" the false positive rate by
174 // approximating a perfect hash.
175 EncodeFixed32(data, val_num);
176 EncodeFixed32(data + 4, filter_num + val_num);
177 // ensure clearing leftovers from different alignment
178 EncodeFixed32(data + 8, 0);
179 return Slice(data, len);
180 }
181 };
182
PrintWarnings()183 void PrintWarnings() {
184 #if defined(__GNUC__) && !defined(__OPTIMIZE__)
185 fprintf(stdout,
186 "WARNING: Optimization is disabled: benchmarks unnecessarily slow\n");
187 #endif
188 #ifndef NDEBUG
189 fprintf(stdout,
190 "WARNING: Assertions are enabled; benchmarks unnecessarily slow\n");
191 #endif
192 }
193
194 struct FilterInfo {
195 uint32_t filter_id_ = 0;
196 std::unique_ptr<const char[]> owner_;
197 Slice filter_;
198 uint32_t keys_added_ = 0;
199 std::unique_ptr<FilterBitsReader> reader_;
200 std::unique_ptr<FullFilterBlockReader> full_block_reader_;
201 std::unique_ptr<PlainTableBloomV1> plain_table_bloom_;
202 uint64_t outside_queries_ = 0;
203 uint64_t false_positives_ = 0;
204 };
205
206 enum TestMode {
207 kSingleFilter,
208 kBatchPrepared,
209 kBatchUnprepared,
210 kFiftyOneFilter,
211 kEightyTwentyFilter,
212 kRandomFilter,
213 };
214
215 static const std::vector<TestMode> allTestModes = {
216 kSingleFilter, kBatchPrepared, kBatchUnprepared,
217 kFiftyOneFilter, kEightyTwentyFilter, kRandomFilter,
218 };
219
220 static const std::vector<TestMode> quickTestModes = {
221 kSingleFilter,
222 kRandomFilter,
223 };
224
225 static const std::vector<TestMode> bestCaseTestModes = {
226 kSingleFilter,
227 };
228
TestModeToString(TestMode tm)229 const char *TestModeToString(TestMode tm) {
230 switch (tm) {
231 case kSingleFilter:
232 return "Single filter";
233 case kBatchPrepared:
234 return "Batched, prepared";
235 case kBatchUnprepared:
236 return "Batched, unprepared";
237 case kFiftyOneFilter:
238 return "Skewed 50% in 1%";
239 case kEightyTwentyFilter:
240 return "Skewed 80% in 20%";
241 case kRandomFilter:
242 return "Random filter";
243 }
244 return "Bad TestMode";
245 }
246
247 // Do just enough to keep some data dependence for the
248 // compiler / CPU
DryRunNoHash(Slice & s)249 static uint32_t DryRunNoHash(Slice &s) {
250 uint32_t sz = static_cast<uint32_t>(s.size());
251 if (sz >= 4) {
252 return sz + s.data()[3];
253 } else {
254 return sz;
255 }
256 }
257
DryRunHash32(Slice & s)258 static uint32_t DryRunHash32(Slice &s) {
259 // Same perf characteristics as GetSliceHash()
260 return BloomHash(s);
261 }
262
DryRunHash64(Slice & s)263 static uint32_t DryRunHash64(Slice &s) {
264 return Lower32of64(GetSliceHash64(s));
265 }
266
267 struct FilterBench : public MockBlockBasedTableTester {
268 std::vector<KeyMaker> kms_;
269 std::vector<FilterInfo> infos_;
270 Random32 random_;
271 std::ostringstream fp_rate_report_;
272 Arena arena_;
273 double m_queries_;
274 StderrLogger stderr_logger_;
275
FilterBenchFilterBench276 FilterBench()
277 : MockBlockBasedTableTester(new BloomFilterPolicy(
278 FLAGS_bits_per_key,
279 static_cast<BloomFilterPolicy::Mode>(FLAGS_impl))),
280 random_(FLAGS_seed),
281 m_queries_(0) {
282 for (uint32_t i = 0; i < FLAGS_batch_size; ++i) {
283 kms_.emplace_back(FLAGS_key_size < 8 ? 8 : FLAGS_key_size);
284 }
285 ioptions_.logger = &stderr_logger_;
286 table_options_.optimize_filters_for_memory =
287 FLAGS_optimize_filters_for_memory;
288 }
289
290 void Go();
291
292 double RandomQueryTest(uint32_t inside_threshold, bool dry_run,
293 TestMode mode);
294 };
295
Go()296 void FilterBench::Go() {
297 if (FLAGS_use_plain_table_bloom && FLAGS_use_full_block_reader) {
298 throw std::runtime_error(
299 "Can't combine -use_plain_table_bloom and -use_full_block_reader");
300 }
301 if (FLAGS_use_plain_table_bloom) {
302 if (FLAGS_impl > 1) {
303 throw std::runtime_error(
304 "-impl must currently be >= 0 and <= 1 for Plain table");
305 }
306 } else {
307 if (FLAGS_impl == 1) {
308 throw std::runtime_error(
309 "Block-based filter not currently supported by filter_bench");
310 }
311 if (FLAGS_impl > 3) {
312 throw std::runtime_error(
313 "-impl must currently be 0, 2, or 3 for Block-based table");
314 }
315 }
316
317 if (FLAGS_vary_key_count_ratio < 0.0 || FLAGS_vary_key_count_ratio > 1.0) {
318 throw std::runtime_error("-vary_key_count_ratio must be >= 0.0 and <= 1.0");
319 }
320
321 // For example, average_keys_per_filter = 100, vary_key_count_ratio = 0.1.
322 // Varys up to +/- 10 keys. variance_range = 21 (generating value 0..20).
323 // variance_offset = 10, so value - offset average value is always 0.
324 const uint32_t variance_range =
325 1 + 2 * static_cast<uint32_t>(FLAGS_vary_key_count_ratio *
326 FLAGS_average_keys_per_filter);
327 const uint32_t variance_offset = variance_range / 2;
328
329 const std::vector<TestMode> &testModes =
330 FLAGS_best_case ? bestCaseTestModes
331 : FLAGS_quick ? quickTestModes : allTestModes;
332
333 m_queries_ = FLAGS_m_queries;
334 double working_mem_size_mb = FLAGS_working_mem_size_mb;
335 if (FLAGS_quick) {
336 m_queries_ /= 7.0;
337 } else if (FLAGS_best_case) {
338 m_queries_ /= 3.0;
339 working_mem_size_mb /= 10.0;
340 }
341
342 std::cout << "Building..." << std::endl;
343
344 std::unique_ptr<BuiltinFilterBitsBuilder> builder;
345
346 size_t total_memory_used = 0;
347 size_t total_size = 0;
348 size_t total_keys_added = 0;
349 #ifdef PREDICT_FP_RATE
350 double weighted_predicted_fp_rate = 0.0;
351 #endif
352 size_t max_total_keys;
353 size_t max_mem;
354 if (FLAGS_m_keys_total_max > 0) {
355 max_total_keys = static_cast<size_t>(1000000 * FLAGS_m_keys_total_max);
356 max_mem = SIZE_MAX;
357 } else {
358 max_total_keys = SIZE_MAX;
359 max_mem = static_cast<size_t>(1024 * 1024 * working_mem_size_mb);
360 }
361
362 ROCKSDB_NAMESPACE::StopWatchNano timer(
363 ROCKSDB_NAMESPACE::SystemClock::Default().get(), true);
364
365 infos_.clear();
366 while ((working_mem_size_mb == 0 || total_size < max_mem) &&
367 total_keys_added < max_total_keys) {
368 uint32_t filter_id = random_.Next();
369 uint32_t keys_to_add = FLAGS_average_keys_per_filter +
370 FastRange32(random_.Next(), variance_range) -
371 variance_offset;
372 if (max_total_keys - total_keys_added < keys_to_add) {
373 keys_to_add = static_cast<uint32_t>(max_total_keys - total_keys_added);
374 }
375 infos_.emplace_back();
376 FilterInfo &info = infos_.back();
377 info.filter_id_ = filter_id;
378 info.keys_added_ = keys_to_add;
379 if (FLAGS_use_plain_table_bloom) {
380 info.plain_table_bloom_.reset(new PlainTableBloomV1());
381 info.plain_table_bloom_->SetTotalBits(
382 &arena_, static_cast<uint32_t>(keys_to_add * FLAGS_bits_per_key),
383 FLAGS_impl, 0 /*huge_page*/, nullptr /*logger*/);
384 for (uint32_t i = 0; i < keys_to_add; ++i) {
385 uint32_t hash = GetSliceHash(kms_[0].Get(filter_id, i));
386 info.plain_table_bloom_->AddHash(hash);
387 }
388 info.filter_ = info.plain_table_bloom_->GetRawData();
389 } else {
390 if (!builder) {
391 builder.reset(
392 static_cast_with_check<BuiltinFilterBitsBuilder>(GetBuilder()));
393 }
394 for (uint32_t i = 0; i < keys_to_add; ++i) {
395 builder->AddKey(kms_[0].Get(filter_id, i));
396 }
397 info.filter_ = builder->Finish(&info.owner_);
398 #ifdef PREDICT_FP_RATE
399 weighted_predicted_fp_rate +=
400 keys_to_add *
401 builder->EstimatedFpRate(keys_to_add, info.filter_.size());
402 #endif
403 if (FLAGS_new_builder) {
404 builder.reset();
405 }
406 info.reader_.reset(
407 table_options_.filter_policy->GetFilterBitsReader(info.filter_));
408 CachableEntry<ParsedFullFilterBlock> block(
409 new ParsedFullFilterBlock(table_options_.filter_policy.get(),
410 BlockContents(info.filter_)),
411 nullptr /* cache */, nullptr /* cache_handle */,
412 true /* own_value */);
413 info.full_block_reader_.reset(
414 new FullFilterBlockReader(table_.get(), std::move(block)));
415 }
416 total_size += info.filter_.size();
417 #ifdef ROCKSDB_MALLOC_USABLE_SIZE
418 total_memory_used +=
419 malloc_usable_size(const_cast<char *>(info.filter_.data()));
420 #endif // ROCKSDB_MALLOC_USABLE_SIZE
421 total_keys_added += keys_to_add;
422 }
423
424 uint64_t elapsed_nanos = timer.ElapsedNanos();
425 double ns = double(elapsed_nanos) / total_keys_added;
426 std::cout << "Build avg ns/key: " << ns << std::endl;
427 std::cout << "Number of filters: " << infos_.size() << std::endl;
428 std::cout << "Total size (MB): " << total_size / 1024.0 / 1024.0 << std::endl;
429 if (total_memory_used > 0) {
430 std::cout << "Reported total allocated memory (MB): "
431 << total_memory_used / 1024.0 / 1024.0 << std::endl;
432 std::cout << "Reported internal fragmentation: "
433 << (total_memory_used - total_size) * 100.0 / total_size << "%"
434 << std::endl;
435 }
436
437 double bpk = total_size * 8.0 / total_keys_added;
438 std::cout << "Bits/key stored: " << bpk << std::endl;
439 #ifdef PREDICT_FP_RATE
440 std::cout << "Predicted FP rate %: "
441 << 100.0 * (weighted_predicted_fp_rate / total_keys_added)
442 << std::endl;
443 #endif
444 if (!FLAGS_quick && !FLAGS_best_case) {
445 double tolerable_rate = std::pow(2.0, -(bpk - 1.0) / (1.4 + bpk / 50.0));
446 std::cout << "Best possible FP rate %: " << 100.0 * std::pow(2.0, -bpk)
447 << std::endl;
448 std::cout << "Tolerable FP rate %: " << 100.0 * tolerable_rate << std::endl;
449
450 std::cout << "----------------------------" << std::endl;
451 std::cout << "Verifying..." << std::endl;
452
453 uint32_t outside_q_per_f =
454 static_cast<uint32_t>(m_queries_ * 1000000 / infos_.size());
455 uint64_t fps = 0;
456 for (uint32_t i = 0; i < infos_.size(); ++i) {
457 FilterInfo &info = infos_[i];
458 for (uint32_t j = 0; j < info.keys_added_; ++j) {
459 if (FLAGS_use_plain_table_bloom) {
460 uint32_t hash = GetSliceHash(kms_[0].Get(info.filter_id_, j));
461 ALWAYS_ASSERT(info.plain_table_bloom_->MayContainHash(hash));
462 } else {
463 ALWAYS_ASSERT(
464 info.reader_->MayMatch(kms_[0].Get(info.filter_id_, j)));
465 }
466 }
467 for (uint32_t j = 0; j < outside_q_per_f; ++j) {
468 if (FLAGS_use_plain_table_bloom) {
469 uint32_t hash =
470 GetSliceHash(kms_[0].Get(info.filter_id_, j | 0x80000000));
471 fps += info.plain_table_bloom_->MayContainHash(hash);
472 } else {
473 fps += info.reader_->MayMatch(
474 kms_[0].Get(info.filter_id_, j | 0x80000000));
475 }
476 }
477 }
478 std::cout << " No FNs :)" << std::endl;
479 double prelim_rate = double(fps) / outside_q_per_f / infos_.size();
480 std::cout << " Prelim FP rate %: " << (100.0 * prelim_rate) << std::endl;
481
482 if (!FLAGS_allow_bad_fp_rate) {
483 ALWAYS_ASSERT(prelim_rate < tolerable_rate);
484 }
485 }
486
487 std::cout << "----------------------------" << std::endl;
488 std::cout << "Mixed inside/outside queries..." << std::endl;
489 // 50% each inside and outside
490 uint32_t inside_threshold = UINT32_MAX / 2;
491 for (TestMode tm : testModes) {
492 random_.Seed(FLAGS_seed + 1);
493 double f = RandomQueryTest(inside_threshold, /*dry_run*/ false, tm);
494 random_.Seed(FLAGS_seed + 1);
495 double d = RandomQueryTest(inside_threshold, /*dry_run*/ true, tm);
496 std::cout << " " << TestModeToString(tm) << " net ns/op: " << (f - d)
497 << std::endl;
498 }
499
500 if (!FLAGS_quick) {
501 std::cout << "----------------------------" << std::endl;
502 std::cout << "Inside queries (mostly)..." << std::endl;
503 // Do about 95% inside queries rather than 100% so that branch predictor
504 // can't give itself an artifically crazy advantage.
505 inside_threshold = UINT32_MAX / 20 * 19;
506 for (TestMode tm : testModes) {
507 random_.Seed(FLAGS_seed + 1);
508 double f = RandomQueryTest(inside_threshold, /*dry_run*/ false, tm);
509 random_.Seed(FLAGS_seed + 1);
510 double d = RandomQueryTest(inside_threshold, /*dry_run*/ true, tm);
511 std::cout << " " << TestModeToString(tm) << " net ns/op: " << (f - d)
512 << std::endl;
513 }
514
515 std::cout << "----------------------------" << std::endl;
516 std::cout << "Outside queries (mostly)..." << std::endl;
517 // Do about 95% outside queries rather than 100% so that branch predictor
518 // can't give itself an artifically crazy advantage.
519 inside_threshold = UINT32_MAX / 20;
520 for (TestMode tm : testModes) {
521 random_.Seed(FLAGS_seed + 2);
522 double f = RandomQueryTest(inside_threshold, /*dry_run*/ false, tm);
523 random_.Seed(FLAGS_seed + 2);
524 double d = RandomQueryTest(inside_threshold, /*dry_run*/ true, tm);
525 std::cout << " " << TestModeToString(tm) << " net ns/op: " << (f - d)
526 << std::endl;
527 }
528 }
529 std::cout << fp_rate_report_.str();
530
531 std::cout << "----------------------------" << std::endl;
532 std::cout << "Done. (For more info, run with -legend or -help.)" << std::endl;
533 }
534
RandomQueryTest(uint32_t inside_threshold,bool dry_run,TestMode mode)535 double FilterBench::RandomQueryTest(uint32_t inside_threshold, bool dry_run,
536 TestMode mode) {
537 for (auto &info : infos_) {
538 info.outside_queries_ = 0;
539 info.false_positives_ = 0;
540 }
541
542 auto dry_run_hash_fn = DryRunNoHash;
543 if (!FLAGS_net_includes_hashing) {
544 if (FLAGS_impl < 2 || FLAGS_use_plain_table_bloom) {
545 dry_run_hash_fn = DryRunHash32;
546 } else {
547 dry_run_hash_fn = DryRunHash64;
548 }
549 }
550
551 uint32_t num_infos = static_cast<uint32_t>(infos_.size());
552 uint32_t dry_run_hash = 0;
553 uint64_t max_queries = static_cast<uint64_t>(m_queries_ * 1000000 + 0.50);
554 // Some filters may be considered secondary in order to implement skewed
555 // queries. num_primary_filters is the number that are to be treated as
556 // equal, and any remainder will be treated as secondary.
557 uint32_t num_primary_filters = num_infos;
558 // The proportion (when divided by 2^32 - 1) of filter queries going to
559 // the primary filters (default = all). The remainder of queries are
560 // against secondary filters.
561 uint32_t primary_filter_threshold = 0xffffffff;
562 if (mode == kSingleFilter) {
563 // 100% of queries to 1 filter
564 num_primary_filters = 1;
565 } else if (mode == kFiftyOneFilter) {
566 if (num_infos < 50) {
567 return 0.0; // skip
568 }
569 // 50% of queries
570 primary_filter_threshold /= 2;
571 // to 1% of filters
572 num_primary_filters = (num_primary_filters + 99) / 100;
573 } else if (mode == kEightyTwentyFilter) {
574 if (num_infos < 5) {
575 return 0.0; // skip
576 }
577 // 80% of queries
578 primary_filter_threshold = primary_filter_threshold / 5 * 4;
579 // to 20% of filters
580 num_primary_filters = (num_primary_filters + 4) / 5;
581 } else if (mode == kRandomFilter) {
582 if (num_infos == 1) {
583 return 0.0; // skip
584 }
585 }
586 uint32_t batch_size = 1;
587 std::unique_ptr<Slice[]> batch_slices;
588 std::unique_ptr<Slice *[]> batch_slice_ptrs;
589 std::unique_ptr<bool[]> batch_results;
590 if (mode == kBatchPrepared || mode == kBatchUnprepared) {
591 batch_size = static_cast<uint32_t>(kms_.size());
592 }
593
594 batch_slices.reset(new Slice[batch_size]);
595 batch_slice_ptrs.reset(new Slice *[batch_size]);
596 batch_results.reset(new bool[batch_size]);
597 for (uint32_t i = 0; i < batch_size; ++i) {
598 batch_results[i] = false;
599 batch_slice_ptrs[i] = &batch_slices[i];
600 }
601
602 ROCKSDB_NAMESPACE::StopWatchNano timer(
603 ROCKSDB_NAMESPACE::SystemClock::Default().get(), true);
604
605 for (uint64_t q = 0; q < max_queries; q += batch_size) {
606 bool inside_this_time = random_.Next() <= inside_threshold;
607
608 uint32_t filter_index;
609 if (random_.Next() <= primary_filter_threshold) {
610 filter_index = random_.Uniformish(num_primary_filters);
611 } else {
612 // secondary
613 filter_index = num_primary_filters +
614 random_.Uniformish(num_infos - num_primary_filters);
615 }
616 FilterInfo &info = infos_[filter_index];
617 for (uint32_t i = 0; i < batch_size; ++i) {
618 if (inside_this_time) {
619 batch_slices[i] =
620 kms_[i].Get(info.filter_id_, random_.Uniformish(info.keys_added_));
621 } else {
622 batch_slices[i] =
623 kms_[i].Get(info.filter_id_, random_.Uniformish(info.keys_added_) |
624 uint32_t{0x80000000});
625 info.outside_queries_++;
626 }
627 }
628 // TODO: implement batched interface to full block reader
629 // TODO: implement batched interface to plain table bloom
630 if (mode == kBatchPrepared && !FLAGS_use_full_block_reader &&
631 !FLAGS_use_plain_table_bloom) {
632 for (uint32_t i = 0; i < batch_size; ++i) {
633 batch_results[i] = false;
634 }
635 if (dry_run) {
636 for (uint32_t i = 0; i < batch_size; ++i) {
637 batch_results[i] = true;
638 dry_run_hash += dry_run_hash_fn(batch_slices[i]);
639 }
640 } else {
641 info.reader_->MayMatch(batch_size, batch_slice_ptrs.get(),
642 batch_results.get());
643 }
644 for (uint32_t i = 0; i < batch_size; ++i) {
645 if (inside_this_time) {
646 ALWAYS_ASSERT(batch_results[i]);
647 } else {
648 info.false_positives_ += batch_results[i];
649 }
650 }
651 } else {
652 for (uint32_t i = 0; i < batch_size; ++i) {
653 bool may_match;
654 if (FLAGS_use_plain_table_bloom) {
655 if (dry_run) {
656 dry_run_hash += dry_run_hash_fn(batch_slices[i]);
657 may_match = true;
658 } else {
659 uint32_t hash = GetSliceHash(batch_slices[i]);
660 may_match = info.plain_table_bloom_->MayContainHash(hash);
661 }
662 } else if (FLAGS_use_full_block_reader) {
663 if (dry_run) {
664 dry_run_hash += dry_run_hash_fn(batch_slices[i]);
665 may_match = true;
666 } else {
667 may_match = info.full_block_reader_->KeyMayMatch(
668 batch_slices[i],
669 /*prefix_extractor=*/nullptr,
670 /*block_offset=*/ROCKSDB_NAMESPACE::kNotValid,
671 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
672 /*get_context=*/nullptr,
673 /*lookup_context=*/nullptr);
674 }
675 } else {
676 if (dry_run) {
677 dry_run_hash += dry_run_hash_fn(batch_slices[i]);
678 may_match = true;
679 } else {
680 may_match = info.reader_->MayMatch(batch_slices[i]);
681 }
682 }
683 if (inside_this_time) {
684 ALWAYS_ASSERT(may_match);
685 } else {
686 info.false_positives_ += may_match;
687 }
688 }
689 }
690 }
691
692 uint64_t elapsed_nanos = timer.ElapsedNanos();
693 double ns = double(elapsed_nanos) / max_queries;
694
695 if (!FLAGS_quick) {
696 if (dry_run) {
697 // Printing part of hash prevents dry run components from being optimized
698 // away by compiler
699 std::cout << " Dry run (" << std::hex << (dry_run_hash & 0xfffff)
700 << std::dec << ") ";
701 } else {
702 std::cout << " Gross filter ";
703 }
704 std::cout << "ns/op: " << ns << std::endl;
705 }
706
707 if (!dry_run) {
708 fp_rate_report_.str("");
709 uint64_t q = 0;
710 uint64_t fp = 0;
711 double worst_fp_rate = 0.0;
712 double best_fp_rate = 1.0;
713 for (auto &info : infos_) {
714 q += info.outside_queries_;
715 fp += info.false_positives_;
716 if (info.outside_queries_ > 0) {
717 double fp_rate = double(info.false_positives_) / info.outside_queries_;
718 worst_fp_rate = std::max(worst_fp_rate, fp_rate);
719 best_fp_rate = std::min(best_fp_rate, fp_rate);
720 }
721 }
722 fp_rate_report_ << " Average FP rate %: " << 100.0 * fp / q << std::endl;
723 if (!FLAGS_quick && !FLAGS_best_case) {
724 fp_rate_report_ << " Worst FP rate %: " << 100.0 * worst_fp_rate
725 << std::endl;
726 fp_rate_report_ << " Best FP rate %: " << 100.0 * best_fp_rate
727 << std::endl;
728 fp_rate_report_ << " Best possible bits/key: "
729 << -std::log(double(fp) / q) / std::log(2.0) << std::endl;
730 }
731 }
732 return ns;
733 }
734
main(int argc,char ** argv)735 int main(int argc, char **argv) {
736 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
737 SetUsageMessage(std::string("\nUSAGE:\n") + std::string(argv[0]) +
738 " [-quick] [OTHER OPTIONS]...");
739 ParseCommandLineFlags(&argc, &argv, true);
740
741 PrintWarnings();
742
743 if (FLAGS_legend) {
744 std::cout
745 << "Legend:" << std::endl
746 << " \"Inside\" - key that was added to filter" << std::endl
747 << " \"Outside\" - key that was not added to filter" << std::endl
748 << " \"FN\" - false negative query (must not happen)" << std::endl
749 << " \"FP\" - false positive query (OK at low rate)" << std::endl
750 << " \"Dry run\" - cost of testing and hashing overhead." << std::endl
751 << " \"Gross filter\" - cost of filter queries including testing "
752 << "\n and hashing overhead." << std::endl
753 << " \"net\" - best estimate of time in filter operation, without "
754 << "\n testing and hashing overhead (gross filter - dry run)"
755 << std::endl
756 << " \"ns/op\" - nanoseconds per operation (key query or add)"
757 << std::endl
758 << " \"Single filter\" - essentially minimum cost, assuming filter"
759 << "\n fits easily in L1 CPU cache." << std::endl
760 << " \"Batched, prepared\" - several queries at once against a"
761 << "\n randomly chosen filter, using multi-query interface."
762 << std::endl
763 << " \"Batched, unprepared\" - similar, but using serial calls"
764 << "\n to single query interface." << std::endl
765 << " \"Random filter\" - a filter is chosen at random as target"
766 << "\n of each query." << std::endl
767 << " \"Skewed X% in Y%\" - like \"Random filter\" except Y% of"
768 << "\n the filters are designated as \"hot\" and receive X%"
769 << "\n of queries." << std::endl;
770 } else {
771 FilterBench b;
772 for (uint32_t i = 0; i < FLAGS_runs; ++i) {
773 b.Go();
774 FLAGS_seed += 100;
775 b.random_.Seed(FLAGS_seed);
776 }
777 }
778
779 return 0;
780 }
781
782 #endif // !defined(GFLAGS) || defined(ROCKSDB_LITE)
783