RocksDB 布隆过滤器

什么是布隆过滤器

对于任意一组键，可以使用一种算法来创建一个称为Bloom filter的位数组。 给定任意键，这个位数组可用于确定键集中是否存在键。有关Bloom过滤器工作原理的更详细说明，请参阅Wikipedia文章。

在RocksDB中，当设置过滤器策略时，每个新创建的SST文件都将包含一个Bloom过滤器，该过滤器用于确定该文件是否包含我们要查找的键。过滤器本质上是一个位数组。多个哈希函数应用于给定的键，每个哈希函数指定数组中的一个位，该位将被设置为1。在读取时，同样的哈希函数也应用在搜索键上，检查位，即。，如果至少有一个探测返回0，则键肯定不存在。

设置布隆过滤器的例子:

  1. rocksdb::BlockBasedTableOptions table_options;
  2. table_options.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, false));
  3. my_cf_options.table_factory.reset(
  4. rocksdb::NewBlockBasedTableFactory(table_options));

生命周期

在RocksDB中，每个SST文件都有一个对应的Bloom过滤器。它是在将SST文件写入存储器时创建的，并作为相关联的SST文件的一部分存储。 Bloom过滤器以相同的方式为所有级别的文件构造(注意，可以通过设置optimize_filters_for_hits选择性地跳过最后一级的Bloom)。

Bloom过滤器只能由一组键创建——没有组合Bloom过滤器的操作。当我们组合两个SST文件时，将从新文件的键创建一个新的Bloom过滤器。

当我们打开一个SST文件时，相应的Bloom过滤器也会打开并加载到内存中。当关闭SST文件时，Bloom过滤器将从内存中删除。 若要在块缓存中缓存Bloom过滤器，请使用:BlockBasedTableOptions::cache_index_and_filter_blocks=true，

基于块的Bloom过滤器(旧格式)

只有当所有的键都适合内存时，才可以构建一个Bloom过滤器。另一方面，分片布卢姆滤波器不会影响其假阳性率。 因此，为了减轻创建SST文件时的内存压力，在旧格式中，为每个2KB的键值块创建一个单独的bloom过滤器。 有关格式的详细信息可以在这里找到。最后，将单个bloom块的偏移量数组存储在SST文件中。

在读取时，可能包含键/值的块的偏移量从SST索引中获得。然后根据偏移量加载相应的布鲁姆滤波器。 如果过滤器提示key可能存在，那么它将搜索实际数据块中的key。

全过滤器(新格式)

旧格式中的各个筛选器块不是缓存对齐的，在查找过程中可能导致大量缓存丢失。 此外，虽然负面反应(即，键不存在)的过滤器保存搜索从数据块，索引已加载和查看。 新的格式full filter通过为整个SST文件创建一个过滤器来解决这些问题。 权衡的结果是需要更多的内存来缓存文件中每个键的散列(而旧格式中只有2KB块的键)。

全过滤器限制键在同一CPU高速缓存线路中的探测位。这通过将CPU缓存遗漏限制为每个键一个来确保快速查找。 注意，这本质上是对bloom空间进行分片，只要我们有多个键，就不会影响bloom的假阳性率。有关详细信息，请参阅下面的”The Math”部分。

在读取时，RocksDB使用与创建SST文件时相同的格式。用户可以通过在选项中设置filter_policy来指定新创建的SST文件的格式。 helper函数NewBloomFilterPolicy可用于创建旧的基于块的(缺省值)和新的完整过滤器。

  1. extern const FilterPolicy* NewBloomFilterPolicy(int bits_per_key,
  2.     bool use_block_based_builder = true);
  3. }

前缀与全键

默认情况下，每个键的散列都被添加到bloom过滤器中。可以通过将BlockBasedTableOptions::whole_key_filtering设置为false来禁用此功能。 当选设置了Options.prefix_extractor，也向bloom添加了前缀的散列。由于独特的前缀比唯一的整键少，因此只存储处于开花状态的前缀将导致较小的开花，其缺点是假阳性率较大。 此外，前缀绽放还可以在::Seek和::SeekForPrev期间选择性地使用(在创建迭代器时使用check_filter)，而整个键绽放只用于点查找。

统计

下面是一些统计数据，可以用来了解你的全开滤镜设置在生产中的表现:

如果启用了前缀并设置了check_filter，则在每个::Seek和::SeekForPrev之后更新以下统计信息。

  1. * rocksdb.bloom.filter.prefix.checked: seek_negatives + seek_positives
  2. * rocksdb.bloom.filter.prefix.useful: seek_negatives

下面的统计数据在每次查找之后都会更新。如果设置了whole_key_filtering，这是检查整个键的bloom的结果，否则这是检查前缀bloom的结果。

  1. * rocksdb.bloom.filter.useful: [true] negatives
  2. * rocksdb.bloom.filter.full.positive: positives
  3. * rocksdb.bloom.filter.full.true.positive: true positives

因此，点查找的假阳性率由((positives - true positives)/(positives - true positives + true negatives)计算。

请注意这些令人困惑的场景:

1.如果设置了whole_key_filtering和prefix，那么在点查找期间不会检查prefix。 2.如果只设置了前缀，那么检查前缀bloom的总次数就是点查找和查找的统计数据的总和。 由于在seek中没有真正的阳性统计数据，因此我们不能得到总的假阳性率:只有点查找的假阳性率。

定制您自己的过滤器策略

FilterPolicy(包括/rocksdb/filter_policy.h)可以扩展到定义的自定义过滤器。要实现的两项主要功能是:

  1. FilterBitsBuilder* GetFilterBitsBuilder()
  2. FilterBitsReader* GetFilterBitsReader(const Slice& contents)

通过这种方式，新的过滤器策略将作为FilterBitsBuilder和FilterBitsReader的工厂。 FilterBitsBuilder提供用于key存储和筛选器生成的接口，FilterBitsReader提供检查筛选器中是否存在密钥的接口。

注意:这两个新接口只适用于新的过滤器格式。原始过滤器格式仍然使用原始方法自定义。

分区的布隆过滤器

它是一个完整过滤器的存储格式。它将筛选器块划分为多个较小的块，以减轻块缓存上的负载。在这里阅读的。

数学

下面是计算bloom过滤器的假positive(FPR)的数学方法。

  • m bits被分成s个碎片，每个碎片的大小为m/s。.
  • n keys
  • k probe/key
  • 对于每个键，随机选择一个切分，并且在切分中随机设置k位。
  • 插入一个键之后，一个特定位仍然为0的概率是，该键之前的所有哈希值要么设置在具有概率(s-1)/s的其他切分上，要么设置在具有概率(1 -1 /(m/s)的相同切分中的其他位。
    • prob_0 = (s-1)/s + 1/s (1-s/m) ^ k
  • 用二项式近似 (1+x)^k ~= 1 + xk if |xk| << 1 and |x| < 1 we have
    • prob_0 = 1-1/s + 1/s (1-sk/m) = 1 - k/m = (1-1/m)^k
  • 注意这个近似 prob_0(s=1) is equal to prob_0.
  • 插入n个键后，位保持0的概率为
    • prob_0_n = (1-1/m)^kn
  • 所以假positive概率是所有k位都是1:
    • FPR = (1 - prob_0_n) ^ k = (1- (1-1/m)^kn) ^ k

注意，FPR速率与碎片的数量s无关。换句话说，只要sk/m << 1，分片就不会影响FPR。 对于s=512、k=6、每个键10位的典型值，只要n >> 307个键，就可以满足这个要求。 在满溢状态下，每个碎片都具有CPU高速缓存线大小，以允许它们与CPU高速缓存线对齐，并在下一次探测期间减少CPU高速缓存丢失。 m将被设置为n * bits_per_key + epsilon，以确保它是碎片大小的倍数，即， cpu缓存线大小