详解布隆过滤器原理与实现

// 计算哈希次数
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
// 计算位数组长度
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
        p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

// 表示经过多少散列函数计算
// 固定14次
maps = 14
type (
    // 定义布隆过滤器结构体
    Filter struct {
        bits   uint
        bitSet bitSetProvider
    }
    // 位数组操作接口定义
    bitSetProvider interface {
        check([]uint) (bool, error)
        set([]uint) error
    }
)

// ARGV:偏移量offset数组
// KYES[1]: setbit操作的key
// 全部设置为1
setScript = `
    for _, offset in ipairs(ARGV) do
        redis.call("setbit", KEYS[1], offset, 1)
    end
    `
// ARGV:偏移量offset数组
// KYES[1]: setbit操作的key
// 检查是否全部为1
testScript = `
    for _, offset in ipairs(ARGV) do
        if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
            return false
        end
    end
    return true
    `

// redis位数组
type redisBitSet struct {
    store *redis.Client
    key   string
    bits  uint
}
// 检查偏移量offset数组是否全部为1
// 是:元素可能存在
// 否:元素一定不存在
func (r *redisBitSet) check(offsets []uint) (bool, error) {
    args, err := r.buildOffsetArgs(offsets)
    if err != nil {
        return false, err
    }
    // 执行脚本
    resp, err := r.store.Eval(testScript, []string{r.key}, args)
    // 这里需要注意一下,底层使用的go-redis
    // redis.Nil表示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
}
// 将k位点全部设置为1
func (r *redisBitSet) set(offsets []uint) error {
    args, err := r.buildOffsetArgs(offsets)
    if err != nil {
        return err
    }
    _, err = r.store.Eval(setScript, []string{r.key}, args)
    // 底层使用的是go-redis,redis.Nil表示操作的key不存在
    // 需要针对key不存在的情况特殊判断
    if err == redis.Nil {
        return nil
    } else if err != nil {
        return err
    }
    return nil
}
// 构建偏移量offset字符串数组,因为go-redis执行lua脚本时参数定义为[]stringy
// 因此需要转换一下
func (r *redisBitSet) buildOffsetArgs(offsets []uint) ([]string, error) {
    var args []string
    for _, offset := range offsets {
        if offset >= r.bits {
            return nil, ErrTooLargeOffset
        }
        args = append(args, strconv.FormatUint(uint64(offset), 10))
    }
    return args, nil
}
// 删除
func (r *redisBitSet) del() error {
    _, err := r.store.Del(r.key)
    return err
}
// 自动过期
func (r *redisBitSet) expire(seconds int) error {
    return r.store.Expire(r.key, seconds)
}
func newRedisBitSet(store *redis.Client, key string, bits uint) *redisBitSet {
    return &redisBitSet{
        store: store,
        key:   key,
        bits:  bits,
    }
}

// k次散列计算出k个offset
func (f *Filter) getLocations(data []byte) []uint {
    // 创建指定容量的切片
    locations := make([]uint, maps)
    // maps表示k值,作者定义为了常量:14
    for i := uint(0); i < maps; i++ {
        // 哈希计算,使用的是"MurmurHash3"算法,并每次追加一个固定的i字节进行计算
        hashValue := hash.Hash(append(data, byte(i)))
        // 取下标offset
        locations[i] = uint(hashValue % uint64(f.bits))
    }
  
    return locations
}

// 添加元素
func (f *Filter) Add(data []byte) error {
    locations := f.getLocations(data)
    return f.bitSet.set(locations)
}
// 检查是否存在
func (f *Filter) Exists(data []byte) (bool, error) {
    locations := f.getLocations(data)
    isSet, err := f.bitSet.check(locations)
    if err != nil {
        return false, err
    }
    if !isSet {
        return false, nil
    }
    return true, nil
}

// 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),
    }
}
// expectedInsertions - 预期总数量
// falseProbability - 预期误差
// 这里也可以改为option模式不会破坏原有的兼容性
func NewFilter(store *redis.Redis, key string, expectedInsertions uint, falseProbability float64) *Filter {
    bits := optimalNumOfBits(expectedInsertions, falseProbability)
    k := optimalNumOfHashFunctions(bits, expectedInsertions)
    return &Filter{
        bits:   bits,
        bitSet: newRedisBitSet(store, key, bits),
        k:      k,
    }
}
// 计算最优哈希次数
func optimalNumOfHashFunctions(m, n uint) uint {
    return uint(math.Round(float64(m) / float64(n) * math.Log(2)))
}
// 计算最优数组长度
func optimalNumOfBits(n uint, p float64) uint {
    return uint(float64(-n) * math.Log(p) / (math.Log(2) * math.Log(2)))
}