布隆过滤器

小空间做大事情

go-zero 里面用到了redis的 bitmap数据类型。其实应该说redis的bitmap在妙用在go-zero让我见识到了

原理分析：
如果你要判断一个数据在 1亿条数据集中是否存在，通法 把1亿条数据读到内存里面遍历做对比，一条数据算0.01kb算，1个G内存没了。但如果你用bitmap一条数据便只算1位，相差 8 * 1024 倍，也就只需要12M左右。但bitmap去重方案底层用到了hash，hash存在冲突，go-zero 里面用到的这方面的技巧也值得研究，大概结论就是 bitmap 12M能装 刚好1亿数据去重，打比方会有0.3%冲突率，但我测试go-zero如果我用24M去装这1亿数据能够有效降低这个0.3%

github代码该篇章地址

在bloom_test.go 中有调用示例

func TestRedisBitSet_Add(t *testing.T) {
    s, clean, err := createMiniRedis()
    assert.Nil(t, err)
    defer clean()
    store := redis.NewRedis(s.Addr(), redis.NodeType)
     // test_key 则为redis的bitmap的key，1024则是用多大的bitmap结构去当布隆过滤的过滤载体，这里就是1024位也就是1kb的redis空间
    filter := New(store, "test_key", 1024)
    assert.Nil(t, filter.Add([]byte("hello")))
    assert.Nil(t, filter.Add([]byte("world")))
    ok, err := filter.Exists([]byte("hello"))
    assert.Nil(t, err)
    assert.True(t, ok)
}


//以下是 filter.Add 的这个方法实现。


func (f *BloomFilter) Add(data []byte) error {
    locations := f.getLocations(data)
    err := f.bitSet.set(locations)
    if err != nil {
        return err
    }
    return nil
}

// 获取你任意字符串在我bitmap中申请好的对应的位。这个才是结合redis的bitmap后的核心处，它必须保证任意字符串来了之后都能随机均匀的分布在申请好的 位 中。
//这里也是冲突发生的地方，无法避免，但go-zero用到了去给redis的key设置3分钟过期时间巧妙清洗数据，而且结合到了lua脚本保证原子性，最终成形go-zero版本的 bloom,。
func (f *BloomFilter) getLocations(data []byte) []uint {
    locations := make([]uint, maps)
    for i := uint(0); i < maps; i++ {
        hashValue := hash.Hash(append(data, byte(i)))
        locations[i] = uint(hashValue % uint64(f.bits))
    }

    return locations
}