HyperLogLog 算法的原理講解以及Redis是如何應(yīng)用它的

這期內(nèi)容當(dāng)中小編將會給大家?guī)碛嘘P(guān)HyperLogLog 算法的原理講解以及Redis是如何應(yīng)用它的，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

問題原形

如果要實(shí)現(xiàn)這么一個(gè)功能：

統(tǒng)計(jì) APP或網(wǎng)頁 的一個(gè)頁面，每天有多少用戶點(diǎn)擊進(jìn)入的次數(shù)。同一個(gè)用戶的反復(fù)點(diǎn)擊進(jìn)入記為 1 次。

聰明的你可能會馬上想到，用 HashMap 這種數(shù)據(jù)結(jié)構(gòu)就可以了，也滿足了去重。的確，這是一種解決方法，除此之外還有其它的解決方案。

問題雖不難，但當(dāng)參與問題中的變量達(dá)到一定數(shù)量級的時(shí)候，再簡單的問題都會變成一個(gè)難題。假設(shè) APP 中日活用戶達(dá)到百萬或千萬以上級別的話，我們采用 HashMap 的做法，就會導(dǎo)致程序中占用大量的內(nèi)存。

我們下面嘗試估算下 HashMap 的在應(yīng)對上述問題時(shí)候的內(nèi)存占用。假設(shè)定義HashMap 中 Key 為 string 類型，value 為 bool。key 對應(yīng)用戶的Id,value是是否點(diǎn)擊進(jìn)入。明顯地，當(dāng)百萬不同用戶訪問的時(shí)候。此HashMap 的內(nèi)存占用空間為：100萬 * (string + bool)。

條件選擇

可以說，在上述問題目前現(xiàn)有的解決方案中，HashMap 是內(nèi)存占用量最多的一種。如果統(tǒng)計(jì)量不多，那么可以使用這種方法解決問題，實(shí)現(xiàn)起來也簡單。

除此之外還有B+ 樹，Bitmap 位圖，以及該文章主要介紹的 HyperLogLog算法解決方案。

在一定條件允許下，如果允許統(tǒng)計(jì)在巨量數(shù)據(jù)面前的誤差率在可接受的范圍內(nèi)，1000萬瀏覽量允許最終統(tǒng)計(jì)出少了一兩萬這樣子，那么就可以采用HyperLogLog算法來解決上面的計(jì)數(shù)類似問題。

HyperLogLog

HyperLogLog，下面簡稱為HLL，它是 LogLog 算法的升級版，作用是能夠提供不精確的去重計(jì)數(shù)。存在以下的特點(diǎn)：

• 代碼實(shí)現(xiàn)較難。

• 能夠使用極少的內(nèi)存來統(tǒng)計(jì)巨量的數(shù)據(jù)，在 Redis 中實(shí)現(xiàn)的 HyperLogLog，只需要12K內(nèi)存就能統(tǒng)計(jì)2^64個(gè)數(shù)據(jù)。

• 計(jì)數(shù)存在一定的誤差，誤差率整體較低。標(biāo)準(zhǔn)誤差為 0.81% 。

• 誤差可以被設(shè)置輔助計(jì)算因子進(jìn)行降低。

稍微對編程中的基礎(chǔ)數(shù)據(jù)類型內(nèi)存占用有了解的同學(xué)，應(yīng)該會對其只需要12K內(nèi)存就能統(tǒng)計(jì)2^64個(gè)數(shù)據(jù)而感到驚訝。為什么這樣說呢，下面我們舉下例子：

取 Java 語言來說，一般long占用8字節(jié)，而一字節(jié)有8位，即：1 byte = 8 bit，即long數(shù)據(jù)類型最大可以表示的數(shù)是：2^63-1。對應(yīng)上面的2^64個(gè)數(shù)，假設(shè)此時(shí)有2^63-1這么多個(gè)數(shù)，從 0 ~ 2^63-1，按照long以及1k = 1024字節(jié)的規(guī)則來計(jì)算內(nèi)存總數(shù)，就是：((2^63-1) * 8/1024)K，這是很龐大的一個(gè)數(shù)，存儲空間遠(yuǎn)遠(yuǎn)超過12K。而 HyperLogLog 卻可以用 12K 就能統(tǒng)計(jì)完。

伯努利試驗(yàn)

在認(rèn)識為什么HyperLogLog能夠使用極少的內(nèi)存來統(tǒng)計(jì)巨量的數(shù)據(jù)之前，要先認(rèn)識下伯努利試驗(yàn)。

伯努利試驗(yàn)是數(shù)學(xué)概率論中的一部分內(nèi)容，它的典故來源于拋硬幣。

硬幣擁有正反兩面，一次的上拋至落下，最終出現(xiàn)正反面的概率都是50%。假設(shè)一直拋硬幣，直到它出現(xiàn)正面為止，我們記錄為一次完整的試驗(yàn)，間中可能拋了一次就出現(xiàn)了正面，也可能拋了4次才出現(xiàn)正面。無論拋了多少次，只要出現(xiàn)了正面，就記錄為一次試驗(yàn)。這個(gè)試驗(yàn)就是伯努利試驗(yàn)。

那么對于多次的伯努利試驗(yàn)，假設(shè)這個(gè)多次為n次。就意味著出現(xiàn)了n次的正面。假設(shè)每次伯努利試驗(yàn)所經(jīng)歷了的拋擲次數(shù)為k。第一次伯努利試驗(yàn)，次數(shù)設(shè)為k1，以此類推，第n次對應(yīng)的是kn。

其中，對于這n次伯努利試驗(yàn)中，必然會有一個(gè)最大的拋擲次數(shù)k，例如拋了12次才出現(xiàn)正面，那么稱這個(gè)為k_max，代表拋了最多的次數(shù)。

伯努利試驗(yàn)容易得出有以下結(jié)論：

1. n 次伯努利過程的投擲次數(shù)都不大于 k_max。

2. n 次伯努利過程，至少有一次投擲次數(shù)等于 k_max

最終結(jié)合極大似然估算的方法，發(fā)現(xiàn)在n和k_max中存在估算關(guān)聯(lián)：n = 2^(k_max) 。這種通過局部信息預(yù)估整體數(shù)據(jù)流特性的方法似乎有些超出我們的基本認(rèn)知，需要用概率和統(tǒng)計(jì)的方法才能推導(dǎo)和驗(yàn)證這種關(guān)聯(lián)關(guān)系。

例如下面的樣子：

第一次試驗(yàn): 拋了3次才出現(xiàn)正面，此時(shí) k=3，n=1
第二次試驗(yàn): 拋了2次才出現(xiàn)正面，此時(shí) k=2，n=2
第三次試驗(yàn): 拋了6次才出現(xiàn)正面，此時(shí) k=6，n=3
第n 次試驗(yàn)：拋了12次才出現(xiàn)正面，此時(shí)我們估算， n = 2^12

假設(shè)上面例子中實(shí)驗(yàn)組數(shù)共3組，那么 k_max = 6，最終 n=3，我們放進(jìn)估算公式中去，明顯： 3 ≠ 2^6 。也即是說，當(dāng)試驗(yàn)次數(shù)很小的時(shí)候，這種估算方法的誤差是很大的。

估算的優(yōu)化

在上面的3組例子中，我們稱為一輪的估算。如果只是進(jìn)行一輪的話，當(dāng) n 足夠大的時(shí)候，估算的誤差率會相對減少，但仍然不夠小。

那么是否可以進(jìn)行多輪呢？例如進(jìn)行 100 輪或者更多輪次的試驗(yàn)，然后再取每輪的 k_max，再取平均數(shù)，即: k_mx/100。最終再估算出 n。下面是LogLog的估算公式：

上面公式的DVLL對應(yīng)的就是n，constant是修正因子，它的具體值是不定的，可以根據(jù)實(shí)際情況而分支設(shè)置。m代表的是試驗(yàn)的輪數(shù)。頭上有一橫的R就是平均數(shù)：(k_max_1 + ... + k_max_m)/m。

這種通過增加試驗(yàn)輪次，再取k_max平均數(shù)的算法優(yōu)化就是LogLog的做法。而 HyperLogLog和LogLog的區(qū)別就是，它采用的不是平均數(shù)，而是調(diào)和平均數(shù)。調(diào)和平均數(shù)比平均數(shù)的好處就是不容易受到大的數(shù)值的影響。下面舉個(gè)例子：

求平均工資:

A的是1000/月，B的30000/月。采用平均數(shù)的方式就是： (1000 + 30000) / 2 = 15500

采用調(diào)和平均數(shù)的方式就是： 2/(1/1000 + 1/30000) ≈ 1935.484

明顯地，調(diào)和平均數(shù)比平均數(shù)的效果是要更好的。下面是調(diào)和平均數(shù)的計(jì)算方式，∑ 是累加符號。

扯上關(guān)系

上面的內(nèi)容我們已經(jīng)知道，在拋硬幣的例子中，可以通過一次伯努利試驗(yàn)中出現(xiàn)的k_max來估算n。

那么這種估算方法如何和下面問題有所關(guān)聯(lián)呢？

統(tǒng)計(jì) APP或網(wǎng)頁 的一個(gè)頁面，每天有多少用戶點(diǎn)擊進(jìn)入的次數(shù)。同一個(gè)用戶的反復(fù)點(diǎn)擊進(jìn)入記為 1 次

HyperLogLog是這樣做的。對于輸入的數(shù)據(jù)，進(jìn)行下面幾個(gè)步驟：

1.比特串

通過hash函數(shù)，將數(shù)據(jù)轉(zhuǎn)為比特串，例如輸入5，便轉(zhuǎn)為：101。為什么要這樣轉(zhuǎn)化呢？

是因?yàn)橐蛼佊矌艑?yīng)上，比特串中，0 代表了反面，1 代表了正面，如果一個(gè)數(shù)據(jù)最終被轉(zhuǎn)化了 10010000，那么從右往左，從低位往高位看，我們可以認(rèn)為，首次出現(xiàn) 1 的時(shí)候，就是正面。

那么基于上面的估算結(jié)論，我們可以通過多次拋硬幣實(shí)驗(yàn)的最大拋到正面的次數(shù)來預(yù)估總共進(jìn)行了多少次實(shí)驗(yàn)，同樣也就可以根據(jù)存入數(shù)據(jù)中，轉(zhuǎn)化后的出現(xiàn)了 1 的最大的位置 k_max 來估算存入了多少數(shù)據(jù)。

2.分桶

分桶就是分多少輪。抽象到計(jì)算機(jī)存儲中去，就是存儲的是一個(gè)以單位是比特(bit)，長度為 L 的大數(shù)組 S ，將 S 平均分為 m 組，注意這個(gè) m 組，就是對應(yīng)多少輪，然后每組所占有的比特個(gè)數(shù)是平均的，設(shè)為 P。容易得出下面的關(guān)系：

• L = S.length

• L = m * p

• 以 K 為單位，S 占用的內(nèi)存 = L / 8 / 1024

在 Redis 中，HyperLogLog設(shè)置為：m=16834，p=6，L=16834 * 6。占用內(nèi)存為=16834 * 6 / 8 / 1024 = 12K

形象化為：

  第0組     第1組                       .... 第16833組
[000 000] [000 000] [000 000] [000 000] .... [000 000]

3. 對應(yīng)

現(xiàn)在回到我們的原始APP頁面統(tǒng)計(jì)用戶的問題中去。

• 設(shè) APP 主頁的 key 為： main

• 用戶 id 為：idn , n->0,1,2,3....

在這個(gè)統(tǒng)計(jì)問題中，不同的用戶 id 標(biāo)識了一個(gè)用戶，那么我們可以把用戶的 id 作為被hash的輸入。即：

hash(id) = 比特串

不同的用戶 id，必然擁有不同的比特串。每一個(gè)比特串，也必然會至少出現(xiàn)一次 1 的位置。我們類比每一個(gè)比特串為一次伯努利試驗(yàn)。

現(xiàn)在要分輪，也就是分桶。所以我們可以設(shè)定，每個(gè)比特串的前多少位轉(zhuǎn)為10進(jìn)制后，其值就對應(yīng)于所在桶的標(biāo)號。假設(shè)比特串的低兩位用來計(jì)算桶下標(biāo)志，此時(shí)有一個(gè)用戶的id的比特串是：1001011000011。它的所在桶下標(biāo)為：11(2) = 1*2^1 + 1*2^0 = 3，處于第3個(gè)桶，即第3輪中。

上面例子中，計(jì)算出桶號后，剩下的比特串是：10010110000，從低位到高位看，第一次出現(xiàn) 1 的位置是 5 。也就是說，此時(shí)第3個(gè)桶，第3輪的試驗(yàn)中，k_max = 5。5 對應(yīng)的二進(jìn)制是：101，又因?yàn)槊總€(gè)桶有 p 個(gè)比特位。當(dāng) p>=3 時(shí)，便可以將 101 存進(jìn)去。

模仿上面的流程，多個(gè)不同的用戶 id，就被分散到不同的桶中去了，且每個(gè)桶有其 k_max。然后當(dāng)要統(tǒng)計(jì)出 mian 頁面有多少用戶點(diǎn)擊量的時(shí)候，就是一次估算。最終結(jié)合所有桶中的 k_max，代入估算公式，便能得出估算值。

下面是 HyperLogLog 的結(jié)合了調(diào)和平均數(shù)的估算公式，變量釋意和LogLog的一樣:

Redis 中對 HyperLogLog 的應(yīng)用

首先，在 Redis 中，HyperLogLog 是它的一種高級數(shù)據(jù)結(jié)構(gòu)。提供有包含但不限于下面兩條命令：

• pfadd key value，將 key 對應(yīng)的一個(gè) value 存入

• pfcount key，統(tǒng)計(jì) key 的 value 有多少個(gè)

回想一下，原始APP頁面統(tǒng)計(jì)用戶的問題。如果 key 對應(yīng)頁面名稱，value 對應(yīng)用戶id。那么問題就剛剛好對應(yīng)上了。

Redis 中的 HyperLogLog 原理

前面我們已經(jīng)認(rèn)識到，它的實(shí)現(xiàn)中，設(shè)有 16384 個(gè)桶，即：2^14 = 16384，每個(gè)桶有 6 位，每個(gè)桶可以表達(dá)的最大數(shù)字是：2^5+2^4+...+1 = 63 ，二進(jìn)制為： 111 111 。

對于命令：pfadd key value

在存入時(shí)，value 會被 hash 成 64 位，即 64 bit 的比特字符串，前 14 位用來選擇這個(gè) value 的比特串中從右往左第一個(gè) 1 出現(xiàn)的下標(biāo)位置數(shù)值要存到那個(gè)桶中去，即前 14 位用來分桶。設(shè)第一個(gè)1出現(xiàn)位置的數(shù)值為 index 。當(dāng) index=5 時(shí)，就是: ....10000 [01 0000 0000 0000]

之所以選 14位 來表達(dá)桶編號是因?yàn)?，分?16384 個(gè)桶，而 2^14 = 16384，剛好地，最大的時(shí)候可以把桶利用完，不造成浪費(fèi)。假設(shè)一個(gè)字符串的前 14 位是：00 0000 0000 0010 (從右往左看) ，其十進(jìn)制值為 2。那么 index 將會被轉(zhuǎn)化后放到編號為 2 的桶。

index 的轉(zhuǎn)化規(guī)則：

首先因?yàn)橥暾?value 比特字符串是 64 位形式，減去 14 后，剩下 50 位，那么極端情況，出現(xiàn) 1 的位置，是在第 50 位，即位置是 50。此時(shí) index = 50。此時(shí)先將 index 轉(zhuǎn)為 2 進(jìn)制，它是：110010 。

因?yàn)?6384 個(gè)桶中，每個(gè)桶是 6 bit 組成的。剛好 110010 就被設(shè)置到了第 2 號桶中去了。請注意，50 已經(jīng)是最壞的情況，且它都被容納進(jìn)去了。那么其他的不用想也肯定能被容納進(jìn)去。

因?yàn)?fpadd 的 key 可以設(shè)置多個(gè) value。例如下面的例子：

pfadd lgh golang
pfadd lgh python
pfadd lgh java

根據(jù)上面的做法，不同的 value，會被設(shè)置到不同桶中去，如果出現(xiàn)了在同一個(gè)桶的，即前 14 位值是一樣的，但是后面出現(xiàn) 1 的位置不一樣。那么比較原來的 index 是否比新 index 大。是，則替換。否，則不變。

最終地，一個(gè) key 所對應(yīng)的 16384 個(gè)桶都設(shè)置了很多的 value 了，每個(gè)桶有一個(gè)k_max。此時(shí)調(diào)用 pfcount 時(shí)，按照前面介紹的估算方式，便可以計(jì)算出 key 的設(shè)置了多少次 value，也就是統(tǒng)計(jì)值。

value 被轉(zhuǎn)為 64 位的比特串，最終被按照上面的做法記錄到每個(gè)桶中去。64 位轉(zhuǎn)為十進(jìn)制就是：2^64，HyperLogLog 僅用了：16384 * 6 /8 / 1024 K 存儲空間就能統(tǒng)計(jì)多達(dá) 2^64 個(gè)數(shù)。

偏差修正

在估算的計(jì)算公式中，constant 變量不是一個(gè)定值，它會根據(jù)實(shí)際情況而被分支設(shè)置，例如下面的樣子。

假設(shè)：m為分桶數(shù)，p是m的以2為底的對數(shù)。

// m 為桶數(shù)
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

上述就是小編為大家分享的HyperLogLog 算法的原理講解以及Redis是如何應(yīng)用它的了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。