木鸟杂记

分布式系统,程序语言,算法设计

漫谈 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.png

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:

empty-bloom-filter.png

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

set-x-bloom-filter.png

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

get-x-bloom-filter.png

当持续插入一些元素后,数组中会有大量位置被置 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 占空间不能太大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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

wx-distributed-system-muniao-s.jpg