布隆过滤器原理与golang实现-ag真人游戏

一 什么是布隆过滤器

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中

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
}