布隆过滤器(Bloom Filter)的原理和实现

原创
${user.getUserNickname()}
LoveIT
2020-06-11 04:12:14
894

海量数据处理以及缓存穿透这两个场景让我认识了 布隆过滤器 ，我查阅了一些资料来了解它，但是很多现成资料并不满足我的需求，所以就决定自己总结一篇关于布隆过滤器的文章。希望通过这篇文章让更多人了解布隆过滤器，并且会实际去使用它！

下面我们将分为几个方面来介绍布隆过滤器：

  1. 什么是布隆过滤器？
  2. 布隆过滤器的原理介绍。
  3. 布隆过滤器使用场景。
  4. 通过 Java 编程手动实现布隆过滤器。
  5. 利用Google开源的Guava中自带的布隆过滤器。
  6. Redis 中的布隆过滤器。

一、什么是布隆过滤器？

在学习任何东西之前我们都应该先去了解一下它是什么？能干什么？

布隆过滤器（Bloom Filter）是一个叫做 Bloom 的老哥于1970年提出的。布隆过滤器是一个神奇的数据结构，可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重\过滤。布隆过滤器的本质是由一个位数组和一系列哈希函数组成的数据结构。所谓位数组，就是指数组中的每个元素只占用1bit，每个元素只能是0或1。因此相对于List、Set、Map等结构，位数组的显著优势就是占用空间更少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

二、布隆过滤器的原理介绍。

当一个元素添加进入布隆过滤器的时候户进行如下操作：

  • 使用K个哈希函数根据元素计算出K个hash值
  • 根据得到的hash值，将位数组中对应的下标值置为1

举个例子，比如现在有一个布隆过滤器有3个哈希函数：hash1,hash2,hash3和一个位数组array，现在要把www.easyblog.top插入到布隆过滤器中，则有如下操作：

  • 对字符串进行三次hash计算，得到3个hash值：h1,h2,h3
  • 根据hash值将对应位数组中的下标值置为1：array[h1]=1,array[h2]=1,array[h3]=1

当需要判断在布隆过滤器中是否存在某个关键字的时候，只需要对关键字再次hash，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

看不懂文字？没关系，让灵魂画手画给你看

看到这里，我们就会发现一个问题：当插入的元素原来越多，位数组中被置为 1 的位置就越多，当一个不在布隆过滤器中的元素，经过哈希计算之后，得到的值在位数组中查询，有可能这些位置也都被置为 1。这样一个不存在布隆过滤器中的也有可能被误判成在布隆过滤器中。但是如果布隆过滤器判断说一个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。简单来说：

  • 布隆过滤器说某个元素在，可能会被误判。
  • 布隆过滤器说某个元素不在，那么一定不在。

三、布隆过滤器使用场景。

  1. 判断给定数据是否存在：比如判断一个数字是否在于包含海量数字的数字集中（数字集很大，亿级以上！）
  2. 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）
  3. 邮箱的垃圾邮件过滤、黑名单功能等等。
  4. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

四、通过 Java 编程手动实现布隆过滤器。

上面我们了解布隆过滤器的原理，知道了布隆过滤器的原理之后就可以自己手动实现一个了。根据原理我们向手动实现一个布隆过滤器的话，我们需要考虑：

  • 1、需要K个哈希函数
  • 2、一个合适大小的位数组
  • 3、添加元素到位数组（布隆过滤器）的方法
  • 4、判断关键字在位数组（布隆过滤器）中是否存在

如果明白了原理实现起来还是比较简单的，实现如下：

package top.easyblog.search;

import java.util.BitSet;

/**
 * 布隆过滤器-JAVA实现
 * 布隆过滤器的原理：
 *  1.需要K个hash函数对插入的关键字进行K次hash计算
 *  2.需要一个足够大的位数组来按照哈希结果把对应下标的值置为1
 *
 * @author ：huangxin
 * @modified ：
 * @since ：2020/06/10 09:31
 */
public class BloomFilter {

    /**
     * 为数组大小
     */
    private static final int ARRAY_SIZE = 1 << 24;

    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位数组，只能存0或1
     */
    private BitSet bitSet = new BitSet(ARRAY_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] hashes = new SimpleHash[SEEDS.length];

    public BloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            hashes[i] = new SimpleHash(ARRAY_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器中
     */
    public void add(Object value) {
        //把关键字带入每个hash函数计算，并把对应下标位置的位数组值设置为1\true
        for (SimpleHash f : hashes) {
            bitSet.set(f.hash(value), true);
        }
    }

    /**
     * 判断元素在布隆过滤器中是否存在
     *
     * @param value 关键字
     * @return 关键字存在返回true, 否则返回false
     */
    public boolean contains(Object value) {
        boolean exist = true;
        for (SimpleHash f : hashes) {
            exist = exist && bitSet.get(f.hash(value));
        }
        return exist;
    }

    /**
     * 存放Hash函数
     */
    private static class SimpleHash {
        int capacity;
        int seed;

        public SimpleHash(int capacity, int seed) {
            this.capacity = capacity;
            this.seed = seed;
        }

        /**
        * 参考HashMap的hash函数设计原理
        */
        public int hash(Object val) {
            int h;
            return (val == null) ? 0 : Math.abs(seed * (capacity - 1) & ((h = val.hashCode()) ^ (h >>> 16)));
        }
    }
}
测试
@Test                                                       
public void test(){                                         
    BloomFilter filter = new BloomFilter();                 
    filter.add("hello");                                    
    filter.add("redis");                                    
    filter.add("www.easyblog.top");                         
                                                            
    System.out.println(filter.contains("hello"));           
    System.out.println(filter.contains("redis"));           
    System.out.println(filter.contains("www.easyblog.top"));
    System.out.println(filter.contains("Java"));            
}

执行结果：

布隆过滤器会有一定的误判，它说一个元素在其内部存在不一定存在，但是如果他说不能存在，那这个元素就一定不存在。

五、使用Google开源的Guava中自带的布隆过滤器。

自己实现的目的主要是为了让自己搞懂布隆过滤器的原理，Guava 中布隆过滤器的实现算是比较权威的，所以实际项目中我们不需要手动实现一个布隆过滤器。

首先我们需要在项目中引入 Guava 的依赖：

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>29.0-jre</version>
</dependency>

使用方法如下：

我们创建了一个最多存放10000个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之（0.01）

 @Test
 public void test() {                                                                                                                 
     BloomFilter<Integer> filter= BloomFilter.create(Funnels.integerFunnel(),
                                                     10_000,
                                                     0.01);
     filter.put(45);                                         
     filter.put(100);                                      
     filter.put(34);                                                                           
     System.out.println(filter.mightContain(100));
     System.out.println(filter.mightContain(45));
     System.out.println(filter.mightContain(67));        
 }

执行结果：

在我们的示例中，当mightContain（） 方法返回true时，我们可以99％确定该元素在过滤器中，当过滤器返回false时，我们可以100％确定该元素不存在于过滤器中。

Guava 提供的布隆过滤器的实现还是很不错的，但是它有一个重大的缺陷就是只能单机使用，而现在互联网一般都是分布式的场景。为了解决这个问题，我们可以使用 Redis 实现的布隆过滤器。

六、Redis 中的布隆过滤器。

Redis 4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：https://redis.io/modules。

RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。

6.1、使用Docker启动RedisBloom

可以参考docker hub上给出的示例：https://hub.docker.com/r/redislabs/rebloom/

docker run -p 6379:6379 --name redis-redisbloom -d redislabs/rebloom:latest

第一次上面命令Redis会从Docker仓库下载RedisBloom。

启动成功之后进入容器的交互界面

#进入容器
docker exec -it redis-redisbloom /bin/bash
#进入redis客户端
redis-cli
RedisBloom常用命令

注意：key表示布隆过滤器名，value是添加的元素

（1）BF.ADD {key} {value}：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。

（2）BF.MADD {key} {value} [value...]：将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同，只不过它允许多个输入并返回多个值。

（3）BF.EXISTS {key} {value}：确定元素是否在布隆过滤器中存在。

（4）BF.MEXITS {key} {vlaue} [value...]：确定一个或者多个元素是否在布隆过滤器中存在。

（5）BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]：创建一个布隆过滤器。

  • key：表示布隆过滤器的名字
  • error_rate：表示误报的期望概率，这应该是介于0到1之间的十进制值。例如，对于期望的误报率0.1％（1000中为1），error_rate应该设置为0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的CPU使用率越高。
  • capacity：过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。
  • expansion：可选参数。如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍
使用示例：

添加元素到布隆过滤器，添加成功返回1，失败返回0


批量添加元素到布隆过滤器

判断元素在布隆过滤器中是否存在，存在返回1，否者返回0

批量判断元素在布隆过滤器中是否存在

6.2 整合SpringBoot使用

详情请参考我在GitHub上的Demohttps://github.com/LoverITer/redis-blooomFilter

参考链接
  • [1] https://segmentfault.com/a/1190000021194652
  • [2] https://segmentfault.com/a/1190000016721700
  • [3] https://blog.csdn.net/lifetragedy/article/details/103945885

留言区

还能输入500个字符