本文出自组内小伙伴

LSM类型的存储引擎查询性能要低于B-tree 类型的存储引擎，RocksDB 有针对性的优化那就是:bloom filter。其实在LevelDB 里就存在bloom filter，但是RocksDB 在LevelDB的基础上又做了优化。本文主要内容包括以下部分：

• Bloom filter 在RocksDB 的实现
• MyRocks 如何利用bloom filter优化查询

Bloom Filter

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

以上内容摘自维基百科，RocksDB 磁盘的数据文件sst中的数据是不会再修改的，非常适合使用bloom filter，当然bloom filter存在一定的误算率：false positive probability。假设BloomFilter中元素总bit数量为m，插入的元素个数为n，

K = m/n * ln2 ，此时误算率最低。

Bloom filter 在 RocksDB 中的实现

Bloom filter 的结构简单讲就是一个位数组，可以基于数据库所有key构建一个bloom filter，但是数据库key总数不可控，一个库一个bloom filter内存消耗也高，这种方式不可取。LevelDB 的做法是每个SST文件保存一份bloom filter，当查询的key可能在该SST时，对应的bloom filter block会被加载进block_cache中(rocksdb_cache_index_and_filter_blocks=true)。RocksDB 延续了LevelDB的方式，但是在bloom filter 存储格式上进一步做了优化。Bloom filter format在RocksDB 分Block-based bloom filter 和 full filter bloom filter，Block-based bloom filter 即LevelDB 采用的存储格式，full filter 是RocksDB 目前采用的格式。

Block-based bloom filter 格式如下：

默认是每2KB 的data 创建一个filter block，所以一个sst 文件会包含很多filter block，给定key，定位filter block的过程如下：

1. 根据key通过index block 获得该key的“data block id”;
2. 根据”data block id” 获取到 offset of filter block：
3. 根据offset of filter block获取到真正的filter block。

Full filter 布隆格式如下：

Full filter 的格式与block-based 格式相比简洁很多，检索filter data的步骤也很简单，给定key，直接去fiter data中判断即可，facebook 描述这种格式相比block-based 格式有40%的查询性能提升。

介绍如何创建bloom filter 之前有必要罗列一下与bloom filter有关的参数，不同的参数设置产生的bloom filter 也不同。

开启bloom filter的方法如下：

block_based_table_factory={cache_index_and_filter_blocks=1;filter_policy=bloomfilter:10:false;whole_key_filtering=0} ;prefix_extractor=capped:3;

cache_index_and_filter_blocks=1: filter data 缓存在block cache中，不指定的话单独分配内存，建议开启。

filter_policy=bloomfilter:10:false ：filter_policy 指定过滤的策略，目前只支持bloom filter，最新的研究包括surf，范围查询效果强于bloom filter，其他文章在介绍。10表示bits_per_key，也就是上一节介绍的K = m/n * ln2中的m/n的值，在内部初始化时bits_per_key还会在乘以ln2，也就是散列函数的个数，该值默认是10。false: 表示use_block_based_builder，也就是bloom filter format是否用LevelDB那种格式存储位数组，建议使用新格式也就是full filter format。

Whole_key_filtering=0：表示不使用full key 过滤，而使用prefix_extractor中指定的prefix key过滤。Prefix bloom filter是RocksDB 针对范围查询的优化，下文还会详细介绍。

代码中对block_based_table_factory 的解析过程如下：

NewBloomFilterPolicy 函数会创建BloomFilterPolicy 对象：

BloomFilterPolicy 继承自FilterPolicy 类，FilterPolicy类相当于接口类，用户可以自定义其他的FilterPolicy，上面解析block_based_table_factory的地方也要实现识别自定义filterpolicy参数的代码。BloomFilterPolicy 类型的对象保存在 BlockBasedTableOptions 结构体内的：std::shared_ptr<const FilterPolicy> filter_policy中，该结构体实例在创建SST的过程中会多次用到。目前RocksDB 的数据文件SST默认格式是BlockBasedTable，字面意思是SST文件是基于block的，SST文件格式不做具体介绍了，可参考官方wiki：https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format。 一个SST文件包括data block、meta block、metaindex block、index block、footer 五个组件。

SST文件 是在immutable memtable flush时创建的，BlockBasedTableBuilder 类用于构建SST，该类继承自TableBuilder接口类。BlockBasedTableBuilder类中并没有直接包含SST的五个组件，只包含了Rep rep_ 成员，Rep结构体内部包含了SST的各个组件，

本文只关注FilterBlockBuilder，该类是用于构建Filter block的类。filter_builder 成员的绑定在Rep的构造函数中：

查阅代码过程中发现skip_filters目前只为false，所以会进入CreateFilerBlockBuilder函数中，该函数会根据filter block的类型创建相应的构建实例，代码如下：

table_opt.filter_policy 即为上文介绍的 BloomFilterPolicy类实例，GetFilterBitsBuilder函数如下：

use_block_based_builder_的值为”filter_policy=bloomfilter:10:false;”中的false，所以该函数返回FullFilterBitsBuilder类实例，也就是上文介绍的new bloom filter format。继续分析CreateFilerBlockBuilder函数，table_opt.partition_filters 默认为false，partition_filters 技术还处于试验阶段不建议生产上使用，所以该函数最终返回FullFilterBlockBuilder类实例，即rep_->filter_builder= new FullFilterBlockBuilder(…)，FullFilterBlockBuilder类用于构建full filter 格式的bloom filter。

上面关于filter block 构建时到底用到哪个类实例已经介绍了，下面就开始进入正题看一下具体的构建过程。BlockBasedTableBuilder类有Add(const Slice& key, const Slice& value) 函数，负责把k-v pair写入到data block，并基于key构建bloom filter。

r->filter_builder 即 FullFilterBlockBuilder，其Add函数如下：

此处可以看出whole_key_filtering和prefix_extractor是可以共存的。如果开启whole_key_filtering，则进入AddKey函数，该函数逻辑比较简单：

filter_bits_builder_ 是FullFilterBitsBuilder 类的实例上文介绍过它的创建过程，该类才是实际的产生bloom filter data的类，其AddKey函数如下：

BloomHash函数根据传入的key计算其落在位数组的哪个位置：

计算完key的哈希值后保存在std::vector<uint32_t> hash_entries_ 中。你可能会疑惑上文介绍过bloom filter使用K个散列函数，而此处只有一个，并没有看到传说中的K个散列函数和一个大的位数组，下面马上揭晓谜底。

memtable 中的k-v pair 都Add完之后，TableBuilder会调用其Finish方法，把SST文件的各个组件组合起来，形成一个完整的SST文件，filter data block在这个过程中产生。

直接进入FullFilterBitsBuilder 类的Finish函数，一探究竟：

上图中代码1处创建位数组，代码2处计算K个散列函数的哈希值。AddHash函数比较有意思，代码如下：

这里并没有看到K个散列函数的影子，这里的逻辑用到了下面这篇论文中的思想：Less Hashing, Same Performance: Building a Better Bloom Filter 。论文提供了一个思想，用1个hash函数，多次移位和加法，达到多个hash 的结果。

以上便是创建bloom filter block的过程，下文介绍bloom filter 在查询中的应用。

Bloom filter 在MyRocks查询中的应用

LSM-based 的存储引擎查询时并不能像B+ tree那样准确的定位到key落在哪个block内，需要遍历key可能在的SST文件来准确地定位到key，这样势必会增加IO，Bloom filter 的作用是可以准确的判断key不在该SST文件内，减少不必要的IO。

下面介绍bloom filter 对 等值查询和范围查询的优化，表结构如下：

Select * from t1 where id =123;
Select * from t1 where  id < 123;
block_based_table_factory={cache_index_and_filter_blocks=1;filter_policy=bloomfilter:10:false;whole_key_filtering=0};prefix_extractor=capped:3;

分别介绍上面两种查询中bloom filter是如何优化查询的。

对于等值查询，MySQL server层那些查询优化的代码这里不介绍了，直接关注进入MyRocks 层后的处理逻辑。ha_rocksdb::index_read_map_impl是MyRocks层进入的函数，因为使用到了主键，所以下一步处理逻辑是get_row_by_rowid函数，代码如下所示。

get_row_by_rowid函数包括2部分工作，1、去底层rocksdb 查找key是否存在，2、如果存在该key，则将k-v格式转成行记录格式返回给server层，如果不存在该key，则返回not found。

我们主要关注第一步底层rocksdb查询的过程，从MyRocks 过渡到RocksDB 是在Rdb_transaction_impl::get函数中完成的，代码如下：

m_rocksdb_tx 是 rocksdb::Transaction 类型，m_rocksdb_tx->Get()函数会进一步调用 write_batch_.GetFromBatchAndDB函数，先从事务的WriteBatch中查找，如果不存在则调用db_->Get 去DB中查找

主要逻辑在GetImpl 中完成。GetImpl 函数的逻辑简单分为三步，先去active memtable中查找，不存在去immutable memtable中查找，还是不存在去sst 文件中查找，代码如下，我们主要关注位置3。

sv->current 表示当前version，version内部包含当前快照下的所有sst文件的元信息，包括每个sst文件key的范围，利用SST文件元信息可以锁定查找的key可能在哪些sst文件中，然后再去这些sst文件中查看key到底在不在，这里就会使用bloom filter判断key是否不在某个sst文件中。

Version::Get 函数实际上是去TableCache中查找的，逻辑是这样的：cache中已经缓存了该key则返回，如果没有则要读取磁盘SST文件。先把该SST文件的index block和filter block读进cache中，bloom filter 判断key不在该SST文件，则返回，判断在，则需要在data block中继续查找。

读取SST文件的index和filter之后进入BlockBasedTable::Get函数，如上所示，FullFilterKeyMayMatch函数进行bloom 过滤，返回false也就是key不在该文件中，后续的逻辑就不会进入到else分支里面了，else分支正是bloom 过滤返回true，key可能在该文件，继续读取data block 来判断key到底在不在

上文介绍过我们没有开启whole_key_filtering，所以使用prefix bloom filter。过滤细节就不在具体介绍了。

上面介绍的是利用主键执行的等值查询，范围查询与等值查询执行逻辑不同。MySQL处理范围查询逻辑可以简单总结为：先利用index_first定位到第一个valid的key，然后利用index_next继续遍历查找。本文只介绍index_first的处理逻辑。

因为不是等值查询，需要设置rocksdb iterator，通过seek(key)查找，setup_scan_iterator函数内部会设置rocksdb iterator，

函数内部会判断是否能用bloom filter，代码如下所示，我们设置了prefix_extractor，并且int(11)是4字节长度，prefix-extractor的cap_len=3,所以prefix_tractor->SameResultWhenAppended()返回true，can_use为true，可以使用bloom filter。如果范围查询的key长度不超过prefix key size，那就不能使用prefix bloom filter，所以在设置prefix_extractor时要根据表的主键结构来设置。

cap_len_ 是我们设置的值，此处我们设置为3，prefix.size()=4，所以返回true，可以使用prefix bloom filter。

iterator设置好之后就是（iteratoer->seek(key)；iterator->valid();iterator->next()）这种逻辑了。RocksDB 的 iterator 十分复杂，本文不介绍，贴一个函数调用栈

最终也是调用FullFilterBlockReader::PrefixMayMatch函数。Prefix bloom filter 是RocksDB 针对范围查询的优化，还有很多细节需要深挖，本文仅介绍到此。

总结

本文主要介绍bloom filter 在RocksDB 中的实现以及如何对查询性能的优化。RocksDB 也实现了prefix bloom filter，但是在设置过滤前缀长度要结合具体的表字段，否则prefix bloom filter并不能起作用，业界也有对范围查询的过滤优化，surf声称更适合范围查询的过滤结构，具体实现细节会在其他文章中介绍。

参考资料

1. https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
2. http://bean-li.github.io/leveldb-sstable-bloom-filter/
3. https://www.jianshu.com/p/b534dc48bb59