大数据领域的近似分析方法(一)

基数估算问题

基数估算(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 都提供了这个功能,其目的就是在一定的误差范围内,用最小的空间复杂度来估算一个数据流的基数。

Spark
Spark 的 Logo

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_algorithm_compare
算法对比

在论文中,论文 “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。

hyperloglog_demo_6
运行结束

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

参考文献:

  1. Count-distinct Problem 的维基百科:https://en.wikipedia.org/wiki/Count-distinct_problem
  2. 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.
  3. Flajolet, Philippe, et al. “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.” 2007.
  4. HyperLogLog 的 demo 网站:http://content.research.neustar.biz/blog/hll.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s