布隆过滤器：原理与leveldb中的实现

布隆过滤器

参考资料：

• bloom filter
  
• leveldb源码
  
• 《C++ primer》第五版
  
• cppreference
  

目录

• 布隆过滤器
  
  
  
  • 基本介绍[1]
    
  • 算法描述
    
    
    
    • 记号说明
      
    • 算法说明
      
    
    
  • leveldb中的布隆过滤器[2]
    
    
    
    • 基本架构
      
      
      
      • 基类FilterPolicy
        
      • BloomHash布隆哈希函数
        
      • BloomFilter 类
        
        
        
        • 双哈希操作
          
        
        
      
      
    
    
  
  

基本介绍[1]

• 布隆过滤器是一个空间优化的概率性数据结构，在1970年由Howard Bloom设计而成。
  
• 用于判断一个元素是否属于一个集合（即预先判断是否存在，不存在则不执行查找）。
  
• 会有两种返回的情况：(a) 元素不存在集合中。(b) 元素可能存在于集合之中。
  

• 发明布隆过滤器的目的：当数据特别巨大，以至于传统的无错误哈希技术占用了巨大的内存。
  
• 在RAM内存紧张的时候，布隆过滤器可以大量减少不必要的内存读写。
  

算法描述

记号说明

我们将采用以下的符号来说明一下布隆过滤器的基本思想。我们有：
(1) m: 布隆过滤器的位宽(bit width).
(2) n: 插入元素的数目。
(3) k: 哈希函数的数目。
算法说明

1.初始化
布隆过滤器将会初始化成一个m位数组，初始时候所有的位将会设成0.同时，它将配有k个哈希函数，每个哈希函数将会把一个元素映射到m个位中的1个位上，这样对于每个元素，在插入后，将会有k个位被置位。k的选取与错误率（假阳率）有关系，并且m与k，n都成一定的比例关系。
2.增加元素（插入）
将元素传递给k和哈希函数，并且将k个位全部置位。
3.检查元素是否位于集合内。
将元素传递给k和哈希函数，得到k个位置。这时候我们有两种情况。
(1) 存在一个位没有被置位。那么元素肯定不位于集合内。
(2) 所有的k个位均被置位。那么元素可能在集合内。
4.删除元素
不可能。对于布隆过滤器，我们无法决定k个bit中应该清零哪一个位。如果我们随意选择了一个位，将影响到其他的元素。会导致假阴性情况的出现。
有人会问：我可以再增加一个布隆过滤器，里面记录了被删除的元素吗？答案是不推荐。因为在这样的一个对偶过滤器中，其假阳性(觉得删除了但实际没有删除)就对应了原布隆过滤器的假阴性(存在于集合中的元素实际没有存在)，没有很大的意义。并且，我们也有可能把重新删除的元素又加入回去，这样就会导致新设立的布隆过滤器不太有实际意义。ref
5.重建过滤器
有时候，假阳性可能太高以至于我们需要重建过滤器。我们应该避免这样的情况。
6.较优配置
布隆过滤器的较优配置是 \(k=\dfrac{m}{n}\ln{2}\), 同时，每个元素应使用的bit数目最优应该为 \(\dfrac{m}{n}=2.08\ln{\dfrac{1}{\varepsilon}}=1.44\log_2{\dfrac{1}{\varepsilon}}\)。证明参见
leveldb中的布隆过滤器[2]

布隆过滤器在leveldb中的实现在util/bloom.cc中。
基本架构

基类FilterPolicy

继承了FilterPolicy这个类。这个类主要有四个虚函数：

• 虚析构函数virtual ~FilterPolicy()
  
• 纯虚函数virtual const char* Name() const = 0;，返回调用的过滤器的名字。
  
• 纯虚函数
  void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0
  
  
  
  • 传入切片 (其实就是管理字符串的一个类，后面有空在分析) 类指针对象，这个对象是根据用户指定的规则进行排序后的有序列表。一个n代表切片列表的大小。一个string指针地址。
    
  • 根据切片列表，生成过滤器，并将它添加到目的地址。
    
  
  
• LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);一个新的布隆过滤器，采用自行定义的 \(\dfrac{m}{n}\)。前面的宏与符号导出有关。
  

1. #ifndef STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
2. #define STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
3. #include <string>
4. #include "leveldb/export.h"
5. namespace leveldb {
6. class Slice;
7. class LEVELDB_EXPORT FilterPolicy {
8. public:
9.   virtual ~FilterPolicy();
10.   virtual const char* Name() const = 0;
11.   virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0;
12.   virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
13. };
14. LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
15. }
16. #endif

复制代码

BloomHash布隆哈希函数

• uint32_t Hash(const char* data, size_t n, uint32_t seed)
  
• 采用近似于murmur hash的方式生成一个哈希值。传入一个字符串，字符串的大小和一个随机种子。种子是一个魔数，笔者不懂数学因此不予深究。（也没有查询到解释的相关资料）
  

这里的哈希函数将进行以下操作：
1. 解析字符串。
在C++中，一个char所占的存储空间为1字节(8bit)，因此我们可以将这个字符串看作是uint8数组。每次我们读取4个字节（四个uint8数），将指针向右移动4位。
哈希值的计算：首先根据种子，字符串大小和魔数生成基础的值 \(h\)。随后，将字符串按上述方式解析后，加上解析值，乘以魔数m并且取前16位。
2. 处理剩余字符串。
上述处理将处理到最终只剩下不满4个字符（4个byte）为止。最终的处理仍然是加上剩余字符的解析值，乘以魔数m。

注意到在进行剩余的字符处理时，我们使用了switch case结构。在C/C++中，switch-case结构在没有使用break的情况下将自动贯穿，也就是自上而下顺序执行每个case，直到执行default结束。为了告诉开发者贯穿是有意为之的并提醒忽略警告，将会定义一个FALLTHROUGH。现代C++17 标准已经有[[fallthrough]]可以使用。

1. uint32_t Hash(const char* data, size_t n, uint32_t seed) {
2.   // Similar to murmur hash
3.   const uint32_t m = 0xc6a4a793;
4.   const uint32_t r = 24;
5.   const char* limit = data + n;
6.   uint32_t h = seed ^ (n * m);
8.   // Pick up four bytes at a time
9.   while (limit - data >= 4) {
10.     uint32_t w = DecodeFixed32(data);
11.     data += 4;
12.     h += w;
13.     h *= m;
14.     h ^= (h >> 16);
15.   }
17.   // Pick up remaining bytes
18.   switch (limit - data) {
19.     case 3:
20.       h += static_cast<uint8_t>(data[2]) << 16;
21.       FALLTHROUGH_INTENDED;
22.     case 2:
23.       h += static_cast<uint8_t>(data[1]) << 8;
24.       FALLTHROUGH_INTENDED;
25.     case 1:
26.       h += static_cast<uint8_t>(data[0]);
27.       h *= m;
28.       h ^= (h >> r);
29.       break;
30.   }
31.   return h;
32. }

复制代码

BloomFilter 类

接下来我们看一看BloomFilter的实现。
首先是显式定义构造函数。

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

复制代码

• explicit关键字阻止了我们在调用函数时隐式构造这个类的对象[3]。假如有一个函数：
  

1. foo(BloomFilter && filter);
2. // 错误：阻止隐式构造。
3. // foo(3);
4. // 正确：显式构造函数。
5. foo(BloomFilter(3));

复制代码

前者将会出现错误，而后者不会。

• 在这个构造函数中，我们通过上面的公式发现，选择 \(k\) 的较优策略为 \(k=\dfrac{m}{n}\ln{2}\)。这里的 \(\dfrac{m}{n}\) 就是我们的 bits_per_key。为了保证布隆过滤器至少有1个哈希函数，也避免其具有太多的哈希函数，进行了简单的剪裁操作。
  

接下来就是命名操作。这里没有什么需要注意的，就需要回顾一下override关键字就好了。

⼀个派⽣类的函数如果覆盖了某个继承⽽来的虚函数，则它的形参类型必须与被它覆盖的基类函数完全⼀致。[4]

在C++中我们可以使用override关键字来告诉编译器继承类中实现的函数将会覆盖基类中的函数，这样编译器将会检查: (1)这个函数在基类中是否存在且为虚函数。(2)形参列表是否相同。

1. const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }

复制代码

接下来是实现过滤器。它将会接受一个切片指针（表示一组待哈希的元素），这一组元素的个数，以及将它储存的地址。
这里笔者注意到一个细节。布隆过滤器存储在一个 std::string 中！笔者个人觉得可能是因为：
(1) std::string 在内存中是连续储存的(stored contiguously)，符合我们的布隆过滤器在比特情况下的操作。
(2) 提供了一系列的管理接口，容易进行操作和修改。[5]
首先进行了布隆过滤器大小的计算。对于比较少元素的情况下，此时布隆分配器的假阳率可能会很高，因此限定布隆过滤器最小的大小为64比特。
其次重新分配空间，不改变原先的值。然后将哈希函数的数目添加到末尾。
然后，array是字符指针(char *)将会指向新增的第一个位置。从这个位置开始对布隆过滤器进行置位操作。
接着，利用前面已经定义的哈希函数，根据传入元素（字符串）的每一个字符进行哈希操作。这里利用了双哈希操作来产生 \(k\) 个哈希值。
双哈希操作

• 根据前面的hash生成一个32位的值。
  
• 这个值通过循环右移17位形成增量delta。
  
• 进入生成 \(k\) 个哈希位置的操作。
  
  
  
  • 判断应该置位的bit并且将其置位。
    
  • 将原始hash值加上增量delta继续生成哈希值。
    
  
  

[code]void CreateFilter(const Slice* keys, int n, std::string* dst) const override {    // Compute bloom filter size (in both bits and bytes)    size_t bits = n * bits_per_key_;    // For small n, we can see a very high false positive rate.  Fix it    // by enforcing a minimum bloom filter length.    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(k_));  // Remember # of probes in filter    char* array = &(*dst)[init_size];    for (int i = 0; i < n; i++) {      // Use double-hashing to generate a sequence of hash values.      // See analysis in [Kirsch,Mitzenmacher 2006].      uint32_t h = BloomHash(keys);      const uint32_t delta = (h >> 17) | (h > 17) | (h