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).
6 #if !defined(GFLAGS) || defined(ROCKSDB_LITE)
9 fprintf(stderr
, "filter_bench requires gflags and !ROCKSDB_LITE\n");
19 #include "memory/arena.h"
20 #include "port/port.h"
21 #include "port/stack_trace.h"
22 #include "rocksdb/cache.h"
23 #include "rocksdb/env.h"
24 #include "rocksdb/system_clock.h"
25 #include "rocksdb/table.h"
26 #include "table/block_based/filter_policy_internal.h"
27 #include "table/block_based/full_filter_block.h"
28 #include "table/block_based/mock_block_based_table.h"
29 #include "table/plain/plain_table_bloom.h"
30 #include "util/cast_util.h"
31 #include "util/gflags_compat.h"
32 #include "util/hash.h"
33 #include "util/random.h"
34 #include "util/stderr_logger.h"
35 #include "util/stop_watch.h"
36 #include "util/string_util.h"
38 using GFLAGS_NAMESPACE::ParseCommandLineFlags
;
39 using GFLAGS_NAMESPACE::RegisterFlagValidator
;
40 using GFLAGS_NAMESPACE::SetUsageMessage
;
42 DEFINE_uint32(seed
, 0, "Seed for random number generators");
44 DEFINE_double(working_mem_size_mb
, 200,
45 "MB of memory to get up to among all filters, unless "
46 "m_keys_total_max is specified.");
48 DEFINE_uint32(average_keys_per_filter
, 10000,
49 "Average number of keys per filter");
51 DEFINE_double(vary_key_count_ratio
, 0.4,
52 "Vary number of keys by up to +/- vary_key_count_ratio * "
53 "average_keys_per_filter.");
55 DEFINE_uint32(key_size
, 24, "Average number of bytes for each key");
57 DEFINE_bool(vary_key_alignment
, true,
58 "Whether to vary key alignment (default: at least 32-bit "
61 DEFINE_uint32(vary_key_size_log2_interval
, 5,
62 "Use same key size 2^n times, then change. Key size varies from "
63 "-2 to +2 bytes vs. average, unless n>=30 to fix key size.");
65 DEFINE_uint32(batch_size
, 8, "Number of keys to group in each batch");
67 DEFINE_double(bits_per_key
, 10.0, "Bits per key setting for filters");
69 DEFINE_double(m_queries
, 200, "Millions of queries for each test mode");
71 DEFINE_double(m_keys_total_max
, 0,
72 "Maximum total keys added to filters, in millions. "
73 "0 (default) disables. Non-zero overrides working_mem_size_mb "
76 DEFINE_bool(use_full_block_reader
, false,
77 "Use FullFilterBlockReader interface rather than FilterBitsReader");
79 DEFINE_bool(use_plain_table_bloom
, false,
80 "Use PlainTableBloom structure and interface rather than "
81 "FilterBitsReader/FullFilterBlockReader");
83 DEFINE_bool(new_builder
, false,
84 "Whether to create a new builder for each new filter");
86 DEFINE_uint32(impl
, 0,
87 "Select filter implementation. Without -use_plain_table_bloom:"
88 "0 = legacy full Bloom filter, "
89 "1 = format_version 5 Bloom filter, 2 = Ribbon128 filter. With "
90 "-use_plain_table_bloom: 0 = no locality, 1 = locality.");
92 DEFINE_bool(net_includes_hashing
, false,
93 "Whether query net ns/op times should include hashing. "
94 "(if not, dry run will include hashing) "
95 "(build times always include hashing)");
97 DEFINE_bool(optimize_filters_for_memory
, false,
98 "Setting for BlockBasedTableOptions::optimize_filters_for_memory");
100 DEFINE_bool(detect_filter_construct_corruption
, false,
102 "BlockBasedTableOptions::detect_filter_construct_corruption");
104 DEFINE_uint32(block_cache_capacity_MB
, 8,
106 "LRUCacheOptions::capacity");
108 DEFINE_bool(charge_filter_construction
, false,
110 "CacheEntryRoleOptions::charged of"
111 "CacheEntryRole::kFilterConstruction");
113 DEFINE_bool(strict_capacity_limit
, false,
115 "LRUCacheOptions::strict_capacity_limit");
117 DEFINE_bool(quick
, false, "Run more limited set of tests, fewer queries");
119 DEFINE_bool(best_case
, false, "Run limited tests only for best-case");
121 DEFINE_bool(allow_bad_fp_rate
, false, "Continue even if FP rate is bad");
123 DEFINE_bool(legend
, false,
124 "Print more information about interpreting results instead of "
127 DEFINE_uint32(runs
, 1, "Number of times to rebuild and run benchmark tests");
129 void _always_assert_fail(int line
, const char *file
, const char *expr
) {
130 fprintf(stderr
, "%s: %d: Assertion %s failed\n", file
, line
, expr
);
134 #define ALWAYS_ASSERT(cond) \
135 ((cond) ? (void)0 : ::_always_assert_fail(__LINE__, __FILE__, #cond))
138 // This could affect build times enough that we should not include it for
139 // accurate speed tests
140 #define PREDICT_FP_RATE
143 using ROCKSDB_NAMESPACE::Arena
;
144 using ROCKSDB_NAMESPACE::BlockContents
;
145 using ROCKSDB_NAMESPACE::BloomFilterPolicy
;
146 using ROCKSDB_NAMESPACE::BloomHash
;
147 using ROCKSDB_NAMESPACE::BloomLikeFilterPolicy
;
148 using ROCKSDB_NAMESPACE::BuiltinFilterBitsBuilder
;
149 using ROCKSDB_NAMESPACE::CachableEntry
;
150 using ROCKSDB_NAMESPACE::Cache
;
151 using ROCKSDB_NAMESPACE::CacheEntryRole
;
152 using ROCKSDB_NAMESPACE::CacheEntryRoleOptions
;
153 using ROCKSDB_NAMESPACE::EncodeFixed32
;
154 using ROCKSDB_NAMESPACE::Env
;
155 using ROCKSDB_NAMESPACE::FastRange32
;
156 using ROCKSDB_NAMESPACE::FilterBitsReader
;
157 using ROCKSDB_NAMESPACE::FilterBuildingContext
;
158 using ROCKSDB_NAMESPACE::FilterPolicy
;
159 using ROCKSDB_NAMESPACE::FullFilterBlockReader
;
160 using ROCKSDB_NAMESPACE::GetSliceHash
;
161 using ROCKSDB_NAMESPACE::GetSliceHash64
;
162 using ROCKSDB_NAMESPACE::Lower32of64
;
163 using ROCKSDB_NAMESPACE::LRUCacheOptions
;
164 using ROCKSDB_NAMESPACE::ParsedFullFilterBlock
;
165 using ROCKSDB_NAMESPACE::PlainTableBloomV1
;
166 using ROCKSDB_NAMESPACE::Random32
;
167 using ROCKSDB_NAMESPACE::Slice
;
168 using ROCKSDB_NAMESPACE::static_cast_with_check
;
169 using ROCKSDB_NAMESPACE::Status
;
170 using ROCKSDB_NAMESPACE::StderrLogger
;
171 using ROCKSDB_NAMESPACE::mock::MockBlockBasedTableTester
;
174 KeyMaker(size_t avg_size
)
175 : smallest_size_(avg_size
-
176 (FLAGS_vary_key_size_log2_interval
>= 30 ? 2 : 0)),
177 buf_size_(avg_size
+ 11), // pad to vary key size and alignment
178 buf_(new char[buf_size_
]) {
179 memset(buf_
.get(), 0, buf_size_
);
180 assert(smallest_size_
> 8);
182 size_t smallest_size_
;
184 std::unique_ptr
<char[]> buf_
;
186 // Returns a unique(-ish) key based on the given parameter values. Each
187 // call returns a Slice from the same buffer so previously returned
188 // Slices should be considered invalidated.
189 Slice
Get(uint32_t filter_num
, uint32_t val_num
) {
190 size_t start
= FLAGS_vary_key_alignment
? val_num
% 4 : 0;
191 size_t len
= smallest_size_
;
192 if (FLAGS_vary_key_size_log2_interval
< 30) {
193 // To get range [avg_size - 2, avg_size + 2]
194 // use range [smallest_size, smallest_size + 4]
196 (val_num
>> FLAGS_vary_key_size_log2_interval
) * 1234567891, 5);
198 char *data
= buf_
.get() + start
;
199 // Populate key data such that all data makes it into a key of at
200 // least 8 bytes. We also don't want all the within-filter key
201 // variance confined to a contiguous 32 bits, because then a 32 bit
202 // hash function can "cheat" the false positive rate by
203 // approximating a perfect hash.
204 EncodeFixed32(data
, val_num
);
205 EncodeFixed32(data
+ 4, filter_num
+ val_num
);
206 // ensure clearing leftovers from different alignment
207 EncodeFixed32(data
+ 8, 0);
208 return Slice(data
, len
);
212 void PrintWarnings() {
213 #if defined(__GNUC__) && !defined(__OPTIMIZE__)
215 "WARNING: Optimization is disabled: benchmarks unnecessarily slow\n");
219 "WARNING: Assertions are enabled; benchmarks unnecessarily slow\n");
223 void PrintError(const char *error
) { fprintf(stderr
, "ERROR: %s\n", error
); }
226 uint32_t filter_id_
= 0;
227 std::unique_ptr
<const char[]> owner_
;
229 Status filter_construction_status
= Status::OK();
230 uint32_t keys_added_
= 0;
231 std::unique_ptr
<FilterBitsReader
> reader_
;
232 std::unique_ptr
<FullFilterBlockReader
> full_block_reader_
;
233 std::unique_ptr
<PlainTableBloomV1
> plain_table_bloom_
;
234 uint64_t outside_queries_
= 0;
235 uint64_t false_positives_
= 0;
247 static const std::vector
<TestMode
> allTestModes
= {
248 kSingleFilter
, kBatchPrepared
, kBatchUnprepared
,
249 kFiftyOneFilter
, kEightyTwentyFilter
, kRandomFilter
,
252 static const std::vector
<TestMode
> quickTestModes
= {
257 static const std::vector
<TestMode
> bestCaseTestModes
= {
261 const char *TestModeToString(TestMode tm
) {
264 return "Single filter";
266 return "Batched, prepared";
267 case kBatchUnprepared
:
268 return "Batched, unprepared";
269 case kFiftyOneFilter
:
270 return "Skewed 50% in 1%";
271 case kEightyTwentyFilter
:
272 return "Skewed 80% in 20%";
274 return "Random filter";
276 return "Bad TestMode";
279 // Do just enough to keep some data dependence for the
281 static uint32_t DryRunNoHash(Slice
&s
) {
282 uint32_t sz
= static_cast<uint32_t>(s
.size());
284 return sz
+ s
.data()[3];
290 static uint32_t DryRunHash32(Slice
&s
) {
291 // Same perf characteristics as GetSliceHash()
295 static uint32_t DryRunHash64(Slice
&s
) {
296 return Lower32of64(GetSliceHash64(s
));
299 const std::shared_ptr
<const FilterPolicy
> &GetPolicy() {
300 static std::shared_ptr
<const FilterPolicy
> policy
;
302 policy
= BloomLikeFilterPolicy::Create(
303 BloomLikeFilterPolicy::GetAllFixedImpls().at(FLAGS_impl
),
309 struct FilterBench
: public MockBlockBasedTableTester
{
310 std::vector
<KeyMaker
> kms_
;
311 std::vector
<FilterInfo
> infos_
;
313 std::ostringstream fp_rate_report_
;
316 StderrLogger stderr_logger_
;
319 : MockBlockBasedTableTester(GetPolicy()),
322 for (uint32_t i
= 0; i
< FLAGS_batch_size
; ++i
) {
323 kms_
.emplace_back(FLAGS_key_size
< 8 ? 8 : FLAGS_key_size
);
325 ioptions_
.logger
= &stderr_logger_
;
326 table_options_
.optimize_filters_for_memory
=
327 FLAGS_optimize_filters_for_memory
;
328 table_options_
.detect_filter_construct_corruption
=
329 FLAGS_detect_filter_construct_corruption
;
330 table_options_
.cache_usage_options
.options_overrides
.insert(
331 {CacheEntryRole::kFilterConstruction
,
332 {/*.charged = */ FLAGS_charge_filter_construction
333 ? CacheEntryRoleOptions::Decision::kEnabled
334 : CacheEntryRoleOptions::Decision::kDisabled
}});
335 if (FLAGS_charge_filter_construction
) {
336 table_options_
.no_block_cache
= false;
338 lo
.capacity
= FLAGS_block_cache_capacity_MB
* 1024 * 1024;
339 lo
.num_shard_bits
= 0; // 2^0 shard
340 lo
.strict_capacity_limit
= FLAGS_strict_capacity_limit
;
341 std::shared_ptr
<Cache
> cache(NewLRUCache(lo
));
342 table_options_
.block_cache
= cache
;
348 double RandomQueryTest(uint32_t inside_threshold
, bool dry_run
,
352 void FilterBench::Go() {
353 if (FLAGS_use_plain_table_bloom
&& FLAGS_use_full_block_reader
) {
354 throw std::runtime_error(
355 "Can't combine -use_plain_table_bloom and -use_full_block_reader");
357 if (FLAGS_use_plain_table_bloom
) {
358 if (FLAGS_impl
> 1) {
359 throw std::runtime_error(
360 "-impl must currently be >= 0 and <= 1 for Plain table");
363 if (FLAGS_impl
> 2) {
364 throw std::runtime_error(
365 "-impl must currently be >= 0 and <= 2 for Block-based table");
369 if (FLAGS_vary_key_count_ratio
< 0.0 || FLAGS_vary_key_count_ratio
> 1.0) {
370 throw std::runtime_error("-vary_key_count_ratio must be >= 0.0 and <= 1.0");
373 // For example, average_keys_per_filter = 100, vary_key_count_ratio = 0.1.
374 // Varys up to +/- 10 keys. variance_range = 21 (generating value 0..20).
375 // variance_offset = 10, so value - offset average value is always 0.
376 const uint32_t variance_range
=
377 1 + 2 * static_cast<uint32_t>(FLAGS_vary_key_count_ratio
*
378 FLAGS_average_keys_per_filter
);
379 const uint32_t variance_offset
= variance_range
/ 2;
381 const std::vector
<TestMode
> &testModes
= FLAGS_best_case
? bestCaseTestModes
382 : FLAGS_quick
? quickTestModes
385 m_queries_
= FLAGS_m_queries
;
386 double working_mem_size_mb
= FLAGS_working_mem_size_mb
;
389 } else if (FLAGS_best_case
) {
391 working_mem_size_mb
/= 10.0;
394 std::cout
<< "Building..." << std::endl
;
396 std::unique_ptr
<BuiltinFilterBitsBuilder
> builder
;
398 size_t total_memory_used
= 0;
399 size_t total_size
= 0;
400 size_t total_keys_added
= 0;
401 #ifdef PREDICT_FP_RATE
402 double weighted_predicted_fp_rate
= 0.0;
404 size_t max_total_keys
;
406 if (FLAGS_m_keys_total_max
> 0) {
407 max_total_keys
= static_cast<size_t>(1000000 * FLAGS_m_keys_total_max
);
410 max_total_keys
= SIZE_MAX
;
411 max_mem
= static_cast<size_t>(1024 * 1024 * working_mem_size_mb
);
414 ROCKSDB_NAMESPACE::StopWatchNano
timer(
415 ROCKSDB_NAMESPACE::SystemClock::Default().get(), true);
418 while ((working_mem_size_mb
== 0 || total_size
< max_mem
) &&
419 total_keys_added
< max_total_keys
) {
420 uint32_t filter_id
= random_
.Next();
421 uint32_t keys_to_add
= FLAGS_average_keys_per_filter
+
422 FastRange32(random_
.Next(), variance_range
) -
424 if (max_total_keys
- total_keys_added
< keys_to_add
) {
425 keys_to_add
= static_cast<uint32_t>(max_total_keys
- total_keys_added
);
427 infos_
.emplace_back();
428 FilterInfo
&info
= infos_
.back();
429 info
.filter_id_
= filter_id
;
430 info
.keys_added_
= keys_to_add
;
431 if (FLAGS_use_plain_table_bloom
) {
432 info
.plain_table_bloom_
.reset(new PlainTableBloomV1());
433 info
.plain_table_bloom_
->SetTotalBits(
434 &arena_
, static_cast<uint32_t>(keys_to_add
* FLAGS_bits_per_key
),
435 FLAGS_impl
, 0 /*huge_page*/, nullptr /*logger*/);
436 for (uint32_t i
= 0; i
< keys_to_add
; ++i
) {
437 uint32_t hash
= GetSliceHash(kms_
[0].Get(filter_id
, i
));
438 info
.plain_table_bloom_
->AddHash(hash
);
440 info
.filter_
= info
.plain_table_bloom_
->GetRawData();
444 static_cast_with_check
<BuiltinFilterBitsBuilder
>(GetBuilder()));
446 for (uint32_t i
= 0; i
< keys_to_add
; ++i
) {
447 builder
->AddKey(kms_
[0].Get(filter_id
, i
));
450 builder
->Finish(&info
.owner_
, &info
.filter_construction_status
);
451 if (info
.filter_construction_status
.ok()) {
452 info
.filter_construction_status
=
453 builder
->MaybePostVerify(info
.filter_
);
455 if (!info
.filter_construction_status
.ok()) {
456 PrintError(info
.filter_construction_status
.ToString().c_str());
458 #ifdef PREDICT_FP_RATE
459 weighted_predicted_fp_rate
+=
461 builder
->EstimatedFpRate(keys_to_add
, info
.filter_
.size());
463 if (FLAGS_new_builder
) {
467 table_options_
.filter_policy
->GetFilterBitsReader(info
.filter_
));
468 CachableEntry
<ParsedFullFilterBlock
> block(
469 new ParsedFullFilterBlock(table_options_
.filter_policy
.get(),
470 BlockContents(info
.filter_
)),
471 nullptr /* cache */, nullptr /* cache_handle */,
472 true /* own_value */);
473 info
.full_block_reader_
.reset(
474 new FullFilterBlockReader(table_
.get(), std::move(block
)));
476 total_size
+= info
.filter_
.size();
477 #ifdef ROCKSDB_MALLOC_USABLE_SIZE
479 malloc_usable_size(const_cast<char *>(info
.filter_
.data()));
480 #endif // ROCKSDB_MALLOC_USABLE_SIZE
481 total_keys_added
+= keys_to_add
;
484 uint64_t elapsed_nanos
= timer
.ElapsedNanos();
485 double ns
= double(elapsed_nanos
) / total_keys_added
;
486 std::cout
<< "Build avg ns/key: " << ns
<< std::endl
;
487 std::cout
<< "Number of filters: " << infos_
.size() << std::endl
;
488 std::cout
<< "Total size (MB): " << total_size
/ 1024.0 / 1024.0 << std::endl
;
489 if (total_memory_used
> 0) {
490 std::cout
<< "Reported total allocated memory (MB): "
491 << total_memory_used
/ 1024.0 / 1024.0 << std::endl
;
492 std::cout
<< "Reported internal fragmentation: "
493 << (total_memory_used
- total_size
) * 100.0 / total_size
<< "%"
497 double bpk
= total_size
* 8.0 / total_keys_added
;
498 std::cout
<< "Bits/key stored: " << bpk
<< std::endl
;
499 #ifdef PREDICT_FP_RATE
500 std::cout
<< "Predicted FP rate %: "
501 << 100.0 * (weighted_predicted_fp_rate
/ total_keys_added
)
504 if (!FLAGS_quick
&& !FLAGS_best_case
) {
505 double tolerable_rate
= std::pow(2.0, -(bpk
- 1.0) / (1.4 + bpk
/ 50.0));
506 std::cout
<< "Best possible FP rate %: " << 100.0 * std::pow(2.0, -bpk
)
508 std::cout
<< "Tolerable FP rate %: " << 100.0 * tolerable_rate
<< std::endl
;
510 std::cout
<< "----------------------------" << std::endl
;
511 std::cout
<< "Verifying..." << std::endl
;
513 uint32_t outside_q_per_f
=
514 static_cast<uint32_t>(m_queries_
* 1000000 / infos_
.size());
516 for (uint32_t i
= 0; i
< infos_
.size(); ++i
) {
517 FilterInfo
&info
= infos_
[i
];
518 for (uint32_t j
= 0; j
< info
.keys_added_
; ++j
) {
519 if (FLAGS_use_plain_table_bloom
) {
520 uint32_t hash
= GetSliceHash(kms_
[0].Get(info
.filter_id_
, j
));
521 ALWAYS_ASSERT(info
.plain_table_bloom_
->MayContainHash(hash
));
524 info
.reader_
->MayMatch(kms_
[0].Get(info
.filter_id_
, j
)));
527 for (uint32_t j
= 0; j
< outside_q_per_f
; ++j
) {
528 if (FLAGS_use_plain_table_bloom
) {
530 GetSliceHash(kms_
[0].Get(info
.filter_id_
, j
| 0x80000000));
531 fps
+= info
.plain_table_bloom_
->MayContainHash(hash
);
533 fps
+= info
.reader_
->MayMatch(
534 kms_
[0].Get(info
.filter_id_
, j
| 0x80000000));
538 std::cout
<< " No FNs :)" << std::endl
;
539 double prelim_rate
= double(fps
) / outside_q_per_f
/ infos_
.size();
540 std::cout
<< " Prelim FP rate %: " << (100.0 * prelim_rate
) << std::endl
;
542 if (!FLAGS_allow_bad_fp_rate
) {
543 ALWAYS_ASSERT(prelim_rate
< tolerable_rate
);
547 std::cout
<< "----------------------------" << std::endl
;
548 std::cout
<< "Mixed inside/outside queries..." << std::endl
;
549 // 50% each inside and outside
550 uint32_t inside_threshold
= UINT32_MAX
/ 2;
551 for (TestMode tm
: testModes
) {
552 random_
.Seed(FLAGS_seed
+ 1);
553 double f
= RandomQueryTest(inside_threshold
, /*dry_run*/ false, tm
);
554 random_
.Seed(FLAGS_seed
+ 1);
555 double d
= RandomQueryTest(inside_threshold
, /*dry_run*/ true, tm
);
556 std::cout
<< " " << TestModeToString(tm
) << " net ns/op: " << (f
- d
)
561 std::cout
<< "----------------------------" << std::endl
;
562 std::cout
<< "Inside queries (mostly)..." << std::endl
;
563 // Do about 95% inside queries rather than 100% so that branch predictor
564 // can't give itself an artifically crazy advantage.
565 inside_threshold
= UINT32_MAX
/ 20 * 19;
566 for (TestMode tm
: testModes
) {
567 random_
.Seed(FLAGS_seed
+ 1);
568 double f
= RandomQueryTest(inside_threshold
, /*dry_run*/ false, tm
);
569 random_
.Seed(FLAGS_seed
+ 1);
570 double d
= RandomQueryTest(inside_threshold
, /*dry_run*/ true, tm
);
571 std::cout
<< " " << TestModeToString(tm
) << " net ns/op: " << (f
- d
)
575 std::cout
<< "----------------------------" << std::endl
;
576 std::cout
<< "Outside queries (mostly)..." << std::endl
;
577 // Do about 95% outside queries rather than 100% so that branch predictor
578 // can't give itself an artifically crazy advantage.
579 inside_threshold
= UINT32_MAX
/ 20;
580 for (TestMode tm
: testModes
) {
581 random_
.Seed(FLAGS_seed
+ 2);
582 double f
= RandomQueryTest(inside_threshold
, /*dry_run*/ false, tm
);
583 random_
.Seed(FLAGS_seed
+ 2);
584 double d
= RandomQueryTest(inside_threshold
, /*dry_run*/ true, tm
);
585 std::cout
<< " " << TestModeToString(tm
) << " net ns/op: " << (f
- d
)
589 std::cout
<< fp_rate_report_
.str();
591 std::cout
<< "----------------------------" << std::endl
;
592 std::cout
<< "Done. (For more info, run with -legend or -help.)" << std::endl
;
595 double FilterBench::RandomQueryTest(uint32_t inside_threshold
, bool dry_run
,
597 for (auto &info
: infos_
) {
598 info
.outside_queries_
= 0;
599 info
.false_positives_
= 0;
602 auto dry_run_hash_fn
= DryRunNoHash
;
603 if (!FLAGS_net_includes_hashing
) {
604 if (FLAGS_impl
== 0 || FLAGS_use_plain_table_bloom
) {
605 dry_run_hash_fn
= DryRunHash32
;
607 dry_run_hash_fn
= DryRunHash64
;
611 uint32_t num_infos
= static_cast<uint32_t>(infos_
.size());
612 uint32_t dry_run_hash
= 0;
613 uint64_t max_queries
= static_cast<uint64_t>(m_queries_
* 1000000 + 0.50);
614 // Some filters may be considered secondary in order to implement skewed
615 // queries. num_primary_filters is the number that are to be treated as
616 // equal, and any remainder will be treated as secondary.
617 uint32_t num_primary_filters
= num_infos
;
618 // The proportion (when divided by 2^32 - 1) of filter queries going to
619 // the primary filters (default = all). The remainder of queries are
620 // against secondary filters.
621 uint32_t primary_filter_threshold
= 0xffffffff;
622 if (mode
== kSingleFilter
) {
623 // 100% of queries to 1 filter
624 num_primary_filters
= 1;
625 } else if (mode
== kFiftyOneFilter
) {
626 if (num_infos
< 50) {
630 primary_filter_threshold
/= 2;
632 num_primary_filters
= (num_primary_filters
+ 99) / 100;
633 } else if (mode
== kEightyTwentyFilter
) {
638 primary_filter_threshold
= primary_filter_threshold
/ 5 * 4;
640 num_primary_filters
= (num_primary_filters
+ 4) / 5;
641 } else if (mode
== kRandomFilter
) {
642 if (num_infos
== 1) {
646 uint32_t batch_size
= 1;
647 std::unique_ptr
<Slice
[]> batch_slices
;
648 std::unique_ptr
<Slice
*[]> batch_slice_ptrs
;
649 std::unique_ptr
<bool[]> batch_results
;
650 if (mode
== kBatchPrepared
|| mode
== kBatchUnprepared
) {
651 batch_size
= static_cast<uint32_t>(kms_
.size());
654 batch_slices
.reset(new Slice
[batch_size
]);
655 batch_slice_ptrs
.reset(new Slice
*[batch_size
]);
656 batch_results
.reset(new bool[batch_size
]);
657 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
658 batch_results
[i
] = false;
659 batch_slice_ptrs
[i
] = &batch_slices
[i
];
662 ROCKSDB_NAMESPACE::StopWatchNano
timer(
663 ROCKSDB_NAMESPACE::SystemClock::Default().get(), true);
665 for (uint64_t q
= 0; q
< max_queries
; q
+= batch_size
) {
666 bool inside_this_time
= random_
.Next() <= inside_threshold
;
668 uint32_t filter_index
;
669 if (random_
.Next() <= primary_filter_threshold
) {
670 filter_index
= random_
.Uniformish(num_primary_filters
);
673 filter_index
= num_primary_filters
+
674 random_
.Uniformish(num_infos
- num_primary_filters
);
676 FilterInfo
&info
= infos_
[filter_index
];
677 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
678 if (inside_this_time
) {
680 kms_
[i
].Get(info
.filter_id_
, random_
.Uniformish(info
.keys_added_
));
683 kms_
[i
].Get(info
.filter_id_
, random_
.Uniformish(info
.keys_added_
) |
684 uint32_t{0x80000000});
685 info
.outside_queries_
++;
688 // TODO: implement batched interface to full block reader
689 // TODO: implement batched interface to plain table bloom
690 if (mode
== kBatchPrepared
&& !FLAGS_use_full_block_reader
&&
691 !FLAGS_use_plain_table_bloom
) {
692 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
693 batch_results
[i
] = false;
696 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
697 batch_results
[i
] = true;
698 dry_run_hash
+= dry_run_hash_fn(batch_slices
[i
]);
701 info
.reader_
->MayMatch(batch_size
, batch_slice_ptrs
.get(),
702 batch_results
.get());
704 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
705 if (inside_this_time
) {
706 ALWAYS_ASSERT(batch_results
[i
]);
708 info
.false_positives_
+= batch_results
[i
];
712 for (uint32_t i
= 0; i
< batch_size
; ++i
) {
714 if (FLAGS_use_plain_table_bloom
) {
716 dry_run_hash
+= dry_run_hash_fn(batch_slices
[i
]);
719 uint32_t hash
= GetSliceHash(batch_slices
[i
]);
720 may_match
= info
.plain_table_bloom_
->MayContainHash(hash
);
722 } else if (FLAGS_use_full_block_reader
) {
724 dry_run_hash
+= dry_run_hash_fn(batch_slices
[i
]);
727 may_match
= info
.full_block_reader_
->KeyMayMatch(
729 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
730 /*get_context=*/nullptr,
731 /*lookup_context=*/nullptr, Env::IO_TOTAL
);
735 dry_run_hash
+= dry_run_hash_fn(batch_slices
[i
]);
738 may_match
= info
.reader_
->MayMatch(batch_slices
[i
]);
741 if (inside_this_time
) {
742 ALWAYS_ASSERT(may_match
);
744 info
.false_positives_
+= may_match
;
750 uint64_t elapsed_nanos
= timer
.ElapsedNanos();
751 double ns
= double(elapsed_nanos
) / max_queries
;
755 // Printing part of hash prevents dry run components from being optimized
757 std::cout
<< " Dry run (" << std::hex
<< (dry_run_hash
& 0xfffff)
760 std::cout
<< " Gross filter ";
762 std::cout
<< "ns/op: " << ns
<< std::endl
;
766 fp_rate_report_
.str("");
769 double worst_fp_rate
= 0.0;
770 double best_fp_rate
= 1.0;
771 for (auto &info
: infos_
) {
772 q
+= info
.outside_queries_
;
773 fp
+= info
.false_positives_
;
774 if (info
.outside_queries_
> 0) {
775 double fp_rate
= double(info
.false_positives_
) / info
.outside_queries_
;
776 worst_fp_rate
= std::max(worst_fp_rate
, fp_rate
);
777 best_fp_rate
= std::min(best_fp_rate
, fp_rate
);
780 fp_rate_report_
<< " Average FP rate %: " << 100.0 * fp
/ q
<< std::endl
;
781 if (!FLAGS_quick
&& !FLAGS_best_case
) {
782 fp_rate_report_
<< " Worst FP rate %: " << 100.0 * worst_fp_rate
784 fp_rate_report_
<< " Best FP rate %: " << 100.0 * best_fp_rate
786 fp_rate_report_
<< " Best possible bits/key: "
787 << -std::log(double(fp
) / q
) / std::log(2.0) << std::endl
;
793 int main(int argc
, char **argv
) {
794 ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
795 SetUsageMessage(std::string("\nUSAGE:\n") + std::string(argv
[0]) +
796 " [-quick] [OTHER OPTIONS]...");
797 ParseCommandLineFlags(&argc
, &argv
, true);
803 << "Legend:" << std::endl
804 << " \"Inside\" - key that was added to filter" << std::endl
805 << " \"Outside\" - key that was not added to filter" << std::endl
806 << " \"FN\" - false negative query (must not happen)" << std::endl
807 << " \"FP\" - false positive query (OK at low rate)" << std::endl
808 << " \"Dry run\" - cost of testing and hashing overhead." << std::endl
809 << " \"Gross filter\" - cost of filter queries including testing "
810 << "\n and hashing overhead." << std::endl
811 << " \"net\" - best estimate of time in filter operation, without "
812 << "\n testing and hashing overhead (gross filter - dry run)"
814 << " \"ns/op\" - nanoseconds per operation (key query or add)"
816 << " \"Single filter\" - essentially minimum cost, assuming filter"
817 << "\n fits easily in L1 CPU cache." << std::endl
818 << " \"Batched, prepared\" - several queries at once against a"
819 << "\n randomly chosen filter, using multi-query interface."
821 << " \"Batched, unprepared\" - similar, but using serial calls"
822 << "\n to single query interface." << std::endl
823 << " \"Random filter\" - a filter is chosen at random as target"
824 << "\n of each query." << std::endl
825 << " \"Skewed X% in Y%\" - like \"Random filter\" except Y% of"
826 << "\n the filters are designated as \"hot\" and receive X%"
827 << "\n of queries." << std::endl
;
830 for (uint32_t i
= 0; i
< FLAGS_runs
; ++i
) {
833 b
.random_
.Seed(FLAGS_seed
);
840 #endif // !defined(GFLAGS) || defined(ROCKSDB_LITE)