Cassandra中BloomFIlter实现详解
零、BloomFilter原理概述
http://hi.baidu.com/waxiga/blog/item/33ef2ff49b138530bd3109ad.html
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html(cassandra中用到了其中的结论,特别注意那个表格)
一、从getFilter()函数入手
1.1第一个getFilter()函数
:传入参数为元素的个数numElements、期望每个元素的桶个数targetBucketsPerElem(
即m/n,m为比特数组位数,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));
}
|
1)maxBucketsPerElement(numElements)函数返回每个元素最大的桶数目。返回值为: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);其中computeBloomSpec(bucketsPerElement)函数主要是创建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)同上,maxBucketsPerElement(numElements)函数返回每个元素最大的桶数目。返回值为: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类
add(String
key)函数分析
1)创建了BloomFilter对象后,接下来分析其中的函数,调用add函数将相应的值加入布隆过滤器,即对其经过哈希后相应的BitSet位置位。
public
void add(String
key){
for
(int
bucketIndex : getHashBuckets(key))
{
filter_.set(bucketIndex);
}
}
|
getHashBuckets(key)函数返回key经过哈希后需要置位的int类型数组,filter_即为创建的BitSet对象。然后调用filter_.set(bucketIndex)对BitSet相应的位置位。
2)getHashBuckets(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值肯定不在里面。
分享到:
相关推荐
2_1_Cassandra配置文件中相关配置项详解
Cassandra技术详解 操作与测试报告 基于nosql实现集群
63页。参照了众多其他的cassandra的资料~
了解一个软件的配置项的意义是使用这个软件的前提,这里介绍 Cassandra 的配置文件(storage-config.xml)中各个配置项的意义,这其中包含有很多配置参数,我们可以对其进行调整以达到理想的性能。
在此项目中,我实现了Bloom Bloom过滤器,编码Bloom Bloom过滤器,Counting Bloom Filter计数。 这些用于Google Bigtable,Apache HBase,Apache Cassandra和PostgreSQL等系统中。 Google Bigtable,Apache HBase,...
2019云栖大会Cassandra一致性详解-201909.pdf
Cassandra关键技术详解[整理].pdf
2.Cassandra ⼀一致性实现 2.1 CAS 2.2 Quorum读写 2.3 不不⼀一致产⽣生原因 2.4 Hinted handoff 2.5 Read repair 2.6 Manual repair 3.Cassandra应⽤用场景 4.总结 视频是mp4格式,配套文档下载地址...
1、cassandra的安装、维护使用 2、java操作cassandra实例 3、cql使用详解
Cassandra查询分析器
cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战cassandra 实战...
cassandra中文版权威指南,官网下载
模式灵活 :使用Cassandra,像文档存储,你不必提前解决记录中的字段。你可以在系统运行时随意的添加或移除字段。这是一个惊人的效率提升,特别是在大型部署上。 真正的可扩展性 :Cassandra是纯粹意义上的水平扩展...
nosql 操作,cassandra添加删除操作代码
NULL 博文链接:https://weijinxian.iteye.com/blog/769407
java导出cassandra数据
The rising popularity of Apache Cassandra rests on its ability to handle very large data sets that include hundreds of terabytes -- and that's why this distributed database has been chosen by ...
DevCenter cassandra客户端 DevCenter cassandra客户端 DevCenter cassandra客户端
Cassandra(apache-cassandra-4.0.1-bin.tar.gz)是一套开源分布式NoSQL数据库系统。它最初由Facebook开发,用于储存收件箱等简单格式数据,集GoogleBigTable的数据模型与Amazon Dynamo的完全分布式的架构于一身...
docker-cassandra, 在 Docker的快速启动中,Cassandra Docker 中的Cassandra这个库提供了在 Docker 中运行Cassandra所需的一切,并为快速的容器启动而调整。为什么?虽然天真的Cassandra图像大约需要 30秒的时间,...