16 | May | 2020 | ZHANG RONG

基数估算问题

基数估算（Cardinality Estimation），也称为 count-distinct problem，一直是大数据领域的重要问题之一。顾名思义，基数估算就是为了估算在一批数据中，它的不重复元素有多少个。

这个问题的应用场景十分广泛。例如：对于 Google 主页面而言，同一个账户可能会访问 Google 主页面多次。于是，在诸多的访问流水中，如何计算出 Google 主页面每天被多少个不同的账户访问过就是一个重要的问题。那么对于 Google 这种访问量巨大的网页而言，其实统计出有十亿的访问量或者十亿零十万的访问量其实是没有太多的区别的，因此，在这种业务场景下，为了节省成本，其实可以只计算出一个大概的值，而没有必要计算出精准的值。

从数学上来说，基数估计这个问题的详细描述是：对于一个数据流 $x_{1},x_{2}, \cdots, x_{s}$ 而言，它可能存在重复的元素，用 $n$ 来表示这个数据流的不同元素的个数，i.e. $n=|\{x_{1},\cdots,x_{s}\}|,$ 并且这个集合可以表示为 $\{e_{1},\cdots,e_{n}\}.$ 目标是：使用 $m$ 这个量级的存储单位，可以得到 $n$ 的估计值 $\hat{n},$ 其中 $m\ll n,$ 并且估计值 $\hat{n}$ 和实际值 $n$ 的误差是可以控制的。

如果是想得到精确的基数，可以使用字典（dictionary）这一个数据结构。对于新来的元素，可以查看它是否属于这个字典；如果属于这个字典，则整体计数保持不变；如果不属于这个字典，则先把这个元素添加进字典，然后把整体计数增加一。当遍历了这个数据流之后，得到的整体计数就是这个数据流的基数了。

cardinality_estimation_naive_solution — Naive Solution

这种算法虽然精准度很高，但是使用的空间复杂度却很高。那么是否存在一些近似的方法，可以估算出数据流的基数呢？其实，在近几十年，不少的学者都提出了很多基数估算的方法，包括 LogLog，HyperLogLog，MinCount 等等。下面将会简要的介绍一下这些方法。

cardinality_estimation_survey_table_1 — 基数估计的部分算法

HyperLogLog 的理论介绍

HyperLogLog 是大数据基数统计中的常见方法，无论是 Redis，Spark 还是 Flink 都提供了这个功能，其目的就是在一定的误差范围内，用最小的空间复杂度来估算一个数据流的基数。

HyperLogLog 算法简要思路是通过一个 hash 函数把数据流 $\mathcal{D}$ 映射到 $\{0,1\}^{\infty},$ 也就是说用二进制来表示数据流中的元素。每一个数据流中的元素 $x$ 都对应着一个 $0,1$ 序列。

在介绍 HyperLogLog 之前，我们可以考虑这个实际的场景。在一个抛硬币的场景下，假设硬币的正面对应着 $1,$ 硬币的反面对应着 $0;$ 依次扔出 $0,0,0,1$ 的概率是多少？通过概率计算可以得到是这个概率是 $1/2^{4}=1/16.$ 那么相当于平均需要扔 $16$ 次，才会获得 $0001$ 这个序列。反之，如果出现了 $0001$ 这个序列，说明起码抛了 $16$ 次硬币。

考虑这样一个 $0,1$ 序列， $w=w_{1}w_{2}\cdots,$ $w_{i}\in\{0,1\}, i\geq 1,$ 令 $k$ 表示第一个 $1$ 出现的位置。也就是说 $w_{1}=w_{2}=\cdots=w_{k-1}=0.$ 那么在扔硬币的场景下，出现这样的序列平均至少需要扔 $2^{k}$ 次。对于一批大量的随机的 $0,1$ 序列，可以根据第一个 $1$ 出现的位置来估算这批 $0,1$ 序列的个数。也就是说：

出现序列 $1XXXXX$ 意味着不重复的元素估计有 $2^1=2$ 个；
出现序列 $01XXXX$ 意味着不重复的元素估计有 $2^2=4$ 个；
出现序列 $001XXX$ 意味着不重复的元素估计有 $2^3=8$ 个；
出现序列 $0001XX$ 意味着不重复的元素估计有 $2^4=16$ 个。

于是，对于随机的 $0,1$ 序列，可以定义函数 $\rho(w_{1}w_{2}\cdots)$ 来表示 $1$ 出现的第一个位置。i.e. $\rho(1XXXXX)=1,$ $\rho(01XXXX)=2,$ $\rho(001XXX)=3,$ $\rho(0001XX)=4.$

简单来看，其实 HyperLogLog 的基数统计就使用了这样的思想，通过二进制中 $1$ 出现的第一个位置来估算整体的数量。首先把这批元素通过 hash 函数处理成 $0,1$ 序列，然后把这批 $0,1$ 序列都放入 $1$ 个桶，然后通过计算这个桶里面所有 $0,1$ 序列的 $\rho(w)$ 的最大值，就可以预估出整体的数量。i.e. $M=\max_{w}\rho(w),$ 整体的数量预估是 $2^{M}=2^{\max_{w}\rho(w)}.$

$1$ 个桶：计算出 $M=\max_{w}\rho(w),$ 预估不重复的元素个数是 $2^{M}.$

那么如果只有 $1$ 个桶，其实是会存在一定的偏差的。为了解决这个问题，一种想法就是重复以上操作，从 hash 函数开始处理成 $0,1$ 序列，每次都把这批 $0,1$ 序列放入 $1$ 个桶，每次获得一个 $M$ 值。总共操作 $m$ 次，第 $j$ 次操作得到的值记为 $M_{j};$ 于是就可以对 $\{M_{1},\cdots,M_{m}\}$ 进行均值处理，可以使用以下方法：

算术平均数： $M=\sum_{j=1}^{m}M_{j};$
几何平均数： $M=\sqrt[m]{M_{1}\cdots M_{m}};$
调和平均数： $M=m/\sum_{j=1}^{m}M_{j}^{-1};$
中位数： $M = median\{M_{1},\cdots,M_{m}\}.$

从而可以预估整体的数量为 $2^{M}.$

如果按照以上的步骤进行操作，就是需要重复进行多次操作，在足够多的情况下，其实是没有必要那么操作的。HyperLogLog 也是用了多个桶，但是用了一个截断的技巧。对于一个 $0,1$ 序列 $x=\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1},$ HyperLogLog 从某个位置 $b$ 开始，低位 $x_{b}\cdots x_{1}$ 用于决定桶的序号，也就是第几个桶。桶的个数就是 $m=2^{b},$ 高位 $\cdots x_{b+2}x_{b+1}$ 用于估算放在桶里面的元素个数。

每次都可以获得一个值，也就是桶里面第一次出现

第 1 个桶：计算出 $M_{1}=\max_{w}\rho(w),$ 预估元素个数 $2^{M_{1}};$
第 2 个桶：计算出 $M_{2}=\max_{w}\rho(w),$ 预估元素个数 $2^{M_{2}};$
….
第 $m$ 个桶：计算出 $M_{m}=\max_{w}\rho(w),$ 预估元素个数 $2^{M_{m}};$

均值的计算，HyperLogLog 使用了调和平均数 $m/\sum_{j=1}^{m}2^{-M_{j}}$ 来估算桶里面的元素个数，那么在有 $m$ 个桶的情况下，整体的元素个数就可以估算为 $E=m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M_{j}}\bigg)^{-1}.$

hyperloglog_algorithm_simple — 原始的 HyperLogLog 算法

其中的 $\alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.$ 当 $m=1$ 的时候， $\int_{0}^{+\infty}\log_{2}\bigg(\frac{2+u}{1+u}\bigg)du$ 是发散的；当 $m\geq 2$ 的时候， $\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du$ 是收敛的。因此，在使用这个算法的时候最好放入 $m\geq 2$ 个桶。

HyperLogLog 分成两块，第一块就是 add 模块，用于分桶和统计；

for v in M:
    set x := h(v);
    set j = 1 + <x(b),...,x(2),x(1)>;
    set w := x(b+1)x(b+2)...; 
    set M[j] := max(M[j], \rho(w));

在 HyperLogLog 算法中，对于集合 $\mathcal{M}$ 中的每一个元素 $v\in\mathcal{M},$ 可以通过 hash 函数转换成一个 $0,1$ 序列 $h(v)=x=<\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}>,$ 其中 $x_{1}$ 表示二进制中的最低位， $x_{2}$ 表示次低位。

然后可以通过 $<x_{b}\cdots x_{1}>_{2}$ 来计算放在第 $j$ 个桶，这里 $j=1+<x_{b}\cdots x_{1}>_{2}.$ 同时将 $x$ 的高位拿出来，也就是 $x_{b+1}x_{b+2}\cdots,$ 计算这批序列的 $\rho$ 函数的最大值，然后记为 $M_{j};$ 这一步也可以称为 merge 模块，也就是进行更新合并。

compute Z := (\sum_{j=1}^{m}2^{-M[j]})^{-1};

上一步就是 HyperLogLog 的另外一步，count 模块，于是，进一步估算出 $E=\alpha_{m}m^{2}Z.$

HyperLogLog 的空间复杂度特别低，大约是 $O(m\log_{2}\log_{2}n)$ 这个量级的，其中 $m$ 是桶的个数， $n$ 是基数。HyperLogLog 的时间复杂度则是 $O(n),$ 只需要遍历一遍所有元素即可得到最终结果。

假设基数为 $2^{k},$ 二进制就是 $k$ 位， $1$ 最晚就会出现在第 $k$ 个位置上；而 $k$ 只需要 $log_{2}k$ 个 bit 就能够存储；
假设基数为 $2^{64},$ 二进制就是 $64$ 位， $1$ 最晚会出现在第 $64$ 个位置上；而 $64$ 需要 $6$ 个 bit 就可以存储。

在论文中，论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 的作者们针对各种算法进行了对比，其实 HyperLogLog 的空间复杂度是非常小的，并且误差也在可控的范围内。

hyperloglog_algorithm_theorem — HyperLogLog 的定理证明

在论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 作者们得到上述定理，精准的给出了 HyperLogLog 算法的误差估计。因此，HyperLogLog 算法其实是有数学定理证明的。

以上只是获得了理论上的 HyperLogLog 算法，但是在实战中，其实是需要进行微调的。主要的微调部分是根据理论中的 $E$ 值来进行调整。将 $E$ 值进行调整的话，情况可以分成三种：

小范围；
中等范围；
大范围；

hyperloglog_algorithm_practical — 实战中的 HyperLogLog

Case（1）：小范围

在小范围的情况下， $E\leq 5m/2,$ 此时的基数相对于桶的数量而言不算太多，因此可能存在多个空桶，需要进行调整。

可以思考这样一个问题：假设有 $m$ 个桶，同时有 $n$ 个球，把这 $n$ 个球随机往这 $m$ 个桶里面扔，每个球只能够进入一个桶，那么空桶个数的期望是多少个？

Answer：假设 $A_{1},\cdots,A_{m}$ 是 $m$ 个桶，

$P(A_{j}=\emptyset)=\bigg(1-\frac{1}{m}\bigg)^{n}$ 表示桶 $A_{j}$ 空的概率；

$P(A_{j}=\emptyset \cap A_{k}=\emptyset)=\bigg(1-\frac{2}{m}\bigg)^{n}$ 表示桶 $A_{j}, A_{k}$ 同时为空的概率（ $j\neq k$ ）；

那么空桶个数的期望就是 $m\cdot\bigg(1-\frac{1}{m}\bigg)^{n},$ 当 $m,n$ 充分大的时候，约为 $me^{-n/m}$ 个。

因此，在小范围的情况下，如果空桶的个数 $V\neq 0,$ 那么可以更新为 $m\ln(m/V).$ 事实上，可以通过 $V=me^{-n/m}$ 解出 $n=m\ln(m/V).$

Case（2）：中等范围

$E$ 值不作调整。

Case（3）：大范围

当 $E>2^{32}/30,$ 那么更新为 $E^{*}=-2^{32}\ln(1-E/2^{32}),$ 其中 $E^{*}>E.$

通过这样的方法， $E^{*}$ 的误差大约在 $\pm 1.04/\sqrt{m}$ 左右。

除此之外， $\alpha_{m}$ 其实也可以用近似值来代替，毕竟如下公式的计算是有一定的成本的。

$\alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.$

近似的值为 $\alpha_{16}=0.673,$ $\alpha_{32}=0.697,$ $\alpha_{64}=0.709,$ $\alpha_{m}=0.7213/(1+1.079/m)$ 当 $m\geq 128.$

HyperLogLog 的案例分析

有一个关于 HyperLogLog 的 demo 网站可以看到 HyperLogLog 的算法过程，其链接是 http://content.research.neustar.biz/blog/hll.html

在这个 demo 中，作者对比了 LogLog 和 HyperLogLog 的区别和运行过程，有助于大家理解整个过程。其中 LogLog 与 HyperLogLog 的区别就在与它们平均值的处理方式不一样，前者是使用算术平均值，后者是使用调和平均值。

LogLog： $\alpha_{m}\cdot m\cdot 2^{\sum_{j=1}^{m}M_{j}/m};$
HyperLogLog： $\alpha_{m}\cdot m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M[j]}\bigg)^{-1};$

hyperloglog_demo_1 — HyperLogLog Demo：初始化

hyperloglog_demo_2 — 第一个 hash 值：3852172429

3852172429 的二进制是：11100101100110110111110010001101，可以划分为100 110110111110010 001101。最后的六位是 001101，十进制就是 13，那么这个数字就会被放入第 13 个桶；而 110110111110010（从低位到高位看）， $\rho$ 函数的值就是 2；于是在第 13 个桶就会把 0 更新成 2。

hyperloglog_demo_3 — 第二个 hash 值：2545698499

2545698499 的二进制是 10010111101111000100011011000011，用同样的分析可得结论。

hyperloglog_demo_4 — 第三个 hash 值：2577699815

2577699815 的二进制是 10011001101001001001001111100111。

hyperloglog_demo_5 — 第四个 hash 值：775376803

775376803 的二进制是 101110001101110100111110100011。

从以上的 Demo 运行过程可以看出，整个 HyperLogLog 的算法逻辑还是相对清晰的，其整个算法的亮点应该在于借助了抛硬币的场景，用抛硬币的结果来估算抛硬币的次数。

参考文献：

Count-distinct Problem 的维基百科：https://en.wikipedia.org/wiki/Count-distinct_problem
Heule, Stefan, Marc Nunkesser, and Alexander Hall. “HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm.” Proceedings of the 16th International Conference on Extending Database Technology. 2013.
Flajolet, Philippe, et al. “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.” 2007.
HyperLogLog 的 demo 网站：http://content.research.neustar.biz/blog/hll.html

ZHANG RONG

Daily Archives: May 16, 2020

大数据领域的近似分析方法（一）

基数估算问题

HyperLogLog 的理论介绍

HyperLogLog 的案例分析

参考文献：

zr9558's Blog