LevelDB 学习笔记1:布隆过滤器

LevelDB 学习笔记1:布隆过滤器

  • 底层是位数组,初始都是 0
  • 插入时,用 k 个哈希函数对插入的数字做哈希,并用位数组长度取余,将对应位置 1
  • 查找时,做同样的哈希操作,查看这些位的值
    • 如果所有位都是 1,说明数字可能存在
    • 如果有某个位不是 1,说明数字一定不存在

数学结论

影响布隆过滤器精度的参数有

  • 哈希函数的个数 k
  • 布隆过滤器位数组的容量 m
  • 布隆过滤器插入的数据数量 n

对于给定的 m 和 n,要想最小化错误率(假阳性),k 应该取

\[k=\frac{m}{n} \ln 2 \]

要求错误率不大于\(\varepsilon\),k 取最优的情况下,m 应该至少为

\[m \geq – 1.44 \log _{2} \varepsilon * n \]

布隆过滤器的优缺点

优点

  • 空间效率高,可以在使用有限内存的情况下处理海量数据
    • 1% 错误率并使用最佳 k 值的布隆过滤器,每个元素只需要使用约 9.6 位
  • 插入和查询都是常数复杂度,即 O(k)

缺点

  • 存在误判
  • 删除元素困难,因为简单地将对应的位置 0 会影响其他元素的判断
    • 可以用一种叫 Counting Bloom filter 的变体

LevelDB 中的布隆过滤器

LevelDB 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中

  • 若过滤器认为 key 不在 sstable 中,那么就没必要查找这个 sstable 了
  • 否则,key 有可能在 sstable 中,应该做查找

使用布隆过滤器可以有效的减少调用 DB::Get() 时的访存次数,从而减小读放大

LevelDB 中布隆过滤器的实现是 BloomFilterPolicy,它是接口类 FilterPolicy 的实现

  • FilterPolicy 类决定了查找过程中要不要读取某个 sstable
  • 允许用户自定义 FilterPolicy 的子类来应用不同的过滤策略

LevelDB 实现时做了优化,它并不是使用 k 个哈希函数,而是应用 rsa2008 中提出的方法只生成一次哈希值,然后用 double-hashing 的方式生成一组哈希值

uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }

一般实现布隆过滤器时,都会选择非加密哈希算法

  • 加密哈希算法,比如 MD5、SHA1,安全性较高,难以找到碰撞或通过加密值反推原文
  • 非加密哈希算法,比如 MurMurHash、CRC32、FNV,计算速度快
  • LevelDB 实现了一个类似于 MurMurHash 的非加密哈希算法

其他应用场景

缓存穿透

做查询的时候,缓存没有命中,就会到数据库中去找,特别地,如果查找一个不存在的 key,那么是一定无法命中缓存,必须去查数据库的,如果有人恶意地使用大量请求来查不存在的 key,就会导致数据库压力过大,甚至崩溃,这种现象称为缓存穿透

用布隆过滤器我们可以直接将这些针对不存在的 key 发起的请求过滤掉

 2 total views,  1 views today

页面下部广告