HyperLogLog函数在Spark中的如何应用

这篇文章给大家分享的是有关HyperLogLog函数在Spark中的如何应用的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

颍州网站建设公司创新互联,颍州网站设计制作，有大型网站制作公司丰富经验。已为颍州上千余家提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱，请找那个售后服务好的颍州做网站的公司定做！

再聚合（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函数在Spark中的如何应用”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！

分享文章：HyperLogLog函数在Spark中的如何应用
浏览地址：http://cqcxhl.cn/article/iegehg.html

重庆分公司，新征程启航

HyperLogLog函数在Spark中的如何应用

再聚合（Reaggregation）的挑战

HyperLogLog 算法回顾

Spark-Alchemy 简介：HLL Native 函数

HyperLogLog 互通性

其他资讯