HyperLogLog函数在Spark中的高级应用

预聚合是高性能分析中的常用技术，例如，每小时100亿条的网站访问数据可以通过对常用的查询纬度进行聚合，被降低到1000万条访问统计，这样就能降低1000倍的数据处理量，从而在查询时大幅减少计算量，提升响应速度。更高层的聚合可以带来进一步的性能提升，例如，在时间维按天聚合，或者通过站点而不是URL聚合。

本文，我们将介绍 spark-alchemy这个开源库中的 HyperLogLog 这一个高级功能，并且探讨它是如何解决大数据中数据聚合的问题。首先，我们先讨论一下这其中面临的挑战。

再聚合（Reaggregation）的挑战

预聚合是数据分析领域的一个强大的技术手段，前提就是所要计算的指标是可重聚合的。聚合操作，顾名思义，是满足结合律的，所以很容易引入再聚合操作，因为聚合操作可以再被进一步聚合。Counts 可以在通过 SUM 再聚合，最小值可以通过 MIN 再聚合，最大值也可以通过 MAX 再聚合。而 distinct counts 是特例，无法做再聚合，例如，不同网站访问者的 distinct count 的总和并不等于所有网站访问者的 distinct count 值，原因很简单，同一个用户可能访问了不同的网站，直接求和就存在了重复统计的问题。 Distinct count 的不可再聚合的特性造成了很大的影响，计算 distinct count 必须要访问到最细粒度的数据，更进一步来说，就是计算 distinct count 的查询必须读取每一行数据。

当这个问题遇上大数据，就会产生新的挑战：计算过程所需的内存和 distinct count 的结果数量是成正比的。近年来，诸如 Apache Spark 的大数据系统以及诸如 Amazon Redshift 的分析型数据库都引入了 distinct count 的近似计算功能——基数估计（cardinality estimation），利用 HyperLogLog（HLL）概率数据结构来实现。在 Spark 中使用近似计算，只需要将 COUNT(DISTINCT x) 替换为 approx_count_distinct(x [, rsd])，其中额外的参数 rsd 表示最大允许的偏差率，默认值为 5%。Databricks 给出的 HLL 性能分析表明，只要最大偏差率大于等于 1%，Spark 的 distinct count 近似计算的运行速度比精确计算高2～8倍。不过，如果我们需要更小的偏差率，近似计算可能会比精确计算耗时更长。 2～8倍的性能提升是相当可观的，不过它牺牲的精确性，大于等于 1% 的最大偏差率在某些场合可能是无法被接受的。另外，2～8倍的性能提升在预聚合所带来的上千倍的性能提升面前也是微不足道的，那我们能做什么？

HyperLogLog 算法回顾

答案其实就在 HyperLogLog 算法本身，Spark 通过 partition 分片执行 MapReduce 实现 HLL 算法的伪代码如下所示：

• Map （每个 partition）
  • 初始化 HLL 数据结构，称作 HLL sketch
  • 将每个输入添加到 sketch 中
  • 发送 sketch
• Reduce
  • 聚合所有 sketch 到一个 aggregate sketch 中
• Finalize
  • 计算 aggregate sketch 中的 distinct count 近似值

值得注意的是，HLL sketch 是可再聚合的：在 reduce 过程合并之后的结果就是一个 HLL sketch。如果我们可以将 sketch 序列化成数据，那么我们就可以在预聚合阶段将其持久化，在后续计算 distinct count 近似值时，就能获得上千倍的性能提升！ 另外这个算法还能带来另一个同样重要的好处：我们不再限于性能问题向估算精度妥协（大于等于1%的估算偏差）。由于预聚合能够带来上千倍的性能提升，我们可以创建估算偏差非常低的 HLL sketch，因为在上千倍的查询性能提升面前，我们完全能够接受预聚合阶段2～5倍的计算耗时。这在大数据业务中基本相当于是免费的午餐：带来巨大性能提升的同时，又不会对大部分业务端的用户造成负面影响。

Spark-Alchemy 简介：HLL Native 函数

由于 Spark 没有提供相应功能，Swoop开源了高性能的 HLL native 函数工具包，作为 spark-alchemy项目的一部分，具体使用示例可以参考 HLL docs。提供了大数据领域最为齐全的 HyperLogLog 处理工具，超过了 BigQuery 的 HLL 支持。 下图所示为 spark-alchemy 处理 initial aggregation (通过 hll_init_agg), reaggregation (通过 hll_merge) 和 presentation (通过 hll_cardinality)。

如果你想了解 HLL sketch 的内存使用量，可以遵循这样一个准则，HLL cardinality estimation 精度每提升2倍， HLL sketch 所需内存提升4倍。大部分场景下，数据行数的较少所带来的收益远超过 HLL sketch 带来的额外存储。

HyperLogLog 互通性

通过近似计算 distinct count 代替精确计算，并且将 HLL sketch 保存成列式数据，最终的查询阶段可以不再需要处理每一行最细粒度的数据，但是仍旧有一个隐性的需求，那就是使用 HLL 数据的系统需要访问所有最细粒度的数据，这是因为目前还没有工业标准来序列化 HLL 数据结构。大部分实现，例如 BigQuery，使用了不透明的二进制数据，也没有相关文档说明，这使得跨系统互通变得困难。这个互通性的问题极大增加了交互式分析系统的成本和复杂度。 交互式分析系统的一个关键要求是快速的查询响应。而这并不是很多诸如 Spark 和 BigQuery 的大数据系统的设计核心，所以很多场景下，交互式分析查询通过关系型或者 NoSQL 数据库来实现。如果 HLL sketch 不能实现数据层面的互通性，那我们又将回到原点。 为了解决这个问题，在 spark-alchemy 项目里，使用了公开的 存储标准，内置支持 Postgres 兼容的数据库，以及 JavaScript。这样使得 Spark 能够成为全局的数据预处理平台，能够满足快速查询响应的需求，例如 portal 和 dashboard 的场景。这样的架构可以带来巨大的受益：

• 99+%的数据仅通过 Spark 进行管理，没有重复
• 在预聚合阶段，99+%的数据通过 Spark 处理
• 交互式查询响应时间大幅缩短，处理的数据量也大幅较少

总结

总结一下，本文阐述了预聚合这个常用技术手段如何通过 HyperLogLog 数据结构应用到 distinct count 操作，这不仅带来了上千倍的性能提升，也能够打通 Apache Spark、RDBM 甚至 JavaScript。虽然有些难以置信，但通过 HLL sketch 以及 Spark 强大的扩展能力，我们确确实实能够得到这样一份免费的午餐。

本文的编译：辰山，阿里巴巴计算平台事业部 EMR 高级开发工程师，目前从事大数据存储方面的开发和优化工作。

欢迎点赞+收藏+转发朋友圈素质三连