布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难，这篇文章主要介绍了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则代表数据存在