ceph/src/rocksdb/util/bloom_test.cc

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