防缓存穿透利器-布隆滤器(BloomFilter)

﹏ヽ暗。殇╰゛Y 2023-10-10 15:12 14阅读 0赞

一、布隆过滤器原理

如果想要判断一个元素是不是在一个集合中存在，一般的想法是将所有元素保存起来，然后再拿着这个元素在集合中一个一个进行比对。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。 针对这种需要在大量数据中去判断某一个值是事否存在的情况，1970年由布隆提出了布隆过滤器的概念。布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 字节 的空间。布隆过滤器除了一个位数组，还有 n个哈希函数。

它具体的实现思想是并不将具体的数据存储在数组中，而是通过hash函数对要存储的数据进行三次hash运算，并将hash运算的结果做为位数组的下标，将对应的数组元素修改为1。

例如：我们要将"oracle"、"database"、"filter"存储到布隆过滤器中可以这样做。如下图所示

从上图中可以看到，我们有三个hash函数(h1()、h2()、h3())和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。

但同学们也会发现，如果我们现在要判断"mysql"是否存在，例如它通过三次hash运算得到的值分别是4,5,10。现在即使你的位数中没有存储“mysql”,布隆过滤器也会判断它存在。这是因为"oracle"、"database"、"filter"算出的hash值已经导致上面的三个位置的值被改为了1，这样就会导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。

产生上面误判的主要原因是hash碰撞导致的。但如果我们将位数组设置的足够大，并且让hash运算执行的次数多一些，这样就会降低误判率。

布隆过率器还有另一个问题就是不能删除。这是因为在位数组上的同一个点有可能有多个输入值的映射，如果删除了会影响布隆过滤器里其他元素的判断结果。

所以我们可以总结出布隆过滤器的优缺点如下：

- 优点：

- 所占空间小(并不存储真正的数据)，空间效率高

- 查询时间短

- 缺点:

- 元素添加到数组中后，不能被删除

- 有一定的误判率

二、布隆过滤器使用场景

- 解决缓存穿透问题，缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中就到数据库中去查，并且出于容错考虑，如果从数据库中查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库中去查询，失去了缓存的意义。在流量大时，可能数据库就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则再到数据库中查。如果不在布隆器中，则直接返回。

- 在业务场景中可以用来判断用户是否阅读过某些文章或视频，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。

- 黑名单：比如在邮件系统中可以使用布隆器设置黑名单，判断邮件地址是否在黑名单中。也可以设IP黑名单防止网格爬虫等。

- 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。

三、实践

3.1 通过 Java 编程手动实现布隆过滤器

package com.heima.rbac.controller;
    
    import java.util.BitSet;
    
    public class MyBloomFilter {
    
        /**
         * 位数组的大小
         */
        private static final int DEFAULT_SIZE = 2 << 24;
        /**
         * 通过这个数组可以创建 6 个不同的哈希函数
         */
        private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132};
    
        /**
         * 位数组。数组中的元素只能是 0 或者 1
         */
        private BitSet bits = new BitSet(DEFAULT_SIZE);
    
        /**
         * 存放包含 hash 函数的类的数组
         */
        private SimpleHash[] func = new SimpleHash[SEEDS.length];
    
        /**
         * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
         */
        public MyBloomFilter() {
            // 初始化多个不同的 Hash 函数
            for (int i = 0; i < SEEDS.length; i++) {
                func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
            }
        }
    
        /**
         * 添加元素到位数组
         */
        public void add(Object value) {
            for (SimpleHash f : func) {
                bits.set(f.hash(value), true);
            }
        }
    
        /**
         * 判断指定元素是否存在于位数组
         */
        public boolean contains(Object value) {
            boolean ret = true;
            for (SimpleHash f : func) {
                ret = ret && bits.get(f.hash(value));
            }
            return ret;
        }
    
        /**
         * 静态内部类。用于 hash 操作！
         */
        public static class SimpleHash {
    
            private int cap;
            private int seed;
    
            public SimpleHash(int cap, int seed) {
                this.cap = cap;
                this.seed = seed;
            }
    
            /**
             * 计算 hash 值
             */
            public int hash(Object value) {
                int h;
                return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
            }
    
        }
    }

3.2 Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 \[module\](https://github.com/RedisLabsModules/rebloom) 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

\`\`\`

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom

> docker exec -it bloomfilter redis-cli

\`\`\`

redis 布隆过滤器主要就两个命令：

- \`bf.add\` 添加元素到布隆过滤器中：\`bf.add urls http://www.itcast.com\`。

- \`bf.exists\` 判断某个元素是否在过滤器中：\`bf.exists urls http://www.itcast.com\`。

上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

- \`error\_rate\`：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。

- \`initial\_size\`：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

\`\`\`