Redis

Redis 16_深入探究布隆过滤器

一、布隆过滤器简介

1.1 布隆过滤器简介

布隆过滤器是一种基于哈希的空间效率高、时间复杂度低的数据结构，用于快速判断一个元素是否可能存在于一个集合中，特别是在大规模数据集中快速判断一个元素是否可能存在于集合中。它基于多个哈希函数和一个位数组来实现，通过哈希函数将元素映射到位数组的多个位置，并将这些位置置为1。在查询时，布隆过滤器只需检查元素对应的位是否都为1，若都为1，则可能存在；若有任何一位为0，则一定不存在。位数组也称为位图（Bitmap），是一种数据结构，用于表示一系列二进制位（0或1）。在计算机内部，位数组通常以连续的二进制位序列的形式存储在内存中，每一位都有一个唯一的地址或索引。

Tips: 布隆过滤器的特性是 不存在的一定不存在，存在的可能存在。

1.2 布隆过滤器的实现

布隆过滤器的核心是 位数组 和 哈希函数

  • 位数组：通常由布尔数组或位数组实现，用于表示元素是否存在的状态。
  • 哈希函数：通常选择多个哈希函数，以增加哈希的随机性和减小冲突的可能性。
1
2
3
4
5

位数组：
+--------------------------+
| 1 0 1 0 0 1 1 0 1 0 1  ... |  <-- 位数组中的每个位
+--------------------------+
  0 1 2 3 4 5 6 7 8 9 10 ... (位数组下标索引)

1.3 布隆过滤器的优缺点

  • 优点：高效的查询速度和低内存占用，特别适用于大规模数据集的快速过滤。
  • 缺点：存在一定的误判率，即可能将不存在的元素误判为存在，这取决于哈希函数的数量和位数组的大小。

1.4 布隆过滤器的应用场景

  • 解决缓存穿透：缓存穿透是指当查询某个数据时，缓存系统中不存在该数据，也就是缓存没有命中，此时查询请求就会转向持久层数据库系统上进行查询，结果发现 数据库中也不存在该数据，数据库只能返回一个空对象，代表此次查询失败。如果这种类请求非常多，或者用户利用这种请求进行恶意攻击，就会给数据库造成很大压力，甚至于崩溃，这种现象就叫缓存穿透。使用布隆过滤器可以有效的解决缓存穿透，具体流程为：（1）将用户可能会访问的热点数据存储在布隆过滤器中（也称缓存预热）；（2）当有用户请求到来时会先经过布隆过滤器进行判断数据是否可能存在，如果请求的数据，在布隆过滤器中不存在，那么该请求将直接被拒绝；（3）否则将继续执行缓存查询，如果缓存不存在，则查询数据库。
  • 数据库查询优化：在数据库查询前使用布隆过滤器进行预筛选，减少对数据库的实际查询次数，提高查询效率。
  • 网络爬虫去重：在网络爬取过程中，使用布隆过滤器对已经爬取的URL进行去重，避免重复爬取相同的页面。
  • 分布式系统中的缓存一致性：在分布式系统中使用布隆过滤器判断某个数据是否存在于缓存中，以减少对底层存储系统的访问。

二、Redis 中的布隆过滤器

2.1 Redis 中的布隆过滤器简介

Redis 布隆过滤器（Bloom Filter）是一种基于概率的数据结构，用于快速检查一个元素是否可能存在于一个集合中。它通过利用位数组和多个哈希函数来实现，可以有效地减少存储空间的占用，同时提供高效的查询性能。

Redis 从版本 4.0 开始提供了布隆过滤器模块（RedisBloom），可以通过 BF.ADD、BF.EXISTS 等命令来操作布隆过滤器。用户可以通过在 Redis 中使用布隆过滤器来实现快速的集合成员查询、去重等功能。

2.2 Redis 中的布隆过滤器使用方法

  • 下载 RedisBloom 模块文件：https://github.com/RedisBloom/RedisBloom 并选择 “Download ZIP” 下载 RedisBloom 源代码压缩文件。
  • config配置
1
2

# 加载 RedisBloom 模块
loadmodule /usr/lib/redis/modules/redisbloom.so
  • 命令行使用
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# 加载 RedisBloom 模块
127.0.0.1:6379> MODULE LOAD /path/to/redisbloom.so
OK

# 创建一个布隆过滤器，并向其中添加元素
127.0.0.1:6379> BF.ADD myfilter item1
(integer) 1
127.0.0.1:6379> BF.ADD myfilter item2
(integer) 1

# 检查元素是否存在于布隆过滤器中
127.0.0.1:6379> BF.EXISTS myfilter item1
(integer) 1
127.0.0.1:6379> BF.EXISTS myfilter item3
(integer) 0
  • Lua脚本使用
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

-- 定义 Lua 脚本
local script = [[
    -- BF.ADD 命令接受两个参数，分别是布隆过滤器的键和要添加的元素
    -- 这里的 KEYS[1] 是布隆过滤器的键，ARGV[1] 是要添加的元素
    return redis.call('BF.ADD', KEYS[1], ARGV[1])
]]

-- 执行 Lua 脚本
local result = redis.call('EVAL', script, 1, 'my_filter', 'item1')
return result