1. 核心概念

在海量数据处理中，数据去重（Deduplication）是一个常见需求，例如统计网站 UV（独立访客）、爬虫 URL 去重、防止垃圾邮件等。Redis 提供了多种数据结构来支持不同场景下的去重需求。

2. 常见方案与原理

2.1 基于 Set（集合）

  • 原理：Redis 的 Set 数据结构天然支持去重，它存储不重复的字符串元素。
  • 适用场景：数据量较小，需要精确去重，且需要存储原始数据。
  • 缺点：内存占用大。如果存储 1 亿个用户 ID，内存消耗巨大。

2.2 基于 Bitmap（位图）

  • 原理：利用 String 类型的 Bit 操作。将数据映射为一个整数偏移量（Offset），将对应位设置为 1。
  • 适用场景：数据是连续整数（如自增 User ID），或者可以通过算法映射为整数。
  • 优势：极度节省空间。1 亿个用户仅需约 12MB 内存（$10^8 / 8 / 1024 / 1024$）。
  • 缺点：不适合稀疏数据（如 ID 为 1 和 100亿，中间会浪费大量 0 位）。

2.3 基于 HyperLogLog（概率计数）

  • 原理：基于概率统计的基数估计算法。它不存储具体数据，只维护基数估值。
  • 适用场景：海量数据统计 UV，允许极小误差（标准误差约 0.81%）。
  • 优势：内存占用极小且固定（约 12KB 即可统计 $2^{64}$ 个不同元素）。
  • 缺点：无法取出原始数据，结果是近似值。

2.4 基于 Bloom Filter（布隆过滤器）

  • 原理：使用多个 Hash 函数将数据映射到 Bitmap 的不同位置。
    • 判断存在：如果所有映射位都为 1，则“可能存在”。
    • 判断不存在：只要有一个映射位为 0，则“一定不存在”。
  • 适用场景：海量数据去重（如爬虫 URL、垃圾短信过滤、缓存穿透保护）。
  • 优势：空间效率极高，查询速度快。
  • 缺点：存在误判率（False Positive，即没存过但判为存在），且默认不支持删除。
  • 实现：Redis 4.0+ 可通过 RedisBloom 模块支持，或使用 Redisson 客户端实现。

3. 方案对比与选择

方案 精确性 空间占用 是否存储原数据 典型场景
Set 精确 高 是 小规模标签、好友列表
Bitmap 精确 极低 (连续整数) 否 (仅状态) 签到、连续 ID 统计
HyperLogLog 近似 (0.81% 误差) 极低 (固定 12KB) 否 亿级 UV 统计
Bloom Filter 存在误判 低 否 爬虫去重、缓存穿透

4. 总结

选择哪种方案取决于对 精确度 和 内存空间 的权衡。

面试回答示例：

“在 Redis 中实现去重主要有四种方式：

  1. Set：最简单，适合数据量小且需要存储原值的精确去重。
  2. Bitmap：适合整数型 ID 的精确去重，空间利用率极高（如用户签到）。
  3. HyperLogLog：适合超大规模的基数统计（如网站 UV），空间极小（12KB），但有约 0.81% 的误差。
  4. 布隆过滤器：适合海量数据的存在性判断（如防止缓存穿透），空间小效率高，但存在一定的误判率（可能误报存在，但绝不会漏报不存在）。”