高并发 之 Redis 布隆过滤器 Bloom Filter
数据库
|
213
|
0

1648 字
|
30 分钟

Redis 布隆过滤器

布隆过滤器主要解决的是缓存穿透、空间效率的问题。以下是具体说明：

介绍

缓存穿透

当缓存失效，大量无效请求直接查询数据库，导致数据库压力增加，降低了系统的整体性能。
通常发生在请求的 ID 不存在于数据库中，尤其是当这些 ID 是随机生成或被恶意攻击时。

布隆过滤器通过在查询前检查请求的 ID 是否存在于布隆过滤器中，能有效地阻止无效请求。
如果布隆过滤器返回该 ID 不存在，可以立即拒绝查询请求，从而避免无效的数据库访问。

空间效率

  • 布隆过滤器：
    布隆过滤器以位数组（bit array）和多个哈希函数来表示集合元素，而不需要存储实际数据。具有很高的空间效率，即使存储大量元素所需的内存也相对较少。例如，存储 10 亿个元素可能只需要 1.2 GB 的内存（误判率为 1%），远比直接存储每个元素要节省空间。

  • 直接存储 ID：
    如果将所有 ID 直接存储在 Redis 中，比如用哈希表或集合，存储 10 亿个元素可能会占用几倍甚至十倍以上的内存。
    每个元素都需要完整存储，并且包括额外的 Redis 元数据，导致内存占用更高。

性能

布隆过滤器可以在常数时间内𝑂(𝑘)（其中𝑘是哈希函数的数量）完成存在性判断，性能更高。
而 Redis 需要根据实际数据结构进行查询，性能上可能略有差异。

误判率

存在误判率，可能会认为某个 ID 存在即使它实际上不存在。
这意味着它有小概率误认为一些数据存在，但实际上不存在，从而先查询redis，再查询mysql。

适用场景

适用于对空间效率要求高、允许少量误判的场景 *防止缓存穿透**、**大数据去重**、**爬虫Url去重复**

那么开始干吧！

环境搭建

  1. 使用 Docker 运行 Redis + RedisBloom 容器
    RedisBloom 官方提供了一个集成了 RedisBloom 模块的 Docker 镜像。
    可以使用以下命令来启动 Redis 实例，并确保使用 RedisBloom 模块：

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

--name redis-bloom: 为容器命名为 redis-bloom。
-p 6379:6379: 将本地主机的 6379 端口映射到容器的 6379 端口。
redislabs/rebloom:latest: 使用 RedisBloom 的官方最新镜像。

  1. 验证 RedisBloom 是否已正确加载

进入容器：

docker exec -it redis-bloom /bin/bash

连接Redis：

redis-cli

验证是否已加载Bloom:

MODULE LIST

可以看到 redisbloom 模块已加载。

> MODULE LIST
1) 1) "name"
   2) "bf"
   3) "ver"
   4) (integer) 20612
   5) "path"
   6) "/usr/lib/redis/modules/redisbloom.so"
   7) "args"
   8) (empty array)

如此，环境就搭建好了。

使用布隆过滤器

指令 描述
BF.RESERVE 创建布隆过滤器，指定容量和误判率
BF.ADD 添加一个元素
BF.MADD 批量添加多个元素
BF.EXISTS 检查一个元素是否存在
BF.MEXISTS 批量检查多个元素是否存在
BF.INFO 获取布隆过滤器的详细信息

BF.RESERVE

描述: 创建一个新的布隆过滤器，指定初始容量和错误率。

格式：

BF.RESERVE key error_rate capacity [EXPANSION expansion] [NONSCALING]

参数解释：

  • key: 布隆过滤器的键名。
  • error_rate: 目标误判率（例如，0.01 表示 1%）。
  • capacity: 过滤器的初始容量，即期望插入的元素数量。
  • EXPANSION (可选): 设置过滤器的增长因子，决定过滤器何时扩容。默认值为 2，表示当过滤器达到容量时，位数组扩容为原来的 2 倍。
  • NONSCALING (可选): 如果提供此参数，过滤器将不会扩容，当达到容量时将不再接受新的插入。

返回值: 创建成功返回 OK。

注意：
误判率越小，误判概率越小，但空间占用也越多。

例子:创建一个key为 bf_user_id 的布隆过滤器，错误率 1%, 初始容量 10000

> BF.RESERVE bf_user_id 0.01 10000
OK
> type bf_user_id
MBbloom--

BF.ADD

描述: 向布隆过滤器中添加一个元素。
格式：

BF.ADD key item
  • key:布隆过滤器的键名
  • item:添加元素内容

例子：添加数字1和字符串2

> bf.Add bf_user_id 1
(integer) 1
> bf.Add bf_user_id "2"
(integer) 1

BF.MADD

描述: 批量向布隆过滤器添加多个元素。

格式：

BF.MADD key item1 item2
  • key: 布隆过滤器的键名。
  • item1 item2...: 要添加的多个元素

例子：向bf_user_id 中添加3，4，5

> bf.madd  bf_user_id 3 4 5
1) (integer) 1
2) (integer) 1
3) (integer) 1

BF.EXISTS

描述: 检查一个元素是否在布隆过滤器中。
格式：

BF.EXISTS key item
  • key: 布隆过滤器的键名。
  • item: 元素

返回值: 存在返回 1，不存在返回 0。

例子：检查 bf_user_id 中是否存在 1

> BF.exists bf_user_id 1
(integer) 1

此处返回1，所以存在

BF.MEXISTS

描述: 批量检查多个元素是否在布隆过滤器中。

格式：

BF.MEXISTS key item1 item2
  • key: 布隆过滤器的键名。
  • item1 item2 ...: 要检查的多个元素
    返回值: 对每个元素返回 1 或 0，表示元素是否存在。
bf.mexists bf_user_id 5 6
1) (integer) 1
2) (integer) 0

BF.INFO

描述: 获取布隆过滤器的详细信息，例如容量、扩容情况、误判率等。
格式：

BF.INFO key
  • key: 布隆过滤器的键名。

返回值: 返回一个包含过滤器信息的数组，包括：

  • Capacity: 当前容量。
  • Size: 位数组的大小。
  • Number of filters: 过滤器链的数量（如果扩容过）。
  • Number of items inserted: 已插入元素的数量。
  • Expansion rate: 扩容因子。

例子：

> bf.info user_id
 1) Capacity
 2) (integer) 10000
 3) Size
 4) (integer) 13888
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 0
 9) Expansion rate
10) (integer) 2
  • Capacity: 10000
  • Size: 位数字大小 13888
  • Number of filters: 过滤器链的数量（如果扩容过）。
  • Number of items inserted: 已插入元素的数量。
  • Expansion rate: 扩容因子。

Golang中使用

常量

  1. 指令 
    const REDIS_ORDER_BF_RESERVE = "BF.RESERVE" // BF.RESERVE
const REDIS_ORDER_BF_ADD = "BF.ADD"         // BF.ADD 
const REDIS_ORDER_BF_MADD = "BF.MADD"       // BF.MADD
const REDIS_ORDER_BF_EXISTS = "BF.EXISTS"   // BF.EXISTS
const REDIS_ORDER_BF_MEXISTS = "BF.MEXISTS" // BF.MEXISTS
const REDIS_ORDER_BF_INFO = "BF.INFO"       // BF.INFO
  2. 报错 
    const REDIS_ERR_ErrItemExists = "ERR item exists" // BF.RESERVE 时如果过滤器存在，会提示这个错误

初始化 redis 连接

这里简化了初始化连接，生产中应当再设置MinIdleConns,PoolSize,ReadTimeout,WriteTimeout,IdleTimeout,PoolTimeout,

package redis_test

import (
    "context"
    "fmt"
    "sync"

    "github.com/redis/go-redis/v9"
)

var once sync.Once
var Redis *redis.Client
var (
    host     = "127.0.0.1"
    port     = "6379"
    username = ""
    password = ""
    db       = 0
)

func InitRedisClient() {
    once.Do(newRedisClient)
}
func newRedisClient() {
    Redis = redis.NewClient(&redis.Options{
        Addr:     fmt.Sprintf("%s:%s", host, port),
        Username: username,
        Password: password,
        DB:       db,
    })

    pong, err := Redis.Ping(context.Background()).Result()
    if err != nil {
        panic("初始化redis失败")
    }
    fmt.Println(pong)

}

定义布隆过滤器对象


// redis 的布隆过滤器
type RedisBloomFilter struct {
    Ctx     context.Context
    Key     string  // 过滤器键
    ErrRate float64 // 误判率
    Cap     int     // 容量
}
// new 一个 bf 对象
func NewRedisBloomFilter(ctx context.Context, key string) *RedisBloomFilter {
    return &RedisBloomFilter{
        Ctx: ctx,
        Key: key,
    }
}

创建过滤器

// 创建 Bloom Filter
func (bf *RedisBloomFilter) Reserve() {
  // bf.reserve key err_rate cap
    err := Redis.Do(bf.Ctx, REDIS_ORDER_BF_RESERVE, bf.Key, bf.ErrRate, bf.Cap).Err()
    if err != nil && err.Error() != REDIS_ERR_ErrItemExists {
        panic(fmt.Sprintf("创建新布隆过滤器失败，err:%v", err))
    }
}

添加


// 向Bloom Filter中添加
func (bf *RedisBloomFilter) Add(item interface{}) {
    if item == nil {
        return
    }
    err := Redis.Do(bf.Ctx, REDIS_ORDER_BF_ADD, bf.Key, item).Err()
    if err != nil {
        panic(err)
    }
}

批量添加


// 批量向Bloom Filter添加 item
func (bf *RedisBloomFilter) MulAdd(items []interface{}) {
    if len(items) == 0 {
        return
    }
    options := []interface{}{REDIS_ORDER_BF_MADD, bf.Key}
    options = append(options, items...)
    err := Redis.Do(bf.Ctx, options...).Err()
    if err != nil {
        panic(err)
    }
}

校验存在性


// 单个item 在布隆过滤器中的存在性
func (bf *RedisBloomFilter) BfExists(item interface{}) bool {

    result, err := Redis.Do(bf.Ctx, REDIS_ORDER_BF_EXISTS, bf.Key, item).Result()
    if err != nil {
        panic(err)
    }
    if result == nil {
        return false
    }
    if reflect.TypeOf(result).Kind() == reflect.Bool {
        return result.(bool)
    } else {
        return false
    }
}

批量校验存在性


// 批量存在性校验
func (bf *RedisBloomFilter) MulExists(items []interface{}) []bool {
    exists := make([]bool, len(items))
    if len(items) == 0 {
        return exists
    }

    options := []interface{}{REDIS_ORDER_BF_MEXISTS, bf.Key}
    options = append(options, items...)
    results, err := Redis.Do(bf.Ctx, options...).Result()
    if err != nil {
        panic(err)
    }
    if results == nil {
        return exists
    }

  // 循环
    for i, v := range results.([]interface{}) {
        if reflect.TypeOf(v).Kind() == reflect.Bool {
            exists[i] = v.(bool)
        } else {
            exists[i] = false
        }

    }
    return exists
}

使用


func TestRedisBloomFilter(t *testing.T) {
    // 连接 redis
    InitRedisClient()

    // Fan的小破站 fanfine.cn
    ctx, _ := context.WithTimeoutCause(context.Background(), time.Second*20, errors.New("操作超时"))
    bf := NewRedisBloomFilter(ctx, "user_id")

    bf.ErrRate = 0.01 // 误判率
    bf.Cap = 10 ^ 8   // 总量

    // 创建过滤器
    bf.Reserve()

  // 添加一个 1
    bf.Add(1)

  // 校验存在性
    fmt.Println("单个校验存在性", bf.BfExists(1))

    // 批量添加 2 3 4 5
    ids := []interface{}{2, 3, 4, 5}
    bf.MulAdd(ids)

    // 批量验证存在性
    checkIds := []interface{}{1, 2, "44", 2112}
    exists := bf.MulExists(checkIds)

    for i, exist := range exists {
        fmt.Println("id:", checkIds[i], "存在性:", exist)
    }
}

输出：

PONG
单个校验存在性 true
id: 1 存在性: true
id: 2 存在性: true
id: 44 存在性: false
id: 2112 存在性: false

本文由 帆 上传。


如果您喜欢这篇文章，请点击链接 高并发 之 Redis 布隆过滤器 Bloom Filter 查看原文。


您也可以直接访问：https://www.fanfine.cn/blog/222

Bloom Filterredis布隆过滤器并发编程缓存穿透高并发
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Golang 并发编程之 sync 包

							
							

							
Golang 的 channel

							
							

							
Golang 的 goroutine 和 GMP模型

							
							

							
分布式缓存 – Redis集群 – 理论篇