布隆过滤器—guava-BloomFilter

发布于 2022年 05月 19日 18:30

 

应用场景:

  • 字处理软件中,需要检查一个英语单词是否拼写正确
  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上
  • 在网络爬虫里,一个网址是否被访问过
  • 邮箱垃圾邮件过滤功能
  • 比特币网络

1.  guava-BloomFilter

2. 分布式场景:  自定义布隆过滤器  hashcode + redis Getbit

 

原理:

 

 

 

 

布隆过滤器

缓存,cache,比如 redis、hashmap,是将数据存放在内存中。
cache 与 filter 有异曲同工之妙。两者为 互补 的关系。

原理:不同于 hashmap 将元素映射到某个具体链表上,filter 将一个元素 散射 到一个 二进制向量 中。

底层:使用一个很长的二进制向量和一个映射函数。

注意:检索一个元素,如果检索结果是元素不在集合中,那么肯定正确的(就表明不在)。如果检索结果是元素在集合中,那么有一定的概率是判断错了(也能不在集合中)

优点:空间效率和查询时间远超一般的算法

缺点:有一定的误识别率和删除困难

 

 

 

判断错误:B实际不存在,但是判断结果是存在:错误映射

特点:判断不存在时肯定是对的,判断存在时可能出错

如果判断 “真正存在” 呢?要去数据库进一步确认


Bloom Filter 使用场景:在前面过滤一次,过滤掉不存在的元素(不存在就是不存在),就不用去数据库查询了

但他也和 cache 是一样的,在后面必须跟一个真正的数据存储系统(DB、文件)

前边是预处理模块,后边的数据权威机构

 

Guava [BloomFilter] 简单使用

guava 依赖:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>19.0</version>
</dependency>
调整参数fpp:手动设置错误率为 0.0001
 // 要处理1亿个数据,用64MB大小的位图

BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),
        size, 0.0001);
     //1%,有个概率问题,布隆越大,占用的空间越多,但是错误概率减小了
        BloomFilter bloomFilter= BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),1000000,0.001);

 

 

测试程序:将 100w 个数据放入布隆结合,分别判断 100w 个在其中的元素的“不存在”概率 和 100w 个不存在其中的元素的 “存在”概率

@Test
public void mmm() {

    int size = 1000_000; //默认fpp 0.03
    BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size); /

    for (int i = 0; i < size; i++) {
        bloomFilter.put(i + "");
    }
        
        //判定存在的元素
    for (int i = 0; i < size; i++) {
        boolean exist = bloomFilter.mightContain(i + "");
        if (!exist) {
            //如果判定为不存在,那么一定不存在。
            System.out.println("发现漏网之鱼!!!" + i);//该语句未执行

        }
    }

    //判定不存在的元素
    int mistake = 0;
    for (int i = size; i < size * 2; i++) {
        boolean exist = bloomFilter.mightContain(i + "");
        if (exist) {
            //如果判定为存在,那么可能不存在。
            mistake++;
            //System.out.println("哦吼~误判了!!!" + i);
        }
    }

    System.out.println("误判率:" + (mistake * 1.0) / size);// 0.030094
}

 

分布式自定义: hashcode  +redis

 // 自定义一个布隆过滤器
    public static class MyBloomFilter {
        // 定义位图的大小,一般需要定义为2的整次幂
        private Integer cap;

        public MyBloomFilter(Integer cap) {
            this.cap = cap;
        }
        // 实现一个hash函数
        public Long hashCode( String value, Integer seed ){
            Long result = 0L;
            for( int i = 0; i < value.length(); i++ ){
                result = result * seed + value.charAt(i);
            }
            return result & (cap - 1);
        }
    }

将位图放入reids 

 

 Redis Getbit 命令用于对 key 所储存的字符串值,获取指定偏移量上的位(bit)。

jedis = new Jedis("localhost", 6379);
myBloomFilter = new MyBloomFilter(1<<29);    // 要处理1亿个数据,用64MB大小的位图



  // 1. 取当前的userId
            Long userId = elements.iterator().next().getUserId();

            // 2. 计算位图中的offset
            Long offset = myBloomFilter.hashCode(userId.toString(), 61);

            // 3. 用redis的getbit命令,判断对应位置的值
            Boolean isExist = jedis.getbit(bitmapKey, offset);

            if( !isExist ){
                // 如果不存在,对应位图位置置1
                jedis.setbit(bitmapKey, offset, true);

                // 更新redis中保存的count值
                Long uvCount = 0L;    // 初始count值
                String uvCountString = jedis.hget(countHashName, countKey);
                if( uvCountString != null && !"".equals(uvCountString) )
                    uvCount = Long.valueOf(uvCountString);
                jedis.hset(countHashName, countKey, String.valueOf(uvCount + 1));

                out.collect(new PageViewCount("uv", windowEnd, uvCount + 1));
            }

 

推荐文章