当前位置: 首页 > news >正文

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则代表数据存在

相关文章:

  • 数组试题(Python实现)
  • PHP 杂项 函数
  • Mybatis持久层框架 | CRUD
  • 内网渗透(八)之基础知识-企业域中计算机分类和专业名
  • Keras深度学习实战——使用深度Q学习进行SpaceInvaders游戏
  • 周赛331总结
  • SSM整合知识点记录
  • 设计模式-模板方法模式
  • MySQL数据库01——mysql的安装和配置(包含workbench安装,超详细)
  • 2/4考试总结
  • Ta-Lib源码解析(三):蜡烛图指标 (Candlestick Indicator) #(附Python重构代码和示意图)(补充中)
  • 【嵌入式】MDK使用sct文件将代码段放入RAM中执行
  • 《基于Xilinx的时序分析、约束和收敛》目录与传送门
  • Jackson序列化带有注解的字段的原理浅析
  • 第十届“图灵杯”NEUQ-ACM程序设计竞赛题解(A-I)
  • Linux ALSA 之九:ALSA ASOC Codec Driver
  • 一文读懂JVM类加载机制过程及原理
  • 一文带你入门MyBatis Plus
  • java split()方法 toLowerCase() 方法
  • Ubuntu - command checklist
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉