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

布隆过滤器

参考资料：

• bloom filter
  
• leveldb
  

目录

• 布隆过滤器
  
  
  
  • 根本介绍
    
  • 算法形貌
    
    
    
    • 记号说明
      
    • 算法说明
      
    
    
  • leveldb中的布隆过滤器
    
    
    
    • 根本架构
      
      
      
      • 基类FilterPolicy
        
      • BloomHash布隆哈希函数
        
      
      
    
    
  
  

根本介绍

• 布隆过滤器是一个空间优化的概率性数据布局，在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中的布隆过滤器

布隆过滤器在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. }

复制代码

未完待续...

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。