hbase中的位图索引--布隆过滤器

   在HBase中，读业务是非常频繁的。很多操作都是客户端根据meta表定位到具体的regionserver然后再查询region中的具体的数据。

   但是现在问题来了，一个region由一个memstore以及多个filestore组成，memstore类似缓存在服务器内存中，可以提高插入的效率，当memstore达到一定大小（由hbase.hregion.memstore.flush.size设置）或者说用户手动flush之后，就会固化存储在hdfs之类的磁盘系统上。也就是说一个region可以对应很多有着有效数据的文件，虽然文件内的数据是按照rowkey进行排序的，但是文件之间的rowkey并没有任何顺序（除非经过一次major_compact合并为一个文件）。

   如果用户现在提出的请求是查看一个rowkey（row1）的随意某个列（cf1:col1）

   即使用 get 'tab','row1','cf1:col1'这样命令

   很有可能的一种现象是，row1在每个文件的starTKEy以及endkey之间，因此regionserver需要扫描每个文件的相关数据块，进行多次物理IO。可是并不能确保每个文件中一定有row1这样的行健，很多物理IO都是无效的，这样以来对性能就有很大的影响。于是乎就有了布隆过滤器，在一定程度上判别文件中是否有指定的行健。

   布隆过滤器分为row以及rowcol两种，原理差不多，以rowcol类型为例：

   在memstore写入到hdfs形成文件时，文件内有一个部分叫做meta，在写入的过程中遵循如下算法：

    1.首先会初始化一个比较长的bit数组不妨叫做bit arr[n]={0}；

    2.利用k个hash函数（k<n），对单个（row:cf:col）这样的数据进行k次hash运算，保证计算结果在[0，n-1]之间；

    3.假设某个hash函数的运算结果为r，则设置arr[r]=1，这样每个（row:cf:col）差不多都可以有k个结果，并将arr数据相应位置设置为1；

    4.如此反复知道所有的数据都被写入文件，然后将arr写入文件中的meta部分

   由于位图索引本身的结构特点，可以保证arr[n]不会很大；所以即使被缓存到内存中（不是memstore）也不会占用太大空间，虽然在关系型数据库中，尤其是oltp系统，位图索引会造成大量锁现象，但是在hbase中，已经写入的文件除非compact否则几乎不会修改。

   现在再来看 get 'tab','row1','cf1:col1'，在判断某个文件是否含有（row1:cf1:col1）时，只需要将row1:cf1:col1进行k个hash运算，并判断是否每个结果对应的arr数组值是不是1，如果有一个不是，则可以表明文件中不存在这一列数据（当然即使全部都是1也不一定代表就有），这样可以避免读不必要的文件，提高查询效率。

   从上可见布隆过滤器可以在一定程度上避免读不必要的文件，可是由于是基于hash函数的，所以也不能说是完全准确的，而且对于大规模的scan这样的操作，完全没有必要使用布隆过滤器。

                        2017.1.15