探究 Presto SQL 引擎 (4)- 统计计数
作者：vivo 互联网用户运营开发团队 - Shuai Guangying
本篇文章介绍了统计计数的基本原理以及 Presto 的实现思路，精确统计和近似统计的细节及各种优缺点，并给出了统计计数在具体业务使用的建议。
系列文章：
一、背景
学习 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 为
则取 age 字段位图中 age=40 的向量：110001。统计其中 1 的个数，即可得到最终结果。
假设查询 SQL 更复杂一些：
则取 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 代码实现如下：
可以看出，每执行一轮实验就会得到一个数字，代表这轮实验抛掷硬币的次数。例如：
执行了 10 轮，可能的结果如下：
执行了 100 轮，可能的结果如下：
执行了 1000 轮，可能的结果如下：
这时候问题就来了，我们这样按上面的规则不停的抛硬币只是为了应付无聊的时间吗？当然不是！我们关注的重点是：
当然，这个最大值是随机变动的，它不是一个固定的值。但是隐约中有个规律：执行的轮次越多，轮次对应的最大值也越大。数学上可以给一个很粗略的公式来拟合这种关系：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 字段为例)：
可以看出相比大段的代码，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
版权声明: 本文为 InfoQ 作者【vivo互联网技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/1a1d5ad0a16079f6c08a762d7】。文章转载请联系作者。
官方公众号：vivo互联网技术，ID：vivoVMIC 2020-07-10 加入
分享 vivo 互联网技术干货与沙龙活动，推荐最新行业动态与热门会议。
评论