漫谈 LevelDB 数据结构（二）：布隆过滤器（Bloom Filter）

早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用 C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。

看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路：从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。

本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第二篇，Bloom Filter。

引子

LevelDB 是一个单机的 KV 存储引擎，但没有使用传统的平衡查找树以平衡读写性能，而是使用了 LSM-tree 结构来组织数据，牺牲部分读性能来换取较高的写吞吐。下面来对照一张图来介绍 LSM-tree 在不同存储介质上的组织方式。

LevelDB 将数据分为两大部分，分别存放在内存和文件系统中。主要数据模块包括 WAL log，memtable，immutable memtable，sstable。按照数据流向依次如下：

1. 当 LevelDB 收到一个写入请求 put(k, v) ，会首先将其操作日志追加到日志文件（WAL）中，以备节点意外宕机恢复。
   
2. 写完 WAL 后，LevelDB 将该条 kv 插入内存中的查找结构：memtable。
   
3. 在 memtable 积累到一定程度后，会 rotate 为一个只读 memtable，即 immutable memtable；同时生成一个新的 memtable 以供写入。
   
4. 当内存有压力后，会将 immutable memtable 顺序写入文件系统，生成一个 level0 层的 sstable（sorted strings table） 文件。该过程称为一次 minor compaction。
   
5. 由于查询操作需要按层次遍历 memtable、immutable 和 sstable。当 sstable 文件生成的越来越多之后，查询性能必然越来越差，因此需要将不同的 sstable 进行归并，称为 major compaction。
   

LevelDB 层次组织

所有在文件系统中的 sstable 文件，被 LevelDB 在逻辑上组织成多个层次（一般是 7 层），并且满足以下性质：

1. 层次越大说明其数据写入越早，即先往上层进行 “放”（minor compaction），上层 “满”（达到容量限制）之后 “溢”（major compaction）到下层进行合并。
   
2. 每层文件总大小都有一定限制，并且成指数级增长。比如 level0 层文件总大小上限为 10MB，level1 层为 100MB，依次类推，最高层（level6 层）没有限制。
   
3. 由于 level0 每个 sstable 文件都是直接由 memtable 落盘而来， 因此多个 sstable 文件的 key 范围可能会有交叠。而其他层的多个 sstable 文件则通过一些规则保证没有交叠。
   

对于 LevelDB 的一次读取操作，需要首先去 memtable、immutable memtable 查找，然后依次去文件系统中各层查找。可以看出，相比写入操作，读取操作实在有点效率低下。我们这种客户端进行一次读请求，进入系统后被变成多次读请求的现象为读放大。

为了减小读放大，LevelDB 采取了几方面措施：

1. 通过 major compaction 尽量减少 sstable 文件
   
2. 使用快速筛选的办法，快速判断 key 是否在某个 sstable 文件中
   

而快速判断某个 key 是否在某个 key 集合中，LevelDB 用的正是布隆过滤器。当然，布隆过滤器只能快速判断 key 一定不在某个 sstable 中，从而在层层查找时跳过某些 sstable 。之后会详述原因，此处按下不表。

作者：青藤木鸟 https://www.qtmuniao.com/2020/11/18/leveldb-data-structures-bloom-filter, 转载请注明出处

原理

Bloom Filter 是 Burton Howard Bloom于 1970 年 提出，相关论文为：[Space/time trade-offs in hash coding with allowable errors](Space/time trade-offs in hash coding with allowable errors)。仅让渡些许准确性，就换取了时空上的高效性，实在是很巧妙的设计。

数据结构

Bloom Filter 底层使用一个位数组（bit array），初始，所表示集合为空时，所有位都为 0：

当往集合中插入一个元素 x 时，利用 k 个独立的哈希函数分别对 x 进行散列，然后将 k 个散列值按数组长度取余后分别将数组中对应位置置为 1：

查找过程和插入过程类似，也是利用同样的 k 个哈希函数对待查找元素按顺序进行哈希，得到 k 个位置。如果位数组中 k 个位置上的位均为 1，则该元素有可能存在；否则，若任意一位置上值为 0，则该值一定不存在。对于下图来说，x1 有可能存在，x2 一定不存在。

当持续插入一些元素后，数组中会有大量位置被置 1，可以想象，肯定会有一些位置冲突，造成误判。使用 k 个独立哈希函数可以部分解决这个问题。但如果对于某个值 y，k 个 hash (y) 计算出来的位置，都恰好被其他时候插入的几个元素值设置为 1，则会误判 y 在集合中。

时空优势

相对于其他表示数据集的数据结构，如平衡二叉搜索树、Trie 树、哈希表，甚至更简单的数组或者链表，Bloom Filter 有着巨大的时空优势。上述提到的表示数据集的数据结构，大都需要对数据项本身存储，可能有的做了压缩，比如 Trie 树。但是 Bloom Filter 走了另一条路，并不存储数据项本身，而是存储数据项的几个哈希值，并且用高效紧凑的位数组来存，避免了指针的额外开销。

如此设计，使得 Bloom Filter 的大小与数据项本身大小（如字符串的长短）无关。如，具有 1% 的误差和最佳 k（哈希函数个数）的 Bloom Filter 来说，平均每个元素只需 9.6 bit。

这种优势的获得，可以理解为在哈希表基础上，忽略了冲突处理，从而省下了额外开销。

参数取舍

从上面对 Bloom Filter 可以粗略的感受到，其误判率应该和以下参数有关：

1. 哈希函数的个数 k
   
2. 底层位数组的长度 m
   
3. 数据集大小 n
   

这几个参数与误判率的关系的推导这里不详细展开，可以参考维基百科，或者这篇 CSDN 文章。这里直接给出结论：

当 k = ln2 * (m/n) 时，Bloom Filter 获取最优的准确率。m/n 即 bits per key（集合中每个 key 平均分到的 bit 数）。

源码

铺垫了 Bloom Filter 背景和基本原理后，让我们来看看 LevelDB 源码是如何将其嵌入系统的。

通用接口

为了减小读放大，尤其是对磁盘访问的读放大，LevelDB 抽象出了一个 FilterPolicy 接口，用以在查找 key 时快速筛掉不符合条件的 SStable，这些 Filter 信息会和数据在 SSTable 文件中一起存储，并且在需要时加载到内存，这要求 Filter 占空间不能太大。

class LEVELDB_EXPORT FilterPolicy {
 public:
  virtual ~FilterPolicy();
  // 过滤策略的名字，用来唯一标识该 Filter 持久化、载入内存时的编码方法。
  virtual const char* Name() const = 0;
  // 给长度为 n 的 keys 集合（可能有重复）创建一个过滤策略，并将策略序列化为 string ，追加到 dst 最后。
  virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const = 0;
  // “过滤” 函数。若调用 CreateFilter 时传入的集合为 keys，则如果 key 在 keys 中，则必须返回 true。
  // 若 key 不在 keys 中，可以返回 true，也可以返回 false，但最好大概率返回 false。
  virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0;
};

抽象出该接口可以让用户根据自己需求实现一些其他的过滤策略。自然的，LevelDB 提供了实现了该接口的一个内置的过滤策略：BloomFilterPolicy：

class BloomFilterPolicy : public FilterPolicy {
 public:
  explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
    // 根据上面提到的结论：k = ln2 * (m/n)，获取哈希函数的个数 k。
    // 这里对 k 进行了向下取整、限制最大值，增加了一点误判率，但是也降低了过滤成本。
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;
  }
  const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; }
  void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
    // 计算 bloom filter 的 bit 数组长度 n，会除以 8 向上取整，因为 bit 数组最后会用 char 数组表示
    size_t bits = n * bits_per_key_;
    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>(k_));  // 记下哈希函数的个数
    char* array = &(*dst)[init_size];
    for (int i = 0; i < n; i++) {
      // 使用 double-hashing 方法，仅使用一个 hash 函数来生成 k 个 hash 值，近似等价于使用 k 个哈希函数的效果
      // 详细分析可以参考：https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // 循环右移 17 bits 作为步长
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }
  bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
    const size_t len = bloom_filter.size();
    if (len < 2) return false;
    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8; // -1 是去掉 k 所占空间
    // 取出创建 Filter 时保存的哈希函数个数 k
    const size_t k = array[len - 1];
    if (k > 30) {
      // 超过我们设定 k 个数，直接返回 true，不滤掉该 SSTable.
      return true;
    }
    uint32_t h = BloomHash(key);
    const uint32_t delta = (h >> 17) | (h << 15);  // 循环右移 17 bits 作为步长
    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;
  }
 private:
  size_t bits_per_key_;
  size_t k_;
};
}

根据上述源代码，LevelDB 在实现时，有以下几个点需要注意：

1. 之前提到的 bit 数组在 C++ 语言中，LevelDB 使用 char 数组来表示。因此计算 bit 数组长度时需要对齐到 8 的倍数，计算下标时需要进行适当转换。
   
2. LevelDB 实现时并未真正使用 k 个哈希函数，而是用了 double-hashing 方法进行了一个优化，号称可以达到相似的正确率。
   

小结

Bloom Filter 通常用于快速判断某个元素是否在集合中。其本质上是通过容忍一定的错误率，来换取时空的高效性。从实现角度来理解，是在哈希表的基础上省下了冲突处理部分，并通过 k 个独立哈希函数来减少误判，LevelDB 在实现时使用了某种优化：利用一个哈希函数来达到近似 k 个哈希函数的效果。

下一篇中，将继续剖析 LevelDB 中用到的另一个经典的数据结构：LRU 缓存（LRU cache）。

参考

1. LevelDB handbook：https://leveldb-handbook.readthedocs.io/zh/latest/bloomfilter.html
   
2. Wikipedia：https://en.wikipedia.org/wiki/Bloom_filter