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, 那么对于一个输入, 某一位没被设置的概率是
而我们一共有 k个独立不相关的Hash函数, 所以这一位保持为 0的概率应该是
假如我们一直插入了 n个元素进来, 某一位是0的概率就是
．用1 减去它, 就是这一位是1 的概率了. 如果我们这时候开始测试元素是否在集合中而发生了错误, 就是说, 明明元素不在集合里面可是Hash 过后每一位都是1．这个的概率就是
, 假设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左右。
相关文章
引用通告
如果您想引用这篇文章到您的Blog，
请复制下面的链接，并放置到您发表文章的相应界面中。
http://www.hadoop.org.cn/hbase/hbase-bloom-filter/trackback/
Comments
One Comment to “HBase中Bloom Filter的使用”
Leave a Reply
[...] 如果这个列组支持布隆过滤器(BLOOMFILTER),那么在内存中有个索引来快速地判断要查找的列是否存在这个行中,减少磁盘IO操作.如果在这个列组你拥有大量的列,每一个列的数据包含的数据非常小，你可能需要在这个列组中应用布隆过滤器。HBase中Bloom Filter的使用已经非常清楚地描述描述了布隆过滤器的用法和容错率算法. [...]