1. 从“数不清”到“估得准”为什么我们需要HyperLogLog在数据爆炸的时代我们每天都在和“计数”打交道。无论是统计一个热门话题的独立阅读用户数还是监控一个大型网站每天的独立访客UV核心问题都是如何在海量数据流中快速、准确地统计不重复元素的个数最直观的想法是用一个集合比如HashSet把所有元素都存起来最后数一下集合的大小。这个方法绝对精确但代价巨大。想象一下你要统计过去一个月内访问你网站的独立IP地址假设每天有1亿次访问其中包含大量重复IP。一个月下来你需要存储的独立IP数量可能高达数千万甚至上亿个。这需要消耗海量的内存每个IP地址假设15字节1亿个就是1.5GB对于实时统计或内存受限的系统如Redis这样的内存数据库来说这几乎是不可接受的。于是我们需要一种“差不多就行”的算法用极小的空间代价换来一个可接受的误差范围内的估计值。这就是基数估计Cardinality Estimation算法的用武之地。而HyperLogLog简称HLL正是这个领域里最著名、应用最广泛的算法之一。它由Philippe Flajolet等人在2007年提出其核心思想可以用一句话概括通过观察数据哈希值的随机分布模式来推测原始数据集的规模。它的魔力在于无论你要统计1万个还是10亿个不重复元素HyperLogLog所需的内存空间几乎是恒定的。在标准误差约0.81%的实现中它只需要大约12KB的内存。用12KB去估算十亿量级的基数这种“四两拨千斤”的能力使其成为大数据场景下基数统计的事实标准。接下来我们就剥开这12KB的神秘面纱看看它到底是如何工作的。2. 抛硬币与观察河流HyperLogLog的直觉来源要理解HyperLogLog我们先从两个更简单的思想实验开始它们构成了HLL的理论基石。2.1 抛硬币与首次正面朝上假设你遇到一个神秘人他声称自己有一枚均匀的硬币并且已经连续抛了若干次。你只被允许问他一个问题来推断他抛了多少次。你会问什么一个聪明的问题是“你第一次抛出正面朝上是在第几次”记这个次数为k。如果他说k1第一次就是正面那么我们很难判断他只抛了1次还是很多次因为第一次就出现正面的概率是1/2。但如果他说k4前三次都是反面第四次才是正面那么我们可以相当肯定他抛硬币的次数不会太少。因为连续抛出3次反面的概率是 (1/2)^3 1/8这意味着在平均意义上你需要进行8组“尝试”才能观察到一次这样的事件。所以抛掷次数的一个粗略估计是 2^k。在这个例子中我们通过观察一个随机过程抛硬币中某个特定模式首次出现正面的位置反向估计了实验的次数。HyperLogLog的核心观察与此类似只不过它用“抛硬币”变成了“计算哈希值前导零的个数”。2.2 观察河流中的最大鱼另一个比喻是估计一条河流中鱼的总数。一个费时费力的方法是把所有的鱼都捞起来数一遍。一个聪明的近似方法是我们只在河里随机捕捞然后记录下抓到的最大的那条鱼的尺寸。直觉是如果鱼的总数很多那么你更有可能抓到一条非常大的鱼如果鱼的总数很少那么你抓到超大鱼的概率就很低。通过“观测到的最大尺寸”这个信息我们可以反过来估算鱼群的总规模。在HyperLogLog中“鱼的尺寸”对应的是哈希值二进制表示中“前导零的数量”。这两个思想实验共同指向了HyperLogLog算法的灵魂利用随机化哈希函数将输入数据均匀打散然后通过观测这个随机序列的极端统计量如最大值来推断原始集合的大小。3. 从比特串到估计值算法核心原理拆解现在我们把直觉转化为具体的算法步骤。整个过程可以看作一个“哈希-观察-聚合”的流水线。3.1 第一步哈希化与比特串观察首先我们需要一个均匀的哈希函数将任意输入元素如用户ID、IP地址映射为一个固定长度的比特串例如64位。这个哈希函数的质量至关重要它必须保证输出尽可能像随机数一样均匀分布。对于每一个输入元素我们计算其哈希值得到一个像010110...101这样的二进制串。HyperLogLog关注的是这个串开头连续零的个数Leading Zeros。例如哈希值001010...前导零个数 2哈希值100110...前导零个数 0哈希值000001...前导零个数 5为什么观察前导零因为在一个均匀随机的比特串中前导零出现的概率是符合几何分布的第一位是1的概率1/2 (对应ρ1)前一位是0接着一位是1的概率1/4 (对应ρ2)前k位是0第k1位是1的概率1/2^(k1) (对应ρk1)这里我们定义ρ为第一个“1”出现的位置从1开始计数。所以ρ的期望值与基数有关。如果基数很小我们很难看到ρ很大的情况就像很难在抛几次硬币后就看到连续很多个反面。如果基数很大在众多哈希值中就很有可能出现一个ρ非常大的“极端值”就像在很多人里很可能有一个生日非常特殊的人。因此对于整个数据集我们维护一个变量所有元素哈希值中ρ的最大值记为max(ρ)。根据“观察最大鱼”的直觉这个max(ρ)包含了关于集合大小的信息。3.2 第二步分桶平均与调和平均数然而直接使用max(ρ)进行估计的方差会很大不稳定。比如仅仅因为一个元素的哈希值非常“特殊”有很多前导零就会严重高估基数。为了平滑这种偶然性HyperLogLog引入了分桶Bucketing的思想。具体做法是取哈希值的前p个比特作为桶索引bucket index。这样我们就有了m 2^p个桶。例如p14则有16384个桶。剩下的比特位如64-1450位用来计算ρ第一个“1”出现的位置注意是在剩下的50位里计算。每个桶只记录落入该桶的所有元素哈希值中ρ的最大值。这样我们就把全局的一个max(ρ)分散到了m个桶的max(ρ)上。由于哈希的均匀性数据被随机地分配到这m个桶中。每个桶平均会负责n/m个元素n为真实基数。接下来我们如何从这m个桶的值记为M[1], M[2], ..., M[m]来估计总数n呢一个朴素的想法是求每个桶估计值的平均数。每个桶的基数估计值大约是2^(M[i])。但算术平均数对离群值极大值非常敏感这又回到了最初的问题。HyperLogLog的精妙之处在于它使用了调和平均数Harmonic Mean。调和平均数对大的离群值不敏感而对小的值更敏感这正好适合我们这里的情况我们担心的是个别桶的极大值导致高估。最终的估计公式为E α_m * m^2 * (∑_{j1}^{m} 2^{-M[j]})^{-1}其中E是估计的基数。m是桶的数量。α_m是一个修正常数用于修正系统偏差其计算公式为α_m (m * ∫_0^∞ (log_2((2u)/(1u)))^m du)^{-1}。对于常用的m值这个常数是预先计算好的如 m16384 时α≈0.7213/(11.079/m) ≈ 0.7213。M[j]是第j个桶中记录的ρ最大值。(∑ 2^{-M[j]})^{-1}就是调和平均数的核心部分。为什么是调和平均数可以从统计学的角度理解在“抛硬币”模型中每个桶的估计值2^M[j]服从一个重尾分布。调和平均数能够有效地降低这个分布的方差从而得到一个更稳定、偏差更小的估计量。这是HyperLogLog相比前身LogLog算法使用算术平均数的主要改进。3.3 第三步修正与最终结果通过调和平均数公式得到初始估计值E后算法还没有结束。为了应对各种边界情况还需要进行修正小范围修正Small Range Correction当估计值E小于(5/2) * m时算法可能因为存在空桶而偏差较大。此时会采用线性计数Linear Counting的方法进行修正。线性计数就是统计有多少个桶是非空的V 空桶数然后用m * log(m/V)来估计。这是一个更简单但在基数较小时更准确的方法。大范围修正Large Range Correction当估计值E非常大接近 2^32 / 30 等阈值时算法也会进行一个简单的乘法修正以降低偏差。整数化最后输出一个整型估计值。经过这一系列步骤——哈希、分桶、记录最大值、调和平均、修正——HyperLogLog就完成了从极小的内存状态m个桶每个桶存一个很小的整数M[j]到一个接近真实基数的估计值的魔法。4. 误差、内存与常数理解HyperLogLog的性能边界理解了原理我们再来看看它的性能指标这决定了我们能在什么场景下放心使用它。4.1 标准误差Standard ErrorHyperLogLog估计值的相对标准误差大约为1.04 / sqrt(m)。其中m是桶的数量。当m2048 (p11)时误差约为1.04 / sqrt(2048) ≈ 2.3%。当m16384 (p14)时误差约为1.04 / sqrt(16384) ≈ 0.81%。当m65536 (p16)时误差约为0.41%。这意味着如果你用p14的HLL去估计一个真实值为1亿的基数你得到的结果大概在9919万到1.0081亿之间波动以约68%的概率。对于绝大多数需要“宏观趋势”而非“精确计数”的场景如UV统计、热门查询去重这个精度已经完全足够。4.2 内存消耗这是HyperLogLog最吸引人的地方。每个桶只需要存储一个ρ的最大值。ρ的范围是多少呢如果我们用64位哈希去掉p位做桶索引剩下64-p位。ρ的最大可能值就是64-p1当剩下所有位都是0时。实际上ρ的值通常很小。对于p14ρ最大为64-14151。存储数字51只需要6个比特2^664 51。因此每个桶理论上只需要6个比特。m16384个桶总共需要16384 * 6 bit 12 KB。在实际实现中如Redis为了方便通常用一个字节8比特来存储每个桶的值因此p14时内存占用为16KB。即便如此16KB对于十亿级基数的估计来说也是微不足道的成本。4.3 神奇的常数α_m公式中的α_m是一个基于积分计算出来的修正因子。它的作用是校正因为使用调和平均数而引入的系统性偏差。这个常数不是凭空想象的而是通过概率分析和蒙特卡洛模拟推导、验证出来的。对于常用的m值我们可以直接查表使用m16-α≈0.673m32-α≈0.697m64-α≈0.709m128-α≈0.7213/(11.079/m)在代码实现中我们通常会预先计算好这个常数表。5. 动手实现一个简化版的HyperLogLog理论可能有些抽象我们通过一个极度简化的Python示例来串联整个流程。这个示例省略了哈希函数、小数据修正等细节专注于展示核心逻辑。import hashlib import math class SimpleHyperLogLog: def __init__(self, p14): 初始化一个简化版HyperLogLog :param p: 用于分桶的比特数桶数 m 2^p self.p p self.m 1 p # 桶的数量2^p self.registers [0] * self.m # 寄存器数组每个桶存rho的最大值 # 简化起见使用一个固定的alpha常数对应较大的m self.alpha 0.7213 / (1.0 1.079 / self.m) def _hash(self, element): 将元素转换为一个整数哈希值模拟64位哈希 # 使用MD5并取部分字节仅用于演示 hash_obj hashlib.md5(str(element).encode(utf-8)) hash_hex hash_obj.hexdigest() # 取前16个字符64位转换为整数 return int(hash_hex[:16], 16) def _rho(self, w): 计算w的二进制表示中第一个1出现的位置从1开始计数 if w 0: # 理论上不会发生因为哈希值均匀分布但做保护 return 65 # 假设最大位宽1 # 找到最低位的1的位置。例如 w8 (0b1000)则 rho4 return (w -w).bit_length() def add(self, element): 向HyperLogLog中添加一个元素 x self._hash(element) # 1. 确定桶索引取前p个比特 index x (64 - self.p) # 假设哈希是64位 # 2. 计算rho在剩下的比特中找第一个1 w x ((1 (64 - self.p)) - 1) # 掩码获取后(64-p)位 rho self._rho(w) # 3. 更新对应桶的寄存器值取最大值 if rho self.registers[index]: self.registers[index] rho def count(self): 估算当前基数 # 计算调和平均数的倒数部分 sum_inverse 0.0 empty_registers 0 for val in self.registers: sum_inverse 2.0 ** (-val) if val 0: empty_registers 1 # 原始估计值 estimate self.alpha * (self.m ** 2) / sum_inverse # 简化版的小数据修正线性计数 if estimate (5.0 / 2.0) * self.m: if empty_registers 0: estimate self.m * math.log(self.m / empty_registers) # 这里省略了超大数据的修正 return int(estimate) # 简单测试 if __name__ __main__: hll SimpleHyperLogLog(p10) # 1024个桶误差约3.2% test_data [fuser_{i} for i in range(5000)] for item in test_data: hll.add(item) print(f真实基数: {len(set(test_data))}) # 5000 print(fHLL估计基数: {hll.count()})运行这段代码你会发现估计值在真实值5000附近波动。增加p桶数或测试数据量可以观察估计精度的变化。这个简化实现清晰地展示了分桶、记录ρ最大值、调和平均这三个核心步骤。6. 实战中的HyperLogLog以Redis为例理论实现有助于理解但在生产环境中我们几乎不会自己从头实现HyperLogLog而是直接使用现成的、经过高度优化的组件。其中最著名的就是Redis的PFADD、PFCOUNT和PFMERGE命令。6.1 Redis HLL的API与使用Redis 从 2.8.9 版本开始内置了HyperLogLog数据结构。PFADD key element [element ...]: 向指定的HLL键中添加一个或多个元素。添加成功返回1否则返回0。 PFADD daily:uv user_001 user_002 user_001 (integer) 1 # 至少有一个新元素被添加PFCOUNT key [key ...]: 返回给定一个或多个HLL的基数估算值。当指定多个key时返回的是它们并集的基数估算值。 PFADD day1 user_001 user_002 PFADD day2 user_002 user_003 PFCOUNT day1 day2 (integer) 3 # 估算 {user_001, user_002, user_003} 的数量PFMERGE destkey sourcekey [sourcekey ...]: 将多个HLL合并取并集到一个新的HLL中。这个操作是幂等的且非常高效。 PFMERGE week:uv day1 day2 day3 day4 day5 day6 day7 OK PFCOUNT week:uv (integer) 15000 # 估算一周的独立用户数6.2 Redis HLL的内部实现与优化Redis的HLL实现非常精妙稀疏表示Sparse Representation当基数很小时很多桶的寄存器值都是0。Redis使用一种稀疏编码来存储可能比直接使用m个字节更节省内存。只有当基数增长到一定程度后才会自动转换为稠密表示完整的m字节数组。寄存器RegisterRedis默认使用p1416384个桶每个桶寄存器占6个比特。但为了字节对齐和操作方便内部用8位1字节来存储每个寄存器因此实际占用16384 * 1 byte 16 KB。这是一个固定的、不可配置的内存开销。纠偏与修正Redis的实现完整包含了我们之前讨论的所有修正步骤小数据线性计数、中间范围标准HLL公式、大数据修正确保了在全基数范围内的准确性。6.3 经典应用场景网站UV统计假设你有一个新闻网站需要统计每篇文章、每天、每周、每月的独立访客数。传统方案的痛点如果为每篇文章的每一天都用一个SET来存储用户ID内存消耗将是灾难性的。假设有10万篇文章每篇文章平均每天有1万个独立访客ID用8字节长整型存储仅一天的数据就需要100,000 * 10,000 * 8 bytes ≈ 7.5 GB内存。HLL解决方案每日UV为每篇文章创建一个HLL键例如article:uv:{article_id}:{date}。每个用户访问时执行PFADD。每天结束时用PFCOUNT获取该文章当日的UV。每个键仅消耗约16KB。每周/每月UV无需存储原始数据。在需要时使用PFMERGE将7天或30天的HLL键合并然后PFCOUNT。例如# 计算文章1234在2023-10月整月的UV PFMERGE tmp_merge_key article:uv:1234:2023-10-01 article:uv:1234:2023-10-02 ... article:uv:1234:2023-10-31 PFCOUNT tmp_merge_key DEL tmp_merge_key # 清理临时键合并操作的时间复杂度是O(m)即与桶数成正比速度极快。内存中仅需一个额外的16KB临时键。这种方案将内存消耗从GB级降到了MB级同时查询速度极快完美解决了海量数据去重统计的难题。7. 边界、陷阱与最佳实践尽管HyperLogLog非常强大但在实际使用中仍需注意一些边界条件和潜在陷阱。7.1 误差的非对称性与置信区间HyperLogLog的误差是高斯分布的这意味着估计值可能偏高也可能偏低。在评估结果时最好使用置信区间。对于标准误差σ如0.81%大约68%的情况下估计值落在真实值的(1-σ)到(1σ)倍之间。大约95%的情况下估计值落在真实值的(1-2σ)到(12σ)倍之间。因此在报告UV数据时更专业的做法是给出一个范围例如“今日UV约为 1,250,000 ± 20,00095%置信度”这比单纯报告一个数字更能反映其概率估计的本质。7.2 哈希函数的质量是生命线HyperLogLog算法的所有理论保证都建立在“哈希函数输出均匀随机”的假设上。如果哈希函数有缺陷容易碰撞、分布不均匀那么估计结果将完全不可信。实践建议永远不要自己写一个简单的哈希函数如取模用于HLL。必须使用密码学强度或经过充分测试的、具有良好雪崩效应的哈希函数如MurmurHash3、SHA-1、MD5后两者虽然密码学上已不安全但均匀性仍很好。Redis等成熟实现内部已经使用了高质量的哈希函数这是我们直接使用它们的重要原因之一。7.3 合并Union的幂等性与精确性HyperLogLog支持无损合并这是它另一个关键特性。合并操作PFMERGE的原理很简单对于每个桶取所有待合并HLL中该桶寄存器值的最大值。因为每个HLL记录的都是自己数据集在该桶上的ρ最大值所以取所有最大值自然就得到了并集在该桶上的ρ最大值。这意味着合并是精确的合并后的HLL对并集基数的估计误差与直接用一个HLL统计全部数据时的误差相同。不会因为合并引入额外误差。合并是幂等的多次合并相同的数据结果不变。7.4 无法进行交集和差集运算这是HyperLogLog的一个主要限制。你可以轻松估算多个集合的并集大小但无法直接估算交集或差集的大小。例如你知道网站周一和周二各自的UVUV(MON),UV(TUE)以及两天总的UVUV(MON ∪ TUE)。你想知道两天都访问的用户数UV(MON ∩ TUE)。根据容斥原理|A ∩ B| |A| |B| - |A ∪ B|。但这里|A|,|B|,|A ∪ B|都是估计值用估计值做加减法结果的误差会被放大可能变得毫无意义尤其是在交集较小时甚至可能算出负数。解决方案如果必须计算交集可以考虑使用其他数据结构如布隆过滤器Bloom Filter的变种或者在某些场景下使用最小签名MinHash等算法来估算杰卡德相似度进而推算交集大小。但这通常更复杂且需要更多资源。7.5 数据更新与持久化HyperLogLog是一个“只增不减”的数据结构。你可以不断添加新元素寄存器值只会增加或不变但无法删除元素。因为它只记录了最大值信息丢失了具体是哪个元素贡献了这个最大值。在Redis中HLL作为一个键存在你可以对其设置过期时间EXPIRE或者定期将数据持久化到RDB/AOF文件中。由于它体积小持久化和加载的速度都很快。8. 超越HyperLogLog相关算法与变种HyperLogLog并非孤立的算法它属于基数估计算法家族的一员。了解它的“亲戚”有助于我们在不同场景做出更优选择。Linear Counting (线性计数)更早、更简单的算法。维护一个比特图bitmap用哈希函数将元素映射到比特位上并置1。基数估计为-m * ln(V)其中m是比特位数V是空比特位的比例。它在基数较小小于比特图大小时非常精确且空间效率高但当基数接近或超过m时误差会急剧增大。HyperLogLog在小数据范围修正时就用到了它。LogLogHyperLogLog的前身。核心思想与HLL相同但在最后聚合桶的估计值时它使用的是算术平均数。正如我们之前讨论的算术平均数对异常值敏感导致估计方差较大。HyperLogLog改用调和平均数显著降低了误差常数从约1.30/√m 降到 1.04/√m。HyperLogLog (HLL)由Google在2012年提出的改进版本主要优化包括更优的稀疏表示对小基数的内存优化比原始HLL更好。改进的偏差修正使用了更精确的、基于经验数据的修正值表减少了在小基数范围的估计偏差。64位哈希使用64位哈希函数将可计数的理论上限提高到约10^19远超原始算法的32位限制。 Google的BigQuery、Apache DataSketch等库实现的就是HLL。Adaptive Counting一种自适应算法在基数较小时使用Linear Counting较大时自动切换到LogLog/HyperLogLog试图结合两者的优点。对于绝大多数应用标准的HyperLogLog或其改进版HLL已经是最优选择。Redis的实现可以看作是HLL的一个生产级稳定版本。当你在设计一个新系统时如果面临海量数据去重统计的挑战HyperLogLog应该是你工具箱中优先考虑的方案。它用极小的空间和可控的误差换来了处理无限规模数据的能力这种权衡在当今的大数据时代显得无比珍贵。