HBase Bloom Filters

布隆过滤器（Bloom filter）是 HBase 的高级功能，在列族定义时可以声明。能够减少特定访问模式下的查询时间。这种模式增加了内存和存储的负担，默认是关闭状态。

布隆过滤器类型

类型	描述
NONE	不使用布隆过滤器
ROW	行键使用布隆过滤器
ROWCOL	列键使用布隆过滤器

列的数量远多于行的数量（除非每行只有一列），使用 ROWCOL 会占用大量的空间。

使用 Bloom filter 的根本原因是默认机制决定了一个存储文件是否包含特定的受限于可用块索引的行键，这个索引是相当粗粒度的，只存储了文件包含块的开始键。例如，系统使用默认的 64KB 作为块大小，1GB 的存储文件分成16384个块，进一步假设每个单元格平均大小是200字节，一个文件中超过500万个单元格。如果用户随机查找一个行键，这个行键很可能在两个块的开始键之间，判断这个键是否真实存在的唯一方法是加载这个块，并扫描查找这个键。

同时以下情况会使问题变得更复杂，对于一个典型程序来说，用户通常会不断的更新数据，Memstore 中的数据不断被 flush 到磁盘，Major compact 会将所有 HFile 合并成大文件，并做数据清理，非常耗时，Minor compact 仅合并最近生成的 HFile，直到合并后的文件达到配置的最大大小。总之一段时间内系统中会存在很多存储文件，其中一些可能包含用户请求行键的单元格，如下图所示（哪个文件包含行键“row-R”）。

Which file has (possibly) "row-R"

这些文件属于同一个 Region （StartKey: "row-A", EndKey: "row-Z"）的同一个列族，只有几个文件包含特定行的更新，文件的块索引包含整个行键的范围（"row-A" ～ "row-Z"），查询“row-R”时会加载每一个文件进行遍历。使用 Bloom filter 的好处是，可以立即判断特定行是否在每一个文件中：能够明确的判断行键不再一个文件中，行键可能在一个文件中（Bloom filter 的特性存在判断可能有错误率，错误率通常为1%）。能够减少块加载，提供整个集群的吞吐量。

HBase 更新模式

在一种场景下，用户对大部分的行都频繁更新，那么大部分的文件都会包含这些行，这种场景不适用 Bloom filter，不能明显减少加载块的数量，额外增加了很多的存储。如果用户批量更新，一行的数据只被写入少数的文件中，这时候 Bloom filter 可以明显发挥作用。

同时还能够提高缓存的命中率，因为加载更少的块，意味着缓存的波动更少。BlockCache 的会把读到的整个 DataBlock 缓存起来，因此更少的加载可以减少与请求数据不相关的数据占用缓存。

添加开销

除了更新模式，另一个决定是否适用 Bloom filter 的因素是添加开销，每项会在过滤器中占用约1字节的存储空间。1GB的存储文件，假设使用很短的行键，如果每个单元格占用20字节，那么布隆过滤器的最大可能占用51MB空间（1GB/20Byte），如果每个单元格占用1KB，那么过滤器最大只需要1MB空间（1GB/1KB）。考虑到过滤器对于查询优化的影响，与1GB的总存储相比，不及1MB的开销比较小。ROW 级别的过滤器相比 ROWCOL 级别的过滤器占用空间更少。

使用行级还是行加列级的过滤器？

取决于业务的使用模式，和存储空间开销

ROW 级别过滤器有效的场景（按效果大小排序）：
扫描行（范围扫描），读整行，读行加列

ROWCOL 级别过滤器有效的场景：
读行加列

下图总结了一般情况下不同级别过滤器的选择标准

Which Bloom filter to use

---

什么是 Bloom Filter？
简单介绍就是一种空间优化的哈希表，使用多个哈希函数计算一个值在哈希表中的占用，能够精确判断一个值不存在，能够在一定错误率下提供一个值可能存在的判断。更详细的介绍，参考之后的更新。

---

References:
《HBase 权威指南》