go-zero源码阅读之布隆过滤器实现代码
作者:飞飞羽毛球 发布时间:2024-05-08 10:23:06
标签:go,zero,布隆过滤器
一. 布隆过滤器简介
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
二. 常用场景
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


猜你喜欢
- 举一个例子,我现在有一些新闻信息,它包括这些字段;新闻ID,新闻Name,新闻ShortIntro,新闻Detail,新闻PublishTi
- 目录项目地址功能概述效果图模块安装提交环境为python3.7 pyqt5==5.13.2 win10 一切正常!说一说大概的思路吧项目地址
- console.log,作为一个前端开发者,可能每天都会用它来分析调试,但这个简单函数背后不简单那一面,你未必知道……基础首先,简单科普这个
- 下面为您介绍sql下用了判断各种资源是否存在的代码,需要的朋友可以参考下,希望对您学习sql的函数及数据库能够有所帮助。-- 库是否存在if
- 简单来说conda有什么用?方便的创建多个python虚拟环境,方便多个python项目同时开发的时候,每个项目都有自己独立的python开
- 介绍本文主要介绍Python中迭代的基本知识和使用什么是迭代在Python中,如果给定一个list或tuple,我们可以通过for循环来遍历
- 1. datetime 库概述以不同格式显示日期和时间是程序中最常用到的功能。Python 提供了一个处理时间的标准函数库 datetime
- 1、django应用Celerydjango框架请求/响应的过程是同步的,框架本身无法实现异步响应。但是我们在项目过程中会经常会遇到一些耗时
- python爬虫模块Request的安装在cmd中,使用如下指令安装requests:pip install requestspython爬
- 前言本文从代码复用的角度一步一步演示如何从python普通代码进化到面向对象,并通过代码去解释一些面向对象的理论。所以,本文前面的内容都是非
- 这篇文章介绍如何利用Selenium的方法进行截图,在测试过程中,是有必要截图,特别是遇到错误的时候进行截图。在selenium for P
- 通过 1至10 阶来拟合对比 均方误差及R评分,可以确定最优的“最大阶数”。import numpy as npimport matplot
- 1)对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 order by 涉及的列上建立索引。2)应尽量避免在 where 子
- 粒子群算法是一种基于鸟类觅食开发出来的优化算法,它是从随机解出发,通过迭代寻找最优解,通过适应度来评价解的品质。PSO算法的搜索性能取决于其
- 情人节快乐!这个节日怎么会少了浪漫的玫瑰花!用Python的turtle库绘图是很简单的,画了一个玫瑰花,下面奉上源码:源码:'
- 在asp中调用sql server的存储过程可以加快程序运行速度,本文介绍了asp使用存储过程的方法。1.调用存储过程的一般方法 先假设在s
- 使用Python方法比用各种命令方便,可以设置超时时间,到底通不通,端口是否开放一眼能看出来。命令和返回完整权限,可以ping通,端口开放,
- 导读:最近数据库经常出现会话阻塞的报警,过一会又会自动消失,昨天晚上恰好发生了一次,于是赶紧进行了查看,不看不知道,一看吓一跳,发现是由da
- 一、临时表空间概念临时表空间用来管理数据库排序操作以及用于存储临时表、中间排序结果等临时对象,当ORACLE里需要用到SORT的时候,并且当
- 每个熟悉python的人都知道,python提供给了我们各种各样原生的数据结构,如list、tuple、set、dict等等。这些形形色色的