一 什么是布隆过滤器
布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中
1.工作原理
当一个元素被加入集合时,通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点位(offset),把它们置为 1。
判断是否存在时,只要看这些点是不是都是 1。
如果这些点有任何一个 0,则被检元素一定不在;
如果都是 1,则被检元素很可能在。这就是布隆过滤器的基本思想。
2.优点
- 空间占用小,相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。
- 布隆过滤器存储空间和插入/查询时间都是常数 O(k) 。
- 散列函数相互之间没有关系,方便由硬件并行实现。
- 布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
3.缺点
- 随着存入的元素数量增加,误算率随之增加
例如元素a hash后的bit点位是 1,2,3; 元素b hash后bit点位也是1,2,3 ,然而b并不存在于布隆表中。 - 元素无法删除
4.误判率推导
m 是该位数组的大小,k 是 Hash 函数的个数。
//todo
二 基于redis bitmap实现布隆过滤器
1.lua实现位bitmap操作, 保证整个操作的原子性
设置bloom 位
--ARGV:偏移量offset数组
--KYES[1]: setbit操作的key
--全部设置为1
for _, offset in ipairs(ARGV) do
redis.call("setbit", KEYS[1], offset, 1)
end
读取
--ARGV:偏移量offset数组
--KYES[1]: getbit操作的key
--检查是否全部为1 ,全部为1 说明已经存在了
for _, offset in ipairs(ARGV) do
if tonumber(redis.call("getbit", KEYS[1], offset)) == 0 then
return false
end
end
return true
2.代码实现
type redisBitSet struct {
store *redis.Redis
key string //redis key
bits uint //bloom表长度
}
//检查bit位 是否是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)
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
}
//设置元素已经存在
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)
if err == redis.Nil {
return nil
}
return err
}
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
}