布隆过滤器

Java

发布日期: 2021-04-21

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

简单来说就是：当我们通过布隆过滤器判断一个元素在不在集合中时；如果布隆过滤器返回的是在集合中，那么集合中可能没有这个元素；如果布隆过滤器返回的不存在于集合中，那么集合中是一定不存在这个元素的。

参考文档

布隆过滤器算法分析

下面通过一个简要例子和图例来对布隆过滤器进行简要的说明。

假如现在有10亿个数组成的集合M（数的范围在1~10亿之间），现在新来一个数x，那么该如何快速的判断这个数在不在集合中？同时又需要尽量的节约内存呢？

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢，同时这些数据实际我们几乎就不会用，仅仅是想知道一个元素在不在一个集合中。由此诞生了散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

消耗空间分析

传统方案：将集合M的数用散列表保存，然后对数x判断是否在散列表中即可；内存计算：假设使用int类型来保存，那么10亿个数消耗的内存 = 4byte(int)*10亿 ≈ 381M。

位图方案：由于我们只关心数x是否存在于集合中，因此我们通标记0和1来标记，通下标来表示数；即开辟空间使用byte数组来保存，那么10亿个数消耗的内存 = 1byte*10亿 ≈ 95M。

上面看去视乎消耗不大，那么我们现在将数据量扩大10倍，即有100亿个数，此时传统方案大约需要3.7G；使用位图的方案大约需要0.9G。

想想我们服务器的内存才多少个G，而这个还仅仅只是这个Java程序中的一个Java对象，同时其他外在因素都未考虑进去，而我们这仅仅是系统中一个小小的判断是否存在的功能；无论是使用位图方案还是传统方案都不是太符合要求。

PS. 不要觉得10亿数据很多；假如公司的一个业务有500万用户，平均每个用户一天产生10条数据，一个月(30天)就是1.5亿条数据，那么一年就是18亿条数据；而这只是一个业务功能中的一个表，如果有多个的话…

布隆过滤器的设计方案

通过上面的内存消耗分析，我们知道需要对方案进行优化；而布隆过滤器正是在位图方案的基础上进行优化设计。它的设计方案如下：

对于100亿个数的要求，我们开辟一个10亿的空间大小；当放入一个数x(判断的时候也类似)，通过几种不同的hash算法计算这个数x的hash值，然后将这几个hash值对应的小标置为1；就像下面这样：

当多个值进入的时候：

从上面的图中可以发现传统的散列表设计使用一个hash的话，会出现hash冲突；因此在布隆过滤器中选择使用多种不同的hash算法得到多个hash值，有多个hash值来定位一个数的位置，这样就可以有效的减小hash冲突概率了。
但是由于其散列表的基础特性依旧没有突破，因此会依然会存在误判的可能（从图中可以很容易地发现），这也就就是布隆过滤器的特性总结一句话就是：

告诉你没有那是真的没有；告诉你有可能是有，也可能是没有。你细品…像不像你问你女票的时候的情况，区别就布隆过滤器说没有那就是真的没有 :)

因此布隆过滤器适合的场景是对误判有一定容忍度的场景，比如说：垃圾邮箱、钓鱼网址、URL地址判重（比如爬虫）、海量图库判重、推荐算法（比如新闻资讯这些推荐给用户，但是需要将用户看过的去掉，如果通过数据库里面的历史记录来去重，时间久了数据量会很大…）

引入布隆过滤器后，也会带来新的问题，导致将系统业务复杂化。正所谓 ‘鱼与熊掌不可兼得’；因此需要仔细思量。

一些示例场景

下面我们通过几个例子来感受下布隆过滤器是如何使用的。

Java实现布隆过滤器

对于布隆过滤器我们在设计的时候需要考虑应该开辟多大的空间才合适；为了保证布隆过滤器有适当的正确率通常会设置几个参数：

k: hash函数个数，用于将一个数据通过不同hash函数计算为不同值;
n = 数据量大小；
m = 位数组长度；
p = 布隆过滤器的容错率；

计算公式如下：

k = -lnP/ln2    m = k*n/ln2 = -lnP*n/(ln2*ln2)

Java的简单实现，对应hash算法使用的是对象默认的，没有去专门设计相关的算法（这个可以去参考guava的hash算法），只是进行简单的处理了下。

public class ConsumerBloomFilter<T> {
    private final byte[] byteMap;
    
    private final int capacity;
    
    private ConsumerBloomFilter(int capacity){
        this.capacity = capacity;
        byteMap = new byte[capacity];
    }
    
    public static <T> ConsumerBloomFilter<T> create(int n, double fpp){
        int capacity = calculateCapacity(n, fpp);
        return new ConsumerBloomFilter<>(capacity);
    }
    
    public void put(T value){
        int[] index = index(value);
        byteMap[index[0]] = 1;
        byteMap[index[1]] = 1;
    }
    
    public boolean mightContain(T value){
        int[] index = index(value);
        for(int i:index){
            if(byteMap[i]==0){
                return false;
            }
        }
        return true;
    }
    
    int[] index(T value){
        // 计算hash: 这里借鉴hashmap的实现
        int hash1 = hash(value);
        int hash2 = hash1^(hash1>>16);
        hash1 = (hash1<0?-hash1:hash1)%capacity;
        hash2 = (hash2<0?-hash2:hash2)%capacity;
        return new int[]{hash1, hash2};
    }
    
    static int hash(Object key) {
        return (key == null) ? 0 : key.hashCode();
    }
    
    /**
     * 为了保证误判率，计算容量
     */
    static int calculateCapacity(int n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
}

Google的guava包中布隆过滤器的使用示例

Google的guava工具包中有对布隆过滤器的实现，Guava中布隆过滤器的实现主要涉及到 BloomFilter 和 BloomFilterStrategies 这2个类，注意各个版本的实现可能会有些许不同。下面我们来看如何使用。

添加如下maven的依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>18.0</version>
</dependency>

基于Guava中布隆过滤器实现对钓鱼网址进行判断：

// 预估数据量大小
int n = 1000000;
// 可以接受的布隆过滤器误判率
double p = 0.1;
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), n, p);

int existNum = 0;
for(int i=0; i<n; i++){
    String url = "www.baidu.com?key="+i;
    // 判断是否存在
    boolean exist = bloomFilter.mightContain(url);
    if(exist){
        existNum++;
    }else {
        // 不存在就放入
        bloomFilter.put(url);
    }
}
System.out.println("误判率："+existNum*1.0*100/n+"%");

Guava中自己实现了相关的hash算法。

基于Redis的Bitmaps来实现

redis的Bitmaps就是相当于去操作一个二进制串对应的位的值。

public class RedisBloomFilter<T> {

    private final RedisTemplate<String, T> redisTemplate;
    private final String key;
    private final int capacity;
    private final int numHashFunctions = 2;

    public RedisBloomFilter(String key, RedisTemplate<String, T> redisTemplate, int n, double p){
        this.redisTemplate = redisTemplate;
        this.key = key;
        this.capacity = calculateCapacity(n, p);
    }


    public void put(T value){
        int[] hash = index(value);
        for(int i = 1; i <= numHashFunctions; ++i) {
            int combinedHash = hash[0] + i * hash[1];
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            this.redisTemplate.opsForValue().setBit(key, combinedHash%capacity, true);
        }
    }

    public void del(T value){
        int[] hash = index(value);
        for(int i = 1; i <= numHashFunctions; ++i) {
            int combinedHash = hash[0] + i * hash[1];
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            this.redisTemplate.opsForValue().setBit(key, combinedHash%capacity, false);
        }
    }

    public boolean mightContain(T value){
        int[] hash = index(value);
        for(int i = 1; i <= numHashFunctions; ++i) {
            int combinedHash = hash[0] + i * hash[1];
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            Boolean exist = this.redisTemplate.opsForValue().getBit(key, combinedHash%capacity);
            if(Boolean.FALSE.equals(exist)){
                return false;
            }
        }
        return true;
    }


    private int[] index(T value){
        int hash1 = hash(value);
        int hash2 = hash1^(hash1>>>16);
        return new int[]{hash1, hash2};
    }

    private static int hash(Object key) {
        return (key == null) ? 0 : key.hashCode();
    }

    private static int calculateCapacity(int n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
}

下面使用个使用布隆过滤器来解决缓存穿透的问题简单示例；我们假设在添加或删除数据后在刷新缓存的同时也更新布隆过滤器的内容；也就是说提前将有的id设置到布隆过滤器里面，然后后面再查询的时候先使用布隆过滤器去判断一下。

@Autowired
private RedisTemplate<String, Student> redisStuTemplate;
@Autowired
private RedisTemplate<String, Long> redisLongTemplate;
private RedisBloomFilter<Long> bloomFilter;
@Test
public void bloomFilterDemo(){
    bloomFilter = new RedisBloomFilter<>("bloom_member_id_table", this.redisLongTemplate, 1000000, 0.01);
    
    bloomFilter.put(1L);
    Student stu =  findById(1L);
    System.out.println(stu);
    stu =  findById(100000L);
    System.out.println(stu);
}

private Student findById(Long uid){
    if(bloomFilter.mightContain(uid)){
        System.out.println("存在");
        
        Student stu = redisStuTemplate.opsForValue().get("member"+uid);
        System.out.println("查询缓存");
        
        if(stu==null){
            System.out.println("查询数据库");
            // 从数据库查询，之后写入缓存
            stu = Student.create();
            if(stu==null){
                // 删除掉会有一定的风险，因此需要考虑hash冲突的问题。
                // bloomFilter.del(uid);
                // 因此这里缓存一个空对象
                stu = new Student();
            }
            redisStuTemplate.opsForValue().set("member"+uid, stu);
        }
        return stu;
    }
    return null;
}