ceph/src/rocksdb/util/bloom_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // 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.
   9
  10 #ifndef GFLAGS
  11 #include <cstdio>
  12 int main() {
  13   fprintf(stderr, "Please install gflags to run this test... Skipping...\n");
  14   return 0;
  15 }
  16 #else
  17
  18 #include <vector>
  19
  20 #include "rocksdb/filter_policy.h"
  21 #include "table/full_filter_bits_builder.h"
  22 #include "util/arena.h"
  23 #include "util/gflags_compat.h"
  24 #include "util/logging.h"
  25 #include "util/testharness.h"
  26 #include "util/testutil.h"
  27
  28 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
  29
  30 DEFINE_int32(bits_per_key, 10, "");
  31
  32 namespace rocksdb {
  33
  34 static const int kVerbose = 1;
  35
  36 static Slice Key(int i, char* buffer) {
  37   std::string s;
  38   PutFixed32(&s, static_cast<uint32_t>(i));
  39   memcpy(buffer, s.c_str(), sizeof(i));
  40   return Slice(buffer, sizeof(i));
  41 }
  42
  43 static int NextLength(int length) {
  44   if (length < 10) {
  45     length += 1;
  46   } else if (length < 100) {
  47     length += 10;
  48   } else if (length < 1000) {
  49     length += 100;
  50   } else {
  51     length += 1000;
  52   }
  53   return length;
  54 }
  55
  56 class BloomTest : public testing::Test {
  57  private:
  58   const FilterPolicy* policy_;
  59   std::string filter_;
  60   std::vector<std::string> keys_;
  61
  62  public:
  63   BloomTest() : policy_(
  64       NewBloomFilterPolicy(FLAGS_bits_per_key)) {}
  65
  66   ~BloomTest() override { delete policy_; }
  67
  68   void Reset() {
  69     keys_.clear();
  70     filter_.clear();
  71   }
  72
  73   void Add(const Slice& s) {
  74     keys_.push_back(s.ToString());
  75   }
  76
  77   void Build() {
  78     std::vector<Slice> key_slices;
  79     for (size_t i = 0; i < keys_.size(); i++) {
  80       key_slices.push_back(Slice(keys_[i]));
  81     }
  82     filter_.clear();
  83     policy_->CreateFilter(&key_slices[0], static_cast<int>(key_slices.size()),
  84                           &filter_);
  85     keys_.clear();
  86     if (kVerbose >= 2) DumpFilter();
  87   }
  88
  89   size_t FilterSize() const {
  90     return filter_.size();
  91   }
  92
  93   void DumpFilter() {
  94     fprintf(stderr, "F(");
  95     for (size_t i = 0; i+1 < filter_.size(); i++) {
  96       const unsigned int c = static_cast<unsigned int>(filter_[i]);
  97       for (int j = 0; j < 8; j++) {
  98         fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.');
  99       }
 100     }
 101     fprintf(stderr, ")\n");
 102   }
 103
 104   bool Matches(const Slice& s) {
 105     if (!keys_.empty()) {
 106       Build();
 107     }
 108     return policy_->KeyMayMatch(s, filter_);
 109   }
 110
 111   double FalsePositiveRate() {
 112     char buffer[sizeof(int)];
 113     int result = 0;
 114     for (int i = 0; i < 10000; i++) {
 115       if (Matches(Key(i + 1000000000, buffer))) {
 116         result++;
 117       }
 118     }
 119     return result / 10000.0;
 120   }
 121 };
 122
 123 TEST_F(BloomTest, EmptyFilter) {
 124   ASSERT_TRUE(! Matches("hello"));
 125   ASSERT_TRUE(! Matches("world"));
 126 }
 127
 128 TEST_F(BloomTest, Small) {
 129   Add("hello");
 130   Add("world");
 131   ASSERT_TRUE(Matches("hello"));
 132   ASSERT_TRUE(Matches("world"));
 133   ASSERT_TRUE(! Matches("x"));
 134   ASSERT_TRUE(! Matches("foo"));
 135 }
 136
 137 TEST_F(BloomTest, VaryingLengths) {
 138   char buffer[sizeof(int)];
 139
 140   // Count number of filters that significantly exceed the false positive rate
 141   int mediocre_filters = 0;
 142   int good_filters = 0;
 143
 144   for (int length = 1; length <= 10000; length = NextLength(length)) {
 145     Reset();
 146     for (int i = 0; i < length; i++) {
 147       Add(Key(i, buffer));
 148     }
 149     Build();
 150
 151     ASSERT_LE(FilterSize(), (size_t)((length * 10 / 8) + 40)) << length;
 152
 153     // All added keys must match
 154     for (int i = 0; i < length; i++) {
 155       ASSERT_TRUE(Matches(Key(i, buffer)))
 156           << "Length " << length << "; key " << i;
 157     }
 158
 159     // Check false positive rate
 160     double rate = FalsePositiveRate();
 161     if (kVerbose >= 1) {
 162       fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
 163               rate*100.0, length, static_cast<int>(FilterSize()));
 164     }
 165     ASSERT_LE(rate, 0.02);   // Must not be over 2%
 166     if (rate > 0.0125) mediocre_filters++;  // Allowed, but not too often
 167     else good_filters++;
 168   }
 169   if (kVerbose >= 1) {
 170     fprintf(stderr, "Filters: %d good, %d mediocre\n",
 171             good_filters, mediocre_filters);
 172   }
 173   ASSERT_LE(mediocre_filters, good_filters/5);
 174 }
 175
 176 // Different bits-per-byte
 177
 178 class FullBloomTest : public testing::Test {
 179  private:
 180   const FilterPolicy* policy_;
 181   std::unique_ptr<FilterBitsBuilder> bits_builder_;
 182   std::unique_ptr<FilterBitsReader> bits_reader_;
 183   std::unique_ptr<const char[]> buf_;
 184   size_t filter_size_;
 185
 186  public:
 187   FullBloomTest() :
 188       policy_(NewBloomFilterPolicy(FLAGS_bits_per_key, false)),
 189       filter_size_(0) {
 190     Reset();
 191   }
 192
 193   ~FullBloomTest() override { delete policy_; }
 194
 195   FullFilterBitsBuilder* GetFullFilterBitsBuilder() {
 196     return dynamic_cast<FullFilterBitsBuilder*>(bits_builder_.get());
 197   }
 198
 199   void Reset() {
 200     bits_builder_.reset(policy_->GetFilterBitsBuilder());
 201     bits_reader_.reset(nullptr);
 202     buf_.reset(nullptr);
 203     filter_size_ = 0;
 204   }
 205
 206   void Add(const Slice& s) {
 207     bits_builder_->AddKey(s);
 208   }
 209
 210   void Build() {
 211     Slice filter = bits_builder_->Finish(&buf_);
 212     bits_reader_.reset(policy_->GetFilterBitsReader(filter));
 213     filter_size_ = filter.size();
 214   }
 215
 216   size_t FilterSize() const {
 217     return filter_size_;
 218   }
 219
 220   bool Matches(const Slice& s) {
 221     if (bits_reader_ == nullptr) {
 222       Build();
 223     }
 224     return bits_reader_->MayMatch(s);
 225   }
 226
 227   double FalsePositiveRate() {
 228     char buffer[sizeof(int)];
 229     int result = 0;
 230     for (int i = 0; i < 10000; i++) {
 231       if (Matches(Key(i + 1000000000, buffer))) {
 232         result++;
 233       }
 234     }
 235     return result / 10000.0;
 236   }
 237 };
 238
 239 TEST_F(FullBloomTest, FilterSize) {
 240   uint32_t dont_care1, dont_care2;
 241   auto full_bits_builder = GetFullFilterBitsBuilder();
 242   for (int n = 1; n < 100; n++) {
 243     auto space = full_bits_builder->CalculateSpace(n, &dont_care1, &dont_care2);
 244     auto n2 = full_bits_builder->CalculateNumEntry(space);
 245     ASSERT_GE(n2, n);
 246     auto space2 =
 247         full_bits_builder->CalculateSpace(n2, &dont_care1, &dont_care2);
 248     ASSERT_EQ(space, space2);
 249   }
 250 }
 251
 252 TEST_F(FullBloomTest, FullEmptyFilter) {
 253   // Empty filter is not match, at this level
 254   ASSERT_TRUE(!Matches("hello"));
 255   ASSERT_TRUE(!Matches("world"));
 256 }
 257
 258 TEST_F(FullBloomTest, FullSmall) {
 259   Add("hello");
 260   Add("world");
 261   ASSERT_TRUE(Matches("hello"));
 262   ASSERT_TRUE(Matches("world"));
 263   ASSERT_TRUE(!Matches("x"));
 264   ASSERT_TRUE(!Matches("foo"));
 265 }
 266
 267 TEST_F(FullBloomTest, FullVaryingLengths) {
 268   char buffer[sizeof(int)];
 269
 270   // Count number of filters that significantly exceed the false positive rate
 271   int mediocre_filters = 0;
 272   int good_filters = 0;
 273
 274   for (int length = 1; length <= 10000; length = NextLength(length)) {
 275     Reset();
 276     for (int i = 0; i < length; i++) {
 277       Add(Key(i, buffer));
 278     }
 279     Build();
 280
 281     ASSERT_LE(FilterSize(), (size_t)((length * 10 / 8) + 128 + 5)) << length;
 282
 283     // All added keys must match
 284     for (int i = 0; i < length; i++) {
 285       ASSERT_TRUE(Matches(Key(i, buffer)))
 286           << "Length " << length << "; key " << i;
 287     }
 288
 289     // Check false positive rate
 290     double rate = FalsePositiveRate();
 291     if (kVerbose >= 1) {
 292       fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
 293               rate*100.0, length, static_cast<int>(FilterSize()));
 294     }
 295     ASSERT_LE(rate, 0.02);   // Must not be over 2%
 296     if (rate > 0.0125)
 297       mediocre_filters++;  // Allowed, but not too often
 298     else
 299       good_filters++;
 300   }
 301   if (kVerbose >= 1) {
 302     fprintf(stderr, "Filters: %d good, %d mediocre\n",
 303             good_filters, mediocre_filters);
 304   }
 305   ASSERT_LE(mediocre_filters, good_filters/5);
 306 }
 307
 308 }  // namespace rocksdb
 309
 310 int main(int argc, char** argv) {
 311   ::testing::InitGoogleTest(&argc, argv);
 312   ParseCommandLineFlags(&argc, &argv, true);
 313
 314   return RUN_ALL_TESTS();
 315 }
 316
 317 #endif  // GFLAGS