尼恩说在前面
亿级海量数据查重，如何实现 ？ 亿级海量数据黑名单 ，如何存储？ 50亿个电话号码，如何判断是否10万个电话号码是否存在？ 安全连接网址，全球数10亿的网址判断？
最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，回复：领电子书
本文目录
- 尼恩说在前面
- 首先回顾一下：四大统计（基数统计，二值统计，排序统计、聚合统计）的原理 和应用场景
- 第1大统计：基数统计
-基数统计的2大类型
-基数统计的应用场景和案例
- 第2大统计：二值统计
-二值统计的4大类型
-二值统计的应用场景和案例
- 第3大统计：排序统计
-排序统计的2大类型
-排序统计的应用场景和案例
-排序统计的场景1：排行榜系统：
-排序统计的场景 2：数据筛选和统计：
- 第4大统计：聚合统计
-Redis 聚合统计的数据结构
-聚合统计的应用场景
-场景1：网站流量分析
-场景2：电商数据分析
-场景3：社交平台用户行为分析
-场景4：游戏数据分析
- 回到前面的相关面试题，都属于二值统计的类型
- 使用 BitMap 位图进行二值统计
- 使用 BitMap 位图进行用户黑名单管理
- 使用 布隆过滤器（Bloom Filter） 进行二值统计
- BloomFilter常见应用场景：
-经典场景：解决缓存穿透的问题
-经典场景：黑名单校验
- 布隆过滤器（Bloom Filter）原理
-哈希函数
- 添加与查询元素步骤
- 布隆过滤器原理
- 数据结构
- 增加元素
- 查询元素
- 删除元素
- 单体服务 本地布隆过滤器 Guava
- Redis 的 BloomFilter (布隆过滤器)
- 安装REDIS 和 REDISBLOOM插件
- Redis 的 BloomFilter 相关命令
- Redis 的 BloomFilter 的c++编码结构
- Redis 的 BloomFilter 的哈希规则（插入/判断规则）
- Redis Client客户端中布隆过滤器的基本使用
- Redis Client 创建一个自定义参数的布隆过滤器
- 实战：使用redisson 布隆过滤器实现用户黑名单
-pom中引入redisson依赖:
-编写代码测试
- 实战：BloomFilter实现亿级海量数据查重/亿级海量数据黑名单
- 布隆过滤器的大小预估
- 布隆过滤器的优点和缺点
- 布隆过滤器的优点：
- 布隆过滤器的 问题
- 其他问题
- Cuckoo Filter 布谷鸟过滤器
- 布谷鸟哈希结构的原理
- Cuckoo Filter 插入
- Cuckoo Filter 插入时的踢出
- Cuckoo Filter 查找
- Cuckoo Filter 删除
- Cuckoo Filter 的问题和优化
- 和Cuckoo Filter 相比，BloomFilter 的不足
- Redis 的 CuckooFilter (布谷鸟过滤器)
- Redis 的 CuckooFilter (布谷鸟过滤器)相关命令
- Redis 的 布谷鸟过滤器 的主要**c++** 数据结构
- Redis 的 布谷鸟过滤器 哈希规则（插入/判断规则）
- Redis 的 布谷鸟过滤器 踢除规则
- Redis Client客户端 布谷鸟过滤器的命令
-创建布谷鸟过滤器
-布谷鸟过滤器中添加元素
-布谷鸟过滤器中添加元素（不存在时则插入）
-CF.RESERVE 和 CF.ADD，CF.ADDNX 的复合体
-布谷鸟过滤器中判断元素是否存在
-布谷鸟过滤器中删除元素
-布谷鸟过滤器中查询元素存在的数量
-将一个布谷鸟过滤器以分片的方式读出
-将一个布谷鸟过滤器以分片的方式写入
-查看布谷鸟过滤器详情
- 实战：CuckooFilter实现亿级海量数据查重/亿级海量数据黑名单
- 布谷鸟过滤器和布隆过滤器的对比
- 布谷鸟过滤器优点和缺点
- 尼恩架构团队塔尖的redis 面试题
- 说在最后：有问题找老架构取经
首先回顾一下：四大统计（基数统计，二值统计，排序统计、聚合统计）的原理 和应用场景
第1大统计：基数统计
基数统计的2大类型
基数统计的应用场景和案例
统计网站注册IP数：使用HyperLogLog可以高效地统计网站注册用户的独立IP数量，为网站运营者提供有价值的数据支持。 统计每日访问IP数：通过对用户访问日志进行处理，使用HyperLogLog可以快速统计出每日的独立访问IP数，有助于分析网站流量和用户行为。 统计页面实时UV PV数：在实时监控系统中，使用HyperLogLog可以估算出页面的实时访问用户数（UV）和页面访问量（PV），为网站运营者提供实时反馈。 统计在线人数：在实时在线人数统计系统中，HyperLogLog可以用于估算当前在线用户的数量，为系统性能优化和用户体验改进提供数据支持。 APP活跃用户数：统计一个APP的日活(日活跃用户数量)、月活数(月活跃用户数量)，即每天或每月有多少不同的用户活跃
UV(Unique Visitor)：独立访客，一般为客户端IP，要去重 PV(Page View)：页面浏览量，不用去重 DAU(Daily Active User)：日活跃用户量，当天登录或者使用某个产品的用户数，要去掉重复登录的用户，多次登录只记录一次 MAU(Monthly Active User)：月活跃用户
若数据量小，通过使用哈希集合可以精确计算基数 若数据量庞大，HyperLogLog 则是一种更合适的近似计算方法。
第2大统计：二值统计
二值统计的4大类型
counts，counts[0]用于记录状态为 0 的元素数量，counts[1]用于记录状态为 1 的元素数量。二值统计的应用场景和案例
第3大统计：排序统计
可以 使用ZSET对文章的点赞数排序并分页展示 对评论根据时间进行排序
排序统计的2大类型
排序统计的应用场景和案例
排序统计的场景1：排行榜系统：
排序统计的场景 2：数据筛选和统计：
第4大统计：聚合统计
Redis 聚合统计的数据结构
SCARD统计集合元素个数、SINTER计算集合交集等）实现简单的聚合。聚合统计的应用场景
场景1：网站流量分析
UV（独立访客）和 PV（页面浏览量）统计： 通过在 Redis 中使用集合记录每个访问用户的唯一标识来统计 UV。 每当有新用户访问，就将其 ID 添加到集合中，利用 SCARD命令获取集合大小即 UV。对于 PV，可以在每次页面加载时，对一个计数器进行递增操作，计数器可以存储在 Redis 的字符串（String）类型中。 热门页面统计： 利用有序集合，将页面 URL 作为元素，页面的访问次数作为分数。 每次页面被访问，就更新对应的分数。通过 ZRANGE命令可以获取访问次数最多的页面列表，从而找出热门页面。
场景2：电商数据分析
商品销售统计：使用哈希存储商品信息，如商品 ID 作为键，包含销量、销售额等信息的字典作为值。每当有商品销售，就更新对应的销量和销售额。通过遍历哈希表中的所有商品记录，可以统计总销量、总销售额等信息。 用户购买行为分析：用集合记录用户购买的商品类别，通过集合的交集、并集等运算，可以分析不同用户群体之间购买行为的相似性。例如，计算购买母婴产品和购买美妆产品的用户群体的交集，找出既购买母婴产品又购买美妆产品的用户。
场景3：社交平台用户行为分析
粉丝重合度分析： 假设在一个社交平台上，有用户 A 和用户 B。使用 Redis 集合分别存储用户 A 的粉丝集合 set:A_fans和用户 B 的粉丝集合set:B_fans。通过 SINTER命令计算两个集合的交集SINTER set:A_fans set:B_fans，可以得到同时是用户 A 和用户 B 粉丝的用户列表。这个数据可以用于分析用户之间的影响力关联，例如，如果两个明星的粉丝重合度很高，可能意味着他们在某些方面具有相似的受众群体。 用户互动统计 对于用户的点赞、评论、分享等互动行为，可以通过有序集合来统计。以用户发布的内容为单位，将内容 ID 作为有序集合的元素，互动次数作为分数。 例如，有序集合 zset:content_interactions存储了所有内容的互动情况。当一条内容获得新的互动时，更新对应的分数。 通过 ZRANGEBYSCORE命令，可以获取互动次数在一定范围内的内容列表，用于发现热门内容或者筛选出需要重点关注的内容。
场景4：游戏数据分析
玩家道具统计：在游戏中，使用哈希来存储玩家的道具信息。例如，哈希表 hash:player_props中，键是玩家 ID，值是一个包含各种道具数量的字典。每次玩家获得或使用道具，就更新对应的道具数量。通过遍历哈希表，可以统计所有玩家的某种道具的总持有量，用于游戏平衡性分析。关卡通关率统计：利用有序集合，将游戏关卡 ID 作为元素，通关玩家数量作为分数。每当有玩家通关一个关卡，就更新对应的分数。通过 ZRANGE命令可以获取通关率最高的关卡列表，用于游戏关卡的优化和推荐。例如，如果某个关卡的通关率过低，开发者可以考虑调整关卡难度。
回到前面的相关面试题，都属于二值统计的类型
使用 BitMap 位图进行二值统计 使用BloomFilter 进行二值统计 使用Cuckoo Filter 布谷鸟过滤器 进行二值统计
使用 BitMap 位图进行二值统计
支持统计 1 的数量 支持统计某个偏移量是不是 1 支持多个 BitMap做And和OR等操作
Set无法完全支持，其他都是可以支持的。BitSet了？($offset/8/1024/1024)MB可以算出，offset最大为4,294,967,296，也就是 2的32次方 ，所以 offset也不能大于这个值。使用 BitMap 位图进行用户黑名单管理
key为user_blacklist，offset 是用户的 id(用户 不能大于 2^32次方, 不能大于10个亿)pom.xml文件中添加以下依赖：<dependency>
<groupId>redis.clients</groupId>
<artifactId>jedis</artifactId>
<version>3.3.0</version>
</dependency>
import redis.clients.jedis.Jedis;
public class RedisUserBlacklist {
public static void main(String[] args) {
// 连接到 Redis 服务器
Jedis jedis = new Jedis("localhost", 6379);
// 假设用户 ID 范围为 1 到 1000
int userId = 123;
// 将用户加入黑名单，将对应位置的位设置为 1
jedis.setbit("user_blacklist", userId - 1, true);
// 检查用户是否在黑名单中
boolean isInBlacklist = jedis.getbit("user_blacklist", userId - 1);
System.out.println("User " + userId + " is in blacklist: " + isInBlacklist);
// 关闭连接
jedis.close();
}
}
setbit方法将位图中对应参与者编号的位设置为 1 表示加入黑名单，再使用getbit方法检查某个参与者是否黑名单。($offset/8/1024/1024)MB可以算出，offset最大为4,294,967,296，也就是 2的32次方 ，所以 offset也不能大于这个值。使用 布隆过滤器（Bloom Filter） 进行二值统计
BloomFilter常见应用场景：
文档存储检查系统也采用布隆过滤器来检测先前存储的数据； Goole Chrome浏览器使用了布隆过滤器加速安全浏览服务； 垃圾邮件地址过滤； 爬虫URL地址去重：布隆过滤器可以用来去重已经爬取过的URL。 黑白名单。 爬虫URL地址去重； 著名Hbase使用了布隆过滤器来查找不存在的行或列，以及减少磁盘查找的IO次数； 减少 昂贵的 磁盘IO 。Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。 减少 重复推送：业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。 解决缓存穿透问题 ：缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。 WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。 Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。 SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
经典场景：解决缓存穿透的问题
经典场景：黑名单校验
布隆过滤器（Bloom Filter）原理
哈希函数
如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。
如果这些点有任何一个 0，则被查询变量一定不在； 如果都是 1，则被查询变量很可能存在
一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
单体服务 本地布隆过滤器 Guava
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {
public static void main(String[] args) {
// 创建一个可以容纳 1000 个元素，误判率为 0.01 的布隆过滤器
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1000, 0.01);
// 插入元素
for (int i = 1; i <= 500; i++) {
bloomFilter.put(i);
}
// 查询元素
int testValue = 450;
boolean mightContain = bloomFilter.mightContain(testValue);
System.out.println("布隆过滤器判断 " + testValue + " 是否存在：" + mightContain);
// 测试误判
int nonExistentValue = 10000;
boolean falsePositive = bloomFilter.mightContain(nonExistentValue);
System.out.println("布隆过滤器对不存在的值 " + nonExistentValue + " 的误判：" + falsePositive);
}
}
Redis 的 BloomFilter (布隆过滤器)
官网：https://redisbloom.io/ GitHub 地址：https://github.com/RedisBloom/RedisBloom 命令文档地址：https://redis.io/docs/stack/bloom/ 支持功能： 可扩展的 BloomFilter (布隆过滤器) ：用于确定一个元素是否存在于一个集群中； 可扩展的 CuckooFilter (布谷鸟过滤器) ：用于确定一个元素是否存在于一个集合中； Count-Min Sketch (最小计数草图) ：用于估计一个数据的出现次数； T-Digest (近似百分位) ： TopK ：维护了 k 个最常见项目的列表；
BloomFilter 类 的相关功能来进行实现的。安装REDIS 和 REDISBLOOM插件
#下载
[root@localhost redis]# /root/redis
[root@localhost redis]# wget https://download.redis.io/releases/redis-5.0.5.tar.gz
#解压安装
[root@localhost redis]# tar -zxvf redis-5.0.5.tar.gz
[root@localhost redis]# ls
redis-5.0.5 redis-5.0.5.tar.gz
[root@localhost redis]# cd redis-5.0.5
[root@localhost redis-5.0.5]# make
https://github.com/RedisLabsModules/redisbloom/
tag:https://github.com/RedisBloom/RedisBloom/tags
[root@localhost redis]# wget https://github.com/RedisBloom/RedisBloom/archive/v2.2.1.tar.gz
[root@localhost redis]# tar -zxf v2.2.1.tar.gz
[root@localhost redis]# ls
redis-5.0.5 redis-5.0.5.tar.gz RedisBloom-2.2.1 v2.2.1.tar.gz
[root@localhost redis]# cd RedisBloom-2.2.1/
[root@localhost RedisBloom-2.2.1]# make
[root@localhost RedisBloom-2.2.1]# ls
changelog contrib Dockerfile docs LICENSE Makefile mkdocs.yml ramp.yml README.md redisbloom.so rmutil src tests
[root@localhost redis-5.0.5]# pwd
/root/redis/redis-5.0.5
[root@localhost redis-5.0.5]# ls
00-RELEASENOTES CONTRIBUTING deps Makefile README.md runtest runtest-moduleapi sentinel.conf tests
BUGS COPYING INSTALL MANIFESTO redis.conf runtest-cluster runtest-sentinel src utils
[root@localhost redis-5.0.5]# ls |grep redis.conf
redis.conf
[root@localhost redis-5.0.5]# vim redis.conf
[root@localhost redis-5.0.5]# ./src/redis-server ./redis.conf &
#查看是否启动成功
[root@localhost redis-5.0.5]# ps -ef|grep 6379
root 4234 4176 0 22:12 pts/0 00:00:07 ./redis-server *:6379
root 8744 4176 0 23:06 pts/0 00:00:00 grep --color=auto 6379
[root@localhost redis-5.0.5]# ./src/redis-cli
127.0.0.1:6379> keys *
(empty list or set)
127.0.0.1:6379>
Redis 的 BloomFilter 相关命令
| 命令 | 格式 | 说明 |
bf.add : 向目标布隆过滤器中添加一个元素； bf.madd : 向目标布隆过滤器中添加多个元素； bf.exists : 在目标布隆过滤器中判断一个元素是否存在； bf.mexists : 在目标布隆过滤器中判断多个元素是否存在； bf.info : 查看对应布隆过滤器的基础信息； bf.debug : 查看对应布隆过滤器的详细信息（包含每个布隆过滤器表的信息）； bf.insert : 向目标布隆过滤器中插入元素，如果对应布隆过滤器不存在则创建； bf.reserve : 修改目标布隆过滤器的属性； bf.loadchunk : 布隆过滤器从 AOF 中加载数据时用到的命令； bf.scandump : 布隆过滤器向 AOF 中持久化数据时用到的命令；
Redis 的 BloomFilter 的c++编码结构
typedef struct SBChain {
SBLink *filters; // 记录所有的布隆过滤器
size_t size; // 记录当前所有布隆过滤器可存储元素的数量
size_t nfilters; // 记录当前布隆过滤器数据的个数
unsigned options; // 创建布隆过滤器表所依赖的参数
unsigned growth; // 创建新的布隆过滤器时其容量是上一个布隆过滤器的容量倍数
} SBChain;
typedef struct SBLink {
struct bloom inner; // 对应的布隆过滤器
size_t size; // 已插入布隆过滤器表中的元素的个数
} SBLink;
struct bloom {
uint32_t hashes; // 记录当前的hash数量
uint8_t force64;
uint8_t n2;
uint64_t entries; // 记录当前布隆过滤器的容量
double error; // 记录当前布隆过滤器的误判率
double bpe;
unsigned char *bf; // 指向布隆过滤器存储内容的内存块
uint64_t bytes; // 记录布隆过滤器存储内容的内存块的大小（字节）
uint64_t bits; // 记录布隆过滤器存储内容的内存块的大小（比特）
};
Redis 的 BloomFilter 的哈希规则（插入/判断规则）
MurmurHash64A首先使用固定的哈希种子，对传入的元素计算其哈希值，并将其作为基础的哈希值； 然后使用传入元素的哈希值作为哈希种子，计算下一次哈希位置的步进值； 利用得到的传入元素的哈希特征，在多个布隆过滤器中进行判断元素是否存在； 判断基础的哈希值对应的比特索引； 利用计算的步进值，判断下一个对应的比特索引；
// 计算传入元素的哈希特征
bloom_hashval bloom_calc_hash64(const void *buffer, int len) {
bloom_hashval rv;
rv.a = MurmurHash64A_Bloom(buffer, len, 0xc6a4a7935bd1e995ULL);
rv.b = MurmurHash64A_Bloom(buffer, len, rv.a);
return rv;
}
// 判断多个布隆过滤器中的对应比特位
for (int ii = sb->nfilters - 1; ii >= 0; --ii) {
if (bloom_check_h(&sb->filters[ii].inner, h)) {
return 0;
}
}
Redis Client客户端中布隆过滤器的基本使用
bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。
> bf.add one-more-filter fans1
(integer) 1
> bf.add one-more-filter fans2
(integer) 1
> bf.add one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans1
(integer) 1
> bf.exists one-more-filter fans2
(integer) 1
> bf.exists one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans4
(integer) 0
> bf.madd one-more-filter fans4 fans5 fans6
1) (integer) 1
2) (integer) 1
3) (integer) 1
> bf.mexists one-more-filter fans4 fans5 fans6 fans7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
Redis Client 创建一个自定义参数的布隆过滤器
bf.add命令时自动创建的。bf.add命令添加元素之前，使用bf.reserve命令创建一个自定义的布隆过滤器。bf.reserve命令有三个参数，分别是：key：键error_rate：期望错误率，期望错误率越低，需要的空间就越大。capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。
> bf.reserve one-more-filter 0.0001 1000000
OK
bf.reserve命令就会报错。bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。error_rate越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。error_rate和 capacity都需要设置一个合适的数值。实战：使用redisson 布隆过滤器实现用户黑名单
pom中引入redisson依赖:
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.16.0</version>
</dependency>
编写代码测试
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
public class RedissonBloomFilterBlacklist {
public static void main(String[] args) {
// 创建 Redisson 配置
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
// 创建 Redisson 客户端
RedissonClient redisson = Redisson.create(config);
// 创建布隆过滤器，用于存储用户黑名单
RBloomFilter<String> blacklistFilter = redisson.getBloomFilter("userBlacklist");
// 初始化布隆过滤器，预计存储 10000 个元素，误报率为 0.01
blacklistFilter.tryInit(10000, 0.01);
// 将用户 ID 添加到黑名单
blacklistFilter.add("user123");
blacklistFilter.add("user456");
// 检查用户是否在黑名单中
boolean isInBlacklist = blacklistFilter.contains("user123");
System.out.println("User123 is in blacklist: " + isInBlacklist);
boolean isNotInBlacklist = blacklistFilter.contains("user789");
System.out.println("User789 is in blacklist: " + isNotInBlacklist);
// 关闭 Redisson 客户端
redisson.shutdown();
}
}
实战：BloomFilter实现亿级海量数据查重/亿级海量数据黑名单
package com.crazymaker.cloud.redis.redission.demo.business;
import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;
/**
* redis BloomFilter 布隆过滤器module 基于位图算法
* 功能：海量数据（亿级）查重
* 优点：占用内存极少，并且插入和查询速度都足够快
* 缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。
*/
@Slf4j
@Service
public class RedisModuleBloomFilter {
@Autowired
private JedisPool jedisPool;
/**
* 手机号是否存在检测
*
* @param filterName 过滤器名称
* @param phone 手机号
* @return true 表示存在
*/
public boolean isExist(String filterName, String phone) {
boolean booleans = false;
try {
//log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = getClient().exists(filterName, phone);
//log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 多手机号 是否存在检测
*
* @param filterName
* @param phones 手机号数组
* @return 返回对应的数组，true 表示存在
*/
public boolean[] isExist(String filterName, String[] phones) {
if (null == phones || phones.length < 1) {
return null;
}
if (phones.length > 1000000) {
return null;
}
boolean[] booleans = null;
try {
//log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = getClient().existsMulti(filterName, phones);
//log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 数据添加到过滤器
*
* @param filterName 过滤器名称
* @param phones 要添加的手机号
* @return
*/
public boolean[] addFilter(String filterName, String[] phones) {
if (null == phones || phones.length < 1) {
return null;
}
boolean[] booleans = null;
try {
log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = this.getClient().addMulti(filterName, phones);
log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 初始化过滤器
*/
public void initFilter() {
try {
Client client = this.getClient();
log.info("[初始化过滤器]数据：应用过滤器开始：{}", System.currentTimeMillis());
//初始化过滤器 投诉
client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_COMPLAINT", 500000, 0.0001);
//初始化过滤器 回T
client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_T", 200000, 0.0001);
log.info("[初始化过滤器]数据：应用过滤器结束：{}", System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
}
public Client getClient() {
Client client = new Client(jedisPool);
return client;
}
public Client getClient(JedisPool pool) {
Client client = new Client(pool);
return client;
}
}
布隆过滤器的大小预估
布隆过滤器的优点和缺点
# 布隆过滤器
# Memory
used_memory:4714576
used_memory_human:4.50M
# set
# Memory
used_memory:73434368
used_memory_human:70.03M
123456789
BloomFilter 是不可以删除元素的，BitSet 可以 BitSet 的偏移量是有限的，BloomFilter 却不是 BitSet 的结果是精准的，BloomFilter 却是存在偏差的 BitSet 的复杂度不是恒订的，偏差值越大，时间复杂度越高。Bloomfilter 是恒定的
布隆过滤器的优点：
支持海量数据场景下高效判断元素是否存在 布隆过滤器存储空间小，并且节省空间，不存储数据本身，仅存储hash结果取模运算后的位标记 不存储数据本身，比较适合某些保密场景
布隆过滤器的 问题
只能添加不能删除 假阳性问题：判断结果为存在的场景，有误判，匹配结果如果是“存在于过滤器中”，实际不一定存在 当容量快满时，hash碰撞的概率变大，插入、查询的错误率也就随之增加了
只能添加不能删除， 因为多个key映射的位置可能相同，如果删除一个，可能导致本来存在的也会被认为不存在，因为存在哈希冲突，可能添加的两个元素占一个坑位，此时如果删除其中一个则另一个的该坑位也为0，也会被认为删除，就会导致误判率增加，故不要轻易删除key 假阳性问题：判断结果为存在的场景，有误判 布隆过滤器中一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。因此，布隆过滤器不适合那些对结果必须精准的应用场景。 全为1不一定存在，有一个0则一定不存在，误判就是把认为存在的，可能不存在的 尽可能使得初始bit数组足够大，不要后续扩容 当容量快满时，hash碰撞的概率变大，插入、查询的错误率也就随之增加了 当实际元素过大时，远远大于初始数组，则必须对布隆过滤器重建，否则误判率会非常大，此时重新分配一个更大的bit数组，然后将原来的元素重新添加进入，再继续判断 使用时要尽可能使得初始bit数组足够大，不要后续扩容，后续要进行重建 当bitmap过小时，要进行重建，重新创建一个更大的bitmap，然后将数据重新加入
其他问题
不支持计数，同一个元素可以多次插入，但效果和插入一次相同 由于错误率影响hash函数的数量，当hash函数越多，每次插入、查询需做的hash操作就越多
Cuckoo Filter 布谷鸟过滤器
布谷鸟哈希结构的原理
key进行哈希，得到桶中的两个位置，此时如果两个位置都为为空则将 key随机存入其中一个位置如果只有一个位置为空则存入为空的位置 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置
Cuckoo Filter 插入
fp = fingerprint(x)
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 异或
第一个桶的索引是通过某个哈希函数计算出来， 第二个是使用第一个索引和指纹的哈希做了一个异或操作，
p1= p2 ^ hash(fp) // 异或
Cuckoo Filter 插入时的踢出
p1 = hash1(x) % l
p2 = hash2(x) % l
Cuckoo Filter 查找
Cuckoo Filter 删除
Cuckoo Filter 的问题和优化
和Cuckoo Filter 相比，BloomFilter 的不足
Redis 的 CuckooFilter (布谷鸟过滤器)
Redis 的 CuckooFilter (布谷鸟过滤器)相关命令
cf.add : 向目标布谷鸟过滤器中添加一个元素； cf.addnx : 向目标布谷鸟过滤器中添加一个元素，只有当元素不存在时才会添加成功； cf.count : 计算在目标布谷鸟过滤器中对应元素的个数，由于是计算对应元素的指纹的存在个数，因此最终结果可能不准确； cf.del : 从布谷鸟过滤器中删除一个元素，删除的是元素的指纹，并且只删除一次； cf.exists : 判断布谷鸟过滤器中对应元素是否存在； cf.mexists : 判断布谷鸟过滤器中多个元素是否存在； cf.info : 获取布谷鸟过滤器的信息； cf.insert : 向布谷鸟过滤器中插入一个元素，如果布谷鸟过滤器不存在则创建； cf.insertnx : 向布谷鸟过滤器中插入一个元素，如果布谷鸟过滤器不存在则创建，如果对应元素已经存在则不会插入成功； cf.reserve : 修改对应布谷鸟过滤器的属性； cf.loadchunk : 持久化的相关命令； cf.scandump : 持久化的相关命令；
Redis 的 布谷鸟过滤器 的主要c++ 数据结构
typedef struct {
uint64_t numBuckets; // bucket 的数量，大小为2次幂的值
uint64_t numItems; // 插入元素的数量
uint64_t numDeletes; // 删除元素的数量
uint16_t numFilters; // 所有子布谷鸟过滤器的数量
uint16_t bucketSize; // 每个 bucket 中可以存储指纹的数量，默认为2
uint16_t maxIterations; // 寻找指纹的存储空间时的最大迭代次数，默认为20次
uint16_t expansion; // 扩展倍数，大小为2次幂的值，默认为2
SubCF *filters; // 所有子布谷鸟过滤器信息的数组
} CuckooFilter;
typedef struct {
uint32_t numBuckets; // bucket 的数量，大小为2次幂的值
uint8_t bucketSize; // 每个 bucket 中可以存储指纹的数量
uint8_t *data; // 实际存储数据的内存块指针
} SubCF;
typedef struct {
uint64_t i1; // 记录元素的一个哈希值
uint64_t i2; // 记录元素的另一个哈希值
uint8_t fp; // 指纹的大小是1到255
} CuckooKey;
Redis 的 布谷鸟过滤器 哈希规则（插入/判断规则）
MurmurHash64A依据传入的元素，利用哈希算法 MurmurHash64A计算其哈希值；利用哈希值计算对应传入元素的指纹信息( fp)，以及对应的两个哈希特征值(h1和h2)；依次判断多个子布谷鸟过滤器中是否有足够的空间来存储新的元素； 每次都使用传入元素的两个哈希特征值 h1 和 h2判断在对应的 bucket 的数组中是否存在空位置： 如果有空位置则将对应的元素指纹插入对应空位； 如果没有空位置则尝试进行踢除操作； 插入元素或者判断元素是否存在结束；
Redis 的 布谷鸟过滤器 踢除规则
Filter_KOInsert将从最新的布谷鸟过滤器中执行踢除操作； 依据传入值的其中一个哈希值，找到对应的 bucket 的位置，获取其中特定位置中的指纹信息，然后将新的指纹存储到特定位置上； 寻找上次获取到的 bucket 中的老的指纹的下一个位置点，判断对应的 bucket 中是否有空闲位置：
如果有空闲位置，则将之前替换出的指纹存到新 bucket 的空闲位置中； 如果没有空闲位置，则再次进行寻找，再次从第2步开始；
Redis Client客户端 布谷鸟过滤器的命令
创建布谷鸟过滤器
CF.RESERVE {key} {capacity} [BUCKETSIZE {bucketsize}] [MAXITERATIONS {maxiterations}]
[EXPANSION {expansion}]
key：布谷鸟过滤器的键。 capacity：布谷鸟过滤器的容量。根据布谷鸟过滤器原理，写入时则可能未满，但由于互踢而被判定为满，需要扩容，故设置时，如果不考虑子过滤器扩容，则需要预设多于实际使用容量的 30%。 bucketsize：存储桶中的元素数，相比于原始的布谷鸟算法，redisbloom 中引入了存储桶的改进方式，以降低互踢次数，提高内存使用效率，但同时也会导致误判提高和写入性能的下降的问题（由于桶的存在，互踢需要将数组桶的内容交换，故性能下降），默认值为 2。 maxiterations：最大互踢次数。 EXPANSION：当容量不足时，扩容的倍率（这里的扩容用词不准，实际上是建立了子过滤器进行实现，根据这个原理，需要注意的是当子过滤器过多时，会成倍数的影响性能），不填默认为 1。例如：1，则当容量 100 满时，自动扩容为 100 + 100。
布谷鸟过滤器中添加元素
CF.ADD {key} {item}
key：布谷鸟过滤器的键，当键不存在时创建一个容量为 1080 的默认过滤器。 item：写入的元素。
布谷鸟过滤器中添加元素（不存在时则插入）
CF.ADDNX {key} {item}
key：布谷鸟过滤器的键，当键不存在时创建一个容量为 1080 的默认过滤器。 item：写入的元素。
CF.RESERVE 和 CF.ADD，CF.ADDNX 的复合体
CF.INSERT {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}
CF.INSERTNX {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}
布谷鸟过滤器中判断元素是否存在
CF.EXISTS {key} {item}
key：布谷鸟过滤器的键。 item：要判断的元素。
布谷鸟过滤器中删除元素
CF.DEL {key} {item}
key：布谷鸟过滤器的键。 item：移除的元素。
布谷鸟过滤器中查询元素存在的数量
CF.COUNT {key} {item}
key：布谷鸟过滤器的键。 item：查询数量元素。
将一个布谷鸟过滤器以分片的方式读出
CF.SCANDUMP {key} {iter}
key：布谷鸟的键。 iter：返回的分片下标，首个下标从 0 开始。
将一个布谷鸟过滤器以分片的方式写入
CF.LOADCHUNK {key} {iter} {data}
key：布谷鸟过滤器的键。 iter：返回的分片下标，首个下标从 0 开始。 data：写入的字节。
查看布谷鸟过滤器详情
CF.INFO {key}
key：布谷鸟过滤器的键。
实战：CuckooFilter实现亿级海量数据查重/亿级海量数据黑名单
package com.crazymaker.cloud.redis.redission.demo.business;
import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;
import java.util.ArrayList;
import java.util.List;
/**
* redis CuckooFilter 布谷鸟过滤器module 基于位图算法
* 功能：亿级海量数据查重/或者亿级海量数据黑名单
* 优点：占用内存极少，并且插入和查询速度都足够快
* 缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。
*/
@Slf4j
@Service
public class RedisModuleCuckooFilter {
@Autowired
private JedisPool jedisPool;
/**
* 手机号是否存在过滤器中
*
* @param filterName 过滤器名称
* @param phone 手机号
* @return true 表示存在
*/
public boolean isExist(String filterName, String phone) {
boolean booleans = false;
try {
//log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = getClient().cfExists(filterName, phone);
//log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 数据添加到过滤器
*
* @param filterName 过滤器名称
* @param phone 要添加的手机号
* @return
*/
public Boolean addFilter(String filterName, String phone) {
Boolean booleans = false;
try {
log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = this.getClient().cfAddNx(filterName, phone);
log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 数据添加到过滤器
*
* @param filterName 过滤器名称
* @param phones 要添加的手机号
* @return
*/
public List<Boolean> addFilter(String filterName, String[] phones) {
if (null == phones || phones.length > 0) {
return new ArrayList<>();
}
List<Boolean> booleans = new ArrayList<>();
try {
log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = this.getClient().cfInsertNx(filterName, phones);
log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 数据从过滤器删除
*
* @param filterName 过滤器名称
* @param phone 要删除的手机号
* @return
*/
public boolean deleteFilter(String filterName, String phone) {
if (null == phone) {
return false;
}
boolean booleans = false;
try {
log.info("[过滤器删除数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
booleans = this.getClient().cfDel(filterName, phone);
log.info("[过滤器删除数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
} catch (Exception e) {
e.printStackTrace();
}
return booleans;
}
/**
* 初始化过滤器
*/
public void initFilter() {
try {
Client client = this.getClient();
log.info("[初始化过滤器]数据：应用过滤器开始：{}", System.currentTimeMillis());
//初始化过滤器 系统白名单
client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_WHITE", 100000, 0.0001);
} catch (Exception e) {
e.printStackTrace();
}
}
public Client getClient() {
Client client = new Client(jedisPool);
return client;
}
public Client getClient(JedisPool pool) {
Client client = new Client(pool);
return client;
}
}
布谷鸟过滤器和布隆过滤器的对比
# 布谷鸟过滤器
# Memory
used_memory:2114792
used_memory_human:2.02M
# set
# Memory
used_memory:73434368
used_memory_human:70.03M
布谷鸟过滤器优点和缺点
空间效率：相较于布隆过滤器，布谷鸟过滤器能够在相同的存储空间内存储更多的元素，且误判率较低。 快速查找：查找操作的时间复杂度为 O(1)，非常快速，适合高吞吐量的场景。 支持删除：与布隆过滤器不同，布谷鸟过滤器支持有效的删除操作，尽管相对复杂，但仍然比布隆过滤器更灵活。 误判率低：布谷鸟过滤器的误判率可以通过调整桶的大小和元素的指纹长度来控制，通常比布隆过滤器更低。 实现简单：数据结构相对简单，易于实现。
删除操作复杂：删除元素时，可能需要迁移指纹，这增加了操作的复杂性。 扩展性限制：当过滤器满时，可能需要重新分配并重建过滤器，这会影响性能。 存储占用：尽管比布隆过滤器更高效，但相较于传统哈希表，布谷鸟过滤器在存储指纹和桶的开销上仍然存在占用。 哈希函数依赖：过滤器的性能依赖于哈希函数的质量，若哈希函数不均匀，可能导致某些桶过载。不适用于小集合：对于小型集合，布谷鸟过滤器的优势不明显，可能不如其他简单的数据结构（如哈希表）更有效。
尼恩架构团队塔尖的redis 面试题
说在最后：有问题找老架构取经
亿级海量数据查重，如何实现 ？ 亿级海量数据黑名单 ，如何存储？ 50亿个电话号码，如何判断是否10万个电话号码是否存在？ 安全连接网址，全球数10亿的网址判断？
使用 BitMap 位图进行二值统计 使用BloomFilter 进行二值统计 使用Cuckoo Filter 布谷鸟过滤器 进行二值统计
空窗1年/空窗2年，如何通过一份绝世好简历， 起死回生 ？
空窗8月：中厂大龄34岁，被裁8月收一大厂offer， 年薪65W，转架构后逆天改命!
空窗2年：42岁被裁2年，天快塌了，急救1个月，拿到开发经理offer，起死回生
空窗半年：35岁被裁6个月， 职业绝望，转架构急救上岸，DDD和3高项目太重要了
空窗1.5年：失业15个月，学习40天拿offer， 绝境翻盘，如何实现？
100W 年薪 大逆袭, 如何实现 ？
100W案例，100W年薪的底层逻辑是什么？ 如何实现年薪百万？ 如何远离 中年危机？
如何 评价一份绝世好简历， 实现逆天改命，包含AI、大数据、golang、Java 等
实现职业转型，极速上岸
关注职业救助站公众号，获取每天职业干货
助您实现职业转型、职业升级、极速上岸
---------------------------------
实现架构转型，再无中年危机
关注技术自由圈公众号，获取每天技术千货
一起成为牛逼的未来超级架构师
几十篇架构笔记、5000页面试宝典、20个技术圣经
请加尼恩个人微信 免费拿走
暗号，请在 公众号后台 发送消息：领电子书
如有收获，请点击底部的"在看"和"赞"，谢谢
