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

时间:2021-02-03 11:46:22

   在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