去重分析在企業(yè)日常分析中的使用頻率非常高，如何在大數(shù)據(jù)場景下快速地進(jìn)行去重分析一直是一大難點。在近期的 Apache Kylin 沙龍上， Kyligence 大數(shù)據(jù)研發(fā)工程師陶加濤為大家揭開了大數(shù)據(jù)分析常用去重算法的神秘面紗。

首先，請大家思考一個問題：在大數(shù)據(jù)處理領(lǐng)域中，什么環(huán)節(jié)是你最不希望見到的?以我的觀點來看，shuffle 是我最不愿意見到的環(huán)節(jié)，因為一旦出現(xiàn)了非常多的 shuffle，就會占用大量的磁盤和網(wǎng)絡(luò) IO，從而導(dǎo)致任務(wù)進(jìn)行得非常緩慢。而今天我們所討論的去重分析，就是一個會產(chǎn)生非常多 shuffle 的場景，先來看以下場景：

 

 

我們有一張商品訪問表，表上有 item 和 user_id 兩個列，我們希望求商品的 UV，這是去重非常典型的一個場景。我們的數(shù)據(jù)是存儲在分布式平臺上的，分別在數(shù)據(jù)節(jié)點 1 和 2 上。

我們從物理執(zhí)行層面上想一下這句 SQL 背后會發(fā)生什么故事：首先分布式計算框架啟動任務(wù), 從兩個節(jié)點上去拿數(shù)據(jù), 因為 SQL group by 了 item 列, 所以需要以 item 為 key 對兩個表中的原始數(shù)據(jù)進(jìn)行一次 shuffle。我們來看看需要 shuffle 哪些數(shù)據(jù)：因為 select/group by 了 item，所以 item 需要 shuffle 。但是，user_id 我們只需要它的一個統(tǒng)計值，能不能不 shuffle 整個 user_id 的原始值呢?

如果只是簡單的求 count 的話, 每個數(shù)據(jù)節(jié)點分別求出對應(yīng) item 的 user_id 的 count, 然后只要 shuffle 這個 count 就行了，因為 count 只是一個數(shù)字, 所以 shuffle 的量非常小。但是由于分析的指標(biāo)是 count distinct，我們不能簡單相加兩個節(jié)點 user_id 的 count distinct 值，我們只有得到一個 key 對應(yīng)的所有 user_id 才能統(tǒng)計出正確的 count distinct 值，而這些值原先可能分布在不同的節(jié)點上，所以我們只能通過 shuffle 把這些值收集到同一個節(jié)點上再做去重。而當(dāng) user_id 這一列的數(shù)據(jù)量非常大的時候，需要 shuffle 的數(shù)據(jù)量也會非常大。我們其實最后只需要一個 count 值，那么有辦法可以不 shuffle 整個列的原始值嗎?我下面要介紹的兩種算法就提供了這樣的一種思路，使用更少的信息位，同樣能夠求出該列不重復(fù)元素的個數(shù)(基數(shù))。

精確算法: Bitmap

 

 

第一種要介紹的算法是一種精確的去重算法，主要利用了 Bitmap 的原理。Bitmap 也稱之為 Bitset，它本質(zhì)上是定義了一個很大的 bit 數(shù)組，每個元素對應(yīng)到 bit 數(shù)組的其中一位。例如有一個集合[2，3，5，8]對應(yīng)的 Bitmap 數(shù)組是[001101001]，集合中的 2 對應(yīng)到數(shù)組 index 為 2 的位置，3 對應(yīng)到 index 為 3 的位置，下同，得到的這樣一個數(shù)組，我們就稱之為 Bitmap。很直觀的，數(shù)組中 1 的數(shù)量就是集合的基數(shù)。追本溯源，我們的目的是用更小的存儲去表示更多的信息，而在計算機(jī)最小的信息單位是 bit，如果能夠用一個 bit 來表示集合中的一個元素，比起原始元素，可以節(jié)省非常多的存儲。

這就是最基礎(chǔ)的 Bitmap，我們可以把 Bitmap 想象成一個容器，我們知道一個 Integer 是 32 位的，如果一個 Bitmap 可以存放最多 Integer.MAX_VALUE 個值，那么這個 Bitmap 最少需要 32 的長度。一個 32 位長度的 Bitmap 占用的空間是 512 M (2^32/8/1024/1024)，這種 Bitmap 存在著非常明顯的問題：這種 Bitmap 中不論只有 1 個元素或者有 40 億個元素，它都需要占據(jù) 512 M 的空間�；氐絼偛徘� UV 的場景，不是每一個商品都會有那么多的訪問，一些爆款可能會有上億的訪問，但是一些比較冷門的商品可能只有幾個用戶瀏覽，如果都用這種 Bitmap，它們占用的空間都是一樣大的，這顯然是不可接受的。

升級版 Bitmap: Roaring Bitmap

 

 

對于上節(jié)說的問題，有一種設(shè)計的非常的精巧 Bitmap，叫做 Roaring Bitmap，能夠很好地解決上面說的這個問題。我們還是以存放 Integer 值的 Bitmap 來舉例，Roaring Bitmap 把一個 32 位的 Integer 劃分為高 16 位和低 16 位，取高 16 位找到該條數(shù)據(jù)所對應(yīng)的 key，每個 key 都有自己的一個 Container。我們把剩余的低 16 位放入該 Container 中。依據(jù)不同的場景，有 3 種不同的 Container，分別是 Array Container、Bitmap Container 和 Run Container，下文將一一介紹。

 

 

首先第一種，是 Roaring Bitmap 初始化時默認(rèn)的 Container，叫做 Array Container。Array Container 適合存放稀疏的數(shù)據(jù)，Array Container 內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是一個 short array，這個 array 是有序的，方便查找。數(shù)組初始容量為 4，數(shù)組最大容量為 4096。超過最大容量 4096 時，會轉(zhuǎn)換為 Bitmap Container。這邊舉例來說明數(shù)據(jù)放入一個 Array Container 的過程：有 0xFFFF0000 和 0xFFFF0001 兩個數(shù)需要放到 Bitmap 中, 它們的前 16 位都是 FFFF，所以他們是同一個 key，它們的后 16 位存放在同一個 Container 中 ; 它們的后 16 位分別是 0 和 1, 在 Array Container 的數(shù)組中分別保存 0 和 1 就可以了，相較于原始的 Bitmap 需要占用 512M 內(nèi)存來存儲這兩個數(shù)，這種存放實際只占用了 2+4=6 個字節(jié)(key 占 2 Bytes，兩個 value 占 4 Bytes，不考慮數(shù)組的初始容量)。

 

 

第二種 Container 是 Bitmap Container，其原理就是上文說的 Bitmap。它的數(shù)據(jù)結(jié)構(gòu)是一個 long 的數(shù)組，數(shù)組容量固定為 1024，和上文的 Array Container 不同，Array Container 是一個動態(tài)擴(kuò)容的數(shù)組。這邊推導(dǎo)下 1024 這個值：由于每個 Container 還需處理剩余的后 16 位數(shù)據(jù)，使用 Bitmap 來存儲需要 8192 Bytes(2^16/8), 而一個 long 值占 8 個 Bytes，所以一共需要 1024(8192/8)個 long 值。所以一個 Bitmap container 固定占用內(nèi)存 8 KB(1024 * 8 Byte)。當(dāng) Array Container 中元素到 4096 個時，也恰好占用 8 k(4096*2Bytes)的空間，正好等于 Bitmap 所占用的 8 KB。而當(dāng)你存放的元素個數(shù)超過 4096 的時候，Array Container 的大小占用還是會線性的增長，但是 Bitmap Container 的內(nèi)存空間并不會增長，始終還是占用 8 K，所以當(dāng) Array Container 超過最大容量(DEFAULT_MAX_SIZE)會轉(zhuǎn)換為 Bitmap Container。

我們自己在 Kylin 中實踐使用 Roaring Bitmap 時，我們發(fā)現(xiàn) Array Container 隨著數(shù)據(jù)量的增加會不停地 resize 自己的數(shù)組，而 Java 數(shù)組的 resize 其實非常消耗性能，因為它會不停地申請新的內(nèi)存，同時老的內(nèi)存在復(fù)制完成前也不會釋放，導(dǎo)致內(nèi)存占用變高，所以我們建議把 DEFAULT_MAX_SIZE 調(diào)得低一點，調(diào)成 1024 或者 2048，減少 Array Container 后期 reszie 數(shù)組的次數(shù)和開銷。

 

 

最后一種 Container 叫做 Run Container，這種 Container 適用于存放連續(xù)的數(shù)據(jù)。比如說 1 到 100，一共 100 個數(shù)，這種類型的數(shù)據(jù)稱為連續(xù)的數(shù)據(jù)。這邊的 Run 指的是 Run Length Encoding(RLE)，它對連續(xù)數(shù)據(jù)有比較好的壓縮效果。原理是對于連續(xù)出現(xiàn)的數(shù)字, 只記錄初始數(shù)字和后續(xù)數(shù)量。例如: 對于 [11, 12, 13, 14, 15, 21, 22]，會被記錄為 11, 4, 21, 1。很顯然，該 Container 的存儲占用與數(shù)據(jù)的分布緊密相關(guān)。最好情況是如果數(shù)據(jù)是連續(xù)分布的，就算是存放 65536 個元素，也只會占用 2 個 short。而最壞的情況就是當(dāng)數(shù)據(jù)全部不連續(xù)的時候，會占用 128 KB 內(nèi)存。

 

 

總結(jié)：用一張圖來總結(jié) 3 種 Container 所占的存儲空間，可以看到元素個數(shù)達(dá)到 4096 之前，選用 Array Container 的收益是最好的，當(dāng)元素個數(shù)超過了 4096 時，Array Container 所占用的空間還是線性的增長，而 Bitmap Container 的存儲占用則與數(shù)據(jù)量無關(guān)，這個時候 Bitmap Container 的收益就會更好。而 Run Container 占用的存儲大小完全看數(shù)據(jù)的連續(xù)性, 因此只能畫出一個上下限范圍 [4 Bytes, 128 KB]。

在 Kylin 中的應(yīng)用

 

 

我們再來看一下 Bitmap 在 Kylin 中的應(yīng)用，Kylin 中編輯 measure 的時候，可以選擇 Count Distinct，且 Return Type 選為 Precisely，點保存就可以了。但是事情沒有那么簡單，剛才上文在講 Bitmap 時，一直都有一個前提，放入的值都是數(shù)值類型，但是如果不是數(shù)值類型的值，它們不能夠直接放入 Bitmap，這時需要構(gòu)建一個全區(qū)字典，做一個值到數(shù)值的映射，然后再放入 Bitmap 中。

 

 

在 Kylin 中構(gòu)建全局字典，當(dāng)列的基數(shù)非常高的時候，全局字典會成為一個性能的瓶頸。針對這種情況，社區(qū)也一直在努力做優(yōu)化，這邊簡單介紹幾種優(yōu)化的策略，更詳細(xì)的優(yōu)化策略可以見文末的參考鏈接。

 

 

1)當(dāng)一個列的值完全被另外一個列包含，而另一個列有全局字典，可以復(fù)用另一個列的全局字典。

 

 

2)當(dāng)精確去重指標(biāo)不需要跨 Segment 聚合的時候，可以使用這個列的 Segment 字典代替(這個列需要字典編碼)。在 Kylin 中，Segment 就相當(dāng)于時間分片的概念。當(dāng)不會發(fā)生跨 Segments 的分析時，這個列的 Segment 字典就可以代替這個全局字典。

 

 

3)如果你的 cube 包含很多的精確去重指標(biāo)，可以考慮將這些指標(biāo)放到不同的列族上。不止是精確去重，像一些復(fù)雜 measure，我們都建議使用多列族去存儲，可以提升查詢的性能。

雖然 Roaring Bitmap 這種算法能大大地減少存儲開銷，但是隨著數(shù)據(jù)量的增大，它依然面臨著存儲上的壓力。下面我們將要介紹的 HyperLogLog(下稱 HLL)是一種非精確的去重算法，它的特點是具有非常優(yōu)異的空間復(fù)雜度(幾乎可以達(dá)到常數(shù)級別)。

 

 

HLL 算法需要完整遍歷所有元素一次，而非多次或采樣;該算法只能計算集合中有多少個不重復(fù)的元素，不能給出每個元素的出現(xiàn)次數(shù)或是判斷一個元素是否之前出現(xiàn)過;多個使用 HLL 統(tǒng)計出的基數(shù)值可以融合。

 

 

 

 

HLL 算法有著非常優(yōu)異的空間復(fù)雜度，可以看到它的空間占用隨著基數(shù)值的增長并沒有變化。HLL 后面不同的數(shù)字代表著不同的精度，數(shù)字越大，精度越高，占用的空間也越大，可以認(rèn)為 HLL 的空間占用只和精度成正相關(guān)。

HLL 算法原理感性認(rèn)知

 

 

HLL 算法的原理會涉及到比較多的數(shù)學(xué)知識，這邊對這些數(shù)學(xué)原理和證明不會展開。舉一個生活中的例子來幫助大家理解 HLL 算法的原理：比如你在進(jìn)行一個實驗，內(nèi)容是不停地拋硬幣，記錄你連續(xù)拋到正面的次數(shù)(這是數(shù)學(xué)中的伯努利過程，感興趣同學(xué)可以自行研究下);如果你最多的連拋正面記錄是 3 次，那可以想象你并沒有做這個實驗太多次，如果你最長的連拋正面記錄是 20 次，那你可能進(jìn)行了這個實驗上千次。

一種理論上存在的情況是，你非常幸運(yùn)，第一次進(jìn)行這個實驗就連拋了 20 次正面，我們也會認(rèn)為你進(jìn)行了很多次這個實驗才得到了這個記錄，這就會導(dǎo)致錯誤的預(yù)估;改進(jìn)的方式是請 10 位同學(xué)進(jìn)行這項實驗，這樣就可以觀察到更多的樣本數(shù)據(jù)，降低出現(xiàn)上述情況的概率。這就是 HLL 算法的核心思想。

HLL 算法具體實現(xiàn)

 

 

HLL 會通過一個 hash 函數(shù)來求出集合中所有元素的 hash 值(二進(jìn)制表示的 hash 值，就可以理解為一串拋硬幣正反面結(jié)果的序列)，得到一個 hash 值的集合，然后找出該 hash 值集合中，第一個 1 出現(xiàn)的最晚的位置。例如有集合為 [010, 100, 001], 集合中元素的第一個 1 出現(xiàn)的位置分別為 2, 1, 3，可以得到里面最大的值為 3，故該集合中第一個 1 出現(xiàn)的最晚的位置為 3。因為每個位置上出現(xiàn) 1 的概率都是 1/2，所以我們可以做一個簡單的推斷，該集合中有 8 個不重復(fù)的元素。

可以看到這種簡單的推斷計算出來集合的基數(shù)值是有較大的偏差的，那如何來減少偏差呢?正如我上面的例子里說的一樣，HLL 通過多次的進(jìn)行試驗來減少誤差。那它是如何進(jìn)行多次的實驗的呢?這里 HLL 使用了分桶的思想，上文中我們一直有提到一個精度的概念，比如說 HLL(10)，這個 10 代表的就是取該元素對應(yīng) Hash 值二進(jìn)制的后 10 位，計算出記錄對應(yīng)的桶，桶中會記錄一個數(shù)字，代表對應(yīng)到該桶的 hash 值的第一個 1 出現(xiàn)的最晚的位置。如上圖，該 hash 值的后 10 位的 hash 值是 0000001001，轉(zhuǎn)成 10 進(jìn)制是 9，對應(yīng)第 9 號桶，而該 hash 值第一個 1 出現(xiàn)的位置是第 6 位，比原先 9 號桶中的數(shù)字大，故把 9 號桶中的數(shù)字更新為 6�？梢钥吹酵暗膫�數(shù)越多，HLL 算法的精度就越高，HLL(10) 有 1024(210) 個桶，HLL(16) 有 65536(216) 個桶。同樣的，桶的個數(shù)越多，所占用的空間也會越大。

 

 

剛才的例子我們省略了一些細(xì)節(jié)，為了讓大家不至于迷失在細(xì)節(jié)中而忽視了重點，真實的 HLL 算法的完整描述見上圖，這邊的重點是計算桶中平均數(shù)時使用調(diào)和平均數(shù)。調(diào)和平均數(shù)的優(yōu)點是可以過濾掉不健康的統(tǒng)計值，使用算術(shù)平均值容易受到極值的影響(想想你和馬云的平均工資)，而調(diào)和平均數(shù)的結(jié)果會傾向于集合中比較小的元素。HLL 論文中還有更多的細(xì)節(jié)和參數(shù)，這邊就不一一細(xì)舉，感興趣的同學(xué)可以自己閱讀下論文。

HLL 評估

 

 

HLL 的誤差分布服從正態(tài)分布，它的空間復(fù)雜度: O(m log2log2N), N 為基數(shù), m 為桶個數(shù)。這邊給大家推導(dǎo)一下它的空間復(fù)雜度，我有 264 個的不重復(fù)元素 (Long. MAX_VALUE)，表達(dá)為二進(jìn)制一個數(shù)是 64 位，這是第一重 log2, 那么第一個 1 最晚可能出現(xiàn)在第 64 位。64 需要 6 個 bit (26=64) 就可以存儲，這是第二重 log2。如果精度為 10，則會有 1024 個桶，所以最外面還要乘以桶的個數(shù)。由于需要完整的遍歷元素一遍，所以它的時間復(fù)雜度是一個線性的時間復(fù)雜度。

在 Kylin 中的應(yīng)用

 

 

在 Kylin 中使用 HLL 非常簡單，在編輯度量的頁面選擇 COUNT DISTINCT，Return Type 選為非 Precisely 的其他選項，大家根據(jù)自己的需求選擇不同的精度就可以愉快地使用了。

總結(jié)

 

 

我們回到最開始的去重場景，看看使用了 Bitmap 和 HLL 會給我們帶來什么增益：無優(yōu)化 case 下，每個 item 對應(yīng)的 user_id 就可以看成存儲原始值的一個集合;在使用 Bitmap 優(yōu)化的 case 下，每個 item 對應(yīng)的 user_id 就可以看成一個 Bitmap 實例，同理 HLL 就是一個 HLL 的實例，Bitmap/HLL 實例占用的空間都會比直接存儲原始值的集合要小，這就達(dá)到了我們開始提的減少 shuffle 數(shù)據(jù)量的需求。

Q&A

Q1：您好，問一下關(guān)于精確去重的問題， 我選擇了非精確去重，最后的誤差率有時候會比界面上提示的值要高一些，這是為什么?

A1：首先 HLL 的誤差分布服從正態(tài)分布，也就是說是在 99% 的情況下是這個誤差，同時 HLL 對于基數(shù)比較低的情況，誤差會偏高。如果你的基數(shù)比較低的話，我推薦使用精確去重。

Q2：我想要了解一下 Bitmap 在 Kylin 中，它最終落盤在 HBase 里面是什么樣子的?

A2：在 HBase 中存儲的當(dāng)然都是 Bytes。這個問題其實就是 Bitmap 的序列化的形式，Roaring Bitmap 提供了序列化和反序列化的實現(xiàn)，你也可以寫自己的序列化 / 反序列化的實現(xiàn)。

Q3：Roaring Bitmap 里這些 container 要我們自己手動的指定嗎?

A3：不需要，Roaring Bitmap 會自動選擇使用哪個 Container。

作者簡介：作者簡介：陶加濤，Kyligence 大數(shù)據(jù)研發(fā)工程師，主要負(fù)責(zé) Kyligence Enterprise 存儲與查詢計算部分。

標(biāo)簽： [db:TAGG]

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。