去重計數在企業日常分析中應用廣泛，如用戶留存、銷售統計、廣告營銷等。海量數據下的去重計數十分消耗資源，動輒幾分鐘，甚至幾小時，Apache Kylin 如何做到秒級的低延遲精確去重呢？

作者：史少鋒，Apache Kylin committer & PMC

什么是去重計數

去重計數是數據分析中的常用分析函數，指查詢某列中不同值的個數，在 SQL 中的函數是 count(distinct col)。它與 count(col) 函數的區別在于有一個 distinct 描述符，意思是去掉重復值，因此稱為去重計數。

去重計數使用廣泛，例如：在網站/app 使用統計中，PV/UV 是最常用的指標，其中 UV(unique visitor，獨立訪問用戶)就是去重后的數字，即同一個用戶的所有訪問記錄只計入一次。對于網站/app 所有者，PV (page view)代表的使用量的高低，UV 代表用戶的多少，兩個數字都很重要；只有結合兩個數字一起，才能更加準確地了解網站/app的用戶、用量增長情況。

△ 圖 1：PV/UV 統計

大數據上去重運算的難點與挑戰

去重運算因為涉及到數值的比較，因此它的計算要比單純的 PV 計數要略復雜。當數據量不大的時候，單機運行的性能或許還能忍受。但是當數據量漸長的時候，所花的時間越來越長，依靠單節點處理難以滿足，此時就需要依靠分布式框架如 MapReduce 或 Spark 等并行處理，把大數據分而治之。

學習過 MapReduce 的朋友，一定對它的 WordCount ?范例非常了解。下圖解釋了使用MapReduce 進行并行詞語出現次數統計的過程：

△ 圖2：WordCount 過程示例

試想，如果你的網站/app，訪問用戶數較大，如一千萬，訪問記錄一億(假設一個人平均點擊 10 次)。假如每個用戶的 ID 已經用 int 表示了，那么一次簡單的去重運算，需要 shuffle 的數據量就是：1億*4字節 = 400 MB = 3200 Mb。以內網千兆網 1000 Mbps 來計算，至少也需要 3 秒的傳輸；再加上磁盤讀寫、排序、序列化、反序列化操作，這樣的一個計數運算最終的時間基本在 10 秒以上。現實中情況可能更加復雜：

• 用戶標識符可能是 email、uuid、身份證、手機號等更長的字符，空間占用更大；

• 去重之前需要某些條件過濾，占用更多計算資源，如查詢過去 2 天在某幾個地區的 UV；

• 訪問記錄多(行為日志往往在數十億以上)；

• 網絡和磁盤 IO 忙，查詢性能會出現抖動。

總之，大數據上的去重計數是一個耗資源的計算，做到秒級的低延遲響應十分困難；如果這方面查詢較頻繁，必定需要優化數據結構和算法。

大數據去重算法

事實上，研究人員早就意識到了這里存在優化空間，開發了多種算法和數據結構。最著名的當屬 HyperLogLog 和 Bitmap 兩種。前不久，Kyligence工程師在 2019 年 4 月的北京 Kylin Meetup 上做了分享，并撰寫了技術文章，感興趣的同學請參考文末的“參考閱讀”【1】和【2】。

這兩種算法結構的共同點是，以非常精湊的結構存儲去重集合的特征(或完整集合)，這樣不但可以回答去重數，還可以用于后續合并運算(如昨天和今天的去重)。相比較于每次都從原始值上做去重，它的存儲和計算效率可以大大提高。

但這兩種算法也有明顯的差異點：

1) HyperLogLog，以下簡稱 HLL，它的空間復雜度非常低(log(log(n)) ，故而得名 HLL)，幾乎不隨存儲集合的大小而變化；根據精度的不同，一個 HLL 占用的空間從 1KB 到 64KB 不等。而 Bitmap 因為需要為每一個不同的 id 用一個 bit 位表示，所以它存儲的集合越大，所占用空間也越大；存儲 1 億內數字的原始 bitmap，空間占用約為 12MB?？梢钥吹?#xff0c;Bitmap 的空間要比 HLL 大約一兩個數量級。

2)HLL 支持各種數據類型作為輸入，使用方便；Bitmap 只支持 int/long 類型的數字作為輸入，因此如果原始值是 string 等類型的話，用戶需要自己提前進行到 int/long 的映射。

3)HLL 之所以支持各種數據類型，是因為其采用了哈希函數，將輸入值映射成一個二進制字節，然后對這個二進制字節進行分桶以及再判斷其首個1出現的最后位置，來估計目前桶中有多少個不同的值。由于使用了哈希函數，以及使用概率估計的方式，因此 HLL 算法的結果注定是非精確的；盡管 HLL 采用了多種糾正方式來減小誤差，但無法改變結果非精確的事實，即便最高精度，理論誤差也超過了 1%。

4)Bitmap 忠實地為每個 id 使用一個 bit 位來代表其出現(1)或不出現(0)；所以只要能保證不同的用戶被映射成不同的 id 值，那么 Bitmap 的結果就是精確的。

綜合看下來，這兩個算法都有各自明顯的優劣：HLL 各種好，但是不精確；Bitmap 雖然占用空間比 HLL多，但能保證精確。

為什么精確去重如此重要

其實，Kylin 在最開始的時候只支持 HLL 算法，因為 HLL 在大數據領域被普遍使用：無奈數據量大性能要求高呀，那就損失點精度吧。如果有人問起有誤差的事情該怎么回答呢，當時我們的說法是：在幾千萬上億的結果上，你還在意那 1% 的誤差嗎？

然而，用戶不是這么想的，在一些場景下，有誤差的結果是難以被接受的。

例如：在渠道導流或廣告投放方面，費用的結算按導流或點擊用戶數來統計的。有誤差的數字，對于業務雙方來說都是難以接受的：購買方擔心多付錢，服務方擔心少收錢。更何況，HLL 的誤差率也是有幾率的，也就是說，可能 99% 的情況下它的錯誤范圍在 1% 內，剩下 1% 的情況下誤差有多大就不好說了，萬一大不少，豈不要造成生產事故了？

此外，如果 UV 結果還要做乘除法，那么這個誤差率會進一步放大。例如用戶增長率=今天用戶數/昨天用戶數；如果分子的數字偏大，分母的數字偏小，那么最終的誤差就更大了，并且你還不知道誤差是多少。一億用戶基數下，1% 的誤差就是一百萬用戶，對于流量比較平穩的網站/app，這點誤差率足以將實際運營效果直接掩蓋，從而失去指導業務的意義。所以，如果你不想某天半夜被老板或業務方叫起來查數據，那還是想想辦法一次解決準確性這個難題吧，以確保日后睡個安穩覺。

所以，沒過多久，我們便意識到，僅有近似算法是不夠的，Kylin 需要支持精確的去重，否則在重要場景中將失去機會。

Kylin 精確去重是如何做到的

如果讀者對 Kylin 有一定了解的話會知道，Kylin 會按照用戶指定的維度、度量對數據進行預計算，將計算出來的度量值，以維度的值為索引存儲在 Cube (默認 HBase 表)中，例如每天的銷售記錄數、銷售額等。

△ 圖3：OLAP Cube

對于 count distinct 度量，只存儲一個數字是不夠的，因為用戶的查詢可能需要遍歷許多單元格然后再做合并，單純的 int 數字不能再做去重合并。因此，過去Kylin 會將 HLL 對象整個序列化后，存儲在 Cube 中維度值所對應的 cell 中。查詢時，將其反序列化，交給 SQL 執行器做合并運算(通過 Kylin 的聚合函數)，最后返回結果時，再從 HLL 對象中獲取去重數。同樣的道理，只要把 HLL替換成 Bitmap，理論上就可以實現精確的去重計數的存儲和查詢。

思路清楚了，但這里依然面臨兩個挑戰：

1)Bitmap 空間占用大

如前面提到的，Bitmap 的空間占用相比于 HLL 是比較大的，但是相比于存儲原始值的集合來說，它又是最小的。一個存儲最大基數是1億的 Bitmap，大約需要(1億/8) 個字節，也就是 12MB，當維度多、基數高的時候，可想而知，這個 Cube 構建出來會占用很大存儲。

調研以后，Kylin 引入了帶壓縮的 Bitmap 實現：Roaring Bitmap。Roaring Bitmap 把一個 32 位的 Integer 劃分為高 16 位和低 16 位，取高 16 位找到該條數據所對應的 key，每個 key 都有自己的一個 Container。把剩余的低 16 位放入該 Container 中。依據不同的場景，有 3 種不同的 Container，分別是 Array Container、Bitmap Container 和 Run Container，它們分別通過不同的壓縮方法來壓縮。實踐證明，Roaring Bitmap 可以顯著減小 Bitmap 的存儲空間和內存占用。

2)Bitmap 只接受 int/long 類型作為輸入

前面提到過，Bitmap 只接受int/long(或可以直接 cast 成這兩種的類型)為輸入值。因此當去重列的類型不是這兩個的時候，用戶需要做一個 1:1 的映射，方能利用 Bitmap 進行去重，這樣使用的難度大大提高了。

比較巧的是，Kylin 默認會對維度構建數據字典(dictionary)，然后通過字典將 string 等值 1:1 映射成 int 值，這樣在后續 Cube 運算和存儲時，使用 int 值代替 string 值，可以大大減少空間占用。讓 Kylin 對去重列也用字典先進行編碼，豈不就可以支持 Bitmap 了？

基本可行，但是 Kylin 維度字典不是完全適用去重。主要原因是：

a) 維度字典是保序的(order preserving)，因此構建后不能再追加修改;

b) 維度字典是對應于每一個 segment 來創建的，當構建下一個 segment 的時候，會重新創建另一個字典。這樣會導致同一個 string 值在兩個 segment 中可能會被編碼成不同的 int 值；或者不同的 string 值，在不同的 cube segment 中可能被編碼成相同的 int 值，那么用在 bitmap 的話，會造成跨 segment 的去重合并后的數值錯誤，所以行不通。

因此，Kylin 需要引入一個可以被追加的、保證在所有segment 中做到唯一映射的字典；因為只是為了回答去重數，它不需要支持反向映射，為了跟普通字典相區分，我們稱之為全局字典(Global Dictionary)(代碼中稱為 AppendTrieDictionary)，意思是它服務于所有 segment 的(當然也可以服務多個 cube)。跟普通字典相比，全局字典放棄了保序性，也不再支持雙向映射(從 int 再解碼回原始 string 值)，它是完全為非 int 數值的精確去重而準備的，在使用中請注意區分。更多關于全局字典的介紹，請參考文末的“參考閱讀”文章【3】【4】。

在解決了上述挑戰之后，Kylin 就可以對海量數據集，根據用戶建立的模型進行 Cube 計算，各維度組合、各維度值組合下的去重集合以 Bitmap 形式存儲下來：

△ 圖 4：含 Bitmap 的 Cube 構建示例

查詢時基于 Bitmap 進行后續運算，如：

select count(distinct 用戶ID) from access_log where 日期 = ‘2019/09/09’

△ 圖5：含Bitmap 的查詢示例

工作還不是到這里就結束了，在多年的實踐中，Kylin 社區開發者們不斷完善 Kylin 的精確去重能力，使得其越來越健壯和完善，其中的一些重要改進包括：

1. 使用Segment Global Dictionary

前面提到，為了確?？?segment 的合并時，同一值可以被始終映射成一個 int，所以開發了全局字典(Global dictionary)，它是可以增長的。那么隨著數據的增加，這個全局字典會逐漸變大，加載它會變得吃力；雖然全局字典內部做了分頁處理，不用一次全部加載到內存，但是如果內存不足的話，依然會影響效率。而有些場景中，業務只看按天的去重結果，不做跨天的去重合并，這樣一來，維護全局的映射也就沒必要了，而只需要維護一個 segment 級別的字典映射(segment 往往按天構建)，就能夠滿足需求。這樣的局部全局字典相比于正常全局字典會更小，更易于加載到內存中處理；當構建完成后，它甚至可以被刪除以節省空間；缺點是，這樣的 cube 的 segment 將不支持合并，因此在使用的時候需要略加注意。

2. 切分小字典提速 Cube 構建

剛提到，全局字典變大以后，在構建的時候，會加載其中的某些頁到內存，內存不夠的時候再載出；如果輸入數據比較亂序，分布在全局字典的很多頁，那么這種載入載出會消耗大量時間。所以，Kylin 引入一種優化策略，在進行編碼之前，先翻出每一個 Mapper 數據中的去重列的 distinct 值，然后用此值去全局字典中查找對應的 int 值，然后生成一個僅供當前 mapper 使用的小字典；在 Cube 構建的時候，使用此小字典而非大字典給當前 Mapper 來使用，從而減少字典頁換入換出操作，提高構建性能。

3. 使用 Hive/Spark 分布式構建外部全局字典

使用全局字典也存在一些局限，例如：

1)字典的構建在任務節點單機上完成，存在性能瓶頸，當有多個去重任務并行執行時，造成任務等待；

2)全局字典不能用于解碼，也不能被其它大數據應用直接使用，導致數據資產浪費。

因此，社區貢獻者提出將全局字典外置成一張 Hive 表(兩個列，一個是原始值，一個是編碼的int值)，利用 Hive/Spark 進行分布式的生成和追加，并在 Cube 構建的時候可以做分布式映射，使 Kylin 任務節點的負載得以減輕，同時外部全局字典可以很容易地被復用，成為企業的數據資產。目前這個功能已經開發完成，將在 Kylin 3.0 中正式發布，敬請期待。

4. Bitmap 數值直接返回

Kylin 保存 Bitmap 是為了 UV 值的二次計算；然而有的查詢是比較簡單的，Cube 預計算已經一步到位了，Bitmap 不會參與二次計算，這種情況下各個HBase 節點就不需要將 Bitmap 傳輸給Kylin，而只要把結果值返回就可以，從而大大減少各個 HBase 節點到Kylin查詢節點的網絡傳輸。Kylin 會自動判斷查詢是否精準匹配預計算結果，決定是否使用此優化。

為什么 Kylin 是唯一能做到秒級去重的引擎

我們知道，Apache Kylin 是為數不多的能夠在超大數據集上做到亞秒級低延遲的 OLAP 分析引擎；Apache Kylin 基于獨特的預計算思想，將整個過程分為離線的 Cube 構建過程和在線的 Cube 查詢兩個階段，且這兩步可以分在兩個獨立集群，互不影響。雖然 Cube 構建會花費一定的時間，但帶來的是后續查詢的大大提速，對于頻繁需要進行檢索/查詢的場景來說，一次構建多次受益，是非常值得的。而沒有預計算的引擎，每次都需要從原始數據開始計算，不但占用大量計算資源，而且在性能、并發和效率方面都難以滿足業務用戶的苛刻要求。

△ 圖6：Apache Kylin 架構圖

引入 Bitmap 和全局字典后，Kylin 實現了秒級的精確去重查詢，在大數據領域可以說是唯一的通用型方案(這句話來自某大型互聯網用戶)。有讀者可能會問，大數據分析引擎這么多，Spark SQL，Presto，ClickHouse，Phoenix，Redshift等等，難道它們做不到嗎？其實沒有什么是做不到，只是受架構的限制，沒有預先的數據準備，要想做到快速的精確去重，需要投入大量的計算資源，例如數據都預熱在內存中、節點之間使用萬兆網連接等等，但這恰恰是多數用戶無法承擔的。此外，隨著數據量和并發的增長，性能和穩定性往往會出現顯著下降，造成用戶體驗急劇下降，也就失去了可行性。當然，如果用戶對性能和并發的要求不高，使用頻率也不高，那么這些技術都是可以滿足的。

總結

Kylin 既支持非精確去重，也支持精確去重，用戶可以根據自己的場景要求選擇合適的去重算法。Kylin 精確去重相比于其它技術的優勢在于：

• 數據離線自動生成壓縮 Bitmap，查詢時沒有數據 shuffle 和落盤，保證了低延遲的同時 100% 準確；

• UV 值可二次合并，滿足靈活查詢的需要；

• 查詢使用標準 SQL 的標準函數，無縫兼容已有系統；

• 既支持整數類型，也支持 string 等類型；

• 使用簡單，無需編程開發；

• 基于 Kylin 的 UDAF，Bitmap 還可以做交集(intersect)運算，實現留存、漏斗等分析功能；

• 已經在 eBay、美團點評、滴滴、丁香園、Vivo、華為、滿幫集團等大型用戶生產環境平穩使用數年。

Apache Kylin 精確去重功能，是 Kylin 社區開發者們在各種復雜情況下不斷研究和努力的成果，凝結了許多人的汗水和智慧，在此向孫業銳、高大月、康凱森、鐘陽紅、靳國衛等同學表示感謝！引入 Bitmap 后，Kylin 的能力大大加強，使用場景得到豐富，這部分內容我們將在下次文章中為您分享。

想體驗 Kylin 秒級精確去重？

Kylin 官網文檔中有操作指南哦：https://kylin.apache.org/docs/tutorial/create_cube.html

參考閱讀

【1】陶加濤 《大數據分析常用去重算法分析『HyperLogLog 篇』》 https://kyligence.io/zh/blog/count-distinct-hyperloglog/

【2】陶加濤 《大數據分析常用去重算法分析『Bitmap 篇』》 https://kyligence.io/zh/blog/count-distinct-bitmap/

【3】康凱森，《Apache Kylin 精確去重和全局字典權威指南》， https://blog.bcmeng.com/post/kylin-distinct-count-global-dict.html

【4】孫業銳，賀小橋《Apache Kylin精確計數與全局字典揭秘》， https://hexiaoqiao.github.io/blog/2016/11/27/exact-count-and-global-dictionary-of-apache-kylin/

往期案例與實踐

Kylin 賦能物聯網大數據分析

如何在 Kylin 中優雅地使用 Spark

如何簡化 SQL 語句之 UDF 實踐

Python + Apache Kylin 讓數據分析更加簡單！

解讀 Kylin 3.0.0 | 更敏捷、更高效的 OLAP 引擎

"Apache and Apache Kylin are either registered trademarks or trademarks of The Apache Software Foundation in the US and/or other countries. No endorsement by The Apache Software Foundation is implied by the use of these marks."

總結

以上是生活随笔為你收集整理的查询去重_如何在 1 秒内做到大数据精准去重？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。