小空间做大事情
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%
在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
}
