乐趣区

关于java:硬核-Redis-布隆Bloom-Filter过滤器原理与实战

jiezi

在 Redis 缓存击穿（生效）、缓存穿透、缓存雪崩怎么解决？中咱们说到能够应用布隆过滤器防止「缓存穿透」。

码哥，布隆过滤器还能在哪些场景应用呀？

比方咱们应用「码哥跳动」开发的「明日头条」APP 看新闻，如何做到每次举荐给该用户的内容不会反复，过滤曾经看过的内容呢？

你会说咱们只有记录了每个用户看过的历史记录，每次举荐的时候去查询数据库过滤存在的数据实现 去重。

实际上，如果历史记录存储在关系数据库里，去重就须要频繁地对数据库进行 exists 查问，当零碎并发量很高时，数据库是很难扛住压力的。

码哥，我能够应用缓存啊，把历史数据存在 Redis 中。

万万不可，这么多的历史记录那要节约多大的内存空间，所以这个时候咱们就能应用布隆过滤器去解决这种 去重问题。又快又省内存，互联网开发必备杀招！

当你 遇到数据量大，又须要去重的时候就能够思考布隆过滤器，如下场景：

  • 解决 Redis 缓存穿透问题（面试重点）；
  • 邮件过滤，应用布隆过滤器实现邮件黑名单过滤；
  • 爬虫爬过的网站过滤，爬过的网站不再爬取；
  • 举荐过的新闻不再举荐；

什么是布隆过滤器

布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，它是一种 space efficient 的概率型数据结构，用于判断一个元素是否在汇合中。

当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据肯定不存在。

哈希表也能用于判断元素是否在汇合中，然而布隆过滤器只须要哈希表的 1/8 或 1/4 的空间复杂度就能实现同样的问题。

布隆过滤器能够插入元素，但不能够删除已有元素。

其中的元素越多，false positive rate(误报率)越大，然而 false negative (漏报)是不可能的。

布隆过滤器原理

BloomFilter 的算法是，首先调配一块内存空间做 bit 数组，数组的 bit 位初始值全副设为 0。

退出元素时，采纳 k 个互相独立的 Hash 函数计算，而后将元素 Hash 映射的 K 个地位全副设置为 1。

检测 key 是否存在，依然用这 k 个 Hash 函数计算出 k 个地位，如果地位全副为 1，则表明 key 存在，否则不存在。

如下图所示：

哈希函数会呈现碰撞，所以布隆过滤器会存在误判。

这里的误判率是指，BloomFilter 判断某个 key 存在，但它理论不存在的概率，因为它存的是 key 的 Hash 值，而非 key 的值。

所以有概率存在这样的 key，它们内容不同，但屡次 Hash 后的 Hash 值都雷同。

对于 BloomFilter 判断不存在的 key，则是 100% 不存在的，反证法，如果这个 key 存在，那它每次 Hash 后对应的 Hash 值地位必定是 1，而不会是 0。布隆过滤器判断存在不肯定真的存在。

码哥，为什么不容许删除元素呢？

删除意味着须要将对应的 k 个 bits 地位设置为 0，其中有可能是其余元素对应的位。

因而 remove 会引入 false negative，这是相对不被容许的。

Redis 集成布隆过滤器

Redis 4.0 的时候官网提供了插件机制，布隆过滤器正式退场。以下网站能够下载官网提供的曾经编译好的可拓展模块。

https://redis.com/redis-enter…

码哥举荐应用 Redis 版本 6.x，最低 4.x 来集成布隆过滤器。如下指令查看版本，码哥装置的版本是 6.2.6。

redis-server -v
Redis server v=6.2.6 sha=00000000:0 malloc=libc bits=64 build=b5524b65e12bbef5

下载

咱们本人编译装置，须要从 github 下载，目前的 release 版本是 v2.2.14，下载地址：https://github.com/RedisBloom…

解压编译

解压

tar -zxvf RedisBloom-2.2.14.tar

编译插件

cd RedisBloom-2.2.14
make

编异胜利，会看到 redisbloom.so 文件。

装置集成

需改 redis.conf 文件，新增 loadmodule配置，并重启 Redis。

loadmodule /opt/app/RedisBloom-2.2.14/redisbloom.so

如果是集群，则每个实例的配置文件都须要退出配置。

指定配置文件并启动 Redis：

redis-server /opt/app/redis-6.2.6/redis.conf

加载胜利的页面如下：

客户端连贯 Redis 测试。

BF.ADD -- 增加一个元素到布隆过滤器
BF.EXISTS -- 判断元素是否在布隆过滤器
BF.MADD -- 增加多个元素到布隆过滤器
BF.MEXISTS -- 判断多个元素是否在布隆过滤器

Redis 布隆过滤器实战

咱们来用布隆过滤器来解决缓存穿透问题，缓存穿透：意味着有非凡申请在查问一个不存在的数据，即数据不存在 Redis 也不存在于数据库。

当用户购买商品创立订单的时候，咱们往 mq 发送音讯，把订单 ID 增加到布隆过滤器。

在增加到布隆过滤器之前，咱们通过 BF.RESERVE 命令手动创立一个名字为 orders error_rate = 0.1，初始容量为 10000000 的布隆过滤器：

# BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING]
BF.RESERVE orders 0.1 10000000
  • key：filter 的名字；
  • error_rate：冀望的错误率，默认 0.1，值越低，须要的空间越大；
  • capacity：初始容量，默认 100，当理论元素的数量超过这个初始化容量时，误判率回升。
  • EXPANSION：可选参数，当增加到布隆过滤器中的数据达到初始容量后，布隆过滤器会主动创立一个子过滤器，子过滤器的大小是上一个过滤器大小乘以 expansion；expansion 的默认值是 2，也就是说布隆过滤器扩容默认是 2 倍扩容；
  • NONSCALING：可选参数，设置此项后，当增加到布隆过滤器中的数据达到初始容量后，不会扩容过滤器，并且会抛出异样（(error) ERR non scaling filter is full）
    阐明：BloomFilter 的扩容是通过减少 BloomFilter 的层数来实现的。每减少一层，在查问的时候就可能会遍历多层 BloomFilter 来实现，每一层的容量都是上一层的两倍（默认）。

如果不应用 BF.RESERVE 命令创立，而是应用 Redis 主动创立的布隆过滤器，默认的 error_rate 是 0.01，capacity是 100。

隆过滤器的 error_rate 越小，须要的存储空间就越大，对于不须要过于准确的场景，error_rate 设置稍大一点也能够。

布隆过滤器的 capacity 设置的过大，会节约存储空间，设置的过小，就会影响准确率，所以在应用之前肯定要尽可能地准确预计好元素数量，还须要加上肯定的冗余空间以防止理论元素可能会意外高出设置值很多。

增加订单 ID 到过滤器

# BF.ADD {key} {item}
BF.ADD orders 10086
(integer) 1

应用 BF.ADD向名称为 orders 的布隆过滤器增加 10086 这个元素。

如果是多个元素同时增加，则应用 BF.MADD key {item ...}，如下：

BF.MADD orders 10087 10089
1) (integer) 1
2) (integer) 1

判断订单是否存在

# BF.EXISTS {key} {item}
BF.EXISTS orders 10086
(integer) 1

BF.EXISTS 判断一个元素是否存在于BloomFilter，返回值 = 1 示意存在。

如果须要批量查看多个元素是否存在于布隆过滤器则应用 BF.MEXISTS，返回值是一个数组：

  • 1：存在；
  • 0：不存在。
# BF.MEXISTS {key} {item}
BF.MEXISTS orders 100 10089
1) (integer) 0
2) (integer) 1

总体说，咱们通过 BF.RESERVE、BF.ADD、BF.EXISTS 三个指令就能实现防止缓存穿透问题。

码哥，如何查看创立的布隆过滤器信息呢？

用 BF.INFO key查看，如下：

BF.INFO orders
 1) Capacity
 2) (integer) 10000000
 3) Size
 4) (integer) 7794184
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 3
 9) Expansion rate
10) (integer) 2

返回值：

  • Capacity：预设容量；
  • Size：理论占用状况，但如何计算待进一步确认；
  • Number of filters：过滤器层数；
  • Number of items inserted：曾经理论插入的元素数量；
  • Expansion rate：子过滤器扩容系数（默认 2）；

码哥，如何删除布隆过滤器呢？

目前布隆过滤器不反对删除，布谷过滤器 Cuckoo Filter 是反对删除的。

Bloom 过滤器在插入我的项目时通常体现出更好的性能和可伸缩性（因而，如果您常常向数据集增加我的项目，那么 Bloom 过滤器可能是现实的）。布谷鸟过滤器在查看操作上更快，也容许删除。

大家有趣味可能够看下：https://oss.redis.com/redisbl…)

码哥，我想晓得你是如何把握这么多技术呢？

其实我也是翻阅官网文档并做一些简略加工而已，这篇的文章内容实战就是基于 Redis 官网文档下面的例子：https://oss.redis.com/redisbl…。

大家遇到问题肯定要急躁的从官网文档寻找答案，造就本人的浏览和定位问题的能力。

Redission 布隆过滤器实战

码哥的样例代码基于 Spring Boot 2.1.4，代码地址：https://github.com/MageByte-Z…。

增加 Redission 依赖：

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

应用 Spring boot 默认的 Redis 配置形式配置 Redission：

spring:
  application:
    name: redission

  redis:
    host: 127.0.0.1
    port: 6379
    ssl: false

创立布隆过滤器

@Service
public class BloomFilterService {

    @Autowired
    private RedissonClient redissonClient;

    /**
     * 创立布隆过滤器
     * @param filterName 过滤器名称
     * @param expectedInsertions 预测插入数量
     * @param falseProbability 误判率
     * @param <T>
     * @return
     */
    public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) {RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falseProbability);
        return bloomFilter;
    }

}

单元测试

@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class BloomFilterTest {

    @Autowired
    private BloomFilterService bloomFilterService;

    @Test
    public void testBloomFilter() {
        // 预期插入数量
        long expectedInsertions = 10000L;
        // 谬误比率
        double falseProbability = 0.01;
        RBloomFilter<Long> bloomFilter = bloomFilterService.create("ipBlackList", expectedInsertions, falseProbability);

        // 布隆过滤器减少元素
        for (long i = 0; i < expectedInsertions; i++) {bloomFilter.add(i);
        }
        long elementCount = bloomFilter.count();
        log.info("elementCount = {}.", elementCount);

        // 统计误判次数
        int count = 0;
        for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {if (bloomFilter.contains(i)) {count++;}
        }
        log.info("误判次数 = {}.", count);
        bloomFilter.delete();}
}

注意事项：如果是 Redis Cluster 集群，则须要 RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");

参考资料

1.https://blog.csdn.net/u010066…
2.https://juejin.cn/book/684473…
3.https://www.cnblogs.com/heiha…
4.https://www.cnblogs.com/allen…
5.https://oss.redis.com/redisbl…
6.https://oss.redis.com/redisbl…
7.https://redis.com/blog/rebloo…

退出移动版