异常教程

Redis HyperLogLog（长文解析）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言：从“数人头”说起

想象这样一个场景：你正在组织一场万人演唱会，需要统计入场观众的数量。如果采用最原始的方法——让工作人员逐个记录每个人的信息，这显然会消耗大量人力和存储资源。但如果只需要估算观众的“基数”（即不同观众的数量），而不要求精确到每一位，那么或许可以用更高效的方式：例如随机选取几个区域，根据这些区域的观众分布推断全场总数。

Redis HyperLogLog 正是基于类似的思想，它能在极小的内存开销下，对海量数据的基数进行近似统计。这对于需要处理高并发、大规模数据的场景（如统计独立用户访问量、去重计数等）而言，是一种革命性的解决方案。

本文将从基础概念、工作原理、实际案例、代码示例等角度，深入浅出地解析 Redis HyperLogLog 的核心机制，并探讨其在工程实践中的应用价值。

HyperLogLog 的核心概念：基数估计与近似算法

1. 什么是基数（Cardinality）？

在数学中，集合的基数表示集合中不同元素的数量。例如，集合 {1, 2, 3, 3, 5} 的基数是 4，因为去重后只剩 4 个元素。在实际应用中，计算基数的需求无处不在：

  • 统计网站某天的独立访客数量
  • 分析某个产品在不同地区的用户覆盖范围
  • 监控日志中出现的唯一错误代码数量

然而，当数据规模达到亿级甚至更大时，直接存储所有元素进行去重会消耗大量内存。例如，若需统计 1 亿个唯一 IP 地址，即使每个 IP 用 4 字节存储，也需要约 380 MB 的空间。

2. 近似算法的必要性

为解决这一问题，计算机科学家提出了 基数估计近似算法，HyperLogLog 是其中最具代表性的一种。这类算法通过牺牲极小的精确性（通常误差率 < 1%），换取内存占用量的指数级降低。

例如，HyperLogLog 在误差率 0.5% 的情况下，仅需约 12 KB 内存 就能估算百亿级数据的基数！

HyperLogLog 的工作原理：从哈希到概率推断

1. 核心思想：利用哈希和随机性

HyperLogLog 的设计基于一个关键观察：

若将数据经过哈希处理后，某些特定模式的出现概率与数据基数密切相关。

具体来说，假设我们对每个元素执行哈希操作，得到一个二进制字符串。若某元素的哈希值在二进制形式中存在连续的前导零（例如 00001011...），则连续零的位数越长，该元素在数据集中出现的概率越低。

通过统计所有元素的哈希值中“最长连续前导零”的位数，可以推断原始数据的基数。例如，若发现某元素的哈希值有连续 20 个前导零，则说明该元素在数据集中非常“稀有”，数据基数可能较大。

2. 具体实现步骤

HyperLogLog 的实现可分为以下步骤：

步骤一：哈希处理

对每个输入元素执行哈希函数（如 MurmurHash3），生成固定长度的二进制字符串。这一步确保不同元素的哈希值分布均匀。

步骤二：分割数据流

将哈希后的二进制字符串分为两部分：

  • 前 m 位：用于决定该元素被分配到的“观测桶”（Register）的索引。例如，若 m = 8，则有 2^8 = 256 个桶。
  • 剩余位：用于计算该元素的“观测值”（即连续前导零的位数）。

步骤三：记录最大观测值

每个观测桶记录其对应元素中最大的连续前导零位数。例如，若某桶中所有元素的哈希值的最大连续零位数为 5，则该桶的值为 5。

步骤四：组合估算

通过所有桶的最大值，应用特定的数学公式（如线性计数器修正）计算最终的基数估计值。

3. 精度与内存的权衡

HyperLogLog 的内存占用与桶的数量（m）成正比。例如：
| 桶数量（m） | 内存占用（约） | 误差率（标准差） |
|-------------|----------------|-----------------|
| 16 | 1 KB | ± 4.8% |
| 256 | 2 KB | ± 1.4% |
| 1024 | 8 KB | ± 0.43% |

通过调整 m 的值，开发者可以在精度和内存之间找到平衡点。

HyperLogLog 的典型应用场景

1. 网站独立访客统计

假设某电商平台需要统计“双十一”期间独立访问用户数。若直接存储每个用户的唯一标识（如 IP+设备号），可能占用数 GB 的内存。而使用 HyperLogLog：

  • 内存消耗仅需约 12 KB（误差率 0.5%）
  • 可实时合并多个服务器的统计结果（通过 PFCOUNT 命令）

2. 实时监控与去重计数

在日志系统中，若需统计某小时内出现的唯一错误代码数量，HyperLogLog 可以在保证低延迟的同时，避免因存储全部错误代码导致的内存爆炸。

3. 社交网络分析

例如，计算某个话题在社交平台上的独立讨论人数，或分析用户兴趣标签的覆盖范围。

使用 Redis HyperLogLog 的实战案例

1. Redis 命令与基本操作

Redis 通过以下命令支持 HyperLogLog：

  • PFADD key element [element ...]：向 HyperLogLog 中添加元素
  • PFCOUNT key [key ...]：获取单个或多个 HyperLogLog 的基数估计值
  • PFMERGE destkey sourcekey [sourcekey ...]：合并多个 HyperLogLog

示例：统计独立访客

import redis  

client = redis.Redis(host='localhost', port=6379, db=0)  

client.pfadd('unique_visitors', 'user123')  
client.pfadd('unique_visitors', 'user456')  
client.pfadd('unique_visitors', 'user123')  # 重复元素不影响结果  

estimated_count = client.pfcount('unique_visitors')  
print(f"Estimated unique visitors: {estimated_count}")

2. 合并多个 HyperLogLog 实例

在分布式系统中，不同服务器可能各自维护一个 HyperLogLog 实例。通过 PFMERGE 可快速合并结果：

client.pfmerge('total_visitors', 'server1_visitors', 'server2_visitors')  
total = client.pfcount('total_visitors')  
print(f"Total estimated visitors across servers: {total}")

HyperLogLog 的性能优势与局限性

1. 优势对比

对比其他基数统计方法（如位图、布隆过滤器），HyperLogLog 在以下方面表现突出：
| 方法 | 内存占用 | 精度可控性 | 支持合并操作 |
|---------------------|-------------------|------------|--------------|
| 位图（Bitmap） | O(N)（N为基数） | 精确 | 否 |
| 布隆过滤器 | O(N)（需额外存储）| 不直接支持 | 否 |
| HyperLogLog | O(1)（固定内存） | 可调节 | 是 |

2. 局限性与适用场景

  • 误差范围：无法完全消除误差，需根据业务需求选择合适的 m 值。
  • 不可逆操作：合并后的 HyperLogLog 无法还原原始数据。
  • 适用场景：适合基数较大（>1000）的场景，小数据集的误差可能较高。

HyperLogLog 的进阶优化与扩展

1. 海量数据的分布式处理

在跨服务器的场景中，可通过以下步骤实现高效统计：

  1. 每个服务器维护一个本地 HyperLogLog 实例，统计局部数据。
  2. 定期将本地实例合并到中心服务器的 HyperLogLog 中。
  3. 使用 PFCOUNT 快速获取全局统计结果。

2. 误差修正与算法改进

Redis 的 HyperLogLog 实现基于 Google 的改进版算法（HLL++），通过以下方式优化精度：

  • 线性计数器：当数据量较小时，直接记录精确值而非近似值。
  • 偏移校正：对极端值（如全零桶）进行特殊处理，减少误差。

结论：HyperLogLog 的工程价值与实践建议

Redis HyperLogLog 通过巧妙的数学设计，将基数统计的内存占用压缩到极致，同时保持高效的写入和查询性能。对于需要处理海量数据去重计数的场景（如用户行为分析、日志监控），它是一种不可多得的轻量级工具。

在实际应用中，开发者需注意以下几点：

  1. 根据业务需求选择合适的误差率和内存配置（例如，通过 redis.conf 中的 hll-sparse-max-bytes 参数）。
  2. 对于小规模数据（如 <1000），可考虑直接使用集合（SET）结构以获得精确结果。
  3. 充分利用 Redis 的 PFMERGE 命令，实现分布式环境下的高效聚合。

掌握 HyperLogLog 的原理与应用，不仅能帮助开发者解决特定场景的性能瓶颈，更能培养对近似算法和概率统计在工程领域价值的深刻理解。

通过本文的解析，希望读者能够理解 Redis HyperLogLog 的核心思想，并在实际项目中灵活运用这一强大的数据结构。

最新发布

查看更多文章