作者：vivo 互联网用户经营开发团队 – Shuai Guangying
本篇文章介绍了统计计数的基本原理以及 Presto 的实现思路，准确统计和近似统计的细节及各种优缺点，并给出了统计计数在具体业务应用的倡议。
系列文章：
探索 Presto SQL 引擎 (1)- 巧用 Antlr
探索 Presto SQL 引擎 (2)- 浅析 Join
探索 Presto SQL 引擎 (3)- 代码生成
一、背景
学习 Hadoop 时接触的第一个样例就是 word count，即统计文本中词的数量。各种 BI、营销产品中不可或缺的模块就是统计报表。在常见的搜寻分页模块，也须要提供总记录数。
统计在 SQL 引擎中堪称最根底、最外围的能力之一。可能因为它太根底了，就像排序一样，咱们经常会漠视它背地的原理。通常的计数是非常简单的，例如统计文本行数在 linux 零碎上一个 wc 命令就搞定了。
除了通常的计数，统计不反复元素个数的需要也十分常见，这种统计称为基数统计。对于 Presto 这种分布式 SQL 引擎，计数的实现原理值得深入研究，特地是基数统计。对于一般计数和基数计数，最典型的例子莫过于 PV/UV。
二、基数统计次要算法
在 SQL 语法外面，基数统计对应到 count(distinct field) 或者 aprox_distinct()。通常做准确计数统计须要用到 Set 这种数据结构。通过 Set 不仅能够取得数量信息，还能不重不漏地获取每一个元素。
Set 外部有两种实现实现原理：Hash 和 Tree。
在海量数据的前提下，Hash 和 Tree 有一个致命的问题：内存耗费，而且随着数据量级的增长，内存耗费也是线性增长。
面对 Set 内存耗费的问题，通常有两种思路：
一种是选取其余内存占用更小的数据结构，例如 bitmap；另一种是放弃准确，从数学上寻求近似解，典型的算法有 Linear Count 和 HyperLogLog。2.1 Bitmap
在数据库畛域 Bitmap 并不是新事物，个别用作索引，称为位图索引。所谓位图索引，就是用一个 bit 位向量来记录某个字段值是否存在于对应的记录。它有一个前置条件：记录要有永恒的编号，相似于从 1 开始的自增主键。
2.1.1 位图向量的构建
举个例子，假如表 user 记录如下：
这是很典型的一张数据库表。对于表中的字段，如何构建位图索引呢？以 age 字段为例：
S1: 确定字段的取值汇合空间: {30,40,50} 一共 3 个选项。S2: 顺次为每个选项构建一个长度为 6 的 bit 向量，失去一个 3 * 6 的位图。3 示意字段 age 的取值基数，6 示意记录数。S3: 基于表设置位图相应向量值。例如：age=30 的记录 id 别离为 {1,2,6}，那么在向量 1,2,6 地位置为 1，其余置为 0。失去 110001。同理，对于 name 字段，其向量位图为：
能够看出，如果对于数据表的一个字段，如果记录数为 n 且字段的取值基数为 m，那么会失去一个 m * n 的位图。
2.1.2 位图向量的利用
有了位图向量，该如何应用呢？假如查问 SQL 为
select count(1) from user where age=40;
则取 age 字段位图中 age=40 的向量：110001。统计其中 1 的个数，即可失去最终后果。
假如查问 SQL 更简单一些：
select count(1) from user where age=40 and name=’baz’
则取 age 字段位图中 age=40 的向量：110001 和 name=’foo’ 的向量：100100。两个向量进行交加运算：
最初统计后果为 1。
对于 Bitmap 的思维，笔者认为最奇妙的一点就是通过位运算实现了汇合运算。如下图所示：
在不同的业务场景中，这里的汇合能够赋予不同的业务含意。
2.1.3 位图向量的长处
将字段的筛选变成了向量计算后，会十分节约内存，而且能够通过分段长度编码等形式对 bitmap 向量进行压缩。而且位运算间接对内存中的二进制位进行操作，执行效率十分高，是性能晋升的一大杀器。
了解了 bitmap 后，能够发现对于整型字段，能够间接用 bitmap 进行基数统计。笔者已经试验过，对于 3 亿数据量级应用 roaringbitmap 工具，bitmap 耗费内存约 30M，而且如果数据分布十分密集内存耗费还有很大的压缩空间。惟一的毛病是非数值型字段，须要进行额定的转换解决。
2.2 Linear Count 算法
Linear Count 简称 LC 算法，LC 算法的流程非常简单 (背地的数学思维不简略)。
算法形容如下：
初始化：给定 m 个房间，房间存储数字，初始化为 0。迭代执行：对于要进行基数统计的汇合，用一个哈希函数解决汇合中的每一个元素。通过哈希函数解决后，元素就能够搁置到一个房间中。收尾：统计 m 个房间中空房间的数量 U。论断：汇合中不反复元素的个数估计值能够通过如下公式计算：n=-m*log(U/m)。这样就把一个统计问题转换成了一个数学问题。公式十分简洁，看到这里大脑中肯定会呈现许多的问题：
这个公式是怎么失去的？
这里波及到概率论与数理统计常识，简略来说就是散布、冀望、方差、最大似然预计。数学相干的常识比拟高级，陈希孺的《概率论与数理统计》根本能笼罩这个公式的数学原理。
这个算法的精确度怎么样？
这个问题从数学的角度，就是问方差 (标准差)。这里没法给一个具体的值，跟满桶率控制，m 的抉择无关。
这个算法相比准确计数很省空间吗？
这个毋庸置疑，不然间接准确统计就能够了。
m 和最终后果 n 须要满足什么关系？
（毕竟当没有空房间时，这个公式就有问题了。）这里间接给论断吧，随着 m 和 n 的增大，m 大概为 n 的十分之一。
2.3 HyperLogLog 算法
HyperLogLog 简称 HLL 算法，它有如下的特点：
能够实现由极小的内存开销统计出巨量的数据。在 Redis 中实现的 HyperLogLog，只须要 12K 内存就能统计 2^64 个数据。能够不便实现分布式扩大。(这个点对算法在业务零碎中落地十分要害)
了解 HLL 算法，须要如下几个知识点的铺垫：伯努利试验、和谐平均数。
伯努利试验有很多的出现形式，本文例举其中的一种：取一枚硬币，一直抛掷，直到硬币落地后果为侧面朝上。这样的执行过程称为一轮试验。从形容能够看出一轮试验实现抛掷硬币的次数是随机的。
一轮试验对应的 Java 代码实现如下：
private Random random = new Random();
/**
- 0 代表侧面
- 1 代表背面
- 抛掷直到呈现侧面
- @return 抛掷的次数
*/
public int tossCoin(){
int r,cnt=0;
do{r=random.nextInt(2);
cnt++;
}while (r<1);
return cnt;}
能够看出，每执行一轮试验就会失去一个数字，代表这轮试验抛掷硬币的次数。例如：
执行了 10 轮，可能的后果如下：
3,1,4,1,1,2,3,4,1,1
执行了 100 轮，可能的后果如下：
1,1,2,1,1,2,1,4,2,1,3,1,1,1,1,3,1,2,1,1,2,4,2,3,2,1,1,1,3,1,2,2,6,1,2,4,1,2,2,1,1,3,1,1,1,1,1,1,1,1,1,4,2,1,1,1,1,1,3,1,2,4,4,4,1,3,2,1,5,1,1,1,1,1,1,1,5,1,1,7,1,1,4,1,3,2,1,1,5,2,1,1,5,2,1,1,4,1,1,1
执行了 1000 轮，可能的后果如下：
1,2,1,2,1,3,3,3,1,1,2,2,1,2,1,1,1,1,1,2,1,7,1,1,1,2,2,1,1,3,5,2,3,2,3,1,1,3,1, …,4,1,1,1,2,2,1,3,1,1,1,2,1,1,1,2,1,4,2,2,1,2,2,2,1,1,1,2,2,2,1,1,1,2,2,1,1,3,2,6,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1
这时候问题就来了，咱们这样按下面的规定不停的抛硬币只是为了应酬无聊的工夫吗？当然不是！咱们关注的重点是：
当然，这个最大值是随机变动的，它不是一个固定的值。然而隐约中有个法则：执行的轮次越多，轮次对应的最大值也越大。数学上能够给一个很粗略的公式来拟合这种关系：n=2^p。
换言之，咱们能够通过 p 来预计 n。到这里就呈现了问题解决思路的转换：
将基数统计问题转换成概率论外面参数估计的问题。
思维转换到了数学畛域，就能够用数学的工具来解决问题。通常用概率论的思维解决问题，会面临如下几个拦路虎。
问题一：最大值不稳固，容易受到极值影响。
在概率上，对于极值咱们的解决策略是多试验几轮，通过平均值来打消极值的影响。这个就引出了第二根底知识点：和谐平均数。
数学上其实有许多的平均数计算形式：算术平均数、几何平均数、平方平均数。这里选用和谐平均数次要是打消极值的影响。通常有个笑话说，我的支出是 1 万，老板的支出是 1 亿，咱们平均收入是 5000 万，我被均匀了。如果用和谐平均数，失去的后果就是 1999.98。
对于和谐平均数的公式，非常容易了解：
对于数学，确切地说是概率论的知识点，还有很多。例如预计办法是有偏预计还是无偏预计？，预计的方差和标准差是多大？这里波及到较为底层的概率论常识，就先略过。
略过数学知识，要害的问题在于，咱们如何将待基数统计问题跟下面的伯努利试验建立联系？这两个点之间的桥梁就是 Hash 函数。第一次见识到 Hash 函数还能这样用，的确大开眼界。
对于雷同的数，通过 hash 函数生成的散列值是雷同的，这就进行了排重。当然不排除不同的数据生成同样的 hash 值，造成抵触。因为选取的 hash 函数例如 MurmurHash3 抵触率低，能够疏忽这个因素。
实际上，因为 Hash 函数生成的二进制串通常具备平均的个性，所以 Hash 函数生成的二进制串能够视为抛掷硬币的后果。
对于一个待进行基数统计的汇合 (例如一个表中符合条件的字段值)，为了升高预计的错误率，咱们分成 m 组。某个值归属于哪个组由 hash 函数生成后果对应的前几位决定，剩下的二进制串用于计算以后轮伯努利试验第一次呈现侧面时抛掷的次数，记为 p。
所以算法形容如下：
简略来说就是统计每个组最大的 p, 而后用现成的公式计算结果即达到预估的后果。
三、分布式计数外围流程
对于 Hadoop 中的入门案例 wordcount，能够发现如果用 Presto SQL 表白如下 (以 tpch 数据集 customer 表 name 字段为例)：
select w, count(1) cnt from (
select split(name,’#’) words from customer
) t1 cross join UNNEST(t1.words) AS t (w)
group by w;
能够看出相比大段的代码，SQL 解决对用于来说要简略的多。无论是哪种表达方式，外围点就是分组统计。
在 MapReduce 框架外围流程如下：
那么在 Presto，其执行流程是什么样呢？
从逻辑上，都是相似的。先分组聚合，而后汇总聚合。
四、基数统计在 Presto 中的落地
对于基数统计问题 Presto 反对两种实现形式。一种是谋求准确的 count distinct; 另一种是提供近似统计的 approx_distinct。
count distinct 的外围细节
以 SQL：select count(distinct id) from hive_table 为例。
即以 id 为主 key, 对数据进行 hash 散发，进行局部聚合，最终整体聚合。仍然是 map-reduce 的思路，只不过数据按 id 进行了散发。
aprox_distinct 的外围细节
这里就免去了基于 id 的 hash 散发策略。所以也缩小了一个 stage。至于 approx_distinct 的外部细节，根底框架 airlift 中，封装了 HyperLogLog 算法的实现，采纳的函数是 MurMurHash3 算法，生成 64 位散列值。前 6 位用于计算以后散列值所在分组 m。实现过程中还有一个很有意思的细节：基于待统计的数据量，实现中同时采纳了 Linear Count 算法和 HyperLogLog 算法。
五、业务倡议
通过下面的剖析，咱们能够发现高基数统计是一个十分耗费内存的操作，特地是在分布式系统背景下，不仅耗费内存，而且波及大量网络数据传输。如果剖析对应的业务场景，能够提供近似值而非准确值，那么就能大幅度降低零碎耗费和响应工夫，晋升用户体验。或者在设计产品的时候，对于一些场景的计数，能够优先提供近似预计，如果用户的确须要准确计数，那么在治理好用户响应工夫预期下，再提供查问准确值的接口。
了解了准确统计和近似统计的细节及各种优缺点，解决问题的思路就会更宽阔。例如：在设计存储索引时，咱们能够优先应用 HyperLogLog 统计一个字段的基数近似值，如果失去的后果不是高基数，那么咱们能够对字段构建 bitmap 索引，借此晋升数据处理的效率。
在《咱们如何走到明天：重塑世界的 6 项翻新》一书中有这样一个观点让人记忆粗浅：咱们掂量越准确，管制的能力就越强。然而它没有说的是，掂量越准确，老本就越大。
参考：
《数据库系统实现》A Linear-Time Probabilistic Counting Algorithm for Database Applications
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm