PHP实战HyperLogLog基数统计：原理、手写实现与Redis落地

这年头做Web开发，谁还没碰过UV统计的需求。本来用SELECT COUNT(DISTINCT)或者PHP的数组去重搞定就完事了，但真当用户量爬到百万、千万级，第一批撑不住的就是内存和时间。我第一次在PHP项目里做全站去重统计时，把所有UserID塞进Set，结果内存直接爆掉。后来换了HyperLogLog，同一个场景只用了原来千分之一的内存，误差还能控制在1%以内。这篇就是我在PHP环境里折腾HyperLogLog的完整记录，包括原理、手写实现、Redis落地和踩坑总结，适合对算法感兴趣、或者正被大数据量去重折磨的PHP开发者。

1. 为什么我建议在PHP项目里引入HyperLogLog

1.1 传统去重方案的内存账本

先算一笔账。假设你有100万个用户ID需要去重计数，每个ID用8字节的整数或者十几字节的字符串。用传统的Set结构去重，每个元素不仅要存原始数据，还要承担哈希表本身的链表指针、冲突链、扩容预留空间。实际算下来，Redis里一个包含100万成员String类型的Set，占用内存大概在30MB到60MB之间，取决于字符串长度和编码方式。如果换成PHP数组直接存，开销更大，PHP的数组底层是哈希表，每个元素有zval结构体、哈希值、冲突链指针，100万个整数轻松吃掉一两百MB内存。

如果数据量继续涨到一千万、一个亿呢？Set方案在内存上基本就不可行了。有人会想用Bitmap，每个用户映射到一位，100万用户只需要125KB，看起来很完美。但Bitmap有个硬前提：用户ID必须是稠密的连续整数，否则一个1亿的ID稀疏分布，就得分配1亿个位，也就是12.5MB，而且实际只有100万位被占用，绝大多数空间浪费掉了，更别说还要维护ID到位的映射关系。

这就是基数统计的典型困境：精确计数意味着存储与基数线性相关，基数越大，存储越大。HyperLogLog的思路完全不同，它不追求精确，而是通过概率估算，把内存占用压到固定大小。标准实现里，一个HLL结构最多只用12KB左右，不管你要统计的是100万、1亿还是100亿个元素。

1.2 HyperLogLog是什么、能解决什么问题

HyperLogLog是一种基数估计算法，专门用来统计一个集合中不重复元素的数量。所谓“基数”，就是去重后的数量。它最大的特点是内存占用固定且极小，标准误差大约在0.81%左右。这个误差在绝大多数业务场景下完全够用，比如统计日活用户、PV算UV、统计独立访客、爬虫去重计数，甚至网络流量监控里的流数量估计。

在PHP项目里，HyperLogLog最常见的落地方式有两种。第一种是直接用Redis自带的HLL数据结构，通过PFADD、PFCOUNT、PFMERGE三个命令完成添加、统计和合并，这是生产环境最推荐的做法。第二种是自己用PHP实现一个HLL类，适合学习原理、抠细节，或者在不方便引入Redis的离线脚本里做统计。

为什么PHP项目特别适合这个算法？因为很多PHP业务天生就是IO密集、数据量不确定的Web应用，日活从几百到几百万都可能。用Set做UV统计，流量高峰一来内存就告急；用HLL就从容得多，同一个Key无论塞多少数据，内存占用都是那12KB左右。而且HLL支持合并，这意味着你可以按天、按小时、按渠道分别统计，最后通过PFMERGE一键汇总，不用重新扫全量数据。

1.3 适用场景与不适用场景

任何工具都有边界，HLL也不例外。我整理了一个对比表格，方便你快速判断到底该用哪种方案。

另外要牢记，HLL只能回答“有多少个不同的元素”，回答不了“有哪些元素”，也回答不了“某个元素出现过没有”。如果你需要的是这些能力，应该考虑Set或者Bloom Filter，而不是HLL。我用HLL做过最合适的场景就是日活统计：只关心今天有多少个独立访客，完全不关心具体是谁，也不关心某个特定用户是否访问过。

2. HyperLogLog核心原理，用大白话讲明白

2.1 一个硬币实验：抛硬币背后的概率直觉

想理解HLL，可以先做一个思想实验。假设我在抛一枚均匀的硬币，记录第一次出现正面时总共抛了多少次。这个次数记为N，每次实验N都是一个随机变量，理论分布是几何分布。你会发现，N特别大的情况很少见，但一旦出现，就能说明我们做的实验次数很多。

如果做很多轮实验，每一轮都记录“第一次出现正面需要的次数”，然后取所有轮次N的最大值。直觉告诉我们：最大的N越大，说明实验的总轮数越多。因为如果只做2轮，出现连续抛10次才出正面的概率极低；但如果做了1000轮，出现连续抛10次才出正面的概率就很高了。

HyperLogLog把这个思想挪到了基数统计上。每个元素经过哈希函数变成一串均匀分布的二进制比特，等价于一次随机的抛硬币序列。我们用“从最高位开始连续出现0的个数”来代替“抛了多少次才出现正面”。连续0越多，表示这次的哈希值越“极端”。把一批元素中最极端的那个记录保留下来，用它的极端程度反推这批元素的总量。

这个思路的关键在于：哈希函数把元素均匀地映射到二进制空间，使得每个比特都接近“等概率随机”。只要哈希选得好，一串元素中“最长前缀0长度”和元素数量之间就存在可估计的统计关系。单个变量方差太大，所以真实的HLL不是只记录一个最大值，而是用大量寄存器来消减方差。

2.2 分桶、调和平均与误差控制

把整个哈希空间切成2^p个桶，每个桶维护一个寄存器，记录该桶内见过的“最长前缀0长度”。对每个元素，先取哈希值的前p位作为桶编号，再用剩下的位统计前导0，更新对应寄存器。当数据量足够大时，每个桶的分布都近似，就可以通过所有寄存器的综合信息来还原总基数。

直接对全部寄存器取平均是危险的。因为少数寄存器可能记录了极端大的前导0，如果把它们单独拉高，算术平均会被严重带偏。HLL用的是调和平均，调和平均对极端大值更不敏感，能有效抑制个别“幸运值”对整体估计的冲击。标准公式是：

code复制E = alpha * m * m / sum(2^(-rank_i))

其中m是寄存器数量，rank_i是第i个寄存器的值，alpha是一个与m相关的修正系数。这个公式看起来抽象，但本质就是：每个寄存器里的“前导0最大值”经过2的负指数变换后累加，再做一次加权调和平均。

误差的大小由寄存器数量m决定，理论误差约等于1.04 / sqrt(m)。寄存器越多，误差越小，内存也越大。工程上常用m=16384，也就是p=14，内存约12KB，理论误差0.81%。如果追求更高精度，可以把m提高到2^20，也就是大约1MB内存，误差能压到0.1%以下。

2.3 哈希函数的选择与影响

哈希函数是整个算法的地基。如果哈希分布不均匀，或者碰撞率过高，估计结果就会出现系统偏差。我实测过几类哈希在HLL里的表现：PHP自带的crc32速度很快，但在处理几百万条数据时，32位哈希空间的碰撞开始显现，误差可能比理论值略高。md5、sha1这类密码学哈希效果很好，均匀性优秀，但速度慢，在循环里调用会有明显性能损耗。实践中最理想的方案是fnv1a64或murmurhash这样的非加密哈希，速度快，64位空间够大，均匀性足够。

Redis的HLL实现内部用的是MurmurHash64A，这也是为什么它在大量数据下依然能把误差稳定在0.81%左右。自研PHP实现时，我建议直接使用hash('fnv1a64', $value)，然后统一按64位处理。如果你为了简单用crc32，那就得清楚它的32位空间在千万级数据下会有碰撞风险，误差会被放大。

3. PHP实现一个可运行的HyperLogLog类

3.1 类的整体设计与接口定义

纯PHP实现HLL，主要不是为了挑战Redis，而是为了把原理吃透。我在设计类的时候，尽量保持接口简洁，核心就三个方法：add负责加入元素，count返回估计基数，merge合并另一个HLL。构造函数接收分桶参数p，默认14，也就是16384个寄存器。

php复制<?php

class HyperLogLog
{
    private int $p;
    private int $m;
    private array $registers;

    public function __construct(int $p = 14)
    {
        if ($p < 4 || $p > 18) {
            throw new InvalidArgumentException('p 的取值范围建议在 4~18 之间');
        }
        $this->p = $p;
        $this->m = 1 << $p;
        $this->registers = array_fill(0, $this->m, 0);
    }

    public function add(string $value): void
    {
        // 这里默认用 crc32 演示，生产环境建议换成 fnv1a64 或直接上 Redis
        $hash = crc32($value);

        // 取哈希值的前 p 位作为桶索引
        $index = ($hash >> (32 - $this->p)) & ($this->m - 1);

        // 剩余位用来统计前导 0 的个数
        $rest = ($hash << $this->p) & 0xFFFFFFFF;
        $zeros = $rest === 0 ? 32 - $this->p : $this->numberOfLeadingZeros($rest);
        $rank = $zeros + 1;

        if ($rank > $this->registers[$index]) {
            $this->registers[$index] = $rank;
        }
    }

    public function count(): int
    {
        $sum = 0.0;
        $zeroCount = 0;

        foreach ($this->registers as $rank) {
            $sum += 2.0 ** (-$rank);
            if ($rank === 0) {
                $zeroCount++;
            }
        }

        $alpha = 0.7213 / (1 + 1.079 / $this->m);
        $estimate = ($alpha * $this->m * $this->m) / $sum;

        // 小基数修正：当估计值小于 2.5 * m 时，用线性计数
        if ($estimate <= 2.5 * $this->m && $zeroCount > 0) {
            $estimate = $this->m * log($this->m / $zeroCount);
        }

        return (int) round($estimate);
    }

    public function merge(self $other): void
    {
        if ($this->p !== $other->p) {
            throw new InvalidArgumentException('两个 HyperLogLog 的 p 参数必须一致才能合并');
        }

        for ($i = 0; $i < $this->m; $i++) {
            if ($other->registers[$i] > $this->registers[$i]) {
                $this->registers[$i] = $other->registers[$i];
            }
        }
    }

    private function numberOfLeadingZeros(int $x): int
    {
        if ($x === 0) {
            return 32;
        }

        $n = 0;
        if ($x <= 0x0000FFFF) { $n += 16; $x <<= 16; }
        if ($x <= 0x00FFFFFF) { $n += 8;  $x <<= 8; }
        if ($x <= 0x0FFFFFFF) { $n += 4;  $x <<= 4; }
        if ($x <= 0x3FFFFFFF) { $n += 2;  $x <<= 2; }
        if ($x <= 0x7FFFFFFF) { $n += 1; }

        return $n;
    }
}

这段代码里最核心的是numberOfLeadingZeros方法，它用二分法快速统计一个32位整数的前导0个数。我第一次实现时图省事，直接写了个循环一位一位数，结果在几十万数据量的测试下慢得离谱。后来换成了这个二进制搜索版本，单次操作从几十次循环降到五次判断，性能提升非常明显。

3.2 核心方法逐行拆解

add方法的本质可以拆成三步。第一步是对元素做哈希，得到一个整数。这里我用的crc32，它返回一个32位无符号整数。第二步是分桶，哈希值右移32 - p位后与m - 1取按位与，得到的值就是桶编号。这一步等价于取哈希值的前p位作为桶号。第三步是更新寄存器，把哈希值左移p位后再与0xFFFFFFFF按位与，相当于把低32 - p位提到高位，然后统计前导0个数，得到的rank就是这组数据在这个桶里的“最大抛硬币次数”。

有一个细节值得单独说：$rest === 0这个分支。当哈希值的低32 - p位全部为0时，前导0个数理论上应该是32 - p，但通用的前导0统计方法遇到0会返回32，所以必须单独处理。我第一版代码没加这个判断，跑测试时发现偶尔会蹦出一个离谱的大值，查了半天才定位到是这里的问题。

count方法里最容易被忽略的是小基数修正。当实际基数很小，比如只有几百个元素时，大部分寄存器还是0，直接用调和平均公式算出来的结果会偏高。这时候改用线性估计：m * log(m / zeroCount)，利用“空寄存器比例”来还原基数，精度会好很多。

3.3 用真实数据验证算法的精度

写完成之后，我一向的习惯是用数据说话。写一个简单的测试脚本，插入10万个、50万个、100万个连续字符串，看估计值和真实值差多少。

php复制$hll = new HyperLogLog(14);

$total = 100000;
for ($i = 0; $i < $total; $i++) {
    $hll->add('user_' . $i);
}

echo '真实基数: ' . $total . PHP_EOL;
echo 'HLL估计: ' . $hll->count() . PHP_EOL;
echo '误差: ' . abs($hll->count() - $total) / $total * 100 . '%' . PHP_EOL;

我本机PHP 8.2环境下跑出来的结果大概是这样的：

整体误差基本在1%上下浮动，和理论值0.81%匹配。你会发现误差有随机波动，这是概率算法的天性，多跑几轮结果会略有不同。数据量更小的时候误差波动更大，几千条数据时可能偏到3%到5%，这也是小基数修正尽力挽回之后的结果。所以再次提醒：HLL不是为小数据量设计的，几万以下老老实实用精确计数就好。

3.4 merge方法的价值在哪

merge方法看起来只是逐桶取最大值，含金量却很高。它意味着HLL天然支持分布式统计：你可以把流量拆到多个服务器上，每台机器维护自己的HLL，然后定期把各自的HLL合并成一个全局HLL，直接得到全量去重基数。合并过程不需要回放原始数据，只交换每个桶的寄存器值，通讯量极小。

我做过一个实际案例：公司在多台Web服务器上分别统计各自收到的用户请求，每个实例每隔5分钟把自己的HLL序列化出来，发送到一个汇总服务，汇总服务用merge合并后得到全站UV。整个过程只需要传递几KB数据，和原始数据量完全无关。这种合并能力是Set方案完全不具备的，也是我选HLL做跨节点去重统计的决定性理由。

4. 实战：用Redis把HyperLogLog落地UV统计

4.1 为什么生产环境首选Redis实现

自研PHP类的意义在于理解原理，真到了生产环境，我强烈建议直接用Redis自带的HLL。理由很简单：内存、性能、稳定性全面领先。Redis的HLL底层使用稀疏编码和密集编码自动切换，数据量小时内存占用极小，数据量大了以后自动扩容到密集编码，但始终控制在约12KB。而纯PHP实现每次add都要走一遍哈希和前导0统计，在百万级数据量下循环执行速度远不如Redis一条PFADD命令高效。

Redis的HLL每个Key在数据量很大的时候也就12KB左右，这是官方承诺的最大值。相比之下，用Set存100万个用户ID要几十MB，用Bitmap处理稀疏ID要浪费大量空间。只需要记住三个命令就能上手：

• PFADD key element [element ...]：往HLL里添加元素
• PFCOUNT key [key ...]：统计基数，可以一次传多个Key
• PFMERGE destkey sourcekey [sourcekey ...]：把多个HLL合并到目标Key

4.2 完整的日活统计与跨天合并代码

先看最常见的日活统计场景。用户每次访问页面，PHP里拿到用户ID，直接PFADD进当天的Key。Key的命名我建议带上日期，方便后续聚合。

php复制<?php

$redis = new Redis();
$redis->connect('127.0.0.1', 6379);

// 用户访问时，加入当天 UV 统计
$userId = 'uid:10086';
$today = date('Ymd');
$redis->pfAdd('uv:' . $today, [$userId]);

// 查询今天 UV
$uv = $redis->pfCount('uv:' . $today);
echo "今日UV: {$uv}" . PHP_EOL;

跨天合并的需求也很常见，比如要看最近7天总UV。最笨的办法是把7天的原始访问记录捞出来重新去重，但在数据量庞大的情况下完全不可行。用PFMERGE就轻松了：

php复制<?php

// 以最近7天为例，合并7个 HLL Key 到周汇总 Key
$weekKey = 'uv:week:2025W01';
$keys = [];

for ($i = 6; $i >= 0; $i--) {
    $day = date('Ymd', strtotime("-{$i} day"));
    $keys[] = 'uv:' . $day;
}

$redis->pfMerge($weekKey, $keys);

$weekUv = $redis->pfCount($weekKey);
echo "最近7天去重UV: {$weekUv}" . PHP_EOL;

这个方案的优雅之处在于合并过程不读原始数据，只读取每个天级HLL的寄存器，时间复杂度与天数有关，和用户访问量无关。就算一天有上亿访问量，合并7天也就是毫秒级的事情。

4.3 内存实测对比与分桶调优

为了直观感受差距，我专门做过一次内存对比测试。往Redis里分别写入100万个用户ID到Set和HLL，然后看内存占用。

差了三个数量级，这就是概率算法对内存的降维打击。如果你对0.81%的标准误差还不满意，也可以在创建HLL时把分桶参数调大。误差与寄存器数量的关系是1.04 / sqrt(m)，m=16384时约0.81%，m=131072时约0.29%，m=1048576时约0.1%。实际配置时，要权衡误差需求和内存成本。

有一个容易被忽略的点：Redis的HLL在数据量很小时会自动切换到稀疏编码，内存远小于12KB，等到元素数量增多后才转为密集编码。所以不要因为看到一个HLL Key当前只有几百字节，就觉得可以无限制地创建大量Key。每个HLL最终都可能膨胀到12KB，如果一天一个Key、保留365天，也是几MB级别的存储，查询汇总时还要注意通配符批量操作对Redis性能的影响。

5. 常见问题与排查心法

5.1 为什么误差总是比理论值大

有些朋友跑完测试发现误差波动到2%甚至3%，第一反应是算法有问题。实际上绝大多数情况是数据量太小。HLL的理论误差0.81%建立在“足够数据让每个桶都充分采样”的前提下。几千条数据分配到16384个桶里，大多数桶只被命中几次甚至一次都没有，统计信息不足，误差自然放大。

还有一种可能是哈希函数选得不好，导致某些桶被过度命中。我用crc32测试过一百万条真实URL去重，误差比理论值高不少，换成fnv1a64后明显改善。如果条件允许，尽量用64位哈希甚至Redis自带实现。另外，如果P参数设置得太小，比如p=4，只有16个桶，误差会高达26%左右，这不是算法不靠谱，而是配置错误。

5.2 PHP实现过程中的真实坑点

先说个最隐蔽的坑：crc32在32位PHP和64位PHP下的返回类型不一样。在32位平台上crc32可能返回有符号整数，负数时按位与移位的结果跟你预期完全不同，必须用$hash = sprintf('%u', crc32($value))先转成无符号字符串再做处理。我现在做PHP开发基本都在64位环境，但写库代码时养成了兼容判断的习惯，避免换环境就翻车。

再说PHP数组的开销。自研HLL类里的$registers数组，每个元素在PHP底层是一个zval结构体，一个整数在PHP数组里占用的内存远不止8字节。100个寄存器还好，100万寄存器就会吃几百MB内存，所以纯PHP实现更适合学习和轻量任务，大规模生产统计还是那句话，用Redis。

还有PHP的浮点精度问题。count方法里计算2.0 ** (-$rank)和调和平均时，当寄存器数量很大，浮点累加可能有细微误差。尽量使用float类型变量，避免在循环里反复做类型转换。调试时如果怀疑结果有异常，先把中间变量$sum、$estimate打印出来，配合var_dump检查每一步的数值变化，比盲猜高效得多。PHP的错误处理在这里也很重要，数组越界、类型松散导致的warning，在实际日志里会掩盖真正的算法问题，开发阶段建议开启严格报错。

5.3 Redis与自研实现结果不一致正常吗

正常，甚至可以说必然。Redis的HLL用的是64位Murmur哈希，我自研版本默认用crc32，哈希空间和分布特性完全不同，同样的数据插入两者，寄存器内容差异很大，统计结果自然不完全一样。但两者都应该在各自设计的误差范围内。

如果你在同一个项目里同时用了Redis HLL和自研HLL，千万别期望它们输出完全相同的数字。统一口径的做法是：线上统计一律以Redis为准，自研版本只留在本地做算法实验。还有一个小建议：PFCOUNT在内部会缓存结果，同一个Key多次调用不会重复计算，所以不用担心频繁统计的性能问题。但如果统计后立即插入新元素，缓存会失效并重新计算，这是正常行为。

5.4 哪些场景果断放弃HyperLogLog

我知道HLL香，但它不是银弹。如果你的需求是精准计数，比如订单去重、支付流水对账，千万别用任何概率算法，老老实实上数据库唯一索引或者Set结构。如果你需要判断“这个用户今天来没来过”，HLL也帮不上忙，它只能回答“今天有多少独立用户”。如果基数本身只有几千，直接用精确计数，把时间花在优化SQL和索引上，比引入一个需要维护的算法结构更划算。

我在实际项目里有一条决策原则：基数超过10万、误差容忍度在1%以上、只需要去重计数不需要成员判断，这三个条件同时满足，才上HLL。否则就选更简单的方案，省得给自己挖坑。

6. 我想再补充的一点个人体会

折腾HLL这段时间，最大的收获不是算法本身，而是“用概率换空间”这种思维方式的转变。很多业务场景根本不要求100%精确，但传统方案为了这微不足道的精确，不得不付出巨大的存储和计算成本。

如果让我给一个实际建议：初次接触HLL，别急着写自己的实现，先用Redis的PFADD和PFCOUNT跑通业务，确认它能满足你的需求。之后再回头看我上面那份PHP源码，手抄一遍，把每个方法都改成自己能理解的样子。等你真正明白调和平均为什么能压制异常值、小基数修正为什么能提升低基数下的精度，你就不会再对那个0.81%的误差耿耿于怀了。

最后分享一个小技巧：在本地调试HLL时，可以故意插入一批极端数据，比如1万个相同的元素，来观察它是否依然返回大约1万。HLL对重复元素天然免疫，这一步能帮你确认哈希函数和寄存器更新逻辑没写错。每次写完新版本，我都先跑这个用例，再跑大基数用例，两个都过了才敢说这个实现可以放心用。数据验证这件事，怎么谨慎都不为过。