HyperLogLog在Presto和ClickHouse中的相容及性能差異

前言

目前HyperLogLog是一種主流的算法，用于估算海量同類型資料的不同值，是以幾乎所有的計算/查詢引擎都有了想關的實作，當然雖然可能其它的優化算法，但算法主體相同，然而不同引擎實作的存儲過程大同小異，如果想要在不同引擎之前共享中間結果，就需要深入了解不同引擎的存儲實作。

Presto是Facebook開源的，完全基于記憶體的并⾏計算，分布式SQL互動式查詢引擎是一種Massively parallel processing (MPP)架構，多個節點管道式執⾏⽀持任意資料源（通過擴充式Connector元件），資料規模GB~PB級。

ClickHouse 是一個真正的列式資料庫管理系統（DBMS)。在 ClickHouse 中，資料始終是按列存儲的，包括矢量（向量或列塊）執行的過程。隻要有可能，操作都是基于矢量進行分派的，而不是單個的值，這被稱為«矢量化查詢執行»，它有利于降低實際的資料處理開銷。

但礙于Presto在實際工作中會出現不穩定性的情況，便推動了Presto HLL計算的遷移，以期更加快速地響應使用者的查詢請求，這便是這篇部落格的背景。

HLL資料共享流程

Presto/Hive上的基數預估的中間結果，實際上是一組格式化的位元組數組，而ClickHouse并不支援直接加載HLL的位元組數組，是以就需要擴充ClickHouse的聚合函數，即開發UDAF（自己寫C++代碼啦，目前CH并不是很友善地編寫UDF/UDAF），完成Presto引擎上計算産生的中間結果的讀取加載過程。至于CH上的記憶體資料存儲格式，依然采用CH本身的實作，以減少工作量。

但需要注意的是，CH即使已經能夠直接加載來自Presto的HLL資料，考慮到Presto和CH在計算HyperLogLog時采用的Hash邏輯不同，一個是小端一個大端，依然不能直接聚合兩個引擎各自産生的中間數組，是以目前的模式是單向的，未來考慮雙向聚合。

簡言之，整個過程就是Presto HLL序列化 => 自定義資料格式 => 寫入CH => 調用CH UDAF聚合，最終完成Presto HLL資料在CH上的聚合過程。

HLL聚合性能比較

Presto

資料總量（條）	HLL資料讀取以及merge耗時（機關秒）
100000	4
200000	9
500000	23
1000000	44

ClickHouse

資料總量	HLL資料讀取及Merge耗時（機關秒）
100000	5
200000	18
500000	46
1000000	91

性能差異分析

源表(viprpdm.ads_mer_high_dim_detail_df)靜态統計資訊：

select count(*) from test_table where dt=‘20210111’;

dt分區的資料總量N_total=2675032

select count(*) from test_table where dt=‘20210111’ and length(test_hll) <=2060;

dt分區中位元組數組長度小于等于2060的總量N_2060=2670580

select count(*) from test_table where dt=‘20210111’ and length(test_hll) <= 1024;

dt分區中位元組數組長度小于等于1024的總量N_1024=1112470

其中rate_1024 = N_1024 / N_total = 0.416，大約占總量的一半

由上的統計資訊可以看到，源表中的HLL資料的位元組數組長度，基本上所有的字段值的長度都約為4096個桶的一半，這裡以Dense類型的存儲格式為主說明性能差異的原因。

一般地Dense類型的資料，會使用一個與桶數相同長度的資料，來儲存每一個value，舉例4096個桶，就對應了4096個slot的數組，其中每個slot會存入一個6位長度的數來表示不同值。

應用程式中最本的計算單元是按位元組來處理，而一個位元組需要8位的比特表示，是以Presto為了更能高效地來存儲和處理HyperLogLog計算的中間結果，會将桶中應該存放的6位值對齊到

4位，即VALUE_BITS >> 1，這樣桶數也會降低到原來的一半BUCKET_BITS >> 1，那麼在不考慮溢出的情況下，就隻需要[2048 * 4 / 8 = 1024, 4096 * 6/8]範圍内的存儲就可以完成計算。

由于對6位的值對齊到4位，必然會出現實際值溢出問題，即某個桶的值超過了2^4，Presto内部會建立一個溢出數組，來儲存溢出的值，這樣依然在溢出的場景能夠很好的工作，雖然這樣的做法相對于直接使用一個位元組來表示桶值複雜，但通常情況下溢出的現象不會很頻繁，是以這種設計在更普遍的情況下會帶來存儲和計算的性能提升。

總結

綜上，目前從Presto HLL資料到CK的中間結果的存儲格式，采用一個位元組來存放完整的桶值，是以抛卻必要的頭部資訊外，需要4096*6/8=3072 bytes。

實際上CK本身在自己的HyperLogLog實作中，也是采用了6位表示的存儲格式，但總的數組大小為(4096*6 + 7)/8，是以可能在大部分情況下，HLL計算性優劣如下：

中間轉換格式 < CK存儲格式 < Presto存儲格式

是以，如果想要更好地打通ClickHouse與Presto之前的HyperLogLog資料，在應用層後續重點工作當是完善ClickHouse側加載Presto HLL資料的過程。

參考項目位址：