在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

    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

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文名称：hbase中的位图索引--布隆过滤器-创新互联
文章地址：http://cdweb.net/article/ijppi.html