精华内容
下载资源
问答
  • 计数布隆过滤器(counting bloom filter)Redis实现分析

    Bloom filter简介

    关于布隆过滤器有众多文章做过介绍,这里不作详解,仅贴出简介:Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定在集合中;但如果检测结果为否,该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况,可见 Bloom filter 是牺牲了正确率和时间以节省空间。
    在这里插入图片描述
    Bloom filter 优点就是它的插入和查询时间都是常数,另外它查询元素却不保存元素本身,具有良好的安全性。它的缺点也是显而易见的,当插入的元素越多,错判“在集合内”的概率就越大了,另外 Bloom filter 也不能删除一个元素,因为多个元素哈希的结果可能在 Bloom filter 结构中占用的是同一个位,如果删除了一个比特位,可能会影响多个元素的检测。

    Counting Bloom filter

    标准Bloom filter对于需要精确检测结果的场景将不再适用,而带计数器的Bloom filter的出现解决了这个问题。Counting Bloom filter实际只是在标准Bloom filter的每一个位上都额外对应得增加了一个计数器,在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。
    在这里插入图片描述
    Counting Bloom Filter通过多占用几倍的存储空间的代价,给Bloom Filter增加了删除操作。这其中最关键的问题是Counting Bloom filter需要增加多少存储量?在论文中给出了相关计算,假设counter数组的长度为m(对应bloom filter的位数组),Ci表示counter数组中第i个counter的大小,即哈希函数映射到第i位的次数,则每个counter最少位数N为:
    在这里插入图片描述
    SBF(Spectral Bloom Filter)作为Counting Bloom Filter的一种实现,将所有counter排成一个位串,counter之间完全不留空隙,然后通过建立索引结构来访问counter,并达到了只使用O(N) + O(m)位的存储目标,O(m)的构建时间。虽然SBF解决了动态counter的存储问题,但其引入了复杂的索引结构,这让每个counter的访问变得复杂而耗时。

    Dynamic Count Filter

    为改进SBF的缺点,人们又发明了DCF(Dynamic Count Filter),其使用两个数组来存储所有的counter,它们的长度都为m(即bloom filter的位数组长度)。第一个数组是一个基本的CBF(即下图中的CBFV,counting bloom filter vector),counter的长度固定,为x = log(M/n),其中M是集合中所有元素的个数,n为集合中不同元素的个数。第二个数组用来处理counter的溢出(即下图中的OFV,overflow vector),数组每一项的长度并不固定,根据counter的溢出情况动态调整。
    在这里插入图片描述
    在查询一个counter时,DCF要求两次内存访问。假设想查询位置为j的counter的值,我们先读出CBFV和OFV的值,分别为Cj和OFj,那么counter的值就可以表示为Vj = (2x×OFj + Cj)。

    在集合增加元素时,如果OFV的最大值从2x – 1增加到2x,OFV就需要给每一项增加1位,否则就会溢出。对应的,当OFV的最大值从2x减少到2x – 1时,OFV就需要减少1位。每次OFV大小改变的时候都需要重新创建一个OFV数组,然后把旧OFV数组的值拷贝到新建的OFV数组中,最后把旧OFV数组的空间释放掉。对于减少的情况,可以采用一些策略延迟OFV的重建,以避免一些临时性的减少导致OFV反复重建。

    基于Redis的实现

    鉴于单机有内存限制,我们不禁就会想到使用外部存储来实现,其中Redis是较好的选择。Redis有如下优点:1. 性能优异,2.接口功能丰富,3.可靠稳定。

    对于DCF的Redis实现,最简单的就是采用standalone模式,主要是因为其能方便支持Lua script并使用事务,另外还需要在客户端实现Sharding分片算法。但其有个缺点就是需要在开始时规定Redis实例数量,如要横向扩展Redis实例则需要将数据进行重分片,代价很大。
    客户端函数包含 query,add,delete 三种操作,且都先通过mod运算进行分片,对应到具体Redis实例后,执行对应Lua脚本。基本流程图如下:
    在这里插入图片描述

    参考资料

    1. bloom filter
    2. Summary Cache: A Scalable Wide-Area
      Web Cache Sharing Protocol
    3. Counting Bloom Filter
    4. Bloom Filter概念和原理
    5. Dynamic Count Filter
    6. Accurate Counting Bloom Filters for Large-Scale Data Processing
    展开全文
  • 布隆过滤器是有效,节省空间的数据结构,用于简洁地表示数据集并支持近似成员资格查询。 传统上,研究人员通常认为,Bloom过滤器有可能返回假阳性,但在行为良好的操作下绝不会返回假阴性。 但是,通过研究主流变体...
  • 本质上布隆过滤器是一种数据结构,比较巧妙的概率数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射...

    什么是布隆过滤器?

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
    在这里插入图片描述

    HashMap 的问题

    讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

    还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。

    布隆过滤器数据结构

    布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:
    在这里插入图片描述
    如果我们要映射一个值到布隆过滤器中(插入),我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:
    在这里插入图片描述
    值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

    这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

    支持删除么

    目前我们知道布隆过滤器可以支持 add 和 isExist 操作,那么 delete 操作可以么,答案是不可以,例如上图中的 bit 位 4 被两个值共同覆盖的话,一旦你删除其中一个值例如 “tencent” 而将其置位 0,那么下次判断另一个值例如 “baidu” 是否存在的话,会直接返回 false,而实际上你并没有删除它。

    如何解决这个问题,答案是计数删除。但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。这样的话,增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。

    如何选择哈希函数个数和布隆过滤器长度

    很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

    另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

    布隆过滤器优点

    1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
    2. 哈希函数相互之间没有关系,方便硬件并行运算
    3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
    4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
    5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
    6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

    布隆过滤器缺陷

    1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白
      名单,存储可能会误判的数据)
    2. 不能获取元素本身
    3. 一般情况下不能从布隆过滤器中删除元素
    4. 如果采用计数方式删除,可能会存在计数回绕问题

    参考博文:https://www.jianshu.com/p/2104d11ee0a2

    展开全文
  • 使用扩展计数布隆过滤器的快速近似哈希表
  • 1、什么是布隆过滤器

    一、什么是布隆过滤器

    布隆过滤器(Bloom Filter)是一个很长的二进制向量和一系列随机映射函数。它是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效的插入和查询,可以用于检索一个元素是否在一个集合中。

    优点:相比于传统的list、set、map等数据结构,它更高效、占用空间更少。
    缺点:返回的结果是概率性(存在误差),不是确切的。


    二、为什么不用HashMap?

    数据存储和查找,map和hashmap应该也是很好的选择,为什么不直接使用map或hashmap,而还要用布隆过滤器呢?
    在这里插入图片描述
    在HashMap中,值映射到HashMap的key,然后可以在O(1)的时间复杂度内返回结果,效率也非常高。
    在这里插入图片描述

    不过,HashMap的也存在一定的问题,表现如下:

    • 存储容量占比高,考虑到负载因子的存在,空间通常是不能被用满。
    • HashMap需要存储key值,而当key值类似URL时占用的空间非常大。

    (负载因子loadFactor表示一个散列表的空间的使用程度,假设initailCapacity为初始化数组大小,得到公式:initailCapacity*loadFactor=HashMap的容量。
    负载因子越大则散列表的装填程度越高,也就是能容纳更多的元素,元素多了,链表大了,此时索引效率就降低;反之,负载因子越小则链表中的数量就越稀疏,此时会对空间造成浪费,不过此时索引效率高。)

    空间、时间占用测试

    unordered_map<string, bool> unordermp;
    main_key = “https://blog.csdn.net/muyuyuzhong/article/details/”;
    sub_key = to_string(i);
    key = main_key + sub_key;

    在这里插入图片描述
    从上面的测试我们看到,当存储key值为53bytes的URL时,占用的内存空间和插入的耗时开销是相当大的,如果数据量达到1亿、10亿,这个时候性能就比较差。

    同样的硬件配置和数据,使用布隆过滤器存储1000万条数据存储消耗的内存约为22.852562M,相比于HashMap的1599.5M,节省约67倍的内存空间。

    另外,Hash一般元素超过表空间的一半就需要扩容,如果不进行扩容hash冲突就会变得严重,以致hash会退化为链表的性能。
    比如,最大表1000bit,元素500,当再有一个新的数据要插入进来的时候就需要对表进行扩容。


    三、布隆过滤器原理

    布隆过滤器是一个bit向量或者说是bit数组:
    在这里插入图片描述
    布隆过滤器不存储key值,内存消耗上相对于hashmap节省了key值的内存消耗。

    1、原理

    当一个元素被加入集合时,通过K个hash函数将这个元素映射成一个位数组中的K个点,把它们置为1。

    2、检索

    通过k个点位的值进行判断。
    • k个点位中有任一为0,被检元素一定不存在。
    • k个点位都是1,被检元素可能存在。

    3、实例

    在这里插入图片描述
    从上面两个图示例子中,我们可以看到bit4在baidu和tencent被置1,表示bit4值出现了覆盖。
    (1)查询“xiazhiqi”是否存在,假设hash1、hash2、hash3哈希函数分别返回1、6、7,三个值,而bit6值为0,说明没有值映射到这个bit位上,因此我们可以很确定的说“xiazhiqi”这个值不存在。
    (2)查询“baidu”是否存在,哈希函数返回1、4、7,检查发现这三个bit的值均为1,我们不能说baidu一定存在,而是只能说可能存在。因为每个bit值都有可能是被其他元素的值覆盖了。


    四、布隆过滤器的设计与实现

    布隆过滤器存在一定的误判,在查找元素值都返回1的时候,我们没法确定该元素就一定存在,不过我们可以通过一些参数的设置来降低误判率。
    假设m为向量表的长度,k为哈希函数的个数,n为要插入的元素个数,p为误判概率。

    布隆过滤器误判率表
    在这里插入图片描述
    为每个URL分配两个字节就可以达到千分之几的冲突。比较保守的实现是,为每个URL
    分配4个字节,项目和位数比是1∶32,误判率是0.00000021167340。对于5000万数量级
    的URL,布隆过滤器只占用200MB的空间。

    在实际应用中,我们一般是可以给定n、p,然后计算出m、k。

    1、m值的选取

    在这里插入图片描述

    2、k值的选取

    在这里插入图片描述

    3、哈希函数选择

    • 常见应用比较广的hash函数有MD5、SHA1、SHA256,一般用于信息安全方面,比如签名认证和加密等。比如我们传文件时习惯对原文件内容计算它的MD5,生成128bit的整数,通常我们说的32位MD5,是转换为HEX格式后的32个字符。
    • MutmurHash相比较MD5,不太安全。但性能是MD5的几十倍。MurmurHash有多个版本,其中MurmurHash3修复了MurmurHash2的一些缺陷同时速度还要快一些,因此很多开源项目有用,比如Nginx、Redis、memcashed、Hadoop等。

    我们这里选择MurmurHash2算法实现。

    4、是否可以删除集合中的元素?

    答案是否。上面我们提到,在布隆过滤器算法中会存在一个bit位被多个元素值覆盖的情况,即bit位碰撞,如果我们删除元素时刚好重置该碰撞bit为0,那么其他元素在查找的时候,就会导致判断出错的问题发生。

    5、部分源码实现

    1) m、k值计算

    void CalcBloomFilterParam(uint32_t n, double p, uint32_t *pm, uint32_t *pk)
    {
        /**
         *  n - Number of items in the filter
         *  p - Probability of false positives, float between 0 and 1 or a number indicating 1-in-p
         *  m - Number of bits in the filter
         *  k - Number of hash functions
         *
         *  f = ln(2) × ln(1/2) × m / n = (0.6185) ^ (m/n)
         * m = -1*n*ln(p)/((ln(2))^2) = -1*n*ln(p)/(ln(2)*ln(2)) = -1*n*ln(p)/(0.69314718055995*0.69314718055995))
         *   = -1*n*ln(p)/0.4804530139182079271955440025
         * k = ln(2)*m/n
        **/
    
        uint32_t m, k, m2;
    
        // 计算指定假阳(误差)概率下需要的比特数
        m =(uint32_t) ceil(-1.0 * n * log(p) / 0.480453); 	//向上舍入为最近的整数
        m = (m - m % 64) + 64;                              			// 8字节对齐
    
        // 计算哈希函数个数
        double double_k = (0.69314 * m / n); 
        k = round(double_k);    // 返回四舍五入整数值
        
        *pm = m;
        *pk = k;
        return;
    }
    

    2) MurmurHash2算法

    uint64_t MurmurHash2_x64 ( const void * key, int len, uint32_t seed )
    {
        const uint64_t m = 0xc6a4a7935bd1e995;
        const int r = 47;
    
        uint64_t h = seed ^ (len * m);
    
        const uint64_t * data = (const uint64_t *)key;
        const uint64_t * end = data + (len/8);
    
        while(data != end)
        {
            uint64_t k = *data++;
    
            k *= m;
            k ^= k >> r;
            k *= m;
    
            h ^= k;
            h *= m;
        }
    
        const uint8_t * data2 = (const uint8_t*)data;
    
        switch(len & 7)
        {
        case 7: h ^= ((uint64_t)data2[6]) << 48;
        case 6: h ^= ((uint64_t)data2[5]) << 40;
        case 5: h ^= ((uint64_t)data2[4]) << 32;
        case 4: h ^= ((uint64_t)data2[3]) << 24;
        case 3: h ^= ((uint64_t)data2[2]) << 16;
        case 2: h ^= ((uint64_t)data2[1]) << 8;
        case 1: h ^= ((uint64_t)data2[0]);
            h *= m;
        };
    
        h ^= h >> r;
        h *= m;
        h ^= h >> r;
    
        return h;
    }
    

    五、布隆过滤器与位图的比较

    1、BitMap

    BitMap在处理海量数据也有着得天独厚的优势,利用内存中连续的二进制位(bit),对大量整型数据做去重和查询。由于每一个数据只占用1个bit,因此占用内存非常小,即使在处理url、邮件地址等其他数据类型时,把字符串变换为整数,也有各式各样的方法。

    BitMap存储空间计算方式:
    找到所有元素里最大的值(假设为N),BitMap所需空间为:
    在这里插入图片描述
    当N为64位整数时,根据上述公式求得S=2^64 / 8 Byte。可以说是一个很大的数字了。
    BitMap优点是:空间不随集合内元素个数的增加而增加,但缺点是:空间随集合内最大元素的增大而增大。

    适用:大规模但数据状态又不是很多的数据的压缩、索引、查询和去重,通常是用来判断某个数据是否存在。Java 中的 BitSet 类就是一个位图,Redis 中也提供了 BitMap 位图类。

    2、布隆过滤器

    优点:占用内存少,插入和查询速度快,时间复杂度都为 O(k),与集合中元素的多少无关。

    缺点:存在误判的情况,只能判断一个数据是否一定不存在, 无法判断一个数据是否一定存在。而且随着数据的增加,误判率会增加;另外数据无法删除。

    优化:可以通过调整hash函数的个数、向量表长度与要存储数值个数之间的比例,降低误判率。

    适用:
    在这里插入图片描述

    展开全文
  • 在介绍布隆过滤器之前我们首先引入几个场景。 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的...
  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...

    简介

    布隆过滤器(Bloom Filter)是1970年由一个叫Bloom的老哥提出的。本质上属于一种数据结构,实际组成是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

    思想

    布隆过滤器的原理:当一个元素被加入集合时,通过 K 个散列(hash)函数将这个元素映射成一个位(bit)数组中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:如果这些点有任何一个 0,则被检元素一定不在;如果都是 1,则被检元素很可能存在。

    特点

    某条数据一定不存在或可能存在。

    优点

    空间:存储数据使用的位数组,极大节省了空间。若在内存中存储海量数据,提升是很可观的;

    时间:插入、查询的时间复杂度都是O(k),k为hash函数数量;

    效率:哈希函数相互之间没有关系,可以在硬件指令层面并行计算;

    数据加密:布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势;

    缺点

    准确率:“某样东西一定不存在或者可能存在”,不能保证100%的准确匹配;

    无法删除数据:只能插入和查询元素,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

    在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

    图解

    网上找的图:

     图三:假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化,将里面每个位都设置位0。对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。

    java代码

    布隆过滤器添加元素

    • 将要添加的元素给k个哈希函数
    • 得到对应于位数组上的k个位置
    • 将这k个位置设为1

    布隆过滤器查询元素

    • 将要查询的元素给k个哈希函数
    • 得到对应于位数组上的k个位置
    • 如果k个位置有一个为0,则肯定不在集合中
    • 如果k个位置全部为1,则可能在集合中

    使用google的Guava布隆过滤器

    1.引入:

            <dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>30.1.1-jre</version>
            </dependency>

    2.使用:

    import com.google.common.base.Charsets;
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    /**
     * 谷歌开源的Guava布隆过滤器
     * @author yangzihe
     * @date 2021/6/3
     */
    public class GuavaBloomFilter {
        public static void main(String[] args) {
            // 总数量
            int total = 1000000;
            // 默认误判率fpp0.03
            BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
            // 初始化 total 条数据到过滤器中
            for (int i = 0; i < total; i++) {
                bf.put("" + i);
            }
            // 判断值是否存在过滤器中
            int count = 0;
            for (int i = 0; i < total + 10000; i++) {
                if (bf.mightContain("" + i)) {
                    count++;
                }
            }
            System.out.println("已匹配数量 " + count);// (1000309 - 1000000)/(1000000 + 10000) * 100 ≈ 0.030594059405940593
    
            //指定误判率:万分之一,提高匹配精度
            BloomFilter<CharSequence> bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
            for (int i = 0; i < total; i++) {
                bfWithFpp.put("" + i);
            }
            int countFpp = 0;
            for (int i = 0; i < total + 10000; i++) {
                if (bfWithFpp.mightContain("" + i)) {
                    countFpp++;
                }
            }
            //误判率 fpp 的值越小,匹配的精度越高。当减少误判率 fpp 的值,需要的存储空间也越大,所以在实际使用过程中需要在误判率和存储空间之间做个权衡。
            System.out.println("指定误判率已匹配数量 " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 100 ≈ 0.0001
        }
    }

    布隆过滤器的误判率(FPP):

    • n:要添加的元素数量;
    • k:哈希的次数;
    • m:布隆过滤器的长度(如比特数组的大小);

    布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算:

    最优哈希函数数量k,如果m是数组长度,n是插入的元素个数,k是hash函数的个数,k计算公式如下:

    Guava布隆过滤器源码记录

    BloomFilter的4个成员变量:

        /** bit数组:Guava实现的以CAS方式设置每个bit位 */
        private final LockFreeBitArray bits;
        /** hash函数的个数 */
        private final int numHashFunctions;
        /** guava中将对象转换为byte的通道 */
        private final Funnel<? super T> funnel;
        /** 将byte转换为n个bit的策略,也是bloomfilter hash映射的具体实现 */
        private final Strategy strategy;

    LockFreeBitArray:封装了布隆过滤器底层bit数组的操作。
    numHashFunctions:哈希函数的个数。
    Funnel:它和PrimitiveSink配套使用,能将任意类型的对象转化成Java基本数据类型,默认用java.nio.ByteBuffer实现,最终均转化为byte数组。
    Strategy:strategy是布隆过滤器的哈希策略,即数据如何映射到位数组,其具体方法在BloomFilterStrategies枚举中。代码如下,主要有2个方法,put和mightContain。

        interface Strategy extends java.io.Serializable {
            /** 设置元素 */
            <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits);
            /** 判断元素是否存在 */
            <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits);
            ...
        }

    构造函数:

    BloomFilter只有一个私有构造函数,对外提供了5个public重载的create方法,在缺省情况下误判率设定为3%,采用BloomFilterStrategies.MURMUR128_MITZ_64的实现。5个重载的create方法最终实现逻辑:

      @VisibleForTesting
      static <T> BloomFilter<T> create(
          Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
        checkNotNull(funnel);
        checkArgument(
            expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
        checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
        checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
        checkNotNull(strategy);
    
        if (expectedInsertions == 0) {
          expectedInsertions = 1;
        }
        /*
         * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
         * is proportional to -log(p), but there is not much of a point after all, e.g.
         * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
         */
        long numBits = optimalNumOfBits(expectedInsertions, fpp);
        int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
        try {
          return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
        } catch (IllegalArgumentException e) {
          throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
        }
      }

    该方法接受4个参数:funnel是插入数据的Funnel,expectedInsertions是期望插入的元素总个数n,fpp即期望误判率p,strategy即哈希策略。

    m:位数组的长度;

    k:哈希函数的个数;

    由上可知,m和k分别通过optimalNumOfBits()方法和optimalNumOfHashFunctions()方法来估计。

      @VisibleForTesting
      static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
          p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
      }
    
      @VisibleForTesting
      static int optimalNumOfHashFunctions(long n, long m) {
        // (m / n) * log(2), but avoid truncation due to division!
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
      }

                                                          

    optimalNumOfHashFunctions()方法的逻辑                         optimalNumOfBits()方法的逻辑

    如果指定期望误判率p,那么最优的m值与期望元素数n呈线性关系。
    最优的k值实际上只与p有关,与m和n都无关,即:

    所以,在创建BloomFilter时,确定合适的p和n值很重要。

    在BloomFilterStrategies枚举中定义了两种哈希策略,都基于著名的MurmurHash算法,分别是MURMUR128_MITZ_32和MURMUR128_MITZ_64。

    参考:https://www.jianshu.com/p/bef2ec1c361f

    Guava 提供的布隆过滤器的实现还是很不错的,但是它有一个重大的缺陷就是只能单机使用(另外,容量扩展也不容易),而现在互联网一般都是分布式的场景。为了解决这个问题,我们就需要用到 Redis 中的布隆过滤器了。然后,为了解决布隆过滤器无法删除数据的问题,引入了counting bloom filter计数式布隆过滤器。redis布隆、counting布隆有缘再续吧。。。

     

    展开全文
  • 布隆过滤器是空间高效的概率 数据结构,通过设想伯顿霍华德布卢姆于1970年,是用于测试一个是否元件是一个的成员组。可能会出现假阳性匹配,但否定否定匹配-换句话说,查询返回“可能在集合中”或“绝对不在集合中”...
  • 什么是布隆过滤器 介绍+优点 应用场景 设计原理 布隆实战 总结 存在的问题 + 总结
  • 详解布隆过滤器

    千次阅读 2019-07-01 00:45:40
    假设我们想要开发一个邮件系统,那么如何实现垃圾邮件的过滤呢。 最简单的办法就是把确定为是垃圾邮件的地址都保存起来,存入黑名单中。当用户接收到黑名单地址的邮件时,直接将邮件归类到垃圾箱中。 垃圾邮件的...
  • 布隆过滤器

    千次阅读 2019-07-22 09:46:17
    本质上布隆过滤器是一种数据结构,比较巧妙的概率数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 List、Set、Map 等数据...
  • 布隆过滤器原理解析

    2019-11-07 17:34:32
    在撸码的时候,经常要判断一个元素是否已经存在。常用的做法是,把已经存在的元素全部存储到一个集合里,然后新的元素查一下看它是否在集合里来确定是否...如果你刚好遇到这方面的问题,那么可以考虑一下布隆过滤器...
  • 过滤器使用场景: 比如有如下几个需求: 1.原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中?  解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了,...
  • 布隆过滤器详解

    2019-10-23 14:55:46
    本质上布隆过滤器是一种数据结构,比较巧妙的概率数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 List、Set、Map 等数据...
  • 谈谈布隆过滤器

    2019-12-17 17:16:23
    布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,...
  • 布隆过滤器 1.为什么诞生 为了高效的插入数据和查询数据 现实场景:从上亿数据中判断一条数据是否存在,使用map,set等常规数据结构,导致内存急速膨胀,需要大量空间,需要一种更为巧妙的方式,判断数据是否存在,...
  • 布隆过滤器学习

    2019-07-04 11:04:24
    布隆过滤器 学习起因,因上课听老师...本质上布隆过滤器是一种数据结构,比较巧妙的概率数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。...
  • 频谱布隆过滤器与常规过滤器不同,因为它们可以存储每个哈希的计数(它可以估计至少索引了哈希的次数)。 我们正在使用有效的base 15解码来压缩和传输客户端的Bloom过滤器。 我们的目标可以用一个简单的方程式来...
  • 本文是《玩转Redis》系列第【11】篇,本文关键字:玩转Redis、Bloom filter、布隆过滤器、无偏hash函数; - 布隆过滤器的底层原理 - 布隆过滤器的底层结构 - 最佳hash函数数量与错误率的关系 - 所需存储空间与...
  • Java redis 模拟布隆过滤器

    千次阅读 2018-12-13 16:21:40
    基本概念 如果想判断一个元素是不是在一个集合里,...首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。   redis对bitmaps的解释: ...
  • 1.布隆过滤器使用场景 比如有如下几个需求: ①、原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中? 解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了...
  • 布隆过滤器简介

    2019-11-20 17:27:31
    引文 思考一个问题:从大量数据里面如何高效率地去重? 有过一点编程经验的人都知道,可以通过Set这种数据结构来做到。比如HashSet,采用了Hash算法,可以在O(1)的复杂度完成数据的添加和查询操作。...布隆过滤器 布...
  • 本质上布隆过滤器是一种数据结构,比较巧妙的概率数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 List、Set、Map 等...
  • 如果已经统计,则不做处理,如果没有则进行计数累加,并更新布隆过滤器 if (!flag) { //先取出旧值 val uvCountMap = "uvCount" val currentKey = w.getEnd.toString var count = 0L if (jedis.hget(uvCountMap, ...
  • 布隆过滤器 为什么需要布隆过滤器 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。 但是...
  • 只是引入布隆过滤器会带来一定的内存消耗,下图是在Key-Value系统中布隆过滤器的典型使用: 布隆过滤器相关扩展 Counting filters 基本的布隆过滤器不支持删除(Deletion)操作,但是 Counting filters 提供了一种...
  • 网上大部分python实现的布隆过滤器库如:pybloomfilter、pybloom 但都是基于py2且哈希函数用的都是sha1类、md5类,效率不如mmh3.所以决定自己实现, git地址:https://github.com/Sssmeb/BloomFilter 第一次自己实现...
  • 布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法 引言 在介绍布隆过滤器之前我们首先引入几个场景。 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的...
  • 布隆过滤器1、 布隆过滤器的概念2、 布隆过滤器的插入与查找2.1 布隆过滤器的插入2.2 布隆过滤器的查找2.3 布隆过滤器产生误判的原因3、布隆过滤器的删除4、布隆过滤器优点5、布隆过滤器缺陷6、使用场景7、海量数据...
  • Redis布隆过滤器

    2019-10-07 10:00:00
    解决了布隆过滤器的一些比较明显的缺点,比如:不能删除元素,不能计数等。除此之外,布谷鸟过滤器不用使用多个hash函数,所以查询性能更高。除此之外,在相同的误判率下,布谷鸟过滤器的空间利用率要明显高于布隆,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,651
精华内容 1,460
关键字:

计数型布隆过滤器