概念

Bloom Filter

主要功能

提高随机读的性能

存储开销

bloom filter 的数据存在 StoreFile 的 meta 中，一旦写入无法更新，因为 StoreFile 是不可变的。Bloomfilter 是一个列族（cf）级别的配置属性，如果你在表中设置了 Bloomfilter，那么 HBase 会在生成 StoreFile 时包含一份 bloomfilter 结构的数据，称其为 MetaBlock；MetaBlock 与 DataBlock（真实的 KeyValue 数据）一起由 LRUBlockCache 维护。所以，开启 bloomfilter 会有一定的存储及内存 cache 开销。

控制粒度

• ROW

  根据 KeyValue 中的 row 来过滤 storefile

  举例：假设有 2 个 storefile 文件 sf1 和 sf2，

  1. sf1 包含 kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v）
  2. sf2 包含 kv3（r3 cf:q1 v）、kv4（r4 cf:q1 v）

  如果设置了 CF 属性中的 bloomfilter 为 ROW，那么 get(r1) 时就会过滤 sf2，get(r3) 就会过滤 sf1

• ROWCOL

  根据 KeyValue 中的 row+qualifier 来过滤 storefile

  举例：假设有 2 个 storefile 文件 sf1 和 sf2，

  1. sf1 包含 kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v）
  2. sf2 包含 kv3（r1 cf:q2 v）、kv4（r2 cf:q2 v）

  如果设置了 CF 属性中的 bloomfilter 为 ROW，无论 get(r1,q1) 还是 get(r1,q2)，都会读取 sf1+sf2；而如果设置了 CF 属性中的 bloomfilter 为 ROWCOL，那么 get(r1,q1) 就会过滤 sf2，get(r1,q2) 就会过滤 sf1

常用场景

1. 根据 key 随机读时，在 StoreFile 级别进行过滤
2. 读数据时，会查询到大量不存在的 key，也可用于高效判断 key 是否存在

举例说明

假设 x、y、z 三个 key 存在于 table 中，W 不存在

使用 Bloom Filter 可以帮助我们减少为了判断 key 是否存在而去做 Scan 操作的次数

• 分别对 x、y、z 运算 hash 函数取得 bit mask，写到 Bloom Filter 结构中

• 对 W 运算 hash 函数，从 Bloom Filter 查找 bit mask

  如果不存在：三个 Bit 位至少有一个为 0，W 肯定不存在该（Bloom Filter 不会漏判）

  如果存在 ：三个 Bit 位全部全部等于 1，路由到负责 W 的 Region 执行 scan，确认是否真的存在（Bloom Filter 有极小的概率误判）

源码解析