当前位置：首页>C++>正文

5大底層邏輯，淺談HyperLogLog底層算法邏輯

C++12-25

5大底層邏輯，淺談HyperLogLog底層算法邏輯

本文是對hyperloglog原理的梳理，整理自知乎答主張戎的回答：大數據領域的近似分析方法（一）。內容涉及高中數學的期望，大學的高等數學以及概率論。

5大底層邏輯、就像文章所言，HyperLogLog是大數據基數統計中的常見方法，無論是 Redis，Spark 還是 Flink 都提供了這個功能，其目的就是在一定的誤差范圍內，用最小的空間復雜度來估算一個數據流的基數。

文章目錄

- 一、基數估計法介紹
- 二、HyperLogLog部分
- - 1、理論基礎介紹
  - 2、引入調和平均數
  - 3、誤差修正
  - 4、Reids中的HyperLogLog
- 三、具體案例講解

一、基數估計法介紹

引出概念：基數估計算法

這種算法（基數估計算法）雖然精準度很高，但是使用的空間復雜度卻很高。那么是否存在一些近似的方法，可以估算出數據流的基數呢？其實，在近幾十年，不少的學者都提出了很多基數估算的方法，包括 LogLog，HyperLogLog，MinCount 等等

二、HyperLogLog部分

1、理論基礎介紹

1、

列舉基數估計算法相關的理論基礎

這里借助拋硬幣的實驗案例，我認為這是理解該算法的關鍵性的第一步（第一個關鍵點）

其實上面的案例并不難理解，無非就是一個概率的數學邏輯，每次正面1/2，拋兩次正面1/2 * 1/2…

2、

概念比較官方，你甚至可以抽象這幾個點：

ρ(x)表示第一個1出現的位置
max ρ(x) 表示一個集合中的最大值，即ρ(x)的最大值
M等于最大的ρ(x)，元素個數為2的M次
此處僅含有一個桶，即幾個桶就會有幾個maxρ(x)，此處只會有一個ρ(x)

明白相關參數的含義（這是第二個關鍵點）

舉一個驗證的案例：

集合中的數字分別為（此處的數字理解為hash結果后的數字）

針對這16個數子，可以構成一個ρ(x)集合，從上往下依次為[0, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]，那么就可以得出maxρ(x)的值為4，然后這個數字放在一個桶里面，即數據的個數為2的4次方，16個。

2、引入調和平均數

1、

針對第一點中只出現一個桶，而導致的誤差情況，該算法采用求平均值減小誤差。當然，進行均值處理也是有很多種的，該算法采用的是調和平均數。（Loglog使用的是算數平均數，HyperLoglog使用的是調和平均數）

知道這個調和平均數這個公式的含義（這是第三個關鍵點）

2、

此處將數據一分為2，前半部分數字表示具體的數，作用和上面第一點的案例相同，后半部分數字的長度用來表示桶的個數。以此再結合調和平均數，于是就得出了最下面的公式

3、

舉例驗證說明

還是上面例子，此時，將一個4位長的數字拆分為2+2。此時的：

X = X4 + X3 + X2 + X1

X = Xb+2 + Xb+1 + Xb + x1 （b = 2）

即桶的個數為2的b次，4個。在調和平均數公式中，就是m = 4。

再得出ρ(x)的最大值，我們可以得出每個桶里面的maxρ(x)都等于2，在公式的基礎上，可以進行計算，如下圖：

當然，這里的計算過程并沒有什么實質性的作用，更像是一種別人給了你結論共識，然后你去反推驗證公式的正確性。

看明白對應的對應的驗證過程（這是第四個關鍵點）

4、

進一步推演該公式

這里的演算過程，本人已經還給了高數老師，明白意思即可，直接跳過。

3、誤差修正

使用上面的算法是能夠進行數字的估算，但是是存在誤差的，所以針對E的值（基數的值）還需要進行一個微調

知道在調和平均數的基礎上，還會根據對應的數值的大小進行誤差修正（這是第五個關鍵點）

下面就是具體的范圍說明：

1、小范圍：E <= 5m / 2

2、中范圍：E值不做調整

3、大范圍：E > 2^32 / 30

4、Reids中的HyperLogLog

HyperLogLog是基數估算算法的其中一種體現，其他類似的算法還有LogLog、MinCount等。我是一名Java開發人員，所有接觸HyperLogLog的場景為使用Redis的一種高級數據結構HyperLogLog，使用該結構可以在數據量很大的情況下，只需要使用很小的空間就能夠近似的統計出所有數據的基數。可用于處理網站的日活統計。

①Redis對于一個輸入的字符串，首先得到64位的hash值。

②用前14位來定位桶的位置，即桶的位個數為2^14個，16384個)。

③后面50位為伯努利過程（拋硬幣的過程），每個桶有6bit，記錄第一次出現1的位置count（6bit最大能表示64-1，63 > 50，滿足條件），如果count > oldcount，就用count替換oldcount。

6bit（每個桶的大小） * 16384個 / 8（1B = 8bit） / 1024（B轉KB） = 12KB，即這就是我們常說的，HyperLogLog所占用的內存只有12KB。

熟悉Redis五種基本數據類型底層的小伙伴應該都知道，Redis對于內存的壓榨是有一手的，這在HyperLogLog中同樣如此。如果比較多的計數值都是0，那么就會采用稀疏存儲的結構。

對于連續多個計數值為0的桶，Redis使用的存儲方式是：00xxxxxx，前綴兩個0，后面6位的值加1表示有連續多少個桶的計數值為0，由于6bit最大能表示64個桶，所以Redis又設計了另一種表示方法：01xxxxxx yyyyyyyy，這樣后面14bit就可以表示16384個桶了，而一個初始狀態的HyperLogLog對象只需要用2個字節來存儲。

如果連續的桶數都不是0，那么Redis的表示方式為1vvvvvxx，即為連續(xx+1)個桶的計數值都是(vvvvv+1)。例如，10011110表示連續3個8。這里使用5bit，最大只能表示32。因此，當某個計數值大于32時，Redis會將這個HyperLogLog對象調整為密集存儲。

Redis從稀疏存儲轉換到密集存儲的條件是：

任意一個計數值從 32 變成 33，因為VAL指令已經無法容納，它能表示的計數值最大為 32
稀疏存儲占用的總字節數超過 3000 字節，這個閾值可以通過 hll_sparse_max_bytes 參數進行調整。

三、具體案例講解

圖片來源張戎的案例：（理解了第二部門的內容，這部分就不難理解了）

該圖表示，將數據分為兩部分，桶占用了6位，即桶有2^6 = 64個，即下方的空格有64個

此處獲取ρ(x)的方式于我們上面說到的有區別，他是從右往左開始，但是思想是一致的，該數字得出p(x) = 2，數據不斷的增加，不斷的增加，遇到相同的桶的位置的時候，如果新的ρ的值更大，則