网站开发方案,网站建设的单可以刷吗,培训机构暑假不能补课,游戏云电脑布隆过滤器简介
Bloom Filter(布隆过滤器)是一种多哈希函数映射的快速查找算法。它是一种空间高效的概率型数据结构#xff0c;通常应用在一些需要快速判断某个元素是否属于集合#xff0c;但是并不严格要求100%正确的场合。
布隆过滤器的优势在于#xff0c;利用很少的空…布隆过滤器简介
Bloom Filter(布隆过滤器)是一种多哈希函数映射的快速查找算法。它是一种空间高效的概率型数据结构通常应用在一些需要快速判断某个元素是否属于集合但是并不严格要求100%正确的场合。
布隆过滤器的优势在于利用很少的空间可以做到精确率较高空间效率和查询时间都比一般的算法要好的多缺点是有一定的误识别率和删除困难。为什么不允许删除元素呢删除意味着需要将对应的 k 个 bits 位置设置为 0其中有可能是其他元素对应的位。
哈希表与布隆过滤器
哈希表也能用于判断元素是否在集合中但是Bloom Filter只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。Bloom Filter可以插入元素但是不可以删除已有元素。集合中的元素越多误报率越大但是不会漏报。
应用场景
布隆过滤器的用处就是能够在节省存储空间的情况下迅速判断一个元素是否在一个集合中。主要有如下几个典型使用场景
网页爬虫对URL的去重避免爬取相同的URL地址反垃圾邮件从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱缓存击穿将已存在的缓存放到布隆过滤器中当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。黑白名单的过滤
原理
如果想判断一个元素是不是在一个集合中一般想到的方法是暂存数据然后查找判定是否存在集合中。这种方法在数据量比较小的情况下适用但是几个中元素较多的时候检索速度就会越来越慢。
可以利用Bitmap只要检查对应点是不是1就可以知道集合中有没有这个数。Bloom filter可以看做是对bitmap的扩展。只是使用多个hash映射函数从而减低hash发生冲突的概率。可以发现由于有hash的介入布隆过滤器整体上是一种非常概率的数据结构存在一定的误判率。所以有这样的特性key命中了布隆过滤器代表key可能在布隆过滤器中、key没有命中布隆过滤器代表key一定不在布隆过滤器中。
在Go 中比较常用的是https://github.com/bits-and-blooms/bloom我们可以通过分析这个开源的项目来看下布隆过滤器的实现原理
例子
package mainimport (fmtgithub.com/bits-and-blooms/bitsetbloom github.com/bits-and-blooms/bloom/v3
)func main() {filter : bloom.NewWithEstimates(1000000, 0.01)filter.Add([]byte(a))if filter.Test([]byte(a)) {fmt.Println(true)return}fmt.Println(false)
}数据结构
type BloomFilter struct {m uintk uintb *bitset.BitSet
}// 这个才是 BloomFilter 真正的底层结构就是一个 []uint64
type BitSet struct {length uintset []uint64
}// 将元素添加到 布隆过滤器 里面
// Add data to the Bloom Filter. Returns the filter (allows chaining)
func (f *BloomFilter) Add(data []byte) *BloomFilter {h : baseHashes(data)for i : uint(0); i f.k; i {f.b.Set(f.location(h, i))}return f
}可以简单理解成下面这张图元素169 经过 hash 函数之后存在了数组中在Bloom Filters 可视化网站 可以看到动态视频。然后判断存不存在只需要判断hash 之后的元素对应的数组位置是不是都等于1 问题
布隆过滤器的容量及误判率该如何设定
假设布隆过滤器容量为 n过滤器误判率为 p qps 为 x一次请求对布隆过滤器的访问次数为 g则极限 qps 场景下每秒对布隆过滤器的访问次数为 xg那每秒可能会有 xg*p 的请求到 数据源中假设我们的数据源的请求 qps限制 为 y那么误判率 p 的估计取值为 y / (x*g)。知道了容量和误判率之后我们就可以通过https://hur.st/bloomfilter/n100000000p0.0002mk 大致预估出 布隆过滤器 的大小 如何更新布隆过滤器
因为布隆过滤器不能够删除所以我们只能定时或者手动更新布隆过滤器
布隆过滤器 Redis 大Key问题
在 n 1 亿p0.0002的数据下布隆过滤器大概在 211.33MiB这个时候我们存在redis 上就会造成 redis 大key 问题有可能会引起redis 的慢查询拖挂 redis。
我们可以定时生成布隆过滤器讲结果存储在 DB 或者对象存储中由每一个服务的实例定时去拉取生成的最新布隆过滤器数据。
Redis布隆过滤器
bitmap
在刚刚我们提到布隆过滤器的核心数据结构为bitmap 在Redis上也支持bitmap其实就是对 string 的每一位进行操作。由此我们也可以得出用 Redis的bitmap实现的布隆过滤器可以存储最大的数据量为512x1024x1024x8 429496729642亿。
我们可以通过 SETBIT 来设置 bit的值GETBIT 来获取 bit位的值
127.0.0.1:6379 SETBIT mykey 7 1
(integer) 0
127.0.0.1:6379 GETBIT mykey 7
(integer) 1
127.0.0.1:6379 SETBIT mykey 7 0
(integer) 1
127.0.0.1:6379 GETBIT mykey 7
(integer) 0
127.0.0.1:6379所以通过Redis bitmap来实现布隆过滤器需要做三件事情
k 次散列函数计算出 k 个位点。插入时将位数组中 k 个位点的值设置为 1。查询时根据 1 的计算结果判断 k 位点是否全部为 1否则表示该元素一定不存在
Bloom Filter
我们也可以通过安装 Redis 的插件https://github.com/RedisBloom/RedisBloom这个插件包含了很多数据类型。Bloom filter布隆过滤器, Cuckoo filter布谷鸟过滤器, Count-min sketch(频率算法), Top-K, t-digest近似百分位算法
在Redis中的操作 bloom filter定义
BF.RESERVE {key} {error_rate} {capacity} 使用给定的期望错误率和初始容量创建空的Bloom过滤器如果不存在的话。如果打算向Bloom过滤器中添加许多项则此命令非常有用否则只能使用BF.ADD 添加项。 初始容量和错误率将决定过滤器的性能和内存使用情况。一般来说错误率越小(即对误差的容忍度越低)每个过滤器条目的空间消耗就越大。
bloom filter基本操作
BF.ADD {key} {item}
单条添加元素 向Bloom filter添加一个元素如果该key不存在则创建该key(过滤器)。 如果项是新插入的则为“1”;如果项以前可能存在则为“0”。
BF.MADD {key} {item} [item…]
批量添加元素 布尔数(整数)的数组。返回值为0或1的范围的数据这取决于是否将相应的输入元素新添加到过滤器中或者是否已经存在。
BF.EXISTS {key} {item}
判断单个元素是否存在 如果存在返回1否则返回0
BF.MEXISTS {key} {item} [item…]
判断多个元素是否存在
其他相关的命令可以在这里查询到https://redis.io/commands/?namebf
127.0.0.1:6379 BF.ADD bfKey 1
(integer) 1
127.0.0.1:6379 BF.ADD bfKey foo
(integer) 1
127.0.0.1:6379 BF.EXISTS bfKey 4
(integer) 0
127.0.0.1:6379 BF.EXISTS bfKey 4
(integer) 0
127.0.0.1:6379 BF.EXISTS bfKey 1
(integer) 1
127.0.0.1:6379 BF.EXISTS bfKey foo
(integer) 1
127.0.0.1:6379布谷鸟过滤器
为了解决布隆过滤器中不能删除且存在误判的缺点本文引入了一种新的哈希算法——cuckoo filter它既可以确保该元素存在的必然性又可以在不违背此前提下删除任意元素仅仅比bitmap牺牲了微量空间效率。
原理
最简单的布谷鸟哈希结构是一维数组结构会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空那么就可以将元素直接放进去。但是如果这两个位置都满了它就不得不「鸠占鹊巢」随机踢走一个然后自己霸占了这个位置。
使用两个哈希函数 h1(x) 、 h2(x) 和两个哈希桶 T1、T2 。插入元素 x 如果 T1[h1(x)] 、T2[h2(x)] 有一个为空则插入两者都空随便选一个插入。如果 T1[h1(x)] 、T2[h2(x)] 都满则随便选择其中一个设为 y 将其踢出插入 x。重复上述过程插入元素 y。 如果插入时踢出次数过多则说明哈希桶满了。则进行扩容、ReHash 后再次插入。查询元素 x 读取 T1[h1(x)] 、T2[h2(x)] 和 x 比对即可 可以通过这个Cuckoo Filter 可视化网站观察到。
其他
布谷鸟哈希布谷鸟过滤器布谷鸟过滤器实现
