关于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 filter
Filter struct {

        // todo counter
        total int64
        hit   int64
        miss  int64

        provider Provider
}

redis实现: internal/redis/redis_bit.go

// 实现Provider接口的两个办法

// Add implement Provider interface
func (r *Provider) Add(data []byte) error {
    location := r.getBitLocation(data)
    return r.set(location)
}

// Exists implement Provider interface
func (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 location
func (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…