HOOOS

亿级DAU统计难题？Redis HyperLogLog如何用12KB内存轻松搞定

0 171 内存斤斤计较工程师 RedisHyperLogLog基数统计
Apple

场景痛点：海量用户活跃统计，内存告急！

想象一下，你的应用拥有上亿甚至几十亿的用户，每天需要统计有多少不同的用户登录或活跃（DAU - Daily Active Users）。最直观的想法是什么？

可能很多人会想到用 Redis 的 Set 数据结构。来一个用户ID，就 SADD 到当天的 Set 里，最后用 SCARD 获取集合大小。简单粗暴，精确无误。

但问题来了：

  1. 内存爆炸： 每个用户ID（假设是 64 位整数或较长字符串）都要存储。如果一天有 1 亿活跃用户，即使只存 8 字节的 long 类型 ID，也需要 100,000,000 * 8 bytes = 800,000,000 bytes ≈ 763 MB 的内存！这还只是一天的数据。一个月下来呢？内存成本扛不住啊。
  2. 数据合并困难： 想统计周活跃用户（WAU）或月活跃用户（MAU）？你需要对多个 Set 做并集运算 (SUNIONSTORE)，这又是一个内存和计算密集型的操作。

面对亿级数据，传统精确计数方法显得力不从心。有没有更节省内存的办法？

救星登场：HyperLogLog - 概率的力量

这时候，就轮到 Redis 的高级数据结构 HyperLogLog (HLL) 出场了。它不是给你一个 100% 精确的数字，而是提供一个极高概率接近真实值的基数估计 (Cardinality Estimation)。

什么是基数？ 就是一个集合中不重复元素的数量。DAU 就是统计一天内不重复的用户ID数量。

HyperLogLog 的核心思想（简化版）：

我们不是要深入到论文级别的数学证明，尝试用个稍微形象点的比喻理解下。想象一下你不停地抛硬币，记录每次抛到正面朝上时，前面连续出现了多少次反面。比如 反正正，记录1；反反正，记录2；正，记录0。如果你抛了很多很多次，记录到的最大连续反面次数（比如是5次，意味着出现了 反反反反反正），这个“最大连续反面次数”的大小，其实能间接反映出你总共抛了多少次硬币。次数越多，出现长连续反面的概率就越大。

HyperLogLog 玩的就是类似的概率游戏，但更精妙：

  1. 哈希： 当一个新元素（比如用户ID user123）加入 HLL 时，HLL 先对它进行哈希，得到一个很长的二进制数（比如 64 位）。这步是为了让元素均匀分布。
  2. 分桶 (Registers)： HLL 内部维护了固定数量（Redis 中是 16384 个，即 2^14）的小桶（称为 registers）。怎么决定元素落入哪个桶？就用哈希值的前 14 位二进制数来当做桶的编号（0 到 16383）。
  3. 数前导零 (Leading Zeros)： 取哈希值的剩下部分（64 - 14 = 50 位），计算这部分二进制表示下从左开始连续有多少个 0。例如，00010101... 的前导零计数是 3。这个计数值，可以粗略理解为我们前面抛硬币例子里的“连续反面次数”。
  4. 记录最大值： 每个桶（总共16384个）只记录一件事：所有曾经落入该桶的元素中，其哈希值剩余部分算出来的最大前导零计数值。如果新来的元素算出的前导零计数大于桶里当前记录的值，就更新它；否则就不动。
  5. 估计： 最后，PFCOUNT 命令怎么估算总数的？它会查看所有 16384 个桶里记录的那些“最大前导零计数值”，然后用一个有点复杂的数学魔法（涉及调和平均数，主要是为了排除一些极端值的影响，让结果更稳定）来估计出整个集合大概有多少个不同的元素。

为啥这样能行？ 直观感觉就是，如果集合里的元素非常多，经过哈希后，总会有一些元素的哈希值落在某个桶里，并且其剩余部分的二进制恰好是 000...01xxxx 这种前面有很多 0 的形式。某个桶记录到的最大前导零数越大，就越暗示着可能有非常多的不同元素被添加过。HLL 通过观察这 16384 个桶的整体情况，综合出一个概率上最靠谱的估计值。

HLL 的惊人优势：内存与精度

  • 内存占用： 这是 HLL 最亮眼的地方。不管你往里面塞 1 百万、1 亿还是 100 亿个不同的用户 ID，它在 Redis 里占用的内存始终是固定的，大约 12KB！

    • 这 12KB 怎么来的？Redis 用 16384 (2^14) 个桶。每个桶需要记录那个“最大前导零计数”。一个 64 位哈希值，前导零最多可能有 64 个（虽然概率极小），需要用 6 个 bit 就能表示 0 到 63 这 64 个可能的值 (2^6 = 64)。所以，总共需要的存储空间大约是 16384 个桶 * 6 bits/桶 = 98304 bits。换算成字节就是 98304 / 8 = 12288 bytes，正好是 12KB。Redis 的实际实现可能会用一些压缩技巧，但量级就在这里，非常稳定。
    • 再对比一下 Set：1 亿用户要 763MB，HLL 只要 12KB！内存效率简直是降维打击，提升了成千上万倍！

  • 精度： 这么小的内存，代价是什么？就是结果不是绝对精确的。Redis 实现的 HLL，它的标准误差率 (Standard Error) 是 0.81%。

    • 这 0.81% 是什么概念？假设真实 DAU 是 1,000,000。那么 HLL 给出的估计值：
      • 有大约 68% 的概率，落在 1,000,000 ± 1 * 0.81% * 1,000,000，也就是 [991900, 1008100] 这个区间。
      • 有大约 95% 的概率，落在 1,000,000 ± 2 * 0.81% * 1,000,000，也就是 [983800, 1016200] 这个区间。
      • 有大约 99.7% 的概率，落在 1,000,000 ± 3 * 0.81% * 1,000,000，也就是 [975700, 1024300] 这个区间。
    • 你看，虽然不是百分百准，但误差基本控制在 1% 上下。对于绝大多数需要基数统计的场景，比如看网站 UV (Unique Visitors)、统计 DAU 趋势、广告触达人数等，这点误差完全可以接受。老板想看的是数量级和变化趋势，是百万级还是千万级？是增长了 10% 还是下跌了 5%？HLL 给出的估计值足够支撑这些判断。

Redis HLL 实战：PFADD, PFCOUNT, PFMERGE

Redis 操作 HyperLogLog 就靠这仨命令，非常简单：

  1. PFADD key element [element ...]

    • 作用：把一个或多个 element 添加到名叫 key 的 HyperLogLog 结构里。
    • 返回值：如果这次添加操作导致 HyperLogLog 内部至少一个桶的计数值发生更新了（比如某个桶的最大前导零数变大了），就返回 1；如果没引起任何更新（比如这个元素之前加过了，或者加了但没能更新任何桶的最大计数值），就返回 0。
    • 注意： 返回 1 或 0，不代表这个 element 是不是第一次加进来！只表示 HLL 内部存储有没有“变动”。
    • 例子：记录 2023 年 10 月 26 日的用户活跃
      # user123 今天第一次活跃
PFADD dau:2023-10-26 user123
# (integer) 1  (假设这次添加更新了 HLL 内部状态)

# user123 又操作了一下，再次记录
PFADD dau:2023-10-26 user123
# (integer) 0  (user123 对应的 HLL 内部信息没变，所以返回 0)

# 同时记录好几个用户活跃
PFADD dau:2023-10-26 user456 user789 userABC
# (integer) 1  (假设这几个用户里至少有一个导致了 HLL 更新)
    • 核心用法： 对于 DAU 统计，你只需要在用户每次活跃时（比如每次 API 请求、每次登录成功），把他的用户 ID 用 PFADD 加到当天的 HLL key（比如 dau:YYYY-MM-DD）里。重复加同一个用户 ID？没关系，HLL 内部会自动处理，不会重复计算基数。

  2. PFCOUNT key [key ...]

    • 作用：获取一个或多个 HyperLogLog 的基数估计值。
      • 只给一个 key：返回这个 HLL 的估计大小。
      • 给多个 key：Redis 会在内部临时合并这几个 HLL（想象一下把它们的 16384 个桶对应合并，取最大值），然后返回这个合并后的整体的基数估计值。这个过程不会创建或修改任何持久化的 HLL key。
    • 返回值：一个整数，就是估计的基数。
    • 例子：
      # 获取 2023-10-26 的 DAU 估计值
PFCOUNT dau:2023-10-26
# (integer) 998500  (这只是个例子，表示估计有 99.85 万)

# 想看看 26 号和 27 号这两天，总共有多少不同的用户活跃过？
# 假设 dau:2023-10-27 单独 PFCOUNT 是 1010000
PFCOUNT dau:2023-10-26 dau:2023-10-27
# (integer) 1503000 (这个数小于 998500 + 1010000，因为 PFCOUNT 自动去重了)
    • 核心用法： 查询某一天的 DAU，或者临时查询某几天加起来的总活跃用户数（已去重）。记住，结果是估计值！

  3. PFMERGE destkey sourcekey [sourcekey ...]

    • 作用：这个厉害了！把一个或多个 sourcekey（源 HLL）的数据合并到 destkey（目标 HLL）里。如果 destkey 不存在，会自动创建。合并的逻辑是：对于 16384 个桶中的每一个，都取所有 sourcekey 对应桶的值中的最大值，存到 destkey 的对应桶里。
    • 返回值：OK
    • 例子：计算 2023 年第 43 周（假设是 10 月 23 日到 29 日）的周活跃用户 (WAU)
      # 先把这一周每天的 DAU 数据合并到一个新的 key 'wau:2023-W43' 里
PFMERGE wau:2023-W43 dau:2023-10-23 dau:2023-10-24 dau:2023-10-25 dau:2023-10-26 dau:2023-10-27 dau:2023-10-28 dau:2023-10-29
# OK

# 合并完成后，查询这个 WAU 的估计值
PFCOUNT wau:2023-W43
# (integer) 5210800 (举例，表示这一周总共有约 521 万不同用户活跃过)
    • 核心用法： 计算 WAU、MAU（月活跃用户）、或者任何跨时间段的去重用户数统计。PFMERGE 是实现这些需求的关键！合并产生的新 HLL (wau:2023-W43) 同样只占用约 12KB 内存，不管它合并了多少天的 HLL 数据。

性能考量

这些命令快不快？非常快！

  • PFADD: 基本上是 O(1) 的常数时间复杂度。哈希一下，找到桶，比较更新一个 6 bit 的数，这能有多慢？跟集合里有多少元素几乎无关。
  • PFCOUNT: 对于单个 HLL，也是 O(1)。虽然内部要遍历 16384 个桶做计算，但这个计算量是恒定的，不随基数大小变化。对于多个 HLL 的 PFCOUNT，需要做临时的合并，复杂度大概是 O(HLL数量 * 16384)，但因为桶操作非常快，实际耗时也很短。
  • PFMERGE: 这个相对会慢一点，因为它要把所有源 HLL 的 16384 个桶都遍历一遍，进行比较和写入目标 HLL。复杂度也是 O(源HLL数量 * 16384)。不过，即使是合并一个月 30 天的 HLL 来算 MAU，这个操作通常也就在毫秒级别，对于后台定时任务来说完全不是问题。

总结就是，HLL 相关操作的性能极好，特别是在你要处理的元素数量巨大时，相比 Set 那种会随着元素增多而变慢的操作（如 SADD O(1)，SCARD O(1) 但内存 O(N)，SUNIONSTORE O(N) 且 N 是所有集合总大小），HLL 的性能优势非常明显。

实践中的小建议

  1. Key 命名规范： 一定要设计好 Key 的名字，方便管理和查询。用业务和时间维度组合是个好办法，比如 dau:productA:2023-10-26，mau:productB:2023-10。
  2. 误差知情： 和用这个数据的同学、老板沟通好，让他们知道这个数字是有误差的，误差范围大概是多少（标准误差 0.81%）。避免因为误解产生问题。如果业务场景要求 100% 精确（比如金融对账），那 HLL 就不合适了。
  3. 只能计数，不能取样： HLL 只告诉你“大概有多少个”，但它不能告诉你“具体是哪些”。如果你需要拿到具体的活跃用户 ID 列表，那还得用 Set 或者其他方式存。
  4. 添加什么元素？ 通常就是用户的唯一标识符，比如 User ID。只要保证同一个用户始终用同一个 ID 去 PFADD 就行。

总结：HyperLogLog 香在哪里？

如果你碰到下面这些情况，别犹豫，Redis HyperLogLog 很可能就是你的菜：

  • 你想知道一个超级大的集合里，到底有多少不重复的东西？（基数统计）
  • 你对内存特别抠门，Set 那种跟着元素数量线性增长的内存消耗你顶不住。
  • 你能接受结果里带一点点误差（比如 1% 左右），不追求绝对精确。
  • 你不需要知道具体有哪些元素，只要个总数就行。
  • 你还需要经常把不同时间段、不同分组的数据合在一起看总数（并集计算），还要自动去重。

对于像亿级 DAU 统计这种典型的“大数据去重计数”问题，HyperLogLog 用它那惊人的内存效率（万年 12KB）和足够好的准确度（0.81% 误差），提供了一个近乎完美的工程解决方案。它完美体现了计算机科学里用概率和近似来换取资源（空间、时间）的思想。下次再为大数据计数烦恼时，试试 HLL 吧，真的香！

点评评价

captcha
健康