关于golang:gozero源码解析布隆过滤器

56次阅读

共计 1945 个字符，预计需要花费 5 分钟才能阅读完成。

本篇文章的前提须要理解布隆过滤器有什么用！

go-zero 中布隆过滤器的实现是借助于 redis 的 setbit 和 getbit 实现的

// New create a Filter, store is the backed redis, key is the key for the bloom filter,
// bits is how many bits will be used, maps is how many hashes for each addition.
// best practices:
// elements - means how many actual elements
// when maps = 14, formula: 0.7*(bits/maps), bits = 20*elements, the error rate is 0.000067 < 1e-4
// for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
func New(store *redis.Redis, key string, bits uint) *Filter {
    return &Filter{
        bits:   bits,
        bitSet: newRedisBitSet(store, key, bits),
    }
}

布隆过滤器（redis 中）实质是一个二进制数组，数组中每一个元素的值只能够是 0 或者 1，长度的范畴是 0~2^32。
对于这个布隆过滤器的形容能够从正文中失去，每一个布隆过滤器的元素会生成 14 个 hash 值，并且误报率为 0.000067

这个过滤器只对外提供了两个接口

增加一个元素到布隆过滤器中 Add
调用 getLocations 获取 14 个 hash 值，而后将布隆过滤器的这 14 个下标设置为 1；
判断元素是否存在于布隆过滤器中 Exists
先获取这 14 个值的 hash 值，而后判断在布隆过滤器中，这 14 个下标的元素值是否为 1，只有有一个不正确，都会返回 false

为了更好的演示布隆过滤器的应用，我创立了两个接口：

用于向布隆过滤器中增加值 post /bloom
判断某个值是否存在于布隆过滤器中 get /bloom/:name

// 初始化配置
rest:
  Name: zero_api
  Host: 0.0.0.0
  Port: 2555

redis:
  address: 127.0.0.1
  port:    6379
  username:
  password:

bloom:
  element: 300

// 初始化一个布隆过滤器，长度为 6000, key 为 test
var TestFilter *bloom.Filter
var RedisClient *redis.Redis

func Init(c config.Config) {port := strconv.FormatInt(c.Redis.Port, 10)

    address := fmt.Sprintf("%s:%s", c.Redis.Address, port)

    RedisClient = redis.New(address)
    TestFilter = bloom.New(RedisClient, "test", 20 * c.Bloom.Element)
}

// 向布隆过滤器中增加元素的逻辑，其实只是调用 Add 接口，并没有其余逻辑
func (l *BloomSetLogic) BloomSet(req types.BloomRequest) (*types.CommonResponse, error) {if err := bloom.TestFilter.Add([]byte(req.Name)); err != nil {return nil, err}
    return common.ReturnOk(nil), nil
}

为了验证咱们的代码失效，启动 http 服务
在增加元素前，查看一下 test 这个二进制数中值为 1 的数量
而后通过 postman 调用增加元素的接口，再次查看 test 这个二进制数中值为 1 的数量

能够在下图中看到，曾经有 14 个数组下标的值被置为 1

判断布隆过滤器是否存在某个值

// 判断 value 值是否存在于布隆过滤器中
func (l *BloomGetLogic) BloomGet(req types.Request) (*types.CommonResponse, error) {exists, err := bloom.TestFilter.Exists([]byte(req.Name))
    if err != nil {return nil, err}

    return common.ReturnOk(exists), nil
}

因为在刚刚咱们向 test 这个过滤器中推入了 good 这个值，能够看到，此时去查问，返回了 true

再查问一个没有推入过的值 hello，此时返回 false