levelDB 代码阅读笔记 04 filter

 1
 2class LEVELDB_EXPORT FilterPolicy {
 3 public:
 4  virtual ~FilterPolicy();
 5
 6  // Return the name of this policy.  Note that if the filter encoding
 7  // changes in an incompatible way, the name returned by this method
 8  // must be changed.  Otherwise, old incompatible filters may be
 9  // passed to methods of this type.
10  virtual const char* Name() const = 0;
11
12  // keys[0,n-1] contains a list of keys (potentially with duplicates)
13  // that are ordered according to the user supplied comparator.
14  // Append a filter that summarizes keys[0,n-1] to *dst.
15  //
16  // Warning: do not change the initial contents of *dst.  Instead,
17  // append the newly constructed filter to *dst.
18  virtual void CreateFilter(const Slice* keys, int n,
19                            std::string* dst) const = 0;
20
21  // "filter" contains the data appended by a preceding call to
22  // CreateFilter() on this class.  This method must return true if
23  // the key was in the list of keys passed to CreateFilter().
24  // This method may return true or false if the key was not on the
25  // list, but it should aim to return false with a high probability.
26  virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
27};
28

1
2  explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
3    // We intentionally round down to reduce probing cost a little bit
4    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
5    if (k_ < 1) k_ = 1;
6    if (k_ > 30) k_ = 30;
7  }
8

 1
 2        uint32_t h = BloomHash(keys[i]);
 3      // kk: 这里每次+delta就相当于生成不同的hash值了
 4      // delta是另一个hash value,通过翻转左右两边得到
 5      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
 6						     // k 是hash函数的个数
 7      for (size_t j = 0; j < k_; j++) {
 8	      // kk: 这里就是把char* 当成bitset 使用
 9        const uint32_t bitpos = h % bits;
10        array[bitpos / 8] |= (1 << (bitpos % 8));
11        h += delta;
12      }
13    }

 1
 2    const size_t init_size = dst->size();
 3    dst->resize(init_size + bytes, 0);
 4    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
 5    // kk: use char array as bitmap
 6    // each char has 8 position
 7    char* array = &(*dst)[init_size];
 8    for (int i = 0; i < n; i++) {
 9      // Use double-hashing to generate a sequence of hash values.
10      // See analysis in [Kirsch,Mitzenmacher 2006].
11      uint32_t h = BloomHash(keys[i]);
12      // kk: 这里每次+delta就相当于生成不同的hash值了
13      // delta是另一个hash value,通过翻转左右两边得到
14      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
15						     // k 是hash函数的个数
16      for (size_t j = 0; j < k_; j++) {
17	      // kk: 这里就是把char* 当成bitset 使用
18        const uint32_t bitpos = h % bits;
19        array[bitpos / 8] |= (1 << (bitpos % 8));
20        h += delta;
21      }
22    }

 1
 2  // Use the encoded k so that we can read filters generated by
 3    // bloom filters created using different parameters.
 4    const size_t k = array[len - 1];
 5    if (k > 30) {
 6      // Reserved for potentially new encodings for short bloom filters.
 7      // Consider it a match.
 8      return true;
 9    }
10
11    uint32_t h = BloomHash(key);
12    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
13    for (size_t j = 0; j < k; j++) {
14      const uint32_t bitpos = h % bits;
15      // 如果其中一个位置为0就返回false
16      if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
17      h += delta;
18    }
19    return true;
20
21