溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

HyperLogLog函數(shù)在Spark中的如何應(yīng)用

發(fā)布時(shí)間：2021-12-06 14:03:40 來源：億速云 閱讀：164 作者：小新 欄目：大數(shù)據(jù)

這篇文章給大家分享的是有關(guān)HyperLogLog函數(shù)在Spark中的如何應(yīng)用的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。


再聚合（Reaggregation）的挑戰(zhàn)

預(yù)聚合是數(shù)據(jù)分析領(lǐng)域的一個(gè)強(qiáng)大的技術(shù)手段，前提就是所要計(jì)算的指標(biāo)是可重聚合的。聚合操作，顧名思義，是滿足結(jié)合律的，所以很容易引入再聚合操作，因?yàn)榫酆喜僮骺梢栽俦贿M(jìn)一步聚合。Counts 可以在通過 SUM 再聚合，最小值可以通過 MIN 再聚合，最大值也可以通過 MAX 再聚合。而 distinct counts 是特例，無法做再聚合，例如，不同網(wǎng)站訪問者的 distinct count 的總和并不等于所有網(wǎng)站訪問者的 distinct count 值，原因很簡單，同一個(gè)用戶可能訪問了不同的網(wǎng)站，直接求和就存在了重復(fù)統(tǒng)計(jì)的問題。
Distinct count 的不可再聚合的特性造成了很大的影響，計(jì)算 distinct count 必須要訪問到最細(xì)粒度的數(shù)據(jù)，更進(jìn)一步來說，就是計(jì)算 distinct count 的查詢必須讀取每一行數(shù)據(jù)。

HyperLogLog函數(shù)在Spark中的如何應(yīng)用  
當(dāng)這個(gè)問題遇上大數(shù)據(jù)，就會產(chǎn)生新的挑戰(zhàn)：   計(jì)算過程所需的內(nèi)存和 distinct count 的結(jié)果數(shù)量是成正比的。   近年來，諸如 Apache Spark 的大數(shù)據(jù)系統(tǒng)以及諸如 Amazon Redshift 的分析型數(shù)據(jù)庫都引入了 distinct count 的近似計(jì)算功能——基數(shù)估計(jì)（cardinality estimation），利用 HyperLogLog（HLL）概率數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。   在 Spark 中使用近似計(jì)算，只需要將 COUNT(DISTINCT x) 替換為 approx_count_distinct(x [, rsd])，其中額外的參數(shù) rsd 表示最大允許的偏差率，默認(rèn)值為 5%。   Databricks 給出的 HLL 性能分析表明，只要最大偏差率大于等于 1%，Spark 的 distinct count 近似計(jì)算的運(yùn)行速度比精確計(jì)算高2～8倍。   不過，如果我們需要更小的偏差率，近似計(jì)算可能會比精確計(jì)算耗時(shí)更長。  
  2～8倍的性能提升是相當(dāng)可觀的，不過它犧牲的精確性，大于等于 1% 的最大偏差率在某些場合可能是無法被接受的。   另外，2～8倍的性能提升在預(yù)聚合所帶來的上千倍的性能提升面前也是微不足道的，那我們能做什么？  

 
 

HyperLogLog 算法回顧

答案其實(shí)就在 HyperLogLog 算法本身，Spark 通過 partition 分片執(zhí)行 MapReduce 實(shí)現(xiàn) HLL 算法的偽代碼如下所示：  

  • Map （每個(gè) partition）

    • 初始化 HLL 數(shù)據(jù)結(jié)構(gòu)，稱作 HLL sketch

    • 將每個(gè)輸入添加到 sketch 中

    • 發(fā)送 sketch

  • Reduce

    • 聚合所有 sketch 到一個(gè) aggregate sketch 中

  • Finalize

    • 計(jì)算 aggregate sketch 中的 distinct count 近似值

值得注意的是，HLL sketch 是可再聚合的：   在 reduce 過程合并之后的結(jié)果就是一個(gè) HLL sketch。   如果我們可以將 sketch 序列化成數(shù)據(jù)，那么我們就可以在預(yù)聚合階段將其持久化，在后續(xù)計(jì)算 distinct count 近似值時(shí)，就能獲得上千倍的性能提升！  
  另外這個(gè)算法還能帶來另一個(gè)同樣重要的好處：   我們不再限于性能問題向估算精度妥協(xié)（大于等于1%的估算偏差）。   由于預(yù)聚合能夠帶來上千倍的性能提升，我們可以創(chuàng)建估算偏差非常低的 HLL sketch，因?yàn)樵谏锨П兜牟樵冃阅芴嵘媲?，我們完全能夠接受預(yù)聚合階段2～5倍的計(jì)算耗時(shí)。   這在大數(shù)據(jù)業(yè)務(wù)中基本相當(dāng)于是免費(fèi)的午餐：   帶來巨大性能提升的同時(shí)，又不會對大部分業(yè)務(wù)端的用戶造成負(fù)面影響。  


 

Spark-Alchemy 簡介：HLL Native 函數(shù)

由于 Spark 沒有提供相應(yīng)功能，Swoop開源了高性能的 HLL native 函數(shù)工具包，作為 spark-alchemy項(xiàng)目的一部分，具體使用示例可以參考 HLL docs。   提供了大數(shù)據(jù)領(lǐng)域最為齊全的 HyperLogLog 處理工具，超過了 BigQuery 的 HLL 支持。  
  下圖所示為 spark-alchemy 處理 initial aggregation (通過    hll_init_agg   ), reaggregation (通過    hll_merge   ) 和 presentation (通過    hll_cardinality   )。  
HyperLogLog函數(shù)在Spark中的如何應(yīng)用  
如果你想了解 HLL sketch 的內(nèi)存使用量，可以遵循這樣一個(gè)準(zhǔn)則，HLL cardinality estimation 精度每提升2倍， HLL sketch 所需內(nèi)存提升4倍。   大部分場景下，數(shù)據(jù)行數(shù)的較少所帶來的收益遠(yuǎn)超過 HLL sketch 帶來的額外存儲。  
 

HyperLogLog 互通性

通過近似計(jì)算 distinct count 代替精確計(jì)算，并且將 HLL sketch 保存成列式數(shù)據(jù)，最終的查詢階段可以不再需要處理每一行最細(xì)粒度的數(shù)據(jù)，但是仍舊有一個(gè)隱性的需求，那就是使用 HLL 數(shù)據(jù)的系統(tǒng)需要訪問所有最細(xì)粒度的數(shù)據(jù)，這是因?yàn)槟壳斑€沒有工業(yè)標(biāo)準(zhǔn)來序列化 HLL 數(shù)據(jù)結(jié)構(gòu)。大部分實(shí)現(xiàn)，例如 BigQuery，使用了不透明的二進(jìn)制數(shù)據(jù)，也沒有相關(guān)文檔說明，這使得跨系統(tǒng)互通變得困難。這個(gè)互通性的問題極大增加了交互式分析系統(tǒng)的成本和復(fù)雜度。  
  交互式分析系統(tǒng)的一個(gè)關(guān)鍵要求是快速的查詢響應(yīng)。而這并不是很多諸如 Spark 和 BigQuery 的大數(shù)據(jù)系統(tǒng)的設(shè)計(jì)核心，所以很多場景下，交互式分析查詢通過關(guān)系型或者 NoSQL 數(shù)據(jù)庫來實(shí)現(xiàn)。如果 HLL sketch 不能實(shí)現(xiàn)數(shù)據(jù)層面的互通性，那我們又將回到原點(diǎn)。  
  為了解決這個(gè)問題，在 spark-alchemy 項(xiàng)目里，使用了公開的 存儲標(biāo)準(zhǔn)，內(nèi)置支持 Postgres 兼容的數(shù)據(jù)庫，以及 JavaScript。這樣使得 Spark 能夠成為全局的數(shù)據(jù)預(yù)處理平臺，能夠滿足快速查詢響應(yīng)的需求，例如 portal 和 dashboard 的場景。這樣的架構(gòu)可以帶來巨大的受益：  

  • 99+%的數(shù)據(jù)僅通過 Spark 進(jìn)行管理，沒有重復(fù)

  • 在預(yù)聚合階段，99+%的數(shù)據(jù)通過 Spark 處理

  • 交互式查詢響應(yīng)時(shí)間大幅縮短，處理的數(shù)據(jù)量也大幅較少

感謝各位的閱讀！關(guān)于“HyperLogLog函數(shù)在Spark中的如何應(yīng)用”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手