从BloomFilter到Counter BloomFilter

文章目录

• ​​前言​​
• ​​1. Traditional BloomFilter​​
• ​​2. Counter BloomFilter​​

本文traditional bloomfilter 和 counter bloomfilter的C++实现 均已上传至：

​​​https://github.com/BaronStack/BloomFilter​​

前言

Bloomfilter 是一个老生常谈的数据结构，应用在存储领域的各个系统之中，用来准确判断一个字符串是否不存在，高效判断一个字符串是否存在，有容错率。

详细描述和代码实现均已上传至github中，本文简单描述一下原理和关键代码。

1. Traditional BloomFilter

传统的BloomFilter实现 就是针对输入的一个字符串列表 作为我们的数据集。

对其中的每一个字符串 通过一个或者多个hash函数生成一个唯一的hash值，将这个值映射到bloomfilter上，把bloomfilter维护的一个bit序列相关的bit位置1。

如下 bloom filter维护的一个bit序列：

第一个string 通过hash 函数 生成的hash值，映射到bloomfilter的三个bit位中，将对应的bit位置1

第二个string 通过同样的hash函数生成一个唯一的hash值，映射到同一个bloomfilter的bit位中，已经为1的就不用置位了

依此，后续的字符串在构造bloom filter的时候都通过如上方式来构造，这样一个数据集只需要完成一次构造。

后续拿着构造好的bit序列来检测输入的string，只需要通过hash函数拿到hash值就能够 通过O(1)的时间（位运算）精确匹配这个输入的string不存在（hash值映射的bit位为0，说明肯定不存在，存在的话之前通过hash值映射的就为1）。

看看如下代码 构造bloomfilter :

// CreateFilter:根据输入的key 批量构建bloom filter
// 参数1： keys, 输入的需要构造成bloomfilter的string列表
// 参数2： n，输入的元素个数
// 参数3： dst 最终的bloomfilter结果
//
// 这里的构造逻辑是通过双hash算法实现的，
// 针对输入的string 先生成一个uint32_t 的hash值
// 再针对其中的num_probe_个bit位进行置1
void BloomFilter::CreateFilter(std::string* keys,int n, std::string *dst ) {
  size_t bits = n * bits_per_key_; // bits_pter_key_表示需要维护的bloomfilter的位数

  if(bits < 64) {
    bits = 64;
  }

  size_t bytes = (bits + 7) / 8;
  bits = bytes * 8;

  const size_t init_size = dst->size();
  dst->resize(init_size + bytes, 0);
  dst->push_back(static_cast<char>(num_probe_));  // Remember # of probes
  char* array = &(*dst)[init_size];
  // Use double-hashing to generate a sequence of hash values.
  // 这里使用双hash算法来生成hash值
  // See analysis in [Kirsch,Mitzenmacher 2006].
  for(size_t i = 0;i < static_cast<size_t>(n); i++) {
    uint32_t h = hash_func_(keys[i]);
    const uint32_t delta = (h >> 17) | (h << 15);
    for (size_t j = 0; j < num_probe_; j++) {
      const uint32_t bitpos = h % bits;
      array[bitpos/8] |= (1 << (bitpos % 8)); // 将bitpos位置置为1
      h += delta;
    }
  }
}      

通过如上构造的bloomfilter 来匹配对应的key，输入的key是否存在于bloomfilter之中

// 检查输入的key 是否存在于构造的bloom filter 之中
bool BloomFilter::KeyMayMatch(std::string key, std::string& bloom_filter){
  const size_t len = bloom_filter.size();
  if (len < 2) return false;

  const char* array = bloom_filter.c_str();
  const size_t bits = (len - 1) * 8;

  // Use the encoded k so that we can read filters generated by
  // bloom filters created using different parameters.
  const size_t k = array[len-1];
  if (k > 30) {
    // Reserved for potentially new encodings for short bloom filters.
    // Consider it a match.
    return true;
  }

  uint32_t h = hash_func_(key);
  const uint32_t delta = (h >> 17) | (h << 15);
  for (size_t j = 0; j < k; j++) {
    const uint32_t bitpos = h % bits;
    if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
    h += delta;
  }
  return true;
}      

2. Counter BloomFilter

Counter Blooomfilter的应用场景是 我们想要动态变更构造好的bloomfilter，比如从bloomfilter中删除一个key的映射。这样我们之前说的traditional bloomfilter的设计就无法实现了，毕竟bit只有一个值，且可能被多个key的hash映射公用。

这个时候可以维护一个counter（下面的代码是一个uint32_t的数值表示上面traditional的bit位，当然也可以uint8_t），按照之前的方式来构造，对每一个输入的key生成一个hash值， 这个hash值映射到bloomfilter之上，让对应的"bit"位自增即可。删除其中的key映射的时候，可以让对应的bit位自减少。

输入第一个string时保持各个bit位为1

当输入第二个时，string的hash值映射到同一个bit，则让bit位数值++即可：

后续的字符串构造过程中类似，也是针对匹配的’bit’位自增即可：

构造过程的实现代码如下：

// CreateCounterFilter: 创建一个计数功能的bloomfilter
// 参数1：keys ,输入多个string类型 的字符串
// 参数2： n, 输入的字符串串长度
// 参数3： 根据输入的字符串构造出来的计数bloom filter
//
// 原理如下：
// 维护一个uint32_t 的数组，其中每一个元素代表一个bit位
// 0 0 0 0 0 ... 0 0 0
//
// add string1 --> hash_func
//          |
//          |
// 0 1 0 1 1 ... 1 0 0
//
// add string2 --> hash_func
//          |
//          |
// 1 2 1 1 2 ... 1 0 1
//
// 如果想要从构造的bloom filter中删除string1,则只需要让hash_func
// 的对应 "bit" 位的数值-1 即可
// remove string1 --> hash_func
//          |
//          |
// 1 1 1 0 1 ... 0 0 1
void CounterFilter::CreateCounterFilter(std::string* keys, int n,
                                        vector<uint32_t> *dst) {
  size_t bits = n* bits_per_key_;

  // 构造一个存放 uint32_t的bloomfilter数组 -- dst
  if(bits < 32) {
    bits = 32;
  }

  size_t bytes = (bits + 7) / 8;
  bits = bytes * 8;

  const size_t init_size = dst->size();
  dst->resize(bits, 0);
  uint32_t* array = &(*dst)[init_size];
  for(size_t i = 0;i < static_cast<size_t>(n); i++) {
    uint32_t h = hash_func_(keys[i]);
    vector<BITTYPE> bit_types;

    Bitcount(h, &bit_types);

    for(size_t j = 0; j < bit_types.size(); j++) {
      if(bit_types[j].is1) {
        array[bit_types[j].bit_pos] ++;
      }
    }
  }
}