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

实现原理

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.htmlfunc 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

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

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

示例

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

  1. 用于向布隆过滤器中增加值 post /bloom
  2. 判断某个值是否存在于布隆过滤器中 get /bloom/:name
// 初始化配置rest:  Name: zero_api  Host: 0.0.0.0  Port: 2555redis:  address: 127.0.0.1  port:    6379  username:  password:bloom:  element: 300
// 初始化一个布隆过滤器， 长度为6000, key为testvar TestFilter *bloom.Filtervar RedisClient *redis.Redisfunc 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}
  1. 为了验证咱们的代码失效，启动http服务
  2. 在增加元素前，查看一下test这个二进制数中值为1 的数量
  3. 而后通过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

  • 误报率
    测试数据较少，暂未验证