关于golang:Go-布隆过滤器

A go bloom filter , base on different implement like redis ...

what?

上一篇在提到缓存击穿的时候, 有一种解决办法就是布隆过滤器布隆过滤器（英語：Bloom Filter）是1970年由布隆提出的。 它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器能够用于检索一个元素是否在一个汇合中。 它的长处是空间效率和查问工夫都远远超过个别的算法，毛病是有肯定的误识别率和删除艰难

why?

布隆过滤器: 能够判断某元素在不在汇合外面, 因为存在肯定的误判和删除简单问题;

个别的应用场景是:

• 避免缓存击穿(避免歹意攻打)
• 垃圾邮箱过滤
• cache digests (缓存索引)
• 模型检测器
• 判断是否存在某行数据,用以缩小对磁盘拜访，进步服务的拜访性能

how?

根本思维

通过多个hash办法, 进行屡次 hash 操作, 使其值位于bit不同位上, 检测该bit上的数据是否为1, 从而判断是否存在

源码剖析

interface: bloom.go

// 过滤器的外围实现, 通过interface的形式, 能够反对多种实现// 目前实现了基于redis bit数据类型的过滤器Provider interface {        Add(data []byte) error        Exists(data []byte) (bool, error)}// Filter is a bloom filterFilter struct {        // todo counter        total int64        hit   int64        miss  int64        provider Provider}

redis实现: internal/redis/redis_bit.go

// 实现Provider接口的两个办法// Add implement Provider interfacefunc (r *Provider) Add(data []byte) error {    location := r.getBitLocation(data)    return r.set(location)}// Exists implement Provider interfacefunc (r *Provider) Exists(data []byte) (bool, error) {    location := r.getBitLocation(data)    return r.check(location)}// 外围办法// 通过14次hash, 每次hash都在数据最初追加一个byte(index), 最初进行取模, 散布在map外面的每个区间// 查看是否存在时, 对每个bit位进行判断, 如果有一个等于0, 则数据不存在// getBitLocation return data hash to bit locationfunc (r *Provider) getBitLocation(data []byte) []uint {    l := make([]uint, maps)    for i := 0; i < maps; i++ {        hashV := r.hash(append(data, byte(i)))        l[i] = uint(hashV % uint64(maps))    }    return l}

todo

1) 能够实现统计数据, 比方总量, 命中率, 失落率等2) 实现其它bloom过滤器provider(目前只有基于redis bit)

example

func test() {    filter := NewRedis("127.0.0.1:6379", "test-bloom", 1024)    _ = filter.Add([]byte("a"))    _ = filter.Add([]byte("b))    _, _ = filter.Exists([]byte("a))    _, _ = filter.Exists([]byte("p))}

我的项目地址

https://github.com/sado0823/g...

references

1.https://github.com/tal-tech/g...

2.http://pages.cs.wisc.edu/~cao...