译者：辰石，阿里巴巴计算平台事业部EMR团队技术专家，目前从事大数据存储以及Spark相关方面的工作。
预先聚合是一种常用高性能分析的手段，通过该方法处理数据的规模可以下降1000倍， 例如网站访问记录可以产生100亿条记录，通过预先聚合可以减少到1000万条记录， 因此数据的处理成本以及处理时间都会相应的减少，此外用户还可以通过更高层次的聚合达到进一步的提升，例如在时间维度上按天进行聚合， 或者按照网站维度上进行聚合而非按照URL来进行聚合。
本篇文章主要介绍开源库spark-alchemy中的HyperLogLog功能 以及他是如何解决数据聚合过程中遇到挑战，首先介绍这些挑战
Reaggregation的挑战
Reaggregation的成立存在先决条件， 预先计算的维度可以再次进行聚合， 在字典释义中聚合表示可聚合性，通过进一步扩展该语义来解释reaggregation - 具有可以再次进行聚合的聚合， 求和，最大值，最小值都是可以reaggregation的， 但是distinct count是不支持reaggregation的，主要因为存在二次计数的问题， 统计每个网站的访问人数的总和并不等于访问网站的总人数，这是由于单个访问者可以访问多个网站。
这种不可重新聚合的特性使得计算distinct count的系统必须访问最细粒度的数据，因此每个查询需要访问每一行数据去统计distinct count。
在大数据领域， distinct counts存在另外一个问题，在计算过程需要的内存大小是更需要统计不同结果集的大小成正比的，为了避免上述问题，近年来一些大数据平台如Apache Spark 以及面向分析的数据库如Amazon RedShift引入基数估计的算法，该算法使用HyperLogLog（HLL）去估计distinct counts， 在spark 中如果要使用基数估计算法，只要使用approx_count_distinct(x [, rsd])代替COUNT(DISTINCT x)就可以运行， 其中可选参数rsd代表可以容忍的误差， 在databricks的测试报告， HLL的聚合性能可以达到精确计算distinct count性能的2-8倍，误差率保持在1%以上，用户可以追求更高精度，但是HLL算法的运行时间可能要比精确计算distinct count时间更长。
2-8倍性能的提升的代价是误差率始终保持在1%以上， 这在某些场景下是不可接受的， 此外在预先聚合能带来1000倍的性能提升面前， 2-8倍性能显得微不足道， 对此我们能做些什么？下面首先介绍下HLL算法。
HyperLogLog算法
HLL算法在Spark 处理流程可以分为以下几个部分
Map阶段
- 初始化HLL sketch数据结构
- 为每个HLL sketch加入输入
- 发送HLL sketch
Reduce
- 合并所有的HLL sketches到聚合的sketch
Finalize
- 从聚合的sketch中计算出distinct count的估计值
HLL sketch是支持reaggreation， reduce阶段合并产生的依旧是HLL sketch，用户可以序列化该结果，并将该结果持久化存储，作为预先聚合的一部分，为后续计算distinct count提供输入，这样就可以带来1000倍的提升。
这种方法还能另外一种好处，通过该方法用户可以将误差率控制1%以内，由于预先聚合可以带来1000倍的提升，我们可以花费更长的时间来计算HLL以便达到更小的误差率，在预先聚合阶段，花费2-5倍的计算预先聚合时间是可以接受的， 对大多数用户而言，性能提升的同时基本没有任何其他方面的牺牲。
Spark-Alchemy介绍： HLL 功能
由于Spark社区不支持HLL功能，Swoop将这部分功能作为spark-alchemy库的一部分进行开源，用户可以参照HLL文档提供的样例， 相比BigQuery的HLL支持，Spark alchemy提供了更加丰富的功能。
下图显示spark alchemy HLL是如何处理聚合的初始化（hll_init_agg）, 重新聚合(hll_merg) 以及最后结果的展示(hll_cardinality).
如果用户担心HLL sketches的存储开销， 通过以下规则可以进行简单的估算： 精度提高2倍， HLL sketches的存储开销将会提升4倍， 在大部分应用程序中，记录数目的减少带来的存储开销的减少远远超过HLL sketch增加的开销
HyperLogLog互操作性
Distinct count精确计算以及估算模式的相互切换以及将HLL sketches保存为列式数据可以避免用户在查询的时候遍历所有记录数据， 但是系统在准备HLL数据的时候还是需要访问所有的记录数据。 此外对于HLLsketches的序列化业界也没有统一的标准，所以HLL的数据在不同的系统中不能够共享， 这种互操作性的不便利性增加交互分析系统的分析成本以及复杂度。
交互式分析系统要求快速的响应时间，但是这个要求不是大数据系统核心的设计目标，这就是为什么现在交互式分析还运行在在关系型或者NoSQL数据库上的原因，没有HLL sketches的互操作性便利，用户可能在交互式查询还是使用原有的方式。
为了解决这个问题， spark alchemey在开发HLL相关功能时，提供了一种存储格式以及原生支持Postgres兼容的数据库， 这样对于要求快速响应时间的系统而言， spark就可以作为数据预处理统一平台， 这种架构的好处如下
- 99%以上的数据通过spark进行管理，没有副本
- 99%以上处理发生在spark支持，包括预先聚合
- 交互式查询性能更高以及需要的资源更少
总结
本文展示了在使用spark alchemy 提供HLL数据结构，预先聚合如何为distinct counts的性能带来1000倍的性能提升， 除此以外由于提供了一种存储格式， HLL数据结构可以在spark， RDBMS甚至JavasCript之间共享。
高阶HLL处理只是spark alchemy提供的功能之一，如果你还有其他需求可以登录spark-alchemy网页获取更多的信息。
最后Swoop工程和科学团队感谢Databricks工程以及支持团队的合作。
