HBase中Bloom Filter的使用_乘物游心

HBase中Bloom Filter的使用_乘物游心
HBase中Bloom Filter的使用
2009-02-12 11:26

HBase中Bloom Filter的使用

作者：马士华 发表于：2008-02-29 18:54 最后更新于：2008-03-01 17:06
版权声明：可以任意转载，转载时请务必以超链接形式标明文章原始出处和作者信息。
http://www.hadoop.org.cn/hbase/hbase-bloom-filter/

　　BigTable是Google的一个分布式的结构化数据存储系统．如果你不懂什么是BigTable．请看美人他爹的这篇文章．HBase是在Hadoop上的建立一个跟BigTable相仿的一个系统．正像BigTable在使用布隆过滤器减少磁盘访问来提高效率．HBase同样使用布隆过滤器来提高效率．我们先来看看布隆过滤器的误差算法，然后再来解释HBase中如何使用布隆过滤器．

布隆过滤器不会有错判(Flase Negative), 可能有误判（False Positive). 我们来算一下我们认为能够接受的误判概率. 假设Hash函数是理想的, 也就是说, 函数值是均一分布的, Bloom Filter 长为 m bits, 那么对于一个输入, 某一位没被设置的概率是image002.gif 而我们一共有 k个独立不相关的Hash函数, 所以这一位保持为 0的概率应该是image005.gif 假如我们一直插入了 n个元素进来, 某一位是0的概率就是image007.gif ．用1 减去它, 就是这一位是1 的概率了. 如果我们这时候开始测试元素是否在集合中而发生了错误, 就是说, 明明元素不在集合里面可是Hash 过后每一位都是1．这个的概率就是image009.gif , 假设m＝20，n=1，k=8算出来的错误率是0.00013955336951317957 (Linux Bash: echo "(1-e(-8*1/20))^8"| bc -l).

在HBase的Wiki中对于如何计算BloomFilterDescriptor的参数描述的不太清楚，即如何确定number-of-values．其实HBase使用布隆过滤器是在建立表的列的时候指定．通过使用布隆过滤器将对每一次列中数据的磁盘访问先做一次判断来减少磁盘访问，对于频繁访问的列将提升很大的性能．当一个HRegion中当HStore中的HStoreFile大于设定值hbase.hregion.max.filesize的大小时，指派这个HRegion调用closeAndSplit()方法．一个HRegion最多只能是 hbase.hregion.max.filesize指定的文件大小．而HBase使用的布隆过滤器是在HStoreFile中调用来判断应用程序所请求的单元格数据是否在磁盘中存储．这就是说在 HBase使用的布隆过滤器取决于hbase.hregion.max.filesize指定的文件最多在这个列能够存储多少个单元格的数据（如果这个列是压缩存储的话，要计算压缩后的数量）．假设我们一个 HRegion保存10000单元格，Hash函数大小为8，我们决定错误率为0.00001．即k=8,容错率为．通过计算则当m=295555时，其容错率为0.000009999973377382059符合我们的要求．那么m就是BloomFilterDescriptor中vectorSize的参数，k就是nbHash的参数，这就是我们建立表的列中BloomFilterDescriptor(final BloomFilterType type, final int vectorSize,final int nbHash)的构造函数的参数．如果我们使用单个参数的构造函数BloomFilterDescriptor(final BloomFilterType type,final int numberOfEntries)，我们给定numberOfEntries一个任何的值，假设n=10000，k=4（默认），m = Math.ceil(number-of-values * 4 / ln(2))＝57708。按算法构建的布隆过滤器其容错率为0.06左右。

相关文章

* 2008-06-26 -- HBase的概念和性能选项 (5)
* 2008-05-29 -- Hadoop Summit Video (3)
* 2008-08-20 -- Hadoop中的子项目Zookeeper能做什么 (6)
* 2008-08-07 -- 函数式编程范式-MapReduce (3)
* 2008-07-02 -- pig语言 (2)