#include <cmath>
#include <vector>
+#include "cache/cache_entry_roles.h"
+#include "cache/cache_reservation_manager.h"
#include "memory/arena.h"
#include "port/jemalloc_helper.h"
#include "rocksdb/filter_policy.h"
using GFLAGS_NAMESPACE::ParseCommandLineFlags;
+// The test is not fully designed for bits_per_key other than 10, but with
+// this parameter you can easily explore the behavior of other bits_per_key.
+// See also filter_bench.
DEFINE_int32(bits_per_key, 10, "");
namespace ROCKSDB_NAMESPACE {
+namespace {
+const std::string kLegacyBloom = test::LegacyBloomFilterPolicy::kClassName();
+const std::string kFastLocalBloom =
+ test::FastLocalBloomFilterPolicy::kClassName();
+const std::string kStandard128Ribbon =
+ test::Standard128RibbonFilterPolicy::kClassName();
+} // namespace
+
static const int kVerbose = 1;
static Slice Key(int i, char* buffer) {
return length;
}
-class BlockBasedBloomTest : public testing::Test {
- private:
- std::unique_ptr<const FilterPolicy> policy_;
- std::string filter_;
- std::vector<std::string> keys_;
-
- public:
- BlockBasedBloomTest() { ResetPolicy(); }
-
- void Reset() {
- keys_.clear();
- filter_.clear();
- }
-
- void ResetPolicy(double bits_per_key) {
- policy_.reset(new BloomFilterPolicy(bits_per_key,
- BloomFilterPolicy::kDeprecatedBlock));
- Reset();
- }
-
- void ResetPolicy() { ResetPolicy(FLAGS_bits_per_key); }
-
- void Add(const Slice& s) {
- keys_.push_back(s.ToString());
- }
-
- void Build() {
- std::vector<Slice> key_slices;
- for (size_t i = 0; i < keys_.size(); i++) {
- key_slices.push_back(Slice(keys_[i]));
- }
- filter_.clear();
- policy_->CreateFilter(&key_slices[0], static_cast<int>(key_slices.size()),
- &filter_);
- keys_.clear();
- if (kVerbose >= 2) DumpFilter();
- }
-
- size_t FilterSize() const {
- return filter_.size();
- }
-
- Slice FilterData() const { return Slice(filter_); }
-
- void DumpFilter() {
- fprintf(stderr, "F(");
- for (size_t i = 0; i+1 < filter_.size(); i++) {
- const unsigned int c = static_cast<unsigned int>(filter_[i]);
- for (int j = 0; j < 8; j++) {
- fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.');
- }
- }
- fprintf(stderr, ")\n");
- }
-
- bool Matches(const Slice& s) {
- if (!keys_.empty()) {
- Build();
- }
- return policy_->KeyMayMatch(s, filter_);
- }
-
- double FalsePositiveRate() {
- char buffer[sizeof(int)];
- int result = 0;
- for (int i = 0; i < 10000; i++) {
- if (Matches(Key(i + 1000000000, buffer))) {
- result++;
- }
- }
- return result / 10000.0;
- }
-};
-
-TEST_F(BlockBasedBloomTest, EmptyFilter) {
- ASSERT_TRUE(! Matches("hello"));
- ASSERT_TRUE(! Matches("world"));
-}
-
-TEST_F(BlockBasedBloomTest, Small) {
- Add("hello");
- Add("world");
- ASSERT_TRUE(Matches("hello"));
- ASSERT_TRUE(Matches("world"));
- ASSERT_TRUE(! Matches("x"));
- ASSERT_TRUE(! Matches("foo"));
-}
-
-TEST_F(BlockBasedBloomTest, VaryingLengths) {
- char buffer[sizeof(int)];
-
- // Count number of filters that significantly exceed the false positive rate
- int mediocre_filters = 0;
- int good_filters = 0;
-
- for (int length = 1; length <= 10000; length = NextLength(length)) {
- Reset();
- for (int i = 0; i < length; i++) {
- Add(Key(i, buffer));
- }
- Build();
-
- ASSERT_LE(FilterSize(), (size_t)((length * 10 / 8) + 40)) << length;
-
- // All added keys must match
- for (int i = 0; i < length; i++) {
- ASSERT_TRUE(Matches(Key(i, buffer)))
- << "Length " << length << "; key " << i;
- }
-
- // Check false positive rate
- double rate = FalsePositiveRate();
- if (kVerbose >= 1) {
- fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
- rate*100.0, length, static_cast<int>(FilterSize()));
- }
- ASSERT_LE(rate, 0.02); // Must not be over 2%
- if (rate > 0.0125) mediocre_filters++; // Allowed, but not too often
- else good_filters++;
- }
- if (kVerbose >= 1) {
- fprintf(stderr, "Filters: %d good, %d mediocre\n",
- good_filters, mediocre_filters);
- }
- ASSERT_LE(mediocre_filters, good_filters/5);
-}
-
-// Ensure the implementation doesn't accidentally change in an
-// incompatible way
-TEST_F(BlockBasedBloomTest, Schema) {
- char buffer[sizeof(int)];
-
- ResetPolicy(8); // num_probes = 5
- for (int key = 0; key < 87; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 3589896109U);
-
- ResetPolicy(9); // num_probes = 6
- for (int key = 0; key < 87; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 969445585U);
-
- ResetPolicy(11); // num_probes = 7
- for (int key = 0; key < 87; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 1694458207U);
-
- ResetPolicy(10); // num_probes = 6
- for (int key = 0; key < 87; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 2373646410U);
-
- ResetPolicy(10);
- for (int key = /*CHANGED*/ 1; key < 87; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 1908442116U);
-
- ResetPolicy(10);
- for (int key = 1; key < /*CHANGED*/ 88; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), 3057004015U);
-
- // With new fractional bits_per_key, check that we are rounding to
- // whole bits per key for old Bloom filters.
- ResetPolicy(9.5); // Treated as 10
- for (int key = 1; key < 88; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), /*SAME*/ 3057004015U);
-
- ResetPolicy(10.499); // Treated as 10
- for (int key = 1; key < 88; key++) {
- Add(Key(key, buffer));
- }
- Build();
- ASSERT_EQ(BloomHash(FilterData()), /*SAME*/ 3057004015U);
-
- ResetPolicy();
-}
-
-// Different bits-per-byte
-
-class FullBloomTest : public testing::TestWithParam<BloomFilterPolicy::Mode> {
+class FullBloomTest : public testing::TestWithParam<std::string> {
protected:
BlockBasedTableOptions table_options_;
BuiltinFilterBitsBuilder* GetBuiltinFilterBitsBuilder() {
// Throws on bad cast
- return &dynamic_cast<BuiltinFilterBitsBuilder&>(*bits_builder_);
+ return dynamic_cast<BuiltinFilterBitsBuilder*>(bits_builder_.get());
}
- const BloomFilterPolicy* GetBloomFilterPolicy() {
+ const BloomLikeFilterPolicy* GetBloomLikeFilterPolicy() {
// Throws on bad cast
- return &dynamic_cast<const BloomFilterPolicy&>(*policy_);
+ return &dynamic_cast<const BloomLikeFilterPolicy&>(*policy_);
}
void Reset() {
}
void ResetPolicy(double bits_per_key) {
- policy_.reset(new BloomFilterPolicy(bits_per_key, GetParam()));
+ policy_ = BloomLikeFilterPolicy::Create(GetParam(), bits_per_key);
Reset();
}
void ResetPolicy() { ResetPolicy(FLAGS_bits_per_key); }
- void Add(const Slice& s) {
- bits_builder_->AddKey(s);
- }
+ void Add(const Slice& s) { bits_builder_->AddKey(s); }
void OpenRaw(const Slice& s) {
bits_reader_.reset(policy_->GetFilterBitsReader(s));
filter_size_ = filter.size();
}
- size_t FilterSize() const {
- return filter_size_;
- }
+ size_t FilterSize() const { return filter_size_; }
Slice FilterData() { return Slice(buf_.get(), filter_size_); }
}
}
+ int GetRibbonSeedFromFilterData() {
+ assert(filter_size_ >= 5);
+ // Check for ribbon marker
+ assert(-2 == static_cast<int8_t>(buf_.get()[filter_size_ - 5]));
+ return static_cast<uint8_t>(buf_.get()[filter_size_ - 4]);
+ }
+
bool Matches(const Slice& s) {
if (bits_reader_ == nullptr) {
Build();
}
return result / 10000.0;
}
-
- uint32_t SelectByImpl(uint32_t for_legacy_bloom,
- uint32_t for_fast_local_bloom) {
- switch (GetParam()) {
- case BloomFilterPolicy::kLegacyBloom:
- return for_legacy_bloom;
- case BloomFilterPolicy::kFastLocalBloom:
- return for_fast_local_bloom;
- case BloomFilterPolicy::kDeprecatedBlock:
- case BloomFilterPolicy::kAutoBloom:
- case BloomFilterPolicy::kStandard128Ribbon:
- /* N/A */;
- }
- // otherwise
- assert(false);
- return 0;
- }
};
TEST_P(FullBloomTest, FilterSize) {
// checking that denoted and computed doubles are interpreted as expected
// as bits_per_key values.
bool some_computed_less_than_denoted = false;
- // Note: enforced minimum is 1 bit per key (1000 millibits), and enforced
- // maximum is 100 bits per key (100000 millibits).
- for (auto bpk :
- std::vector<std::pair<double, int> >{{-HUGE_VAL, 1000},
- {-INFINITY, 1000},
- {0.0, 1000},
- {1.234, 1234},
- {3.456, 3456},
- {9.5, 9500},
- {10.0, 10000},
- {10.499, 10499},
- {21.345, 21345},
- {99.999, 99999},
- {1234.0, 100000},
- {HUGE_VAL, 100000},
- {INFINITY, 100000},
- {NAN, 100000}}) {
+ // Note: to avoid unproductive configurations, bits_per_key < 0.5 is rounded
+ // down to 0 (no filter), and 0.5 <= bits_per_key < 1.0 is rounded up to 1
+ // bit per key (1000 millibits). Also, enforced maximum is 100 bits per key
+ // (100000 millibits).
+ for (auto bpk : std::vector<std::pair<double, int> >{{-HUGE_VAL, 0},
+ {-INFINITY, 0},
+ {0.0, 0},
+ {0.499, 0},
+ {0.5, 1000},
+ {1.234, 1234},
+ {3.456, 3456},
+ {9.5, 9500},
+ {10.0, 10000},
+ {10.499, 10499},
+ {21.345, 21345},
+ {99.999, 99999},
+ {1234.0, 100000},
+ {HUGE_VAL, 100000},
+ {INFINITY, 100000},
+ {NAN, 100000}}) {
ResetPolicy(bpk.first);
- auto bfp = GetBloomFilterPolicy();
+ auto bfp = GetBloomLikeFilterPolicy();
EXPECT_EQ(bpk.second, bfp->GetMillibitsPerKey());
EXPECT_EQ((bpk.second + 500) / 1000, bfp->GetWholeBitsPerKey());
computed -= 0.5;
some_computed_less_than_denoted |= (computed < bpk.first);
ResetPolicy(computed);
- bfp = GetBloomFilterPolicy();
+ bfp = GetBloomLikeFilterPolicy();
EXPECT_EQ(bpk.second, bfp->GetMillibitsPerKey());
EXPECT_EQ((bpk.second + 500) / 1000, bfp->GetWholeBitsPerKey());
auto bits_builder = GetBuiltinFilterBitsBuilder();
- for (int n = 1; n < 100; n++) {
- auto space = bits_builder->CalculateSpace(n);
- auto n2 = bits_builder->CalculateNumEntry(space);
+ if (bpk.second == 0) {
+ ASSERT_EQ(bits_builder, nullptr);
+ continue;
+ }
+
+ size_t n = 1;
+ size_t space = 0;
+ for (; n < 1000000; n += 1 + n / 1000) {
+ // Ensure consistency between CalculateSpace and ApproximateNumEntries
+ space = bits_builder->CalculateSpace(n);
+ size_t n2 = bits_builder->ApproximateNumEntries(space);
EXPECT_GE(n2, n);
- auto space2 = bits_builder->CalculateSpace(n2);
- EXPECT_EQ(space, space2);
+ size_t space2 = bits_builder->CalculateSpace(n2);
+ if (n > 12000 && GetParam() == kStandard128Ribbon) {
+ // TODO(peterd): better approximation?
+ EXPECT_GE(space2, space);
+ EXPECT_LE(space2 * 0.998, space * 1.0);
+ } else {
+ EXPECT_EQ(space2, space);
+ }
+ }
+ // Until size_t overflow
+ for (; n < (n + n / 3); n += n / 3) {
+ // Ensure space computation is not overflowing; capped is OK
+ size_t space2 = bits_builder->CalculateSpace(n);
+ EXPECT_GE(space2, space);
+ space = space2;
}
}
// Check that the compiler hasn't optimized our computation into nothing
}
Build();
- EXPECT_LE(FilterSize(),
- (size_t)((length * 10 / 8) + CACHE_LINE_SIZE * 2 + 5));
+ EXPECT_LE(FilterSize(), (size_t)((length * FLAGS_bits_per_key / 8) +
+ CACHE_LINE_SIZE * 2 + 5));
// All added keys must match
for (int i = 0; i < length; i++) {
double rate = FalsePositiveRate();
if (kVerbose >= 1) {
fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
- rate*100.0, length, static_cast<int>(FilterSize()));
+ rate * 100.0, length, static_cast<int>(FilterSize()));
+ }
+ if (FLAGS_bits_per_key == 10) {
+ EXPECT_LE(rate, 0.02); // Must not be over 2%
+ if (rate > 0.0125) {
+ mediocre_filters++; // Allowed, but not too often
+ } else {
+ good_filters++;
+ }
}
- EXPECT_LE(rate, 0.02); // Must not be over 2%
- if (rate > 0.0125)
- mediocre_filters++; // Allowed, but not too often
- else
- good_filters++;
}
if (kVerbose >= 1) {
- fprintf(stderr, "Filters: %d good, %d mediocre\n",
- good_filters, mediocre_filters);
+ fprintf(stderr, "Filters: %d good, %d mediocre\n", good_filters,
+ mediocre_filters);
}
EXPECT_LE(mediocre_filters, good_filters / 5);
}
TEST_P(FullBloomTest, OptimizeForMemory) {
- if (GetParam() == BloomFilterPolicy::kStandard128Ribbon) {
- // TODO Not yet implemented
- return;
- }
char buffer[sizeof(int)];
for (bool offm : {true, false}) {
table_options_.optimize_filters_for_memory = offm;
total_keys += nkeys;
total_fp_rate += FalsePositiveRate();
}
- EXPECT_LE(total_fp_rate / double{nfilters}, 0.011);
- EXPECT_GE(total_fp_rate / double{nfilters}, 0.008);
+ if (FLAGS_bits_per_key == 10) {
+ EXPECT_LE(total_fp_rate / double{nfilters}, 0.011);
+ EXPECT_GE(total_fp_rate / double{nfilters},
+ CACHE_LINE_SIZE >= 256 ? 0.007 : 0.008);
+ }
int64_t ex_min_total_size = int64_t{FLAGS_bits_per_key} * total_keys / 8;
+ if (GetParam() == kStandard128Ribbon) {
+ // ~ 30% savings vs. Bloom filter
+ ex_min_total_size = 7 * ex_min_total_size / 10;
+ }
EXPECT_GE(static_cast<int64_t>(total_size), ex_min_total_size);
int64_t blocked_bloom_overhead = nfilters * (CACHE_LINE_SIZE + 5);
- if (GetParam() == BloomFilterPolicy::kLegacyBloom) {
+ if (GetParam() == kLegacyBloom) {
// this config can add extra cache line to make odd number
blocked_bloom_overhead += nfilters * CACHE_LINE_SIZE;
}
EXPECT_GE(total_mem, total_size);
// optimize_filters_for_memory not implemented with legacy Bloom
- if (offm && GetParam() != BloomFilterPolicy::kLegacyBloom) {
+ if (offm && GetParam() != kLegacyBloom) {
// This value can include a small extra penalty for kExtraPadding
fprintf(stderr, "Internal fragmentation (optimized): %g%%\n",
(total_mem - total_size) * 100.0 / total_size);
#ifdef ROCKSDB_JEMALLOC
fprintf(stderr, "Jemalloc detected? %d\n", HasJemalloc());
if (HasJemalloc()) {
+#ifdef ROCKSDB_MALLOC_USABLE_SIZE
// More than 5% internal fragmentation
EXPECT_GE(total_mem, total_size * 105 / 100);
+#endif // ROCKSDB_MALLOC_USABLE_SIZE
}
#endif // ROCKSDB_JEMALLOC
// No storage penalty, just usual overhead
}
}
+class ChargeFilterConstructionTest : public testing::Test {};
+TEST_F(ChargeFilterConstructionTest, RibbonFilterFallBackOnLargeBanding) {
+ constexpr std::size_t kCacheCapacity =
+ 8 * CacheReservationManagerImpl<
+ CacheEntryRole::kFilterConstruction>::GetDummyEntrySize();
+ constexpr std::size_t num_entries_for_cache_full = kCacheCapacity / 8;
+
+ for (CacheEntryRoleOptions::Decision charge_filter_construction_mem :
+ {CacheEntryRoleOptions::Decision::kEnabled,
+ CacheEntryRoleOptions::Decision::kDisabled}) {
+ bool will_fall_back = charge_filter_construction_mem ==
+ CacheEntryRoleOptions::Decision::kEnabled;
+
+ BlockBasedTableOptions table_options;
+ table_options.cache_usage_options.options_overrides.insert(
+ {CacheEntryRole::kFilterConstruction,
+ {/*.charged = */ charge_filter_construction_mem}});
+ LRUCacheOptions lo;
+ lo.capacity = kCacheCapacity;
+ lo.num_shard_bits = 0; // 2^0 shard
+ lo.strict_capacity_limit = true;
+ std::shared_ptr<Cache> cache(NewLRUCache(lo));
+ table_options.block_cache = cache;
+ table_options.filter_policy =
+ BloomLikeFilterPolicy::Create(kStandard128Ribbon, FLAGS_bits_per_key);
+ FilterBuildingContext ctx(table_options);
+ std::unique_ptr<FilterBitsBuilder> filter_bits_builder(
+ table_options.filter_policy->GetBuilderWithContext(ctx));
+
+ char key_buffer[sizeof(int)];
+ for (std::size_t i = 0; i < num_entries_for_cache_full; ++i) {
+ filter_bits_builder->AddKey(Key(static_cast<int>(i), key_buffer));
+ }
+
+ std::unique_ptr<const char[]> buf;
+ Slice filter = filter_bits_builder->Finish(&buf);
+
+ // To verify Ribbon Filter fallbacks to Bloom Filter properly
+ // based on cache charging result
+ // See BloomFilterPolicy::GetBloomBitsReader re: metadata
+ // -1 = Marker for newer Bloom implementations
+ // -2 = Marker for Standard128 Ribbon
+ if (will_fall_back) {
+ EXPECT_EQ(filter.data()[filter.size() - 5], static_cast<char>(-1));
+ } else {
+ EXPECT_EQ(filter.data()[filter.size() - 5], static_cast<char>(-2));
+ }
+
+ if (charge_filter_construction_mem ==
+ CacheEntryRoleOptions::Decision::kEnabled) {
+ const size_t dummy_entry_num = static_cast<std::size_t>(std::ceil(
+ filter.size() * 1.0 /
+ CacheReservationManagerImpl<
+ CacheEntryRole::kFilterConstruction>::GetDummyEntrySize()));
+ EXPECT_GE(
+ cache->GetPinnedUsage(),
+ dummy_entry_num *
+ CacheReservationManagerImpl<
+ CacheEntryRole::kFilterConstruction>::GetDummyEntrySize());
+ EXPECT_LT(
+ cache->GetPinnedUsage(),
+ (dummy_entry_num + 1) *
+ CacheReservationManagerImpl<
+ CacheEntryRole::kFilterConstruction>::GetDummyEntrySize());
+ } else {
+ EXPECT_EQ(cache->GetPinnedUsage(), 0);
+ }
+ }
+}
+
namespace {
inline uint32_t SelectByCacheLineSize(uint32_t for64, uint32_t for128,
uint32_t for256) {
// ability to read filters generated using other cache line sizes.
// See RawSchema.
TEST_P(FullBloomTest, Schema) {
- if (GetParam() == BloomFilterPolicy::kStandard128Ribbon) {
- // TODO ASAP to ensure schema stability
- return;
+#define EXPECT_EQ_Bloom(a, b) \
+ { \
+ if (GetParam() != kStandard128Ribbon) { \
+ EXPECT_EQ(a, b); \
+ } \
+ }
+#define EXPECT_EQ_Ribbon(a, b) \
+ { \
+ if (GetParam() == kStandard128Ribbon) { \
+ EXPECT_EQ(a, b); \
+ } \
+ }
+#define EXPECT_EQ_FastBloom(a, b) \
+ { \
+ if (GetParam() == kFastLocalBloom) { \
+ EXPECT_EQ(a, b); \
+ } \
+ }
+#define EXPECT_EQ_LegacyBloom(a, b) \
+ { \
+ if (GetParam() == kLegacyBloom) { \
+ EXPECT_EQ(a, b); \
+ } \
+ }
+#define EXPECT_EQ_NotLegacy(a, b) \
+ { \
+ if (GetParam() != kLegacyBloom) { \
+ EXPECT_EQ(a, b); \
+ } \
}
+
char buffer[sizeof(int)];
- // Use enough keys so that changing bits / key by 1 is guaranteed to
+ // First do a small number of keys, where Ribbon config will fall back on
+ // fast Bloom filter and generate the same data
+ ResetPolicy(5); // num_probes = 3
+ for (int key = 0; key < 87; key++) {
+ Add(Key(key, buffer));
+ }
+ Build();
+ EXPECT_EQ(GetNumProbesFromFilterData(), 3);
+
+ EXPECT_EQ_NotLegacy(BloomHash(FilterData()), 4130687756U);
+
+ EXPECT_EQ_NotLegacy("31,38,40,43,61,83,86,112,125,131", FirstFPs(10));
+
+ // Now use enough keys so that changing bits / key by 1 is guaranteed to
// change number of allocated cache lines. So keys > max cache line bits.
+ // Note that the first attempted Ribbon seed is determined by the hash
+ // of the first key added (for pseudorandomness in practice, determinism in
+ // testing)
+
ResetPolicy(2); // num_probes = 1
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 1);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 1);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(1567096579, 1964771444, 2659542661U),
- 3817481309U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("11,13,17,25,29,30,35,37,45,53", FirstFPs(10));
- }
+ SelectByCacheLineSize(1567096579, 1964771444, 2659542661U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 3817481309U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1705851228U);
+
+ EXPECT_EQ_FastBloom("11,13,17,25,29,30,35,37,45,53", FirstFPs(10));
+ EXPECT_EQ_Ribbon("3,8,10,17,19,20,23,28,31,32", FirstFPs(10));
ResetPolicy(3); // num_probes = 2
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 2);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 2);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(2707206547U, 2571983456U, 218344685),
- 2807269961U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("4,15,17,24,27,28,29,53,63,70", FirstFPs(10));
- }
+ SelectByCacheLineSize(2707206547U, 2571983456U, 218344685));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 2807269961U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1095342358U);
+
+ EXPECT_EQ_FastBloom("4,15,17,24,27,28,29,53,63,70", FirstFPs(10));
+ EXPECT_EQ_Ribbon("3,17,20,28,32,33,36,43,49,54", FirstFPs(10));
ResetPolicy(5); // num_probes = 3
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 3);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 3);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(515748486, 94611728, 2436112214U),
- 204628445));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("15,24,29,39,53,87,89,100,103,104", FirstFPs(10));
- }
+ SelectByCacheLineSize(515748486, 94611728, 2436112214U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 204628445U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 3971337699U);
+
+ EXPECT_EQ_FastBloom("15,24,29,39,53,87,89,100,103,104", FirstFPs(10));
+ EXPECT_EQ_Ribbon("3,33,36,43,67,70,76,78,84,102", FirstFPs(10));
ResetPolicy(8); // num_probes = 5
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 5);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 5);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(1302145999, 2811644657U, 756553699),
- 355564975));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("16,60,66,126,220,238,244,256,265,287", FirstFPs(10));
- }
+ SelectByCacheLineSize(1302145999, 2811644657U, 756553699));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 355564975U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 3651449053U);
+
+ EXPECT_EQ_FastBloom("16,60,66,126,220,238,244,256,265,287", FirstFPs(10));
+ EXPECT_EQ_Ribbon("33,187,203,296,300,322,411,419,547,582", FirstFPs(10));
ResetPolicy(9); // num_probes = 6
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 6);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(2092755149, 661139132, 1182970461),
- 2137566013U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("156,367,791,872,945,1015,1139,1159,1265,1435", FirstFPs(10));
- }
+ SelectByCacheLineSize(2092755149, 661139132, 1182970461));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 2137566013U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1005676675U);
+
+ EXPECT_EQ_FastBloom("156,367,791,872,945,1015,1139,1159,1265", FirstFPs(9));
+ EXPECT_EQ_Ribbon("33,187,203,296,411,419,604,612,615,619", FirstFPs(10));
ResetPolicy(11); // num_probes = 7
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 7);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 7);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(3755609649U, 1812694762, 1449142939),
- 2561502687U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("34,74,130,236,643,882,962,1015,1035,1110", FirstFPs(10));
- }
+ SelectByCacheLineSize(3755609649U, 1812694762, 1449142939));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 2561502687U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 3129900846U);
+
+ EXPECT_EQ_FastBloom("34,74,130,236,643,882,962,1015,1035,1110", FirstFPs(10));
+ EXPECT_EQ_Ribbon("411,419,623,665,727,794,955,1052,1323,1330", FirstFPs(10));
// This used to be 9 probes, but 8 is a better choice for speed,
// especially with SIMD groups of 8 probes, with essentially no
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
- SelectByImpl(9, 8));
- EXPECT_EQ(
+ EXPECT_EQ_LegacyBloom(GetNumProbesFromFilterData(), 9);
+ EXPECT_EQ_FastBloom(GetNumProbesFromFilterData(), 8);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(178861123, 379087593, 2574136516U),
- 3709876890U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("130,240,522,565,989,2002,2526,3147,3543", FirstFPs(9));
- }
+ SelectByCacheLineSize(178861123, 379087593, 2574136516U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 3709876890U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1855638875U);
+
+ EXPECT_EQ_FastBloom("130,240,522,565,989,2002,2526,3147,3543", FirstFPs(9));
+ EXPECT_EQ_Ribbon("665,727,1323,1755,3866,4232,4442,4492,4736", FirstFPs(9));
// This used to be 11 probes, but 9 is a better choice for speed
// AND accuracy.
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
- SelectByImpl(11, 9));
- EXPECT_EQ(
+ EXPECT_EQ_LegacyBloom(GetNumProbesFromFilterData(), 11);
+ EXPECT_EQ_FastBloom(GetNumProbesFromFilterData(), 9);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(1129406313, 3049154394U, 1727750964),
- 1087138490));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("3299,3611,3916,6620,7822,8079,8482,8942,10167", FirstFPs(9));
- }
+ SelectByCacheLineSize(1129406313, 3049154394U, 1727750964));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 1087138490U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 459379967U);
+
+ EXPECT_EQ_FastBloom("3299,3611,3916,6620,7822,8079,8482,8942", FirstFPs(8));
+ EXPECT_EQ_Ribbon("727,1323,1755,4442,4736,5386,6974,7154,8222", FirstFPs(9));
ResetPolicy(10); // num_probes = 6, but different memory ratio vs. 9
for (int key = 0; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 6);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 61);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(1478976371, 2910591341U, 1182970461),
- 2498541272U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
- }
+ SelectByCacheLineSize(1478976371, 2910591341U, 1182970461));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 2498541272U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1273231667U);
+
+ EXPECT_EQ_FastBloom("16,126,133,422,466,472,813,1002,1035", FirstFPs(9));
+ EXPECT_EQ_Ribbon("296,411,419,612,619,623,630,665,686,727", FirstFPs(10));
ResetPolicy(10);
for (int key = /*CHANGED*/ 1; key < 2087; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 6);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), /*CHANGED*/ 184);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(4205696321U, 1132081253U, 2385981855U),
- 2058382345U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
- }
+ SelectByCacheLineSize(4205696321U, 1132081253U, 2385981855U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 2058382345U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 3007790572U);
+
+ EXPECT_EQ_FastBloom("16,126,133,422,466,472,813,1002,1035", FirstFPs(9));
+ EXPECT_EQ_Ribbon("33,152,383,497,589,633,737,781,911,990", FirstFPs(10));
ResetPolicy(10);
for (int key = 1; key < /*CHANGED*/ 2088; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 6);
- EXPECT_EQ(
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 184);
+
+ EXPECT_EQ_LegacyBloom(
BloomHash(FilterData()),
- SelectByImpl(SelectByCacheLineSize(2885052954U, 769447944, 4175124908U),
- 23699164));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ("16,126,133,422,466,472,813,1002,1035,1159", FirstFPs(10));
- }
+ SelectByCacheLineSize(2885052954U, 769447944, 4175124908U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 23699164U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1942323379U);
+
+ EXPECT_EQ_FastBloom("16,126,133,422,466,472,813,1002,1035", FirstFPs(9));
+ EXPECT_EQ_Ribbon("33,95,360,589,737,911,990,1048,1081,1414", FirstFPs(10));
// With new fractional bits_per_key, check that we are rounding to
// whole bits per key for old Bloom filters but fractional for
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(GetNumProbesFromFilterData(), 6);
- EXPECT_EQ(BloomHash(FilterData()),
- SelectByImpl(/*SAME*/ SelectByCacheLineSize(2885052954U, 769447944,
- 4175124908U),
- /*CHANGED*/ 3166884174U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ(/*CHANGED*/ "126,156,367,444,458,791,813,976,1015,1035",
- FirstFPs(10));
- }
+ EXPECT_EQ_Bloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 184);
+
+ EXPECT_EQ_LegacyBloom(
+ BloomHash(FilterData()),
+ /*SAME*/ SelectByCacheLineSize(2885052954U, 769447944, 4175124908U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 3166884174U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 1148258663U);
+
+ EXPECT_EQ_FastBloom("126,156,367,444,458,791,813,976,1015", FirstFPs(9));
+ EXPECT_EQ_Ribbon("33,54,95,360,589,693,737,911,990,1048", FirstFPs(10));
ResetPolicy(10.499);
for (int key = 1; key < 2088; key++) {
Add(Key(key, buffer));
}
Build();
- EXPECT_EQ(static_cast<uint32_t>(GetNumProbesFromFilterData()),
- SelectByImpl(6, 7));
- EXPECT_EQ(BloomHash(FilterData()),
- SelectByImpl(/*SAME*/ SelectByCacheLineSize(2885052954U, 769447944,
- 4175124908U),
- /*CHANGED*/ 4098502778U));
- if (GetParam() == BloomFilterPolicy::kFastLocalBloom) {
- EXPECT_EQ(/*CHANGED*/ "16,236,240,472,1015,1045,1111,1409,1465,1612",
- FirstFPs(10));
- }
+ EXPECT_EQ_LegacyBloom(GetNumProbesFromFilterData(), 6);
+ EXPECT_EQ_FastBloom(GetNumProbesFromFilterData(), 7);
+ EXPECT_EQ_Ribbon(GetRibbonSeedFromFilterData(), 184);
+
+ EXPECT_EQ_LegacyBloom(
+ BloomHash(FilterData()),
+ /*SAME*/ SelectByCacheLineSize(2885052954U, 769447944, 4175124908U));
+ EXPECT_EQ_FastBloom(BloomHash(FilterData()), 4098502778U);
+ EXPECT_EQ_Ribbon(BloomHash(FilterData()), 792138188U);
+
+ EXPECT_EQ_FastBloom("16,236,240,472,1015,1045,1111,1409,1465", FirstFPs(9));
+ EXPECT_EQ_Ribbon("33,95,360,589,737,990,1048,1081,1414,1643", FirstFPs(10));
ResetPolicy();
}
RawFilterTester() : metadata_ptr_(&*(data_.end() - 5)) {}
Slice ResetNoFill(uint32_t len_without_metadata, uint32_t num_lines,
- uint32_t num_probes) {
+ uint32_t num_probes) {
metadata_ptr_[0] = static_cast<char>(num_probes);
EncodeFixed32(metadata_ptr_ + 1, num_lines);
uint32_t len = len_without_metadata + /*metadata*/ 5;
}
Slice Reset(uint32_t len_without_metadata, uint32_t num_lines,
- uint32_t num_probes, bool fill_ones) {
+ uint32_t num_probes, bool fill_ones) {
data_.fill(fill_ones ? 0xff : 0);
return ResetNoFill(len_without_metadata, num_lines, num_probes);
}
Slice ResetWeirdFill(uint32_t len_without_metadata, uint32_t num_lines,
- uint32_t num_probes) {
+ uint32_t num_probes) {
for (uint32_t i = 0; i < data_.size(); ++i) {
data_[i] = static_cast<char>(0x7b7b >> (i % 7));
}
TEST_P(FullBloomTest, RawSchema) {
RawFilterTester cft;
+ // Legacy Bloom configurations
// Two probes, about 3/4 bits set: ~50% "FP" rate
// One 256-byte cache line.
OpenRaw(cft.ResetWeirdFill(256, 1, 2));
// Four 64-byte cache lines.
OpenRaw(cft.ResetWeirdFill(256, 4, 2));
EXPECT_EQ(uint64_t{7123594913907464682U}, PackedMatches());
+
+ // Fast local Bloom configurations (marker 255 -> -1)
+ // Two probes, about 3/4 bits set: ~50% "FP" rate
+ // Four 64-byte cache lines.
+ OpenRaw(cft.ResetWeirdFill(256, 2U << 8, 255));
+ EXPECT_EQ(uint64_t{9957045189927952471U}, PackedMatches());
+
+ // Ribbon configurations (marker 254 -> -2)
+
+ // Even though the builder never builds configurations this
+ // small (preferring Bloom), we can test that the configuration
+ // can be read, for possible future-proofing.
+
+ // 256 slots, one result column = 32 bytes (2 blocks, seed 0)
+ // ~50% FP rate:
+ // 0b0101010111110101010000110000011011011111100100001110010011101010
+ OpenRaw(cft.ResetWeirdFill(32, 2U << 8, 254));
+ EXPECT_EQ(uint64_t{6193930559317665002U}, PackedMatches());
+
+ // 256 slots, three-to-four result columns = 112 bytes
+ // ~ 1 in 10 FP rate:
+ // 0b0000000000100000000000000000000001000001000000010000101000000000
+ OpenRaw(cft.ResetWeirdFill(112, 2U << 8, 254));
+ EXPECT_EQ(uint64_t{9007200345328128U}, PackedMatches());
}
TEST_P(FullBloomTest, CorruptFilters) {
RawFilterTester cft;
for (bool fill : {false, true}) {
+ // Legacy Bloom configurations
// Good filter bits - returns same as fill
OpenRaw(cft.Reset(CACHE_LINE_SIZE, 1, 6, fill));
ASSERT_EQ(fill, Matches("hello"));
ASSERT_TRUE(Matches("world"));
// Dubious filter bits - returns true (for now)
- // Similar, with 255 / -1
- OpenRaw(cft.Reset(CACHE_LINE_SIZE, 1, 255, fill));
+ // Similar, with 253 / -3
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 1, 253, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ // #########################################################
+ // Fast local Bloom configurations (marker 255 -> -1)
+ // Good config with six probes
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 6U << 8, 255, fill));
+ ASSERT_EQ(fill, Matches("hello"));
+ ASSERT_EQ(fill, Matches("world"));
+
+ // Becomes bad/reserved config (always true) if any other byte set
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, (6U << 8) | 1U, 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, (6U << 8) | (1U << 16), 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, (6U << 8) | (1U << 24), 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ // Good config, max 30 probes
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 30U << 8, 255, fill));
+ ASSERT_EQ(fill, Matches("hello"));
+ ASSERT_EQ(fill, Matches("world"));
+
+ // Bad/reserved config (always true) if more than 30
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 31U << 8, 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 33U << 8, 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 66U << 8, 255, fill));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ OpenRaw(cft.Reset(CACHE_LINE_SIZE, 130U << 8, 255, fill));
ASSERT_TRUE(Matches("hello"));
ASSERT_TRUE(Matches("world"));
}
+
+ // #########################################################
+ // Ribbon configurations (marker 254 -> -2)
+ // ("fill" doesn't work to detect good configurations, we just
+ // have to rely on TN probability)
+
+ // Good: 2 blocks * 16 bytes / segment * 4 columns = 128 bytes
+ // seed = 123
+ OpenRaw(cft.Reset(128, (2U << 8) + 123U, 254, false));
+ ASSERT_FALSE(Matches("hello"));
+ ASSERT_FALSE(Matches("world"));
+
+ // Good: 2 blocks * 16 bytes / segment * 8 columns = 256 bytes
+ OpenRaw(cft.Reset(256, (2U << 8) + 123U, 254, false));
+ ASSERT_FALSE(Matches("hello"));
+ ASSERT_FALSE(Matches("world"));
+
+ // Surprisingly OK: 5000 blocks (640,000 slots) in only 1024 bits
+ // -> average close to 0 columns
+ OpenRaw(cft.Reset(128, (5000U << 8) + 123U, 254, false));
+ // *Almost* all FPs
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+ // Need many queries to find a "true negative"
+ for (int i = 0; Matches(std::to_string(i)); ++i) {
+ ASSERT_LT(i, 1000);
+ }
+
+ // Bad: 1 block not allowed (for implementation detail reasons)
+ OpenRaw(cft.Reset(128, (1U << 8) + 123U, 254, false));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
+
+ // Bad: 0 blocks not allowed
+ OpenRaw(cft.Reset(128, (0U << 8) + 123U, 254, false));
+ ASSERT_TRUE(Matches("hello"));
+ ASSERT_TRUE(Matches("world"));
}
INSTANTIATE_TEST_CASE_P(Full, FullBloomTest,
- testing::Values(BloomFilterPolicy::kLegacyBloom,
- BloomFilterPolicy::kFastLocalBloom,
- BloomFilterPolicy::kStandard128Ribbon));
+ testing::Values(kLegacyBloom, kFastLocalBloom,
+ kStandard128Ribbon));
+
+static double GetEffectiveBitsPerKey(FilterBitsBuilder* builder) {
+ union {
+ uint64_t key_value = 0;
+ char key_bytes[8];
+ };
+
+ const unsigned kNumKeys = 1000;
+
+ Slice key_slice{key_bytes, 8};
+ for (key_value = 0; key_value < kNumKeys; ++key_value) {
+ builder->AddKey(key_slice);
+ }
+
+ std::unique_ptr<const char[]> buf;
+ auto filter = builder->Finish(&buf);
+ return filter.size() * /*bits per byte*/ 8 / (1.0 * kNumKeys);
+}
+
+static void SetTestingLevel(int levelish, FilterBuildingContext* ctx) {
+ if (levelish == -1) {
+ // Flush is treated as level -1 for this option but actually level 0
+ ctx->level_at_creation = 0;
+ ctx->reason = TableFileCreationReason::kFlush;
+ } else {
+ ctx->level_at_creation = levelish;
+ ctx->reason = TableFileCreationReason::kCompaction;
+ }
+}
+
+TEST(RibbonTest, RibbonTestLevelThreshold) {
+ BlockBasedTableOptions opts;
+ FilterBuildingContext ctx(opts);
+ // A few settings
+ for (CompactionStyle cs : {kCompactionStyleLevel, kCompactionStyleUniversal,
+ kCompactionStyleFIFO, kCompactionStyleNone}) {
+ ctx.compaction_style = cs;
+ for (int bloom_before_level : {-1, 0, 1, 10}) {
+ std::vector<std::unique_ptr<const FilterPolicy> > policies;
+ policies.emplace_back(NewRibbonFilterPolicy(10, bloom_before_level));
+
+ if (bloom_before_level == 0) {
+ // Also test new API default
+ policies.emplace_back(NewRibbonFilterPolicy(10));
+ }
+
+ for (std::unique_ptr<const FilterPolicy>& policy : policies) {
+ // Claim to be generating filter for this level
+ SetTestingLevel(bloom_before_level, &ctx);
+
+ std::unique_ptr<FilterBitsBuilder> builder{
+ policy->GetBuilderWithContext(ctx)};
+
+ // Must be Ribbon (more space efficient than 10 bits per key)
+ ASSERT_LT(GetEffectiveBitsPerKey(builder.get()), 8);
+
+ if (bloom_before_level >= 0) {
+ // Claim to be generating filter for previous level
+ SetTestingLevel(bloom_before_level - 1, &ctx);
+
+ builder.reset(policy->GetBuilderWithContext(ctx));
+
+ if (cs == kCompactionStyleLevel || cs == kCompactionStyleUniversal) {
+ // Level is considered.
+ // Must be Bloom (~ 10 bits per key)
+ ASSERT_GT(GetEffectiveBitsPerKey(builder.get()), 9);
+ } else {
+ // Level is ignored under non-traditional compaction styles.
+ // Must be Ribbon (more space efficient than 10 bits per key)
+ ASSERT_LT(GetEffectiveBitsPerKey(builder.get()), 8);
+ }
+ }
+
+ // Like SST file writer
+ ctx.level_at_creation = -1;
+ ctx.reason = TableFileCreationReason::kMisc;
+
+ builder.reset(policy->GetBuilderWithContext(ctx));
+
+ // Must be Ribbon (more space efficient than 10 bits per key)
+ ASSERT_LT(GetEffectiveBitsPerKey(builder.get()), 8);
+ }
+ }
+ }
+}
} // namespace ROCKSDB_NAMESPACE
int main(int argc, char** argv) {
+ ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
::testing::InitGoogleTest(&argc, argv);
ParseCommandLineFlags(&argc, &argv, true);
projects / ceph.git / blobdiff