在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://bjjierui.cn/article/ijppi.html
