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
0
投稿
猜你喜欢
- 关于文件名:必须以如下方式命名,不要乱起名,也无需专门手动控制加载哪个文件.env 全局默认配置文件,不论什么环境都会加载合并.env.de
- 首先来描述下环境,在机器上有很多个JAVA程序,我们在每个JAVA程序里都配置了一个启动|停止|重启的脚本举个例子:我们现在要同时运行这些脚
- MySQL支持大量的列类型,它可以被分为3类:数字类型、日期和时间类型以及字符串(字符)类型。本节首先给出可用类型的一个概述,并且总结每个列
- 用asp程序进行网页设计,大多因为需要访问数据库,然后再将数据显示到页面,如果数据很多的话,页面的访问速度也就变慢了,为了解决这个问题,可以
- 描述super() 函数用于调用下一个父类(超类)并返回该父类实例的方法。super 是用来解决多重继承问题的,直接用类名调用父类方法在使用
- 一 什么是XML?python与json数据的交互详情 在这篇文章中我们介绍了json是一种独立于编程语言和平台的数据存储和交换方
- 1.假设已经有mysql-5.5.10.tar.gz以及cmake-2.8.4.tar.gz两个源文件(1)先安装cmake(mysql5.
- 最近我在Go Forum 中发现了String size of 20 character 的问题,“hollowaykeanho” 给出了相
- MAC地址也叫物理地址、硬件地址,由网络设备制造商生产时烧录在网卡(Network lnterface Card)的EPROM(一种闪存芯片
- 一、复习首先将上次画的矩形做复杂一些的小程序:import pygame,sys, randompygame.init()screen =
- pandas: shape()获取Dataframe的行数和列数返回列数:df.shape[1]返回行数:df.shape[0]  
- Cloudflare 有一项功能挺不错的,就是将页面上所有的邮箱地址都加密起来,防止机器人抓到然后干坏事。这项功能要在后台开启 email
- 效果图:代码如下:<!DOCTYPE html><html lang="en"><head
- 关于 Settings Sync扩展:Settings Sync可以同步你当前的VSCode配置环境,当你需要在其它的电脑工作时,您不用重头
- 链表的反转是一个很常见、很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表。实现链表反转有两种方式
- CAPTCHA,全称为“Completely Automated Public Turing test to tell Computers
- Null模式我想每个人都有一种经历,为了获取某属性,但是有时候属性是None,那么需要你做异常处理, 而假如你想节省这样的条件过滤的代码,可
- 本文以实例形式讲述了Python中切片操作的用法,分享给大家供大家参考借鉴,具体如下:取一个list或tuple的部分元素是非常常见的操作。
- Usage example (libtiff wrapper)from libtiff import TIFF# to open a tif
- 本文主要给大家分享一个实战项目,通过python代码写一款我们儿时大多数人玩过的游戏---小弹球游戏。只不过当时,我们是在游戏机上玩,现在我