Redis：HyperLogLog 底层原理

一、 核心数学原理从抛硬币到基数估算HyperLogLog (HLL) 的本质是用极小的内存空间通过概率统计推算出海量集合中不重复元素的个数基数Cardinality。1. 伯努利试验前导零的秘密将任意输入的数据通过哈希函数映射为一串 64 位的伪随机二进制串。可以把二进制串中的0看作硬币反面1看作正面。连续出现 1 个0前导零的概率是1/21/21/2。连续出现kkk个0的概率是1/2k1/2^k1/2k。推论如果在大量哈希值中我们观察到的最长连续前导零个数为kmaxk_{max}kmax​那么在宏观概率上我们大约处理了2kmax2^{k_{max}}2kmax​个不同的元素。这就是 HLL 估算的数学基石。2. 分桶与调和平均数消灭极大误差单纯依靠一次kmaxk_{max}kmax​的偶然性太大比如你第一次抛硬币就连续出了 10 个反面系统会误以为你抛了 1024 次。为了降低方差HLL 引入了分桶Registers将数据分散到 16384 个桶中每个桶独立记录自己遇到的最大前导零个数。估算总数时不使用简单的算术平均而是使用调和平均数Harmonic Mean。调和平均数对极值极度不敏感能有效削弱少数“运气极好的异常大值”对全局估算的干扰最终将标准误差稳定在0.81%。二、 底层数据结构披着 String 外衣的极致压缩HyperLogLog 在 Redis 中并非独立的数据类型它的物理载体完完全全是String 类型的底层实现 —— SDS简单动态字符串。1. 密集编码Dense的 12KB 奇迹在标准状态下Redis 强制划分出16384 个桶2142^{14}214。由于哈希值剩余用来计算前导零的位数为 50 位最大值为 50所以每个桶只需要6 bits就能存下2664502^6 64 50266450。16384 个桶×\times×6 bits / 8 12288 Bytes 12 KB。Redis 通过极其复杂的 C 语言位运算无视 SDS 固有的字节边界硬生生地在连续的 12KB 内存中划出了这 16384 个 6-bit 的小格子。2. 稀疏编码Sparse的按需分配为了避免一个只存了 10 个元素的 HLL 也直接占用 12KBRedis 设计了稀疏编码。它使用游程编码RLE将大段大段连续的、值为 0 的空桶压缩成几个字节的指令。当元素增多稀疏编码变得庞大或某个桶的值超过 32 时会发生不可逆的转换固化为 12KB 的密集编码。三、 存储估计过程演示以“双十一千万级日活 UV 统计”为例业务场景淘宝双十一大促需要实时统计首页的日活跃用户数UV。不能有重复不能极度消耗内存。我们使用 Redis 命令PFADD homepage_uv:20261111 user_id。步骤 1哈希打散与寻址分桶用户U_8848访问首页。系统对U_8848进行 MurmurHash64 计算得到一串二进制0110 0000 1111 ...中间省略... 0001 1011取前 14 位假设前 14 位转换为十进制是5。这就决定了该用户的特征将被放入第 5 号桶。步骤 2提取特征计算前导零看剩余的 50 位从左到右数0的个数直到遇到第一个1。假设剩余位是0001 1011...连续遇到了 3 个0。那么该元素的特征值就是3143 1 4314。步骤 3择优更新桶内厮杀系统去查看第 5 号桶当前的记录值。如果第 5 号桶原本记录的是2说明之前落入此桶的元素最多只有 2 个前导零。因为424 242系统将第 5 号桶的值更新为 4。如果第 5 号桶原本记录的是6说明之前来过特征更强的元素464 646系统什么都不做直接丢弃该数据。这就是天然去重的核心。步骤 4宏观估算PFCOUNT 查询当老板需要看大盘数据执行PFCOUNT homepage_uv:20261111时Redis 瞬间遍历底层的 12KB SDS 结构读取出 16384 个桶内的最大前导零数值。将这 16384 个数值代入调和平均数公式。经过常数修正后直接返回一个估算值例如28,543,921人。代价对比如果用传统 Set 存下这两千八百万个长整型 UID大约需要200 MB ~ 300 MB内存而 HLL 永远只占12 KB仅仅牺牲了不到 1% 的精度。