资讯详情

BloomFilter怎么用？使用布隆过滤器来判断key是否存在？

一、前言

今天，我和一位同事谈了一个问题，说我最近在做推荐。如何判断用户是否看过这个片段？想了想，你可以用布隆过滤器来满足这个需求。

布隆，不是LOL布隆。我们的布隆是1970年提出的一个叫布隆的外国人计划：如果你判断这一点key如果不存在，就不存在。如果不存在，key它存在，所以它可能不存在。所以当它不存在时，你总是可以详细地布隆。 在这里插入图片描述

布隆的原理是什么？

布隆过滤器是由高空间利用率的概率数据结构Burton Bloom1970年提出测试一个元素是否集合。

新建的布隆过滤器是一串0Bit数组(假设有m位)同时声明k不同Hash随机分布产生统一的函数（k常数小于m)。

插入数据

在布隆过滤器中添加元素时，通过kHash函数映射元素Bit这些位置的值设置为1和1Bit不同的数据可以共享位置。如下图所示，假设布隆过滤器的k为3，插入其中X1、X2的过程。

查询

查询元素时，仍通过kHash函数得到相应的k位，判断目标位置是否为1。如果目标位置为1，则认为该元素在布隆过滤器中，否则认为该元素不存在。下图显示了布隆过滤器中的查询Y1和Y是否存在过程。

查询y1y2 从上图可以看出，虽然从未插入布隆过滤器Y2这个元素，但布隆过滤器判断Y2.因此，布隆过滤器可能存在误判，即假阳性（false positive）。到目前为止，我们可以得出布隆过滤器的几个特点：

  • Bit不同的数据可以共享位置。
  • 存在假阳性（false positive），布隆过滤器中的元素越多，假阳性的可能性就越大，但没有假阴性（false negative），也就是说，存在的元素不会被误判为不存在。
  • 布隆过滤器可以添加元素，但不能删除，因为Bit位置可以共享，删除时可能会影响其他元素。
  • 数据量越大，占用的内存就越大。
  • 容错率越低，内存越大，因为bit更多的位置。

优化

鉴于布隆过滤器会越来越大，我们可以给出一些建议：

  • 做好业务拆分，建立多个布隆过滤器，各个业务用相对应的。

这样做的好处是可以防止数据增长，导致数据增长key太大，影响性能，不容易扩展，毕竟redis或者内存大小有上限。另一个优点是可以平衡请求，防止所有请求都进入节点，导致热点key，访问倾斜。

  • 定期重置，定期重建

如果业务允许，我们可以从新的统计数据中清空数据。

三、实现代码

简单的HashMap实现

首先，我们定义一个长度固定的数组，然后通过两次hash，计算数据值，再和array的size取余，更新相应的字段为1，会有很多容错，这与我们的数组长度和我们有关hash次数有关。因此，根据业务选择。

另外，这是一个单节点，我们的机器存在jvm内存，如果我们重启服务，数据就会消失。

package com.ares.bloom;  public class BloomFilter { 
             /** * 数组长度 */     private int size;     /** * 数组 */     private int[] array;     public BloomFilter(int size) { 
                 this.size = size;         this.array = new int[size];     }     /** * 添加数据 */     public void add(String item) { 
                 int firstIndex = func1(item);         int secondIndex = func2(item);         array[firstIndex % size] = 1;         array[secondIndex % size] = 1;
    }
    /** * 判断数据 item 是否存在集合中 */
    public boolean contains(String item) { 
        
        int firstIndex = func1(item);
        int secondIndex = func2(item);
        int firstValue = array[firstIndex % size];
        int secondValue = array[secondIndex % size];
        return firstValue != 0 && secondValue != 0;
    }
    /** * hash 算法 func1 */
    private int func1(String key) { 
        
        int hash = 7;
        System.out.println(hash);
        hash += 61 * hash + key.hashCode();
        System.out.println(hash);
        hash ^= hash >> 15;
        System.out.println(hash);
        hash += hash << 3;
        System.out.println(hash);

        hash ^= hash >> 7;
        System.out.println(hash);

        hash += hash << 11;
        System.out.println(hash);

        return Math.abs(hash);
    }
    /** * hash 算法 func2 */
    private int func2(String key) { 
        
        int hash = 7;
        for (int i = 0, len = key.length(); i < len; i++) { 
        
            hash += key.charAt(i);
            hash += (hash << 7);
            hash ^= (hash >> 17);
            hash += (hash << 5);
            hash ^= (hash >> 13);
        }
        return Math.abs(hash);
    }


    public static void main(String[] args) { 
        
        BloomFilter filter = new BloomFilter(10000);
        System.out.println(filter.contains("1"));
        System.out.println(filter.contains("2"));
        filter.add("1");
        System.out.println(filter.contains("1"));
        filter.add("2");
        System.out.println("---------------------------------");
        System.out.println(filter.contains("2"));


    }
}

结果：

/Library/Java/JavaVirtualMachines/jdk1.8.0_261.jdk/Contents/Home/bin/java -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:60696,suspend=y,server=n -javaagent:/Users/apple/Library/Caches/JetBrains/IntelliJIdea2020.1/captureAgent/debugger-agent.jar -Dfile.encoding=UTF-8 -classpath /private/var/folders/5b/_717vl_x3d1dx5jx8512k7300000gn/T/classpath2097007646.jar com.ares.bloom.BloomFilter
Connected to the target VM, address: '127.0.0.1:60696', transport: 'socket'
7
483
483
4347
4314
8839386
false
7
484
484
4356
4390
8995110
false
7
483
483
4347
4314
8839386
7
483
483
4347
4314
8839386
true
7
484
484
4356
4390
8995110
---------------------------------
7
484
484
4356
4390
8995110
true
Disconnected from the target VM, address: '127.0.0.1:60696', transport: 'socket'

Process finished with exit code 0

使用Google开源的Guava自带布隆过滤器

Guava 提供了自带的布隆过滤器，而且有相关的参数可以配置，可以更好的实现。

但是Guava还是基于单台机器的，在分布式架构上就不通用了。

引入依赖

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

demo:

package com.ares.bloom;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import lombok.extern.slf4j.Slf4j;

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

@Slf4j
public class GravaBloomTest { 
        
    public static void main(String[] args) { 
        
        intBloom();
        stringBloom();
    }

    public static void intBloom(){ 
        
        Integer count = 5000000;
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), count,0.01);
        for (int i = 0; i < count; i++) { 
        
            bloomFilter.put(i);
        }

        long begin = System.currentTimeMillis();
        if (bloomFilter.mightContain(50000)){ 
        
            log.info("成功过滤到 50000");
        }
        long end = System.currentTimeMillis();
        log.info("布隆过滤器消耗时间"+(end - begin)/1000000L+"毫秒");
    }

    public static  void stringBloom(){ 
        
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),5000000,0.01);
        List<String> list = new ArrayList<>(5000000);
        for (int i = 0; i < 5000000; i++) { 
        
            String uuid = UUID.randomUUID().toString();
            bloomFilter.put(uuid);
            list.add(uuid);
        }
        int mightContainNumber1= 0;
        NumberFormat percentFormat = NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2);

        for (int i=0;i < 500;i++){ 
        
            String key = list.get(i);
            if (bloomFilter.mightContain(key)){ 
        
                mightContainNumber1++;
            }
        }
        log.info("【key真实存在的情况】布隆过滤器认为存在的key值数：" + mightContainNumber1);
        log.info("================================================================================");
        int mightContainNumber2 = 0;
        for (int i=0;i < 5000000;i++){ 
        
            String key = UUID.randomUUID().toString();
            if (bloomFilter.mightContain(key)){ 
        
                mightContainNumber2++;
            }
        }

        log.info("【key不存在的情况】布隆过滤器认为存在的key值数：" + mightContainNumber2);
        log.info("【key不存在的情况】布隆过滤器的误判率为：" + percentFormat.format((float)mightContainNumber2 / 5000000));
    }
}

结果：

从结果可以看到，从500万的数据中判断一个key是否存在时间还是很快的，而且我们知道， String key = UUID.randomUUID().toString(); uuid 每次生成都是不一样的，我们在第二次处理的时候，发现，我们用已经存在的去查，肯定是可以查到的。我们用不存在的差，设置了1%的误差，所以就会有50636命中了存在。这个也是因为，他们hash碰撞到了一个位上。

/Library/Java/JavaVirtualMachines/jdk1.8.0_261.jdk/Contents/Home/bin/java -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:63708,suspend=y,server=n -javaagent:/Users/apple/Library/Caches/JetBrains/IntelliJIdea2020.1/captureAgent/debugger-agent.jar -Dfile.encoding=UTF-8 -classpath /private/var/folders/5b/_717vl_x3d1dx5jx8512k7300000gn/T/classpath815744853.jar com.ares.bloom.GravaBloomTest
Connected to the target VM, address: '127.0.0.1:63708', transport: 'socket'
22:31:31.060 [main] INFO com.ares.bloom.GravaBloomTest - 成功过滤到 50000
22:31:31.062 [main] INFO com.ares.bloom.GravaBloomTest - 布隆过滤器消耗时间0毫秒
22:31:48.839 [main] INFO com.ares.bloom.GravaBloomTest - 【key真实存在的情况】布隆过滤器认为存在的key值数：5000000
22:31:48.839 [main] INFO com.ares.bloom.GravaBloomTest - ================================================================================
22:31:53.642 [main] INFO com.ares.bloom.GravaBloomTest - 【key不存在的情况】布隆过滤器认为存在的key值数：50636
22:31:53.642 [main] INFO com.ares.bloom.GravaBloomTest - 【key不存在的情况】布隆过滤器的误判率为：1.01%
Disconnected from the target VM, address: '127.0.0.1:63708', transport: 'socket'

Process finished with exit code 0

分布式处理——用redis实现布隆过滤器

前面我们用的都是单台机器内存上的布隆过滤器，我们要用到分布式，就要用到redis来处理了。如果用redis的布隆，

首先，如果我们没有钱，自己搭建的redis

我们需要安装插件：

1、点击https://redis.io/modules 找到RedisBloom 2、点击进去下载RedisBloom-master.zip文件，上传到linux 3、解压缩刚才的RedisBloom文件

unzip RedisBloom-master.zip
cd RedisBloom-master

编译安装

make

make完生成redisbloom.so，拷贝到redis的安装目录。

cp redisbloom.so /home/www/server/redis

在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址,如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址

loadmodule /home/www/server/redis/redisbloom.so

保存以后重启redis服务

 redis-server redis.conf --loadmodule /home/www/server/redis/redisbloom.so

上面我们有提到需要重启Redis，在本地和测试环境还可以，但是正式环境能不重启就不需要重启，那这么做可以不重启Redis，使用module load命令执行。

> MODULE LOAD /home/www/server/redis/redisbloom.so
> module list
1) 1) "name"
   2) "bf"
   3) "ver"
   4) (integer) 999999

看到以上数据则说明redisbloom加载成功了，模块名name为"bf"，模块版本号ver为999999。

pom中引入redisson依赖:

<dependency>
   <groupId>org.redisson</groupId>
   <artifactId>redisson-spring-boot-starter</artifactId>
   <version>3.13.1</version>
</dependency>

demo：

	public void patchingConsum(ConsumPatchingVO vo) throws ParseException { 
        
		Config config = new Config();
		SingleServerConfig singleServerConfig = config.useSingleServer();
		singleServerConfig.setAddress("redis://127.0.0.1:6379");
		singleServerConfig.setPassword("123456");
		RedissonClient redissonClient = Redisson.create(config);
		RBloomFilter<String> bloom = redissonClient.getBloomFilter("name");
		// 初始化布隆过滤器； 大小:100000，误判率:0.01
		bloom.tryInit(100000L, 0.01);
		// 新增10万条数据
		for(int i=0;i<100000;i++) { 
        
			bloom.add("name" + i);
		}
		// 判断不存在于布隆过滤器中的元素
		List<String> notExistList = new ArrayList<>();
		for(int i=0;i<100000;i++) { 
        
			String str = 
        标签： gn丝印三极管
 
锐单商城拥有海量元器件数据手册、
          IC替代型号，打造
          电子元器件IC百科大全！

锐单商城 - 一站式电子元器件采购平台