1 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5 #include "leveldb/filter_policy.h"
6
7 #include "leveldb/slice.h"
8 #include "util/hash.h"
9
10 namespace leveldb {
11
12 namespace {
BloomHash(const Slice & key)13 static uint32_t BloomHash(const Slice& key) {
14 return Hash(key.data(), key.size(), 0xbc9f1d34);
15 }
16
17 class BloomFilterPolicy : public FilterPolicy {
18 public:
BloomFilterPolicy(int bits_per_key)19 explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
20 // We intentionally round down to reduce probing cost a little bit
21 k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
22 if (k_ < 1) k_ = 1;
23 if (k_ > 30) k_ = 30;
24 }
25
Name() const26 const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }
27
CreateFilter(const Slice * keys,int n,std::string * dst) const28 void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
29 // Compute bloom filter size (in both bits and bytes)
30 size_t bits = n * bits_per_key_;
31
32 // For small n, we can see a very high false positive rate. Fix it
33 // by enforcing a minimum bloom filter length.
34 if (bits < 64) bits = 64;
35
36 size_t bytes = (bits + 7) / 8;
37 bits = bytes * 8;
38
39 const size_t init_size = dst->size();
40 dst->resize(init_size + bytes, 0);
41 dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
42 char* array = &(*dst)[init_size];
43 for (int i = 0; i < n; i++) {
44 // Use double-hashing to generate a sequence of hash values.
45 // See analysis in [Kirsch,Mitzenmacher 2006].
46 uint32_t h = BloomHash(keys[i]);
47 const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
48 for (size_t j = 0; j < k_; j++) {
49 const uint32_t bitpos = h % bits;
50 array[bitpos / 8] |= (1 << (bitpos % 8));
51 h += delta;
52 }
53 }
54 }
55
KeyMayMatch(const Slice & key,const Slice & bloom_filter) const56 bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
57 const size_t len = bloom_filter.size();
58 if (len < 2) return false;
59
60 const char* array = bloom_filter.data();
61 const size_t bits = (len - 1) * 8;
62
63 // Use the encoded k so that we can read filters generated by
64 // bloom filters created using different parameters.
65 const size_t k = array[len - 1];
66 if (k > 30) {
67 // Reserved for potentially new encodings for short bloom filters.
68 // Consider it a match.
69 return true;
70 }
71
72 uint32_t h = BloomHash(key);
73 const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
74 for (size_t j = 0; j < k; j++) {
75 const uint32_t bitpos = h % bits;
76 if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
77 h += delta;
78 }
79 return true;
80 }
81
82 private:
83 size_t bits_per_key_;
84 size_t k_;
85 };
86 } // namespace
87
NewBloomFilterPolicy(int bits_per_key)88 const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
89 return new BloomFilterPolicy(bits_per_key);
90 }
91
92 } // namespace leveldb
93