go-zero源码阅读之布隆过滤器实现代码
作者:飞飞羽毛球 时间:2024-05-08 10:23:06
一. 布隆过滤器简介
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
二. 常用场景
1. 解决缓存穿透
2. 数据去重,如用户是否发送过短信
3. 特定数据识别
三. go-zero的布隆过滤器实现
1. 简介
依赖redis.bitmap, 将数据多次hash后,插入到多个特定位,并设置为1。当进行数据检测时,经过相同hash后,检测所有位,只要其中一位为0,则代表数据不存在,否则数据可能存在。
2. 布隆过滤器结构体
type (
// A Filter is a bloom filter.
// 结构体
Filter struct {
bits uint
bitSet bitSetProvider
}
// 位数组接口定义
bitSetProvider interface {
check([]uint) (bool, error)
set([]uint) error
}
)
3. 初始化方法
func New(store *redis.Redis, key string, bits uint) *Filter {
return &Filter{
bits: bits,
bitSet: newRedisBitSet(store, key, bits),
}
}
初始化方法比较简单,具体操作依赖newRedisBitSet
4. newRedisBitSet方法
func newRedisBitSet(store *redis.Redis, key string, bits uint) *redisBitSet {
return &redisBitSet{
store: store,
key: key,
bits: bits,
}
}
简单的初始化, 初始化结束
5. 数据添加--Add
func (f *Filter) Add(data []byte) error {
// 获取数据多次hash后的各key
locations := f.getLocations(data)
// 插入数据
return f.bitSet.set(locations)
}
首先获取hash后的key的切片,然后调用set方法,将数据插入位数组(redis.bitmap)
6. 数据添加--set
func (r *redisBitSet) set(offsets []uint) error {
// 将[]uint转为[]string
args, err := r.buildOffsetArgs(offsets)
if err != nil {
return err
}
// 执行lua脚本
_, err = r.store.Eval(setScript, []string{r.key}, args)
if err == redis.Nil {
return nil
}
return err
}
首先将[]uint转为[]string, 因为redis lua需要[]string,然后执行lua脚本进行数据插入,使用lua是为了保证原子性
7. 数据添加--lua脚本
setScript = `
for _, offset in ipairs(ARGV) do
redis.call("setbit", KEYS[1], offset, 1)
end
`
for循环获取到每个偏移量,使用setbit命令设置各偏移量为1
8. 数据检测--Exists
func (f *Filter) Exists(data []byte) (bool, error) {
// 同数据set一致,获取数据多次hash后,偏移量切片
locations := f.getLocations(data)
// 调用check方法进行检测
isSet, err := f.bitSet.check(locations)
if err != nil {
return false, err
}
return isSet, nil
}
首先调用getLocations方法获取数据多次hash后偏移量切片,调用check方法进行数据检测
9. 数据检测--check
func (r *redisBitSet) check(offsets []uint) (bool, error) {
// []uint转为[]string,和set调用的一致
args, err := r.buildOffsetArgs(offsets)
if err != nil {
return false, err
}
//执行lua脚本,检测各偏移量数据是否都存在
resp, err := r.store.Eval(testScript, []string{r.key}, args)
// 根据返回值判断数据是否存在
// key不存在特殊处理
if err == redis.Nil {
return false, nil
} else if err != nil {
return false, err
}
exists, ok := resp.(int64)
if !ok {
return false, nil
}
return exists == 1, nil
}
执行lua脚本判断数据是否存在,根据返回值返回数据是否存在
10. 数据检测--lua脚本
testScript = `
for _, offset in ipairs(ARGV) do
if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
return false
end
end
return true
`
fou循环判断各偏移量是否存在,只要有一个为0,就代表数据不存在,各offset都为1则代表数据存在
来源:https://blog.csdn.net/qq_22323251/article/details/128893869
标签:go,zero,布隆过滤器
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
在 Python 应用中使用 MongoDB的方法
2023-09-13 21:53:11
百度、谷歌和雅虎的近日LOGO
2008-05-19 12:11:00
![](https://img.aspxhome.com/file/UploadPic/20085/19/2008519122037724s.gif)
利用Python实现sqlite3增删改查的封装
2021-06-19 14:57:05
VS2015安装之后加装Sql server2014详细步骤
2024-01-18 04:39:56
Python爬虫框架Scrapy常用命令总结
2022-02-21 20:45:23
![](https://img.aspxhome.com/file/2023/3/118293_0s.png)
Vue实例中生命周期created和mounted的区别详解
2024-04-29 13:08:15
![](https://img.aspxhome.com/file/2023/9/132919_0s.png)
win10下Python3.6安装、配置以及pip安装包教程
2022-09-27 12:29:46
![](https://img.aspxhome.com/file/2023/3/101303_0s.png)
使用python统计文件行数示例分享
2022-08-22 22:49:38
PHP接口多继承及tarits实现多继承效果的方法
2023-11-21 04:23:33
10个最容易犯的HTML标签错误
2010-09-13 12:37:00
![](https://img.aspxhome.com/file/UploadPic/20109/13/01-23s.jpg)
一些需要禁用的PHP危险函数(disable_functions)
2023-11-23 15:29:25
质量更好的tags标签效果
2008-06-04 12:24:00
![](https://img.aspxhome.com/file/UploadPic/20086/4/css-tags_35s.gif)
Python 通过爬虫实现GitHub网页的模拟登录的示例代码
2022-04-27 00:26:39
![](https://img.aspxhome.com/file/2023/4/86564_0s.jpg)
ASP中遍历和操作Application对象的集合
2007-09-13 12:45:00
SQL Server存储过程中编写事务处理的方法小结
2024-01-15 15:24:24
python机器学习之随机森林(七)
2023-10-20 00:25:13
关于mysql主备切换canal出现的问题解决
2024-01-28 14:29:08
python中黄金分割法实现方法
2022-05-15 01:45:24
Python环境下安装使用异步任务队列包Celery的基础教程
2023-08-23 23:06:48
详解Python调试神器之PySnooper
2021-05-20 06:51:12
![](https://img.aspxhome.com/file/2023/3/99023_0s.png)