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

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

潁州網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),潁州網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為潁州上千余家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營銷網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的潁州做網(wǎng)站的公司定做！

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

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

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

 
 

HyperLogLog 算法回顧

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

  • Map （每個 partition）

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

    • 將每個輸入添加到 sketch 中

    • 發(fā)送 sketch

  • Reduce

    • 聚合所有 sketch 到一個 aggregate sketch 中

  • Finalize

    • 計算 aggregate sketch 中的 distinct count 近似值

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


 

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

由于 Spark 沒有提供相應(yīng)功能，Swoop開源了高性能的 HLL native 函數(shù)工具包，作為 spark-alchemy項目的一部分，具體使用示例可以參考 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)存使用量，可以遵循這樣一個準(zhǔn)則，HLL cardinality estimation 精度每提升2倍， HLL sketch 所需內(nèi)存提升4倍。   大部分場景下，數(shù)據(jù)行數(shù)的較少所帶來的收益遠(yuǎn)超過 HLL sketch 帶來的額外存儲。  
 

HyperLogLog 互通性

通過近似計算 distinct count 代替精確計算，并且將 HLL sketch 保存成列式數(shù)據(jù)，最終的查詢階段可以不再需要處理每一行最細(xì)粒度的數(shù)據(jù)，但是仍舊有一個隱性的需求，那就是使用 HLL 數(shù)據(jù)的系統(tǒng)需要訪問所有最細(xì)粒度的數(shù)據(jù)，這是因為目前還沒有工業(yè)標(biāo)準(zhǔn)來序列化 HLL 數(shù)據(jù)結(jié)構(gòu)。大部分實現(xiàn)，例如 BigQuery，使用了不透明的二進(jìn)制數(shù)據(jù)，也沒有相關(guān)文檔說明，這使得跨系統(tǒng)互通變得困難。這個互通性的問題極大增加了交互式分析系統(tǒng)的成本和復(fù)雜度。  
  交互式分析系統(tǒng)的一個關(guān)鍵要求是快速的查詢響應(yīng)。而這并不是很多諸如 Spark 和 BigQuery 的大數(shù)據(jù)系統(tǒng)的設(shè)計核心，所以很多場景下，交互式分析查詢通過關(guān)系型或者 NOSQL 數(shù)據(jù)庫來實現(xiàn)。如果 HLL sketch 不能實現(xiàn)數(shù)據(jù)層面的互通性，那我們又將回到原點。  
  為了解決這個問題，在 spark-alchemy 項目里，使用了公開的 存儲標(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ù)據(jù)量也大幅較少

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

分享題目：HyperLogLog函數(shù)在Spark中的如何應(yīng)用
文章路徑：http://muchs.cn/article46/iegehg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、標(biāo)簽優(yōu)化、外貿(mào)網(wǎng)站建設(shè)、移動網(wǎng)站建設(shè)、App設(shè)計、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站優(yōu)化排名