levelDB 代码阅读笔记 04 filter

Overview

FilterPolicy接口

 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

其中CreateFilter的含义是从n个key生成一个 std::string. 生成的std::string可以包含n个key的信息(类似于生成了一个全集) 从而后续判断某个key是否在其中。

bloomfilter

一个十分经典的filter 一般用于判断某个元素是否在一个集合中 如果返回false,则一定不存在。 如果返回true,则大概率存在。返回true的情况存在一定的false positive.

基本原理

Info

其核心原理有两部分:

  1. 通过k个hash function对元素进行映射。 类似于从高维空间映射到低维空间。 不同的hash function映射到了不同的低维空间。 如果在每个低维空间,两个元素经过k个hash function的值都相同,那么这两个元素大概率相同。 如果任意一个hash function的值不同,那么这两个element一定不同。

  2. 每个元素存k个hash 值还是很占空间,怎么办? 将所有的hash值放到同一个长度为m的bitmap上。 并认为如果一个元素不在集合中,那么大概率至少有一个bit不会被任何全集中的其他元素置为1.

注意,这里说的"经过hash function的值"实际上说的是 "hash(element) % m 的值",其中m为bitmap的长度

高维空间映射到低维空间

Info

有木有觉得和局部敏感HASH LSH很像? 参考 simdhash笔记 (simhash是用来处理文本相似的LSH算法,后面可以补一个LSH的笔记)

尤其是核心原理中的第一点,几乎是完全一样的。都是利用hash function来做映射从而减少信息。 最大的区别是LSH可以通过hash值的相似度来判断key的相似度,但是bloom filter中用的hash function是非LSH,只能判断相等或者不等。

false positive的来源

对于不在集合中的元素,有一定概率被误判为在集合中。

这一误判实际上有两方面原因

Tip
  1. hash function带来的误判。 可能两个不同的元素的k组 hash(element) % m 得到的值是完全相同的。

  2. 将映射之后得到的值放到同一个bitmap上带来的误判。 可能不存在于集合中的元素B算出的k个值恰好被若干个其他元素的结果置为了1. 从而带来误判

bloomfilter在levelDB中的实现

最佳k值

有几个值得说明 其一是构造函数中,hash function的个数为 bits_per_key * ln(2)

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
Warning

首先要知道,hash function的个数k并不是越多越好。

  • 当k太小时,上一节所述的false positive的来源1会更容易发生
  • 当k太大时,上一节所述的false positive的来源2会更容易发生(因为每个元素占用了k个bit位,如果k比较大,很容易就把整个bitmap占满了)

那么k的值多少是比较合理的呢? 可以推倒出k最好为 m/n * ln2. 其中m为bitmap的长度,n为key的个数。 m/n就是代码中的bits_per_key

最佳k值

如何得到k个hash function

k是一个变量,那么问题来了 上哪里找那么多不同的hash function去?

levelDB中采用了double hash的做法来生成k个不同的hash值

Tip

double hashing 本来是一种用于处理open addressing hash冲突的办法。 和一般的linear probing 或者 quadratic probing的方法不同,double hash每次probing的长度是由key经过另一个hash function计算出来的(因此称之为double hashing). 由于每次probing的step是由key决定的,从而避免了频繁重复的hash冲突。

而levelDB这里用double hashing生成k个不同的hash value. 计算成本非常低

具体来说,如下代码中的h是hash value1, delta是hash value2(没有用另一个hash function,而是简单的交换前后两部分的bit来生成一个不同的hash value).

 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    }

bitmap实现

levledb中没有用std::bitset,而是用一个char数组。每个位置表示8个bit.

另外,最后生成的dst的结构为: 将hash function的个数k encode进了dst中

|bitmap....|k

 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

一点思考

通常一个算法是要在空间复杂度和时间复杂度之间做取舍 但是bloom filter的空间和时间复杂度都很优秀,那么牺牲了什么呢? 牺牲了准确率

在一些场景下,的确不需要100%准确。从而对时空复杂度的优化带来了空间。

参考链接

Posts in this Series