欢迎投稿

今日深度:

Cassandra中布隆过滤器实现详解【原创】,cassandra布隆

Cassandra中布隆过滤器实现详解【原创】,cassandra布隆


 

CassandraBloomFIlter实现详解

零、BloomFilter原理概述

http://hi.baidu.com/waxiga/blog/item/33ef2ff49b138530bd3109ad.html

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.htmlcassandra中用到了其中的结论,特别注意那个表格)

一、从getFilter()函数入手

1.1第一个getFilter()函数 传入参数为元素的个数numElements、期望每个元素的桶个数targetBucketsPerElem( m/nm为比特数组位数,n为元素个数)。核心代码:

public static BloomFilter getFilter(long numElements, int targetBucketsPerElem)

{

int maxBucketsPerElement = Math.max(1, maxBucketsPerElement(numElements));

int bucketsPerElement = Math.min(targetBucketsPerElem, maxBucketsPerElement);

BloomCalculations.BloomSpecification spec = BloomCalculations.computeBloomSpec(bucketsPerElement);

return new BloomFilter(spec.K, bucketsFor(numElements, spec.bucketsPerElement));

}

 

 

1maxBucketsPerElementnumElements)函数返回每个元素最大的桶数目。返回值为:min(BloomCalculations.probs.length - 1, Integer.MAX_VALUE - 20) / (double)numElements);其中前一项值为15.maxBucketsPerElement 变量最大值为15

2)实际每个元素的桶数目为min(targetBucketsPerElem, maxBucketsPerElement);即取期望的桶数目和实际可能最大的桶数目中间的小值。

3)根据实际每个元素的桶数目,选择哈希函数的个数。BloomCalculations.BloomSpecification spec = BloomCalculations.computeBloomSpec(bucketsPerElement);其中computeBloomSpecbucketsPerElement)函数主要是创建BloomSpecification对象,new BloomSpecification(optKPerBuckets[bucketsPerElement], bucketsPerElement);其中构造函数参数为在当前bucketsPerElement的情况下,误报率最低的哈希函数的个数(即最优的哈希函数的个数optK)。

4)创建BloomFilter对象并返回。参数为哈希函数个数spec.K,以及BitSet对象(由bucketsFor()函数返回。该函数主要是根据元素数目和每个元素的桶数目,创建具有min(Integer.MAX,numElements * bucketsPer + 20)大小的BitSet)。

 

1.2第二个getFilter()函数:传入参数是元素个数和错误率。

public static BloomFilter getFilter(long numElements, double maxFalsePosProbability)

{

assert maxFalsePosProbability <= 1.0 : "Invalid probability";

int bucketsPerElement = maxBucketsPerElement(numElements);

BloomCalculations.BloomSpecification spec = BloomCalculations.computeBloomSpec(bucketsPerElement, maxFalsePosProbability);

return new BloomFilter(spec.K, bucketsFor(numElements, spec.bucketsPerElement));

}

 

1)同上,maxBucketsPerElementnumElements)函数返回每个元素最大的桶数目。返回值为:min(BloomCalculations.probs.length - 1, Integer.MAX_VALUE - 20) / (double)numElements);其中前一项值为15.maxBucketsPerElement 变量最大值为15

2根据每个元素的最大的桶数目和错误率,创建BitSet对象。

3)主要函数BloomCalculations.computeBloomSpec(bucketsPerElement, maxFalsePosProbability);

主要作用就是求出满足错误率要求的最小的butcktsPerElement和最小的哈希函数个数K

4)最后构造BloomFilter对象返回,跟前一个一样。

可以总结下,maxBucketsPerElement最大是15,故哈希函数个数最多为8个。

 

二、BloomFilter

 

addString key)函数分析

1)创建了BloomFilter对象后,接下来分析其中的函数,调用add函数将相应的值加入布隆过滤器,即对其经过哈希后相应的BitSet位置位。

public void addString key{

for (int bucketIndex : getHashBuckets(key))

{

filter_.set(bucketIndex);

}

}

getHashBucketskey)函数返回key经过哈希后需要置位的int类型数组,filter_即为创建的BitSet对象。然后调用filter_.set(bucketIndex)BitSet相应的位置位。

 

2getHashBuckets(key)->Filter.getHashBuckets(key)->Filter.getHashBuckets(key, hashCount, buckets())->Filter.getHashBuckets(byte[] b, int hashCount, int max)

其中buckets()函数即返回filter_.size()一个小点注意下:BItSet构造函数创建对象时,如果你指定的大小不是字对齐的,则创建后的大小会自动对其。比如你指定大小为100,实际创建的大小就是128

 

3)关键的哈希函数就是Filter.getHashBuckets(byte[] b, int hashCount, int max)

static int[] getHashBuckets(byte[] b, int hashCount, int max)

{

int[] result = new int[hashCount];

int hash1 = hasher.hash(b, b.length, 0);

int hash2 = hasher.hash(b, b.length, hash1);

for (int i = 0; i < hashCount; i++)

{

result[i] = Math.abs((hash1 + i * hash2) % max);

}

return result;

}

 

从代码中可以看出,这个哈希函数用到了双重散列,我们知道在所有的开放寻址法中,双重散列是最好方法之一。因为双重散列用到了O(m^2)种探查序列。具体分析可参见算法导论11.4节。

 

哈希函数用的是MurmurHash对象的hash函数,该函数很复杂,就不分析了。代码如下:

public int hash(byte[] data, int length, int seed) {

int m = 0x5bd1e995;

int r = 24;

 

int h = seed ^ length;

 

int len_4 = length >> 2;

 

for (int i = 0; i < len_4; i++) {

int i_4 = i << 2;

int k = data[i_4 + 3];

k = k << 8;

k = k | (data[i_4 + 2] & 0xff);

k = k << 8;

k = k | (data[i_4 + 1] & 0xff);

k = k << 8;

k = k | (data[i_4 + 0] & 0xff);

k *= m;

k ^= k >>> r;

k *= m;

h *= m;

h ^= k;

}

 

// avoid calculating modulo

int len_m = len_4 << 2;

int left = length - len_m;

 

if (left != 0) {

if (left >= 3) {

h ^= (int) data[length - 3] << 16;

}

if (left >= 2) {

h ^= (int) data[length - 2] << 8;

}

if (left >= 1) {

h ^= (int) data[length - 1];

}

 

h *= m;

}

 

h ^= h >>> 13;

h *= m;

h ^= h >>> 15;

 

return h;

}

 

isPresent(String key)函数分析

1)函数代码如下:

public boolean isPresent(String key)

{

for (int bucketIndex : getHashBuckets(key))

{

if (!filter_.get(bucketIndex))

{

return false;

}

}

return true;

}

 

2)由add函数分析就很容易了,根据key值哈希后得到的数组,判断数组中的值是否置位,只有所有的位都置位了才可能在里面,只要有一位没有置位,则key值肯定不在里面。

 

 

www.htsjk.Com true http://www.htsjk.com/cassandra/34251.html NewsArticle Cassandra中布隆过滤器实现详解【原创】,cassandra布隆   Cassandra 中 BloomFIlter 实现详解 零、 BloomFilter 原理概述 http://hi.baidu.com/waxiga/blog/item/33ef2ff49b138530bd3109ad.html http://pages.cs.wisc.edu/~cao...
相关文章
    暂无相关文章
评论暂时关闭