`
qiemengdao
  • 浏览: 276566 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

Cassandra中BloomFIlter实现详解

 
阅读更多
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值肯定不在里面。
分享到:
评论

相关推荐

    Cassandra技术详解 操作与测试报告

    ### Cassandra技术详解与操作测试报告 #### 一、Cassandra概述 Cassandra是一个开源的分布式数据库管理系统,由Facebook开发,并随后捐赠给Apache基金会。它的设计灵感来源于Amazon的Dynamo和Google的Bigtable,...

    cassandra详解

    Cassandra详解 Cassandra是一款高度可扩展、最终一致性的分布式结构化键值存储系统,由Facebook的Avinash Lakshman(Dynamo的贡献者)和Prashant Malik共同创建。最初用于支持Facebook的收件箱搜索功能,后于2008年...

    Cassandra 分布式数据库详解

    当 `AutoBootstrap` 设置为 `TRUE`,Cassandra 会根据集群当前状态调整自身,比如分配合适的 Token 并迁移数据,以实现负载均衡。如果设置为 `FALSE`,新节点不会进行这种自动调整,但这并不意味着它不加入集群,...

    2019云栖大会Cassandra一致性详解-201909.pdf

    【Cassandra一致性详解】 在2019云栖大会上,郭泽晖(索月)对Cassandra的一致性进行了深入的解析。Cassandra是一个分布式NoSQL数据库系统,它遵循CAP定理,即在分布式系统中,无法同时保证一致性(Consistency)、...

    Distributed-Systems-Bloom-Filters-Coded-Bloom-Filter-Counting-Bloom-Filter:在此项目中,我实现了Bloom Bloom过滤器,编码Bloom Bloom过滤器,Counting Bloom Filter计数。 这些用于Google Bigtable,Apache HBase,Apache Cassandra和PostgreSQL等系统中

    在此项目中,我实现了Bloom Bloom过滤器,编码Bloom Bloom过滤器,Counting Bloom Filter计数。 这些用于Google Bigtable,Apache HBase,Apache Cassandra和PostgreSQL等系统中。 Google Bigtable,Apache HBase,...

    Cassandra关键技术详解[整理].pdf

    Cassandra 关键技术详解 Cassandra 是一种 NoSQL 数据库,属于键值存储系统,广泛应用于社交网络、工业大数据等领域。下面是 Cassandra 的关键技术详解。 1. NoSQL 运动与 Cassandra 系统 NoSQL 运动始于 1998 年...

    分布式数据库Cassandra 一致性详解.zip

    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格式,配套文档下载地址...

    cassandra权威指南(中文)

    - **配置参数详解**:包括Cassandra的配置文件详解,如`cassandra.yaml`中的关键参数设置方法。 - **性能调优**:提供性能调优的最佳实践,包括硬件选型、JVM参数调整、系统监控等方面的内容。 #### 五、Cassandra...

    Cassandra详解(ppt)

    **Cassandra详解** Cassandra是一款分布式NoSQL数据库系统,由Facebook于2008年设计,后成为Apache软件基金会的顶级项目。它被设计用于处理大规模数据,具有高可用性、可扩展性和线性可扩展性的特点。在本PPT中,...

    Java连接cassandra实现简单的增删查demo

    在Java编程环境中,连接Cassandra数据库并实现基本的增、删、查操作是常见的任务。Cassandra是一款分布式NoSQL数据库,常用于处理大规模数据。在这个示例中,我们将探讨如何通过Java来操作Cassandra数据库。 首先,...

    Cassandra在饿了么的应用

    7. **Cassandra的数据结构**:主要介绍了Memtable、SSTable和Bloomfilter等关键数据结构,它们构成了Cassandra存储数据和索引的方式。 8. **CQL(Cassandra Query Language)**:CQL语言类似于SQL语言,提供了DDL和...

    java NoSql Cassandra hector

    Java NoSQL Cassandra Hector详解 在当今大数据时代,非关系型数据库(NoSQL)因其灵活性、高可扩展性和高性能,越来越受到开发者的...在实际项目中,结合Cassandra的特性进行优化,可以实现更高效的数据存储和检索。

    Cassandra架构与应用

    ### Cassandra架构与应用详解 #### 一、Cassandra概述与背景 Cassandra,作为一款分布式数据库,其设计初衷旨在应对互联网大规模Web2.0应用所带来的挑战,尤其是针对那些需要高并发处理、海量数据存储和快速查询...

    Cassandra1.2

    Cassandra 提供了数据复制功能,可以在集群中的多个节点间复制数据,以实现容错。1.2 版本中,用户可以自定义复制因子,调整数据的冗余程度和读写性能。 ### 4. Gossip 协议 Cassandra 使用Gossip协议进行节点间的...

    2_1_Cassandra配置文件中相关配置项详解

    这些配置项在 Cassandra 的 cassandra.yaml 文件中定义,它们直接影响到 Cassandra 集群的性能、稳定性和安全性。正确理解和配置这些参数对于优化 Cassandra 集群至关重要。在实际部署和运行 Cassandra 时,应根据...

    Cassandra权威指南【中文版】

    Cassandra,作为NoSQL数据库家族中的重要成员,因其高可用性、可扩展性和出色的性能,在大数据处理领域得到了广泛应用。本书旨在帮助读者理解Cassandra的核心概念、架构设计以及实际操作技巧。 在Cassandra的世界里...

    Learning_Apache_Cassandra

    在本文档中,标题“Learning_Apache_Cassandra”透露了内容的主题,即学习Apache Cassandra。...通过阅读本书,读者应能够掌握Cassandra的核心概念,能够在实际项目中有效地实现和使用Cassandra来存储和检索数据。

    DevCenter cassandra客户端

    用户可以通过图形化界面定义键空间(keyspaces)、列族(column families,Cassandra中的表)以及它们的字段,支持主键和索引的配置。 2. **CQL编辑器**:DevCenter内置了一个Cassandra查询语言(CQL)的编辑器,...

    cassandra安装使用教程

    1、cassandra的安装、维护使用 2、java操作cassandra实例 3、cql使用详解

    spring boot与cassandra集成,使用JPA方式。

    在本文中,我们将深入探讨如何将Spring Boot框架与Cassandra数据库集成,并利用Java Persistence API (JPA) 进行数据操作。Spring Boot以其简洁的配置和开箱即用的特性,已经成为Java开发中的首选框架之一。而...

Global site tag (gtag.js) - Google Analytics