统计 UV（Unique Visitor，独立访客数）几乎是每个数据团队都会遇到的需求，看起来只是一句 COUNT(DISTINCT user_id)，数据量一大却常常最先成为瓶颈。这篇文章想回答两个问题：去重计数为什么难，以及有哪些办法、各自付出了什么代价。

难在哪：去重计数不可加

PV（浏览量）可以按天算好再相加：周一 100 次、周二 100 次，两天就是 200 次。UV 不行：周一 100 人、周二 100 人，两天合计可能是 100 人（全是同一批人），也可能是 200 人（完全不重合）。

每天的 UV 是一个数字，而算两天的 UV 需要的是「到底是哪些人」。 这就是去重计数的不可加性，也是它难算的根源：

• 不能只保存结果，必须保存能「合并」的中间状态；

• 中间状态的大小和不同元素的个数成正比，人越多越占内存；

• 数据分布不均时，某个分组下的人特别多，就会出现数据倾斜。

所以下面这些方法，本质上都是在回答同一个问题：用什么样的数据结构来表示「一群人」，让它既省空间、又能合并。

先说一点数学：基数

一个集合中不同元素的个数叫基数（Cardinality）：

元素有限时，基数就是数一数；元素无限时会出现很反直觉的事，比如「无穷」和「无穷加一」一样多。感兴趣可以看看希尔伯特旅馆悖论。工程上我们只关心有限集合，难点不在定义，而在规模。

精确方案一：哈希集合

最直接的做法是把见过的元素都放进一个集合，最后数集合的大小。SQL 里的 COUNT(DISTINCT ...) 背后就是这个思路。

Set<Long> set = new HashSet<>(Arrays.asList(1L, 3L, 3L, 5L));
System.out.println(set.size()); // 3

• 优点：对任何类型都绝对精确。

• 缺点：占内存。一亿个 64 位整数，光数据本身就要 100,000,000 × 8 字节 ≈ 762.9 MB；HashSet 还要为每个元素额外存对象和哈希表结构，实际占用会大得多。

数据倾斜时：先分桶再汇总

按天统计 UV 时，一天的所有数据都会被分到同一个计算节点去重。数据量大时，可以先按用户 ID 的哈希把数据拆成若干桶，各桶独立去重，再把各桶的结果相加：

SELECT day, SUM(cnt) AS uv
FROM (
    SELECT day, COUNT(DISTINCT user_id) AS cnt
    FROM T
    GROUP BY day, MOD(HASH_CODE(user_id), 1024)
)
GROUP BY day;

这里相加之所以正确，是因为同一个用户只会落进同一个桶，桶与桶之间没有重复。这正是前面「不可加」问题的一个绕法：把集合拆成互不相交的几块，各块的基数就可以相加了。

精确方案二：Bitmap

如果 ID 是整数，可以换一种更紧凑的表示：准备一个很长的位数组，ID 是几，就把第几位置成 1。集合 {1, 3, 5} 就是：

基数就是 1 的个数，两个集合求并集就是按位或（OR）——这一步非常快，而且合并后依然精确。这意味着可以每天存一份 Bitmap，需要周 UV、月 UV 时把每天的 Bitmap 按位或起来再数，不必回头扫原始日志。

BitSet

Java 自带 BitSet：

BitSet bits = new BitSet();
for (int id : new int[] {1, 3, 3, 5}) {
    bits.set(id);
}
System.out.println(bits.cardinality()); // 3

一亿个 ID 只需要 100,000,000 位 ≈ 11.9 MB，比哈希集合小了几十倍。但它有个明显的弱点：数据稀疏时很浪费。只存 1、8888、99999999 三个数，也要开一个将近一亿位的数组。

RoaringBitmap：按块挑选最省的存法

RoaringBitmap 的思路是：把 32 位整数按高 16 位分成最多 65536 个块，每个块只存低 16 位，并根据块里数据的疏密，自动选择最省空间的容器：

为什么分界线是 4096？一个 short 占 2 字节，4096 个正好是 8 KB，和 Bitmap Container 一样大。元素再多，用数组就不如用位图划算了。下图是三种容器的内存占用随元素个数变化的情况：

使用起来和 BitSet 差不多：

<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
    <version>0.9.47</version>
</dependency>

RoaringBitmap bitmap = RoaringBitmap.bitmapOf(1, 3, 3, 5);
System.out.println(bitmap.getCardinality()); // 3

// 超出 32 位整数范围（约 42 亿）时，用 64 位版本
Roaring64Bitmap bitmap64 = Roaring64Bitmap.bitmapOf(1L, 3L, 3L, 5L);
System.out.println(bitmap64.getLongCardinality()); // 3

ID 不是整数怎么办：全局字典

用户 ID 往往是字符串。这时可以先建一张全局字典，给每个字符串分配一个连续的整数编号，再用编号构建 Bitmap。下图是 Flink 搭配 Hologres 实现的方案，详见阿里云文档：

字典的难点在于高并发下「查不到就插入」要保证同一个字符串只拿到一个编号。Fluss：重塑实时开发一文介绍了用 Fluss 的 Insert If Not Exists 做全局字典的做法。

近似方案一：Bloom Filter

如果只想知道「这个人来过没有」，可以用 Bloom Filter：用 k 个不同的哈希函数把元素映射到位数组的 k 个位置并置 1；查询时，只要有一个位置是 0，元素就一定不在集合里；全是 1 则可能在。

因为不同元素可能撞到同样的位置，Bloom Filter 会有假阳性（说在其实不在），但不会有假阴性（说不在就真不在）。用它计数的方法是：来一条数据先查一下，「不在」才计数并放进去。假阳性会让一部分新用户被误认为来过，所以计出来的数会略微偏小。

假阳性率取决于位数组长度 m、元素个数 n 和哈希函数个数 k，常用的近似公式是：

按最优的 k 计算，要把假阳性率压到 1%，每个元素大约需要 9.6 位。用 Guava 实现：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>32.1.2-jre</version>
</dependency>

// 预计放 500 个元素，假阳性率 1%
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);
filter.put(1);
filter.put(3);
filter.put(5);
System.out.println(filter.mightContain(2)); // 大概率 false
System.out.println(filter.mightContain(5)); // true

近似方案二：HyperLogLog

大多数分析场景并不需要精确到个位数：日活是 1003 万还是 1005 万，对决策几乎没有影响。如果愿意接受 1%~2% 的误差，HyperLogLog（HLL）只用几 KB 内存就能估计上亿的基数。

直觉：从抛硬币说起

一直抛硬币，直到第一次出现正面，记下前面连续出现了几次反面。如果有人告诉你「我见过的最长纪录是连续 10 次反面」，你大概会猜他抛了上千轮——因为连续 10 次反面的概率是 1/1024。

HLL 用的是同一个直觉：把每个元素哈希成一串均匀分布的二进制位，从一端数起看有几个连续的 0（论文从左边数「前导 0」，下面的图从右边数，道理一样）。任意一个哈希值以 3 个 0 结尾的概率是 1/8，见过的最长连续 0 越长，说明不同的元素越多；如果最长纪录是 r，基数大约就是 2 的 r 次方。

分桶平均：把运气成分降下来

只看一个最大值，偶然性太大。HLL 用哈希值的前几位把元素分到 m 个桶，用剩下的位数连续的 0，每个桶各记一个最大值，最后用调和平均把各桶的估计合起来。下图中前 4 位决定放进第 11 个桶，其余部分末尾有 5 个 0，这个桶就记下 5：

其中 $r_j$ 是第 j 个桶的记录（论文中定义为连续 0 的个数加 1），$\alpha_m$ 是修正常数。估计的相对标准误差约为：

举个例子：取 $m = 2^{11} = 2048$ 个桶，$\sigma \approx 2.3\%$，按三倍标准差估算，约 99.7% 的情况下误差在 7% 以内。每个桶用 5 位存记录，总共 2048 × 5 位 ≈ 1.25 KB。

可以在下面亲手试一试：换桶的个数、数据量和数据批次，看估计值离真实值有多远、占多少内存。默认就是上面例子里的 2048 个桶。

用起来

<dependency>
    <groupId>net.agkn</groupId>
    <artifactId>hll</artifactId>
    <version>1.6.0</version>
</dependency>

// log2m = 13，即 8192 个桶；每个桶 5 位
HLL hll = new HLL(13, 5);
HashFunction murmur = Hashing.murmur3_128();
for (long id : new long[] {1L, 3L, 3L, 5L}) {
    // addRaw 要求传入已经哈希过的值，原始 ID 需先过一遍哈希函数
    hll.addRaw(murmur.hashLong(id).asLong());
}
System.out.println(hll.cardinality()); // 约等于 3

HLL 的另一个好处是可合并：两个 HLL 逐桶取最大值，就得到并集的 HLL。和 Bitmap 一样，可以每天存一份，按需合成周、月的估计。本站的访客数统计就是这么做的：按小时为全站和每篇内容各存一份 HLL（PostgreSQL 的 hll 扩展，2¹⁴ 个桶），从不保存逐次访问的明细。

怎么选

一些经验：

• 报表、看板：HLL 足够，省下的资源可以换来更细的维度和更长的时间范围。

• 结算、对账、人群圈选：需要精确，优先考虑 RoaringBitmap；ID 不是整数就先建全局字典。

• 数据倾斜：无论用哪种结构，都可以先按用户 ID 分桶，把一个大集合拆成互不相交的小集合。

参考资料

• Philippe Flajolet 等，HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm，AofA 2007：HLL 的原始论文。

• Stefan Heule、Marc Nunkesser、Alexander Hall，HyperLogLog in Practice，EDBT 2013：Google 对 HLL 的工程改进（HLL++）。

• Samy Chambi、Daniel Lemire 等，Better bitmap performance with Roaring bitmaps，Software: Practice and Experience，2016。

• Burton H. Bloom，Space/Time Trade-offs in Hash Coding with Allowable Errors，Communications of the ACM，1970：Bloom Filter 的原始论文。

• 神奇的 HyperLogLog：中文的通俗讲解。