最近做了一个项目，点赞接口相关采用的是布隆过滤器，在测试的过程中发现，有的取消点赞了，布隆过滤器不删除元素，出现了误判行为，虽然实际上用户是感知不到 bloom 里面添加了元素的，也能够正常取关，有二次校验。bloom 在大数据占用这块，还是很有优势的，不过代码上实现要复杂点，所以我打算给这块代码重构了

技术选型 布隆过滤器和咆哮位图

首先我了解到 Bitmap 位图在存储非连续，松散型元素时，存在内存占用非常大的问题，这个时候我们会想，如果 Bitmap 对稀疏数据也有很好的支持，内存占用很低，那就太棒了~ 虽然它不行，但是—— Roaring Bitmap （咆哮位图）行

什么是 Roaring Bitmap？

Roaring Bitmap （咆哮位图）是一种高效存储稀疏大整数集合的数据结构，由 Daniel Lemire 团队于2015年提出。它通过智能分层存储机制，在保证快速位运算的同时，实现了惊人的空间压缩效率。

它的优势

  • 极致压缩： Roaring Bitmap 采用了多种压缩策略，针对不同密度的数据集自动选择最优的存储方式，从而实现了极高的压缩率。例如，对于稀疏数据集，Roaring Bitmap 会使用数组存储，而对于密集数据集，则会使用位图存储。

  • 高效运算： Roaring Bitmap 支持高效的集合运算，例如并集、交集、差集等，这些运算的时间复杂度通常与数据集的大小成线性关系。此外，Roaring Bitmap 还支持快速检索和遍历，可以满足各种复杂的查询需求。

  • 易于使用： Roaring Bitmap 提供了丰富的 API 接口，可以方便地集成到各种编程语言和应用中。

Bloom Filter VS Roaring Bitmap

通过表格的方式，从各维度对比一波 Bitmap 和 Roaring Bitmap，如下：

特性

Roaring Bitmap

Bloom Filter

数据结构类型

精确型（每个位直接对应一个元素）

概率型（通过哈希间接映射元素）

内存消耗

与最大偏移量成正比（如偏移量范围大则内存高）

与元素数量和误判率相关（通常更节省内存）

查询性能

O(1)（直接访问偏移量）

O(k)（需计算 k 个哈希函数）

准确性

100% 精确（无漏判、无误判）

存在误判（False Positive），但无漏判

支持删除操作

✔️ 可直接修改位值

❌ 不支持（需 Counting Bloom Filter 变种，但会提升内存占用）

适用场景

1. 精确状态标记（用户签到） 2. 实时统计

1. 存在性检查（缓存穿透防护） 2. 去重过滤

稀疏数据优化

BitMap稀疏时内存浪费，但Roaring能够弥补缺点

✔️ 哈希映射压缩空间，适合稀疏数据

典型操作

SETBIT、GETBIT、BITCOUNT

BF.ADD（添加）、BF.EXISTS（检查存在性）

实现复杂度

简单（直接位操作）

中等（需处理多个哈希函数和误判率计算）

通过对比发现基本上完胜，安装Roaring Bitmap，在 GitHub 上，有一个集成了 Roaring Bitmap 的 Docker 容器，访问地址：https://github.com/aviggiano/redis-roaring