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 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
13 fprintf(stderr
, "Please install gflags to run this test... Skipping...\n");
22 #include "memory/arena.h"
23 #include "port/jemalloc_helper.h"
24 #include "rocksdb/filter_policy.h"
25 #include "table/block_based/filter_policy_internal.h"
26 #include "test_util/testharness.h"
27 #include "test_util/testutil.h"
28 #include "util/gflags_compat.h"
29 #include "util/hash.h"
31 using GFLAGS_NAMESPACE::ParseCommandLineFlags
;
33 DEFINE_int32(bits_per_key
, 10, "");
35 namespace ROCKSDB_NAMESPACE
{
37 static const int kVerbose
= 1;
39 static Slice
Key(int i
, char* buffer
) {
41 PutFixed32(&s
, static_cast<uint32_t>(i
));
42 memcpy(buffer
, s
.c_str(), sizeof(i
));
43 return Slice(buffer
, sizeof(i
));
46 static int NextLength(int length
) {
49 } else if (length
< 100) {
51 } else if (length
< 1000) {
59 class BlockBasedBloomTest
: public testing::Test
{
61 std::unique_ptr
<const FilterPolicy
> policy_
;
63 std::vector
<std::string
> keys_
;
66 BlockBasedBloomTest() { ResetPolicy(); }
73 void ResetPolicy(double bits_per_key
) {
74 policy_
.reset(new BloomFilterPolicy(bits_per_key
,
75 BloomFilterPolicy::kDeprecatedBlock
));
79 void ResetPolicy() { ResetPolicy(FLAGS_bits_per_key
); }
81 void Add(const Slice
& s
) {
82 keys_
.push_back(s
.ToString());
86 std::vector
<Slice
> key_slices
;
87 for (size_t i
= 0; i
< keys_
.size(); i
++) {
88 key_slices
.push_back(Slice(keys_
[i
]));
91 policy_
->CreateFilter(&key_slices
[0], static_cast<int>(key_slices
.size()),
94 if (kVerbose
>= 2) DumpFilter();
97 size_t FilterSize() const {
98 return filter_
.size();
101 Slice
FilterData() const { return Slice(filter_
); }
104 fprintf(stderr
, "F(");
105 for (size_t i
= 0; i
+1 < filter_
.size(); i
++) {
106 const unsigned int c
= static_cast<unsigned int>(filter_
[i
]);
107 for (int j
= 0; j
< 8; j
++) {
108 fprintf(stderr
, "%c", (c
& (1 <<j
)) ? '1' : '.');
111 fprintf(stderr
, ")\n");
114 bool Matches(const Slice
& s
) {
115 if (!keys_
.empty()) {
118 return policy_
->KeyMayMatch(s
, filter_
);
121 double FalsePositiveRate() {
122 char buffer
[sizeof(int)];
124 for (int i
= 0; i
< 10000; i
++) {
125 if (Matches(Key(i
+ 1000000000, buffer
))) {
129 return result
/ 10000.0;
133 TEST_F(BlockBasedBloomTest
, EmptyFilter
) {
134 ASSERT_TRUE(! Matches("hello"));
135 ASSERT_TRUE(! Matches("world"));
138 TEST_F(BlockBasedBloomTest
, Small
) {
141 ASSERT_TRUE(Matches("hello"));
142 ASSERT_TRUE(Matches("world"));
143 ASSERT_TRUE(! Matches("x"));
144 ASSERT_TRUE(! Matches("foo"));
147 TEST_F(BlockBasedBloomTest
, VaryingLengths
) {
148 char buffer
[sizeof(int)];
150 // Count number of filters that significantly exceed the false positive rate
151 int mediocre_filters
= 0;
152 int good_filters
= 0;
154 for (int length
= 1; length
<= 10000; length
= NextLength(length
)) {
156 for (int i
= 0; i
< length
; i
++) {
161 ASSERT_LE(FilterSize(), (size_t)((length
* 10 / 8) + 40)) << length
;
163 // All added keys must match
164 for (int i
= 0; i
< length
; i
++) {
165 ASSERT_TRUE(Matches(Key(i
, buffer
)))
166 << "Length " << length
<< "; key " << i
;
169 // Check false positive rate
170 double rate
= FalsePositiveRate();
172 fprintf(stderr
, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
173 rate
*100.0, length
, static_cast<int>(FilterSize()));
175 ASSERT_LE(rate
, 0.02); // Must not be over 2%
176 if (rate
> 0.0125) mediocre_filters
++; // Allowed, but not too often
180 fprintf(stderr
, "Filters: %d good, %d mediocre\n",
181 good_filters
, mediocre_filters
);
183 ASSERT_LE(mediocre_filters
, good_filters
/5);
186 // Ensure the implementation doesn't accidentally change in an
188 TEST_F(BlockBasedBloomTest
, Schema
) {
189 char buffer
[sizeof(int)];
191 ResetPolicy(8); // num_probes = 5
192 for (int key
= 0; key
< 87; key
++) {
193 Add(Key(key
, buffer
));
196 ASSERT_EQ(BloomHash(FilterData()), 3589896109U);
198 ResetPolicy(9); // num_probes = 6
199 for (int key
= 0; key
< 87; key
++) {
200 Add(Key(key
, buffer
));
203 ASSERT_EQ(BloomHash(FilterData()), 969445585U);
205 ResetPolicy(11); // num_probes = 7
206 for (int key
= 0; key
< 87; key
++) {
207 Add(Key(key
, buffer
));
210 ASSERT_EQ(BloomHash(FilterData()), 1694458207U);
212 ResetPolicy(10); // num_probes = 6
213 for (int key
= 0; key
< 87; key
++) {
214 Add(Key(key
, buffer
));
217 ASSERT_EQ(BloomHash(FilterData()), 2373646410U);
220 for (int key
= /*CHANGED*/ 1; key
< 87; key
++) {
221 Add(Key(key
, buffer
));
224 ASSERT_EQ(BloomHash(FilterData()), 1908442116U);
227 for (int key
= 1; key
< /*CHANGED*/ 88; key
++) {
228 Add(Key(key
, buffer
));
231 ASSERT_EQ(BloomHash(FilterData()), 3057004015U);
233 // With new fractional bits_per_key, check that we are rounding to
234 // whole bits per key for old Bloom filters.
235 ResetPolicy(9.5); // Treated as 10
236 for (int key
= 1; key
< 88; key
++) {
237 Add(Key(key
, buffer
));
240 ASSERT_EQ(BloomHash(FilterData()), /*SAME*/ 3057004015U);
242 ResetPolicy(10.499); // Treated as 10
243 for (int key
= 1; key
< 88; key
++) {
244 Add(Key(key
, buffer
));
247 ASSERT_EQ(BloomHash(FilterData()), /*SAME*/ 3057004015U);
252 // Different bits-per-byte
254 class FullBloomTest
: public testing::TestWithParam
<BloomFilterPolicy::Mode
> {
256 BlockBasedTableOptions table_options_
;
259 std::shared_ptr
<const FilterPolicy
>& policy_
;
260 std::unique_ptr
<FilterBitsBuilder
> bits_builder_
;
261 std::unique_ptr
<FilterBitsReader
> bits_reader_
;
262 std::unique_ptr
<const char[]> buf_
;
266 FullBloomTest() : policy_(table_options_
.filter_policy
), filter_size_(0) {
270 BuiltinFilterBitsBuilder
* GetBuiltinFilterBitsBuilder() {
271 // Throws on bad cast
272 return &dynamic_cast<BuiltinFilterBitsBuilder
&>(*bits_builder_
);
275 const BloomFilterPolicy
* GetBloomFilterPolicy() {
276 // Throws on bad cast
277 return &dynamic_cast<const BloomFilterPolicy
&>(*policy_
);
281 bits_builder_
.reset(BloomFilterPolicy::GetBuilderFromContext(
282 FilterBuildingContext(table_options_
)));
283 bits_reader_
.reset(nullptr);
288 void ResetPolicy(double bits_per_key
) {
289 policy_
.reset(new BloomFilterPolicy(bits_per_key
, GetParam()));
293 void ResetPolicy() { ResetPolicy(FLAGS_bits_per_key
); }
295 void Add(const Slice
& s
) {
296 bits_builder_
->AddKey(s
);
299 void OpenRaw(const Slice
& s
) {
300 bits_reader_
.reset(policy_
->GetFilterBitsReader(s
));
304 Slice filter
= bits_builder_
->Finish(&buf_
);
305 bits_reader_
.reset(policy_
->GetFilterBitsReader(filter
));
306 filter_size_
= filter
.size();
309 size_t FilterSize() const {
313 Slice
FilterData() { return Slice(buf_
.get(), filter_size_
); }
315 int GetNumProbesFromFilterData() {
316 assert(filter_size_
>= 5);
317 int8_t raw_num_probes
= static_cast<int8_t>(buf_
.get()[filter_size_
- 5]);
318 if (raw_num_probes
== -1) { // New bloom filter marker
319 return static_cast<uint8_t>(buf_
.get()[filter_size_
- 3]);
321 return raw_num_probes
;
325 bool Matches(const Slice
& s
) {
326 if (bits_reader_
== nullptr) {
329 return bits_reader_
->MayMatch(s
);
332 // Provides a kind of fingerprint on the Bloom filter's
333 // behavior, for reasonbly high FP rates.
334 uint64_t PackedMatches() {
335 char buffer
[sizeof(int)];
337 for (int i
= 0; i
< 64; i
++) {
338 if (Matches(Key(i
+ 12345, buffer
))) {
339 result
|= uint64_t{1} << i
;
345 // Provides a kind of fingerprint on the Bloom filter's
346 // behavior, for lower FP rates.
347 std::string
FirstFPs(int count
) {
348 char buffer
[sizeof(int)];
351 for (int i
= 0; i
< 1000000; i
++) {
352 // Pack four match booleans into each hexadecimal digit
353 if (Matches(Key(i
+ 1000000, buffer
))) {
355 rv
+= std::to_string(i
);
356 if (fp_count
== count
) {
365 double FalsePositiveRate() {
366 char buffer
[sizeof(int)];
368 for (int i
= 0; i
< 10000; i
++) {
369 if (Matches(Key(i
+ 1000000000, buffer
))) {
373 return result
/ 10000.0;
376 uint32_t SelectByImpl(uint32_t for_legacy_bloom
,
377 uint32_t for_fast_local_bloom
) {
378 switch (GetParam()) {
379 case BloomFilterPolicy::kLegacyBloom
:
380 return for_legacy_bloom
;
381 case BloomFilterPolicy::kFastLocalBloom
:
382 return for_fast_local_bloom
;
383 case BloomFilterPolicy::kDeprecatedBlock
:
384 case BloomFilterPolicy::kAutoBloom
:
385 case BloomFilterPolicy::kStandard128Ribbon
:
394 TEST_P(FullBloomTest
, FilterSize
) {
395 // In addition to checking the consistency of space computation, we are
396 // checking that denoted and computed doubles are interpreted as expected
397 // as bits_per_key values.
398 bool some_computed_less_than_denoted
= false;
399 // Note: enforced minimum is 1 bit per key (1000 millibits), and enforced
400 // maximum is 100 bits per key (100000 millibits).
402 std::vector
<std::pair
<double, int> >{{-HUGE_VAL
, 1000},
416 ResetPolicy(bpk
.first
);
417 auto bfp
= GetBloomFilterPolicy();
418 EXPECT_EQ(bpk
.second
, bfp
->GetMillibitsPerKey());
419 EXPECT_EQ((bpk
.second
+ 500) / 1000, bfp
->GetWholeBitsPerKey());
421 double computed
= bpk
.first
;
422 // This transforms e.g. 9.5 -> 9.499999999999998, which we still
423 // round to 10 for whole bits per key.
425 computed
/= 1234567.0;
426 computed
*= 1234567.0;
428 some_computed_less_than_denoted
|= (computed
< bpk
.first
);
429 ResetPolicy(computed
);
430 bfp
= GetBloomFilterPolicy();
431 EXPECT_EQ(bpk
.second
, bfp
->GetMillibitsPerKey());
432 EXPECT_EQ((bpk
.second
+ 500) / 1000, bfp
->GetWholeBitsPerKey());
434 auto bits_builder
= GetBuiltinFilterBitsBuilder();
435 for (int n
= 1; n
< 100; n
++) {
436 auto space
= bits_builder
->CalculateSpace(n
);
437 auto n2
= bits_builder
->CalculateNumEntry(space
);
439 auto space2
= bits_builder
->CalculateSpace(n2
);
440 EXPECT_EQ(space
, space2
);
443 // Check that the compiler hasn't optimized our computation into nothing
444 EXPECT_TRUE(some_computed_less_than_denoted
);
448 TEST_P(FullBloomTest
, FullEmptyFilter
) {
449 // Empty filter is not match, at this level
450 ASSERT_TRUE(!Matches("hello"));
451 ASSERT_TRUE(!Matches("world"));
454 TEST_P(FullBloomTest
, FullSmall
) {
457 ASSERT_TRUE(Matches("hello"));
458 ASSERT_TRUE(Matches("world"));
459 ASSERT_TRUE(!Matches("x"));
460 ASSERT_TRUE(!Matches("foo"));
463 TEST_P(FullBloomTest
, FullVaryingLengths
) {
464 char buffer
[sizeof(int)];
466 // Count number of filters that significantly exceed the false positive rate
467 int mediocre_filters
= 0;
468 int good_filters
= 0;
470 for (int length
= 1; length
<= 10000; length
= NextLength(length
)) {
472 for (int i
= 0; i
< length
; i
++) {
477 EXPECT_LE(FilterSize(),
478 (size_t)((length
* 10 / 8) + CACHE_LINE_SIZE
* 2 + 5));
480 // All added keys must match
481 for (int i
= 0; i
< length
; i
++) {
482 ASSERT_TRUE(Matches(Key(i
, buffer
)))
483 << "Length " << length
<< "; key " << i
;
486 // Check false positive rate
487 double rate
= FalsePositiveRate();
489 fprintf(stderr
, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
490 rate
*100.0, length
, static_cast<int>(FilterSize()));
492 EXPECT_LE(rate
, 0.02); // Must not be over 2%
494 mediocre_filters
++; // Allowed, but not too often
499 fprintf(stderr
, "Filters: %d good, %d mediocre\n",
500 good_filters
, mediocre_filters
);
502 EXPECT_LE(mediocre_filters
, good_filters
/ 5);
505 TEST_P(FullBloomTest
, OptimizeForMemory
) {
506 if (GetParam() == BloomFilterPolicy::kStandard128Ribbon
) {
507 // TODO Not yet implemented
510 char buffer
[sizeof(int)];
511 for (bool offm
: {true, false}) {
512 table_options_
.optimize_filters_for_memory
= offm
;
515 uint64_t total_size
= 0;
516 uint64_t total_mem
= 0;
517 int64_t total_keys
= 0;
518 double total_fp_rate
= 0;
519 constexpr int nfilters
= 100;
520 for (int i
= 0; i
< nfilters
; ++i
) {
521 int nkeys
= static_cast<int>(rnd
.Uniformish(10000)) + 100;
523 for (int j
= 0; j
< nkeys
; ++j
) {
527 size_t size
= FilterData().size();
529 // optimize_filters_for_memory currently depends on malloc_usable_size
530 // but we run the rest of the test to ensure no bad behavior without it.
531 #ifdef ROCKSDB_MALLOC_USABLE_SIZE
532 size
= malloc_usable_size(const_cast<char*>(FilterData().data()));
533 #endif // ROCKSDB_MALLOC_USABLE_SIZE
536 total_fp_rate
+= FalsePositiveRate();
538 EXPECT_LE(total_fp_rate
/ double{nfilters
}, 0.011);
539 EXPECT_GE(total_fp_rate
/ double{nfilters
}, 0.008);
541 int64_t ex_min_total_size
= int64_t{FLAGS_bits_per_key
} * total_keys
/ 8;
542 EXPECT_GE(static_cast<int64_t>(total_size
), ex_min_total_size
);
544 int64_t blocked_bloom_overhead
= nfilters
* (CACHE_LINE_SIZE
+ 5);
545 if (GetParam() == BloomFilterPolicy::kLegacyBloom
) {
546 // this config can add extra cache line to make odd number
547 blocked_bloom_overhead
+= nfilters
* CACHE_LINE_SIZE
;
550 EXPECT_GE(total_mem
, total_size
);
552 // optimize_filters_for_memory not implemented with legacy Bloom
553 if (offm
&& GetParam() != BloomFilterPolicy::kLegacyBloom
) {
554 // This value can include a small extra penalty for kExtraPadding
555 fprintf(stderr
, "Internal fragmentation (optimized): %g%%\n",
556 (total_mem
- total_size
) * 100.0 / total_size
);
557 // Less than 1% internal fragmentation
558 EXPECT_LE(total_mem
, total_size
* 101 / 100);
559 // Up to 2% storage penalty
560 EXPECT_LE(static_cast<int64_t>(total_size
),
561 ex_min_total_size
* 102 / 100 + blocked_bloom_overhead
);
563 fprintf(stderr
, "Internal fragmentation (not optimized): %g%%\n",
564 (total_mem
- total_size
) * 100.0 / total_size
);
565 // TODO: add control checks for more allocators?
566 #ifdef ROCKSDB_JEMALLOC
567 fprintf(stderr
, "Jemalloc detected? %d\n", HasJemalloc());
569 // More than 5% internal fragmentation
570 EXPECT_GE(total_mem
, total_size
* 105 / 100);
572 #endif // ROCKSDB_JEMALLOC
573 // No storage penalty, just usual overhead
574 EXPECT_LE(static_cast<int64_t>(total_size
),
575 ex_min_total_size
+ blocked_bloom_overhead
);
581 inline uint32_t SelectByCacheLineSize(uint32_t for64
, uint32_t for128
,
586 #if CACHE_LINE_SIZE == 64
588 #elif CACHE_LINE_SIZE == 128
590 #elif CACHE_LINE_SIZE == 256
593 #error "CACHE_LINE_SIZE unknown or unrecognized"
598 // Ensure the implementation doesn't accidentally change in an
599 // incompatible way. This test doesn't check the reading side
600 // (FirstFPs/PackedMatches) for LegacyBloom because it requires the
601 // ability to read filters generated using other cache line sizes.
603 TEST_P(FullBloomTest
, Schema
) {
604 if (GetParam() == BloomFilterPolicy::kStandard128Ribbon
) {
605 // TODO ASAP to ensure schema stability
608 char buffer
[sizeof(int)];
610 // Use enough keys so that changing bits / key by 1 is guaranteed to
611 // change number of allocated cache lines. So keys > max cache line bits.
613 ResetPolicy(2); // num_probes = 1
614 for (int key
= 0; key
< 2087; key
++) {
615 Add(Key(key
, buffer
));
618 EXPECT_EQ(GetNumProbesFromFilterData(), 1);
620 BloomHash(FilterData()),
621 SelectByImpl(SelectByCacheLineSize(1567096579, 1964771444, 2659542661U),
623 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
624 EXPECT_EQ("11,13,17,25,29,30,35,37,45,53", FirstFPs(10));
627 ResetPolicy(3); // num_probes = 2
628 for (int key
= 0; key
< 2087; key
++) {
629 Add(Key(key
, buffer
));
632 EXPECT_EQ(GetNumProbesFromFilterData(), 2);
634 BloomHash(FilterData()),
635 SelectByImpl(SelectByCacheLineSize(2707206547U, 2571983456U, 218344685),
637 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
638 EXPECT_EQ("4,15,17,24,27,28,29,53,63,70", FirstFPs(10));
641 ResetPolicy(5); // num_probes = 3
642 for (int key
= 0; key
< 2087; key
++) {
643 Add(Key(key
, buffer
));
646 EXPECT_EQ(GetNumProbesFromFilterData(), 3);
648 BloomHash(FilterData()),
649 SelectByImpl(SelectByCacheLineSize(515748486, 94611728, 2436112214U),
651 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
652 EXPECT_EQ("15,24,29,39,53,87,89,100,103,104", FirstFPs(10));
655 ResetPolicy(8); // num_probes = 5
656 for (int key
= 0; key
< 2087; key
++) {
657 Add(Key(key
, buffer
));
660 EXPECT_EQ(GetNumProbesFromFilterData(), 5);
662 BloomHash(FilterData()),
663 SelectByImpl(SelectByCacheLineSize(1302145999, 2811644657U, 756553699),
665 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
666 EXPECT_EQ("16,60,66,126,220,238,244,256,265,287", FirstFPs(10));
669 ResetPolicy(9); // num_probes = 6
670 for (int key
= 0; key
< 2087; key
++) {
671 Add(Key(key
, buffer
));
674 EXPECT_EQ(GetNumProbesFromFilterData(), 6);
676 BloomHash(FilterData()),
677 SelectByImpl(SelectByCacheLineSize(2092755149, 661139132, 1182970461),
679 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
680 EXPECT_EQ("156,367,791,872,945,1015,1139,1159,1265,1435", FirstFPs(10));
683 ResetPolicy(11); // num_probes = 7
684 for (int key
= 0; key
< 2087; key
++) {
685 Add(Key(key
, buffer
));
688 EXPECT_EQ(GetNumProbesFromFilterData(), 7);
690 BloomHash(FilterData()),
691 SelectByImpl(SelectByCacheLineSize(3755609649U, 1812694762, 1449142939),
693 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
694 EXPECT_EQ("34,74,130,236,643,882,962,1015,1035,1110", FirstFPs(10));
697 // This used to be 9 probes, but 8 is a better choice for speed,
698 // especially with SIMD groups of 8 probes, with essentially no
699 // change in FP rate.
700 // FP rate @ 9 probes, old Bloom: 0.4321%
701 // FP rate @ 9 probes, new Bloom: 0.1846%
702 // FP rate @ 8 probes, new Bloom: 0.1843%
703 ResetPolicy(14); // num_probes = 8 (new), 9 (old)
704 for (int key
= 0; key
< 2087; key
++) {
705 Add(Key(key
, buffer
));
708 EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
711 BloomHash(FilterData()),
712 SelectByImpl(SelectByCacheLineSize(178861123, 379087593, 2574136516U),
714 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
715 EXPECT_EQ("130,240,522,565,989,2002,2526,3147,3543", FirstFPs(9));
718 // This used to be 11 probes, but 9 is a better choice for speed
720 // FP rate @ 11 probes, old Bloom: 0.3571%
721 // FP rate @ 11 probes, new Bloom: 0.0884%
722 // FP rate @ 9 probes, new Bloom: 0.0843%
723 ResetPolicy(16); // num_probes = 9 (new), 11 (old)
724 for (int key
= 0; key
< 2087; key
++) {
725 Add(Key(key
, buffer
));
728 EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
729 SelectByImpl(11, 9));
731 BloomHash(FilterData()),
732 SelectByImpl(SelectByCacheLineSize(1129406313, 3049154394U, 1727750964),
734 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
735 EXPECT_EQ("3299,3611,3916,6620,7822,8079,8482,8942,10167", FirstFPs(9));
738 ResetPolicy(10); // num_probes = 6, but different memory ratio vs. 9
739 for (int key
= 0; key
< 2087; key
++) {
740 Add(Key(key
, buffer
));
743 EXPECT_EQ(GetNumProbesFromFilterData(), 6);
745 BloomHash(FilterData()),
746 SelectByImpl(SelectByCacheLineSize(1478976371, 2910591341U, 1182970461),
748 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
749 EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
753 for (int key
= /*CHANGED*/ 1; key
< 2087; key
++) {
754 Add(Key(key
, buffer
));
757 EXPECT_EQ(GetNumProbesFromFilterData(), 6);
759 BloomHash(FilterData()),
760 SelectByImpl(SelectByCacheLineSize(4205696321U, 1132081253U, 2385981855U),
762 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
763 EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
767 for (int key
= 1; key
< /*CHANGED*/ 2088; key
++) {
768 Add(Key(key
, buffer
));
771 EXPECT_EQ(GetNumProbesFromFilterData(), 6);
773 BloomHash(FilterData()),
774 SelectByImpl(SelectByCacheLineSize(2885052954U, 769447944, 4175124908U),
776 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
777 EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
780 // With new fractional bits_per_key, check that we are rounding to
781 // whole bits per key for old Bloom filters but fractional for
784 for (int key
= 1; key
< 2088; key
++) {
785 Add(Key(key
, buffer
));
788 EXPECT_EQ(GetNumProbesFromFilterData(), 6);
789 EXPECT_EQ(BloomHash(FilterData()),
790 SelectByImpl(/*SAME*/ SelectByCacheLineSize(2885052954U, 769447944,
792 /*CHANGED*/ 3166884174U));
793 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
794 EXPECT_EQ(/*CHANGED*/ "126,156,367,444,458,791,813,976,1015,1035",
799 for (int key
= 1; key
< 2088; key
++) {
800 Add(Key(key
, buffer
));
803 EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
805 EXPECT_EQ(BloomHash(FilterData()),
806 SelectByImpl(/*SAME*/ SelectByCacheLineSize(2885052954U, 769447944,
808 /*CHANGED*/ 4098502778U));
809 if (GetParam() == BloomFilterPolicy::kFastLocalBloom
) {
810 EXPECT_EQ(/*CHANGED*/ "16,236,240,472,1015,1045,1111,1409,1465,1612",
817 // A helper class for testing custom or corrupt filter bits as read by
818 // built-in FilterBitsReaders.
819 struct RawFilterTester
{
820 // Buffer, from which we always return a tail Slice, so the
821 // last five bytes are always the metadata bytes.
822 std::array
<char, 3000> data_
;
823 // Points five bytes from the end
826 RawFilterTester() : metadata_ptr_(&*(data_
.end() - 5)) {}
828 Slice
ResetNoFill(uint32_t len_without_metadata
, uint32_t num_lines
,
829 uint32_t num_probes
) {
830 metadata_ptr_
[0] = static_cast<char>(num_probes
);
831 EncodeFixed32(metadata_ptr_
+ 1, num_lines
);
832 uint32_t len
= len_without_metadata
+ /*metadata*/ 5;
833 assert(len
<= data_
.size());
834 return Slice(metadata_ptr_
- len_without_metadata
, len
);
837 Slice
Reset(uint32_t len_without_metadata
, uint32_t num_lines
,
838 uint32_t num_probes
, bool fill_ones
) {
839 data_
.fill(fill_ones
? 0xff : 0);
840 return ResetNoFill(len_without_metadata
, num_lines
, num_probes
);
843 Slice
ResetWeirdFill(uint32_t len_without_metadata
, uint32_t num_lines
,
844 uint32_t num_probes
) {
845 for (uint32_t i
= 0; i
< data_
.size(); ++i
) {
846 data_
[i
] = static_cast<char>(0x7b7b >> (i
% 7));
848 return ResetNoFill(len_without_metadata
, num_lines
, num_probes
);
852 TEST_P(FullBloomTest
, RawSchema
) {
854 // Two probes, about 3/4 bits set: ~50% "FP" rate
855 // One 256-byte cache line.
856 OpenRaw(cft
.ResetWeirdFill(256, 1, 2));
857 EXPECT_EQ(uint64_t{11384799501900898790U}, PackedMatches());
859 // Two 128-byte cache lines.
860 OpenRaw(cft
.ResetWeirdFill(256, 2, 2));
861 EXPECT_EQ(uint64_t{10157853359773492589U}, PackedMatches());
863 // Four 64-byte cache lines.
864 OpenRaw(cft
.ResetWeirdFill(256, 4, 2));
865 EXPECT_EQ(uint64_t{7123594913907464682U}, PackedMatches());
868 TEST_P(FullBloomTest
, CorruptFilters
) {
871 for (bool fill
: {false, true}) {
872 // Good filter bits - returns same as fill
873 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 6, fill
));
874 ASSERT_EQ(fill
, Matches("hello"));
875 ASSERT_EQ(fill
, Matches("world"));
877 // Good filter bits - returns same as fill
878 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
* 3, 3, 6, fill
));
879 ASSERT_EQ(fill
, Matches("hello"));
880 ASSERT_EQ(fill
, Matches("world"));
882 // Good filter bits - returns same as fill
883 // 256 is unusual but legal cache line size
884 OpenRaw(cft
.Reset(256 * 3, 3, 6, fill
));
885 ASSERT_EQ(fill
, Matches("hello"));
886 ASSERT_EQ(fill
, Matches("world"));
888 // Good filter bits - returns same as fill
889 // 30 should be max num_probes
890 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 30, fill
));
891 ASSERT_EQ(fill
, Matches("hello"));
892 ASSERT_EQ(fill
, Matches("world"));
894 // Good filter bits - returns same as fill
895 // 1 should be min num_probes
896 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 1, fill
));
897 ASSERT_EQ(fill
, Matches("hello"));
898 ASSERT_EQ(fill
, Matches("world"));
900 // Type 1 trivial filter bits - returns true as if FP by zero probes
901 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 0, fill
));
902 ASSERT_TRUE(Matches("hello"));
903 ASSERT_TRUE(Matches("world"));
905 // Type 2 trivial filter bits - returns false as if built from zero keys
906 OpenRaw(cft
.Reset(0, 0, 6, fill
));
907 ASSERT_FALSE(Matches("hello"));
908 ASSERT_FALSE(Matches("world"));
910 // Type 2 trivial filter bits - returns false as if built from zero keys
911 OpenRaw(cft
.Reset(0, 37, 6, fill
));
912 ASSERT_FALSE(Matches("hello"));
913 ASSERT_FALSE(Matches("world"));
915 // Type 2 trivial filter bits - returns false as 0 size trumps 0 probes
916 OpenRaw(cft
.Reset(0, 0, 0, fill
));
917 ASSERT_FALSE(Matches("hello"));
918 ASSERT_FALSE(Matches("world"));
920 // Bad filter bits - returns true for safety
921 // No solution to 0 * x == CACHE_LINE_SIZE
922 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 0, 6, fill
));
923 ASSERT_TRUE(Matches("hello"));
924 ASSERT_TRUE(Matches("world"));
926 // Bad filter bits - returns true for safety
927 // Can't have 3 * x == 4 for integer x
928 OpenRaw(cft
.Reset(4, 3, 6, fill
));
929 ASSERT_TRUE(Matches("hello"));
930 ASSERT_TRUE(Matches("world"));
932 // Bad filter bits - returns true for safety
933 // 97 bytes is not a power of two, so not a legal cache line size
934 OpenRaw(cft
.Reset(97 * 3, 3, 6, fill
));
935 ASSERT_TRUE(Matches("hello"));
936 ASSERT_TRUE(Matches("world"));
938 // Bad filter bits - returns true for safety
939 // 65 bytes is not a power of two, so not a legal cache line size
940 OpenRaw(cft
.Reset(65 * 3, 3, 6, fill
));
941 ASSERT_TRUE(Matches("hello"));
942 ASSERT_TRUE(Matches("world"));
944 // Bad filter bits - returns false as if built from zero keys
945 // < 5 bytes overall means missing even metadata
946 OpenRaw(cft
.Reset(static_cast<uint32_t>(-1), 3, 6, fill
));
947 ASSERT_FALSE(Matches("hello"));
948 ASSERT_FALSE(Matches("world"));
950 OpenRaw(cft
.Reset(static_cast<uint32_t>(-5), 3, 6, fill
));
951 ASSERT_FALSE(Matches("hello"));
952 ASSERT_FALSE(Matches("world"));
954 // Dubious filter bits - returns same as fill (for now)
955 // 31 is not a useful num_probes, nor generated by RocksDB unless directly
956 // using filter bits API without BloomFilterPolicy.
957 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 31, fill
));
958 ASSERT_EQ(fill
, Matches("hello"));
959 ASSERT_EQ(fill
, Matches("world"));
961 // Dubious filter bits - returns same as fill (for now)
962 // Similar, with 127, largest positive char
963 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 127, fill
));
964 ASSERT_EQ(fill
, Matches("hello"));
965 ASSERT_EQ(fill
, Matches("world"));
967 // Dubious filter bits - returns true (for now)
968 // num_probes set to 128 / -128, lowest negative char
969 // NB: Bug in implementation interprets this as negative and has same
970 // effect as zero probes, but effectively reserves negative char values
972 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 128, fill
));
973 ASSERT_TRUE(Matches("hello"));
974 ASSERT_TRUE(Matches("world"));
976 // Dubious filter bits - returns true (for now)
977 // Similar, with 255 / -1
978 OpenRaw(cft
.Reset(CACHE_LINE_SIZE
, 1, 255, fill
));
979 ASSERT_TRUE(Matches("hello"));
980 ASSERT_TRUE(Matches("world"));
984 INSTANTIATE_TEST_CASE_P(Full
, FullBloomTest
,
985 testing::Values(BloomFilterPolicy::kLegacyBloom
,
986 BloomFilterPolicy::kFastLocalBloom
,
987 BloomFilterPolicy::kStandard128Ribbon
));
989 } // namespace ROCKSDB_NAMESPACE
991 int main(int argc
, char** argv
) {
992 ::testing::InitGoogleTest(&argc
, argv
);
993 ParseCommandLineFlags(&argc
, &argv
, true);
995 return RUN_ALL_TESTS();