正文 

当前位置： 首页 > java > java教程

5分钟搞懂布隆过滤器，掌握亿级数据过滤算法(代码片段)

码农在新加坡 码农在新加坡     2022-12-04     250

关键词：

首发于微信公众号：【码农在新加坡】，欢迎关注。

个人博客网站：5分钟搞懂布隆过滤器，掌握亿级数据过滤算法

布隆过滤器是什么

本质上布隆过滤器(Bloom Filter)是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 某样东西一定不存在或者可能存在。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

可以一句话总结：

  • 如果Bloom Filter告诉你某个数据不存在，那么它一定不存在。
  • 如果Bloom Filter告诉你某个数据存在，那么它不一定存在。

然后你可能要问了，他都不一定存在了，那它有什么用。
它虽然不保证100%存在，但是这个误判率却是可以控制的，一般根据场景你可以设置一个可以接受的错误率，比如 0.0001(万分之一)，0.00001(十万分之一)。在很多场景下，这个概率是可以接受的。在这些场景下，它就有用武之地了。

而它的优点非常明显，就是极少的空间占用，一般比正常存所有数据可以节省90%左右以上的内存。

如果有人对具体的误判率怎么用数学公式推算出来的算法感兴趣。下面的详解部分会给出推导的链接。

实际场景

根据实际场景来让大家了解一下在什么场景下需要布隆过滤器，它又解决了什么问题。

我们有一个需求，是判断任意的两个userid有没有聊过天。即(useridA, useridB)是否聊过天，来决定前端场景是否展示对方的username。
我们最初的设计是放在Redis里面，存放的格式是：

Redis String
Key: prefixuseridA,useridB
Value: "1"

我们的Userid是int32的递增值，现在已经有10位整数。（eg: 1212341234）。所以这个key至少有22字节。

但是最终统计出来，我们的userid聊天的唯一Key：(useridA, useridB) 有4 Billion(40亿)的数据。

也就是我们至少需要存40亿的数据到Redis。

内存预估

Redis使用SDS的数据结构来储存字符串。
格式简化后如下图所示：

  • Key占用储存空间：Key(22)+SDS(9)=31;
  • Value占用储存空间：Value(1)+SDS(9)+redisObject(16)=26;

总内存占用：(31+26) * 4 billion = 228G。

我们预估未来还有10倍的增长空间，那就是2.28T。

当然这只是粗略的估计，Redis有更加复杂详细的规则来优化内存占用。
我自己尝试过插入一百万的数据到Redis，实际内存占用跟我的计算公式差不多。
所以这个内存占用是非常夸张的，我们需要用技术方案来优化这个内存占用。

这个时候我们就需要解决内存的占用过多的问题，布隆过滤器(Bloom Filter)闪耀登场。

详解

图解理论

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数，二进制大家应该都清楚，存储的数据不是0就是1，默认是0。

主要用于判断一个元素是否在一个集合中，0代表不存在某个数据，1代表存在某个数据。
布隆过滤器使用k个hash函数，每个哈希函数映射到Bit位的某一位，这样当k个位都为1的时候，我们认为这个元素存在。
如图所示：

流程

Set流程

  1. 设置K个hash函数. (f1, f2, f3, … fk).
  2. 对数据 (eg: golang) 进行hash，得到k个值. (2,6,11, …)
  3. 在Bit Array指定的位置设置为1.

Check流程

  1. 使用K个hash函数得到K个值。
  2. 在Bit Array上各个位置查看对应的值是否为1.
  3. 任何一个值为0，则此元素不存在。
  4. 所有的值都为0，则我们认为此元素存在。

布隆过滤器计算器

我们首先定义以下布隆过滤器的相关变量。

  • n: 总的数据量的数量大小。
  • p: 误判率的大小 (0.01 means 1%)
  • k: hash函数的数量
  • m: 需要的Bit数组的Bits空间量。

我们可以把 n,p 作为输入，就可以得到 k, m 作为输出。
也可以使用 n,p,k 作为输入，可以得到 m 作为输出。

这里是在线布隆过滤器计算器 布隆过滤器计算器

下图是我计算出来的值。

可以对比最初的设计方案，4 Billion的数据， 0.001的错误率。只需要7GB的内存。
7/228=3%， 差不多节省了97的内存空间。

误判率

你可能会好奇，误判率是什么。
因为我们使用的是hash映射。不同的数据经过不同的hash函数是有几率映射到同一个位置的。
例如：

f1(golang)=2, f2(golang)=6, f3(golang)=11
 
 
f1(python)=6
f2(java)=11
f3(cpp)=2

当我们把 python, jave, cpp 插入到Bit Array后，位置(2,6,11)的值都为1。
这个时候我们检查 golang 是否存在，由于这几个位置的值都为1， 所以系统会告诉我们 golang 存在。
实际上我们并没有插入 golang， 这就产生了误判。

所以我们回到最初的定义：
本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 某样东西一定不存在或者可能存在。

  • 如果布隆过滤器告诉你个数据不存在，那么它一定不存在。
  • 如果布隆过滤器告诉你某个数据存在，那么它可能存在。（也可能不存在，误判）。

实现

Redis内实现

Redis在4.0版本推出了 module 的形式，可以将 module 作为插件额外实现Redis的一些功能。官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module。
它主要使用的命令包含两个命令:

  1. bff.add key value //添加某个value
  2. bff.exists key value //判断某个value是否存在。

RedisBloom 安装

Redis不是默认就有，需要安装module才可以使用其命令。
未安装之前提示：

127.0.0.1:6379> bf.add bloom_key bloom_value
(error) ERR unknown command `bf.add`, with args beginning with: `bloom_key`, `bloom_value`,

可以使用docker安装，也可以使用源码安装：
这里只展示一下docker安装并测试简单指令，有需要源码安装的可以网上查看教程。

  1. 拉镜像
  2. docker运行redisbloom
  3. 进入docker
  4. 执行redis-cli
docker pull redislabs/rebloom:latest
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom bash
# redis-cli
127.0.0.1:6379> bf.add bloom_key bloom_value
(integer) 1
127.0.0.1:6379> bf.exists bloom_key bloom_value
(integer) 1
127.0.0.1:6379> bf.exists bloom_key bloom_other
(integer) 0

Redis的Bloom Filter内部使用Redis的Bitmap来实现。
Bitmap基于最小的单位bit进行存储，所以非常省空间。
redis中bit映射被限制在512MB之内。
有兴趣可以看一下Redis的官方文档。Redis BloomFilter

go语言Bloom Filter实现

由于Redis的Bloom Filter并非Redis原生自带的功能，需要安装module才能使用，很多时候生产环境使用的云服务并不一定完美支持，所以一般开发过程中都是自己实现Bloom Filter并储存储存介质中。(比如：使用Redis的setbit/getbit储存在Bitmap中)。

我们项目使用Golang，所以我自己实现了一个Golang的Bloom Filter并储存在Redis中，也可以选择储存在其他介质中，只需要实现BitmapProvider interface就可以。Bloom Filter和具体储存完全解耦。

源代码如下：Go-bloom

实现详解

我们的实现中，使用了Redis的Bitmap， Bitmap有 GETBIT和SETBIT 命令来操作Bit。
在Redis中，一个字符串最多可以为512MB。

所以需要把数据分片到多个string中。

核心代码如下：

const redisMaxLength int64 = 8 * 512 * 1024 * 1024  //512M
 
offsets := []int64f1("data1"), f2("data1"), ..., fk("data1")
 
for _, offset := range offsets 
    index := int64(offset / redisMaxLength)
    thisOffset := offset % redisMaxLength
    key := fmt.Sprintf("%s:%d", r.keyPrefix, index)
 
 
    redis.client.SetBit(key, thisOffset, 1)  //set
    redis.client.GetBit(key, thisOffset)  //get

使用案例

var client *redis.Client
client = redis.NewClient(&redis.Options
    Addr:     "127.0.0.1:6379",
    Password: "",
    DB:       0,
    PoolSize: 256,
)
//use the estimate m and k.
m, k := bloom.EstimateParameters(100000, 0.001)
//new a Bloom Filter
bitSet := bloom.NewRedisBitSet("test_key", m, client)
b := bloom.New(m, k, bitSet)

//check exist
data := []byte("some key")
exists, err := b.Exists(data)
err = b.Add(data)
exists, err := b.Exists(data)

总结

优点

  • 布隆过滤器告诉我们一个元素是否在一个集合里
  • 布隆过滤器非常省内存空间

缺点

  • 不支持删除 因为布隆过滤器是通过多个哈希函数把数据映射到多个bit中，那么不同的value可能映射到其中相同的bit中，所以如果删除某一个value，会影响所有其他映射到同样的bit中的value。
  • 误判率 由于是hash映射，所以多个value可能映射到同样的bit位中，可以通过增大hash的数量来减少误判率，但是无法完全避免。
  • 如果总的元素数量大于最初预估的总元素数量，误判率就会升高，需要重新扩容并初始化布隆过滤器。

<全文完>

欢迎关注我的微信公众号：码农在新加坡，有更多好的技术分享。

个人博客网站：5分钟搞懂布隆过滤器，掌握亿级数据过滤算法

5分钟搞懂布隆过滤器，掌握亿级数据过滤算法(代码片段)

...坡】，欢迎关注。个人博客网站：5分钟搞懂布隆过滤器，掌握亿级数据过滤算法布隆过滤器是什么本质上布隆过滤器(BloomFilter)是一种数据结构，比较巧妙的概率型数据结构（probabilisticdatastructure），特... 查看详情

如何判断一个元素是否存在于一个亿级数据集中？(代码片段)

布隆过滤器的概念布隆过滤器（BloomFilter）于1970年由布隆提出的，是专门用于检索一个元素是否存在于一个集合中的算法。你可能会想，判断一个元素是否在集合中，这不就是集合自带的功能吗？元素数量少的时候的确没问题，... 查看详情

图解布隆过滤器，十分钟带你理解什么是布隆过滤器

...文章里我们说了解决缓存穿透的办法之一，就是使用布隆过滤器，但是由于并没有详细介绍什么是布隆过滤器，所以就有很多小伙伴问我——到底什么是布隆过滤器？那么接下来就来给大家介绍什么是布隆过滤器以及他的实现原... 查看详情

小工匠聊架构-布隆过滤器在亿级流量的电商系统中的应用

...请求超高并发，会导致崩溃预防缓存穿透“神器”：布隆过滤器布隆过滤器在电商商品中的实践如何减少布隆过滤器的误判？布隆过滤器在Java中的应用布隆过滤器在项目中的应用初始化后，对应商品被删怎么办，布隆怎么办？Pr... 查看详情

c++数据结构与算法：布隆过滤器（bloomfilter）原理与实现(代码片段)

...thub.com/dongyusheng/csdn-code/tree/master/BloomFilter一、什么是布隆过滤器布隆过滤器（BloomFilter）是1970年由布隆提出的它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合... 查看详情

布隆过滤器(bloomfilter)(代码片段)

布隆过滤器(BloomFilter)是一种基于Hash的高效查找数据结构，它能够快速答复“某个元素是否存在”的问题。布隆过滤器只能用于添加元素与查询元素，不能够用于删除元素。在布隆过滤器之前，使用的是基于Hash的快速查找算法。... 查看详情

高级数据结构----跳跃表布隆过滤器一致性哈希雪花算法(代码片段)

...跃表与其它结构相比1.4使用场景1.5Redis中的跳跃表2、布隆过滤器(BloomFilter)2.1什么是布隆过滤器2.2原理2.3场景(Redis缓存穿透)3、一致性哈希3.1普通哈希3.2一致性哈希算法3.2.1基本原理3.2.2优点3.2.3hash环的偏斜3 查看详情

一文读懂布隆过滤器(代码片段)

什么是布隆过滤器？布隆过滤器（BloomFilter）是1970年由布隆提出的本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你“某样东西一定不存在或者可... 查看详情

布隆过滤器(代码片段)

...时能够迅速返回避免缓存及DB挂掉，引出了今天讲的布隆过滤器。布隆过滤器（BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。... 查看详情

redis十五.缓存穿透与布隆过滤器原理(代码片段)

目录一.布隆过滤简基础二.布隆过滤器原理三.redis缓存穿透Google布隆过滤器Guava解决缓存穿透Redis布隆过滤器解决缓存穿透(推荐)redis安装布隆过滤器插件四.模拟Guava编码通过redis实现布隆过滤器一.布隆过滤简基础首先了解一个需... 查看详情

布隆过滤器原理(代码片段)

简介：　　　　布隆过滤器（BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要... 查看详情

亿级流量多级缓存架构

...alue);redis.expire(key,300,SECOND);returnmysqlvalueelsereturnvalue;2.布隆过滤器解决缓存穿透问题：对于恶意攻击，向服务器请求大量不存在的数据造成的缓存穿透使用布隆过滤器需要把所有数据提前放入布隆过滤器，并且在增加数... 查看详情

caffeine缓存性能算法&布隆过滤器(代码片段)

算法优化缓存最重要的是命中率，我们知道，普通的缓存主要基于以下三种算法淘汰旧数据：FIFO先进先出LRU最久未使用LFU最少使用频率以上三种算法都有缺点，比如先进先出算法没有考虑使用频率；LRU也没有... 查看详情

10分钟搞懂：亿级用户的分布式数据存储解决方案！

...，才能支撑更多次亿级用户的涌入。接下来，你将花费十分钟掌握以下三方面内容：1、MySQL复制：包括主从复制和主主复制；2、数据分片：数据分片的原理、分片的方案、分片数据库的扩容；3、数据库分布式部署的几种方案。... 查看详情

手撕stlbitset（位图）布隆过滤器(代码片段)

位图位图的实现位图的应用哈希切割布隆过滤器布隆过滤器优点布隆过滤器缺陷布隆过滤器的应用场景布隆过滤器实现布隆过滤器删除如何选择哈希函数个数和布隆过滤器长度代码实现：相关面试题位图，就是用每一位... 查看详情

手撕stlbitset（位图）布隆过滤器(代码片段)

位图位图的实现位图的应用哈希切割布隆过滤器布隆过滤器优点布隆过滤器缺陷布隆过滤器的应用场景布隆过滤器实现布隆过滤器删除如何选择哈希函数个数和布隆过滤器长度代码实现：相关面试题位图，就是用每一位... 查看详情

c++布隆过滤器原理及实现(代码片段)

概念布隆过滤器（BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好... 查看详情

c++从青铜到王者第二十一篇:哈希的应用之位图布隆过滤器(代码片段)

...的概念2.位图的面试题3.位图的实现4.位图的应用二、布隆过滤器1.布隆过滤器的提出2.布隆过滤器的概念3.布隆过滤器的插入3.布隆过滤器的查找4.布隆过滤器的删除5.布隆过滤器的优点和缺点三、海量数据面试题1.哈希切割2.位图... 查看详情