本文主要是介绍RocksDB参数记录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
布隆过滤器(Bloom Filter)
LSM类型的存储引擎查询性能要低于B-tree 类型的存储引擎,RocksDB 有针对性的优化那就是:bloom filter。其实在LevelDB 里就存在bloom filter,但是RocksDB 在LevelDB的基础上又做了优化。
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 目前采用的格式,facebook 描述这种格式相比block-based 格式有40%的查询性能提升。
开启bloom filter的方法如下:
block_based_table_factory={cache_index_and_filter_blocks=1;filter_policy=bloomfilter:10:false;whole_key_filtering=1} ;
cache_index_and_filter_blocks=1: filter data 缓存在block cache中,不指定的话单独分配内存,建议开启。
filter_policy=bloomfilter:10:false :filter_policy 指定过滤的策略,目前只支持bloom filter。10表示bits_per_key,也就是上一节介绍的K = m/n * ln2中的m/n的值,在内部初始化时bits_per_key还会在乘以ln2,也就是散列函数的个数,该值默认是10,表示可能有1%的误判率。false: 表示use_block_based_builder,也就是bloom filter format是否用LevelDB那种格式存储位数组,false时表示使用新格式也就是full filter format。
whole_key_filtering=1:表示使用full key 过滤。
------
补充
Bloom过滤器是基于可能性的数据结构,用于检测一个元素是不是存在于一个结合中。RocksDB中的Bloom过滤器通过一个名为filter_polic的选项控制。当一个用户调用Get(key),会有一个文件列表,可能包含这个key。通常是Level 0的所有文件,以及大于0的每一层中的一个文件。然而,在我们读取每个文件前,我们先咨询bloom过滤器。Bloom过滤器会过滤掉大部分不包含该key的文件的读取。在大多数时候,Get通常只会做一次文件读取。Bloom过滤器总是保持在内存中,以方便打开文件,除非BlockBasedTableOptions::cache_index_and_filter_blocks为true。打开的文件的数量通过max_open_files选项控制。
有两个bloom过滤器类型:基于块的,和全过滤。
基于块的过滤器
通过调用一下接口使用基于块的过滤器:
options.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, true))
基于块的bloom过滤器是根据每个块分别建立的。在一个读取中,我们先咨询一个索引,返回我们正在找的块。现在我们有一个块了,我们咨询bloom过滤器来过滤这个块。
全过滤
通过一下调用设置全过滤:
options.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, false))
全过滤针对每个文件构建。每个文件只有一个bloom过滤器,这意味着我们可以先查询bloom过滤器,而不用查询索引。如果key不在bloom过滤器,相比基于块的过滤器,我们省略一个索引搜索。
参考:布隆过滤器(Bloom Filter)在MyRocks中的使用分析 - 文章详情
这篇关于RocksDB参数记录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!