一，前言

在互聯(lián)網(wǎng)行業(yè)中存在兩個(gè)比較重要的指標(biāo)：PV（頁(yè)面訪問量）和 UV（用戶訪問量）

如果有這樣的一個(gè)業(yè)務(wù)：

統(tǒng)計(jì)PV，那么你會(huì)怎么做？
我們可以使用Redis的incr、incrby指令，給每個(gè)網(wǎng)頁(yè)配置一個(gè)獨(dú)立Redis計(jì)數(shù)器就可以了，把這個(gè)技術(shù)區(qū)的key后綴加上當(dāng)它的日期，這樣一個(gè)請(qǐng)求過來，就可以通過執(zhí)行incr、incrby指令統(tǒng)計(jì)所有PV。

那么統(tǒng)計(jì)UV又該怎么做呢？

UV和PV不同，UV需要對(duì)同一用戶的訪問進(jìn)行去重，此時(shí)很快就能想到使用Redis中的set來存儲(chǔ)，但是會(huì)面臨以下問題：

1. 對(duì)于數(shù)據(jù)量越來越大，存儲(chǔ)數(shù)據(jù)的空間占用越來越大
2. 統(tǒng)計(jì)的性能比較慢，雖然可以通過異步方式統(tǒng)計(jì)，但是性能并不理想

因此引入了Redis的新數(shù)據(jù)類型HyperLogLog。

二，Hyperloglog簡(jiǎn)介

HyperLogLog 是一種概率數(shù)據(jù)結(jié)構(gòu)，用于在恒定的內(nèi)存大小下估計(jì)集合的基數(shù)（不同元素的個(gè)數(shù)）。它不是一個(gè)獨(dú)立的數(shù)據(jù)類型，而是一種特殊的 string 類型，它可以使用極小的空間來統(tǒng)計(jì)一個(gè)集合中不同元素的數(shù)量，也就是基數(shù)。在Redis中，每個(gè)HyperLogLog鍵只需要花費(fèi)12KB內(nèi)存，就可以計(jì)算接近2^64個(gè)不同的基數(shù)。（為什么是12KB呢？下面會(huì)詳細(xì)講解）

hyperloglog 類型的底層實(shí)現(xiàn)是 SDS（simple dynamic string），它和 string 類型相同，只是在操作時(shí)會(huì)使用一種概率算法來計(jì)算基數(shù)。hyperloglog 的誤差率為 0.81%，也就是說如果真實(shí)基數(shù)為 1000，那么 hyperloglog 計(jì)算出來的基數(shù)可能在 981 到 1019 之間
?

三，Redis中Hyperloglog的使用

PFADD key element [element …]

將任意數(shù)量的元素添加到指定的 HyperLogLog 里面，當(dāng)PFADD key element [element …]指令執(zhí)行時(shí)，如果HyperLogLog的估計(jì)近似基數(shù)在命令執(zhí)行之后出現(xiàn)了變化，那么命令返回1，否則返回0，如果HyperLogLog命令執(zhí)行時(shí)給定的鍵不存在，那么程序?qū)⑾葎?chuàng)建一個(gè)空的HyperLogLog結(jié)構(gòu)，再執(zhí)行命令。
該命令可以只給定key不給element，這種以方式被調(diào)用時(shí)：

如果給定的鍵存在且已經(jīng)是一個(gè)HyperLogLog，那么這種調(diào)用不會(huì)產(chǎn)生任何效果
如果給定的鍵不存在，那么命令會(huì)創(chuàng)建一個(gè)空的HyperLogLog，并且給客戶端返回1
返回值：
如果HyperLogLog數(shù)據(jù)結(jié)構(gòu)內(nèi)部存儲(chǔ)的數(shù)據(jù)被修改了，那么返回1，否則返回0

時(shí)間復(fù)雜度：O(1)

PFCOUNT key [key …]

PFCOUNT 指令后面可以跟多個(gè)key，當(dāng)PFCOUNT key [key …]命令作用于單個(gè)鍵時(shí)，返回存儲(chǔ)在給定鍵的HyperLogLog的近似基數(shù)，如果鍵不存在，則返回0；當(dāng)PFCOUNT key [key …]命令作用于多個(gè)鍵時(shí)，返回所給定HyperLogLog的并集的近似基數(shù)，這個(gè)近似基數(shù)是通過將索引給定HyperLogLog合并至一個(gè)臨時(shí)HyperLogLog來計(jì)算得出的。

返回值：返回給定HyperLogLog包含的唯一元素的近似數(shù)量的整數(shù)值

時(shí)間復(fù)雜度：當(dāng)命令作用于單個(gè)HyperLogLog時(shí)，時(shí)間復(fù)雜度為O(1)，并且具有非常低的平均常數(shù)時(shí)間。當(dāng)命令作用于N個(gè)HyperLogLog時(shí)，時(shí)間復(fù)雜度為O(N)，常數(shù)時(shí)間會(huì)比單個(gè)HyperLogLog要大的多。

PFMERGE destkey sourcekey [sourcekey …]

將多個(gè)HyperLogLog合并到一個(gè)HyperLogLog中，合并后HyperLogLog的基數(shù)接近于所有輸入HyperLogLog的可見集合的并集，合并后得到的HyperLogLog會(huì)被存儲(chǔ)在destkey鍵里面，如果該鍵不存在，那么命令在執(zhí)行之前，會(huì)先為該鍵創(chuàng)建一個(gè)空的HyperLogLog。

返回值：字符串回復(fù)，返回OK

時(shí)間復(fù)雜度：O(N)，其中N為被合并的HyperLogLog的數(shù)量，不過這個(gè)命令的常數(shù)復(fù)雜度比較高

四，Hyperloglog原理

Hyperloglog基于概率論中的伯努利試驗(yàn)并結(jié)合了極大似然估算方法，并進(jìn)行了分桶優(yōu)化。

1. 伯努利試驗(yàn)

在認(rèn)識(shí)為什么Hyperloglog能夠使用極少的內(nèi)存（12K）來統(tǒng)計(jì)巨量的數(shù)據(jù)之前，先認(rèn)識(shí)一下伯努利試驗(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)。

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

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

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

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

上述案例可以看出，假設(shè)n=3，此時(shí)通過估算關(guān)系n=2^kmax，2^5 ≠3，而且偏差很大。因此得出結(jié)論，這種估算方法誤差很大。

2. 估值優(yōu)化

關(guān)于上述估值偏差較大的問題，可以采用如下方式結(jié)合來縮小誤差：

• 增加測(cè)試的輪數(shù)，取平均值。假設(shè)三次伯努利試驗(yàn)為1輪測(cè)試，我們?nèi)〕鲞@一輪試驗(yàn)中最大的的kmax作為本輪測(cè)試的數(shù)據(jù)，同時(shí)我們將測(cè)試的輪數(shù)定位100輪，這樣我們?cè)?00輪實(shí)驗(yàn)中，將會(huì)得到100個(gè)kmax，此時(shí)平均數(shù)就是(k_max_1 + … + k_max_m)/m，這里m為試驗(yàn)的輪數(shù)，此處為100.
• 增加修正因子，修正因子是一個(gè)不固定的值，會(huì)根據(jù)實(shí)際情況來進(jìn)行值的調(diào)整。

上述這種增加試驗(yàn)輪數(shù)，取Kmax的平均值的方法，是loglog算法的實(shí)現(xiàn)。因此loglog它的估算公式如下：

loglog與Hyperloglog的區(qū)別在于：loglog采用算數(shù)平均數(shù)，而Hyperloglog采用調(diào)和平均數(shù)

調(diào)和平均數(shù)：

調(diào)和平均數(shù)的效果更好，例如以下例子：

一個(gè)小區(qū)內(nèi)有100戶，現(xiàn)在要統(tǒng)計(jì)小區(qū)的平均工資，小區(qū)的工資可以分為大致6000左右，10000左右的，還有一戶100000000以上。

此時(shí)使用算數(shù)平均會(huì)導(dǎo)致結(jié)果和現(xiàn)實(shí)相差很大。

使用調(diào)和平均：那戶工資上100000000的，對(duì)整體的影響就幾乎可以忽視。

3. Hyperloglog實(shí)現(xiàn)原理

圖示：

Redis中Hyperloglog前14位進(jìn)行分桶，后50位進(jìn)行獲取Kmax

3.1?將數(shù)據(jù)轉(zhuǎn)化為bit串

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

是因?yàn)橐蛼佊矌艑?duì)應(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 的最大的位置 Kmax 來估算存入了多少數(shù)據(jù)。

3.2?分桶

分桶就是分多少輪。在拋硬幣中我們可以將三次實(shí)驗(yàn)分為一組，用這一組的Kmax求平均值當(dāng)作一次的Kmax，這樣可以減少誤差。

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

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

為什么Hyperloglog大小為12K?

由上圖可知：

1. 后14位用于分桶，也就是需要2^14 = 16384個(gè)桶（0~16383，也就是14位全0~全1）
2. 每個(gè)桶子需要存儲(chǔ)前50位得到的Kmax值（起始開始最多連續(xù)零個(gè)數(shù)），而50位最多有50個(gè)0，因此Kmax最大取到50，2^6 = 64 > 50，因此每個(gè)桶只需要6個(gè)bit位就可以保存Kmax
3. 每8個(gè)bit位為1字節(jié)，每1024字節(jié)為1K

綜合以上兩點(diǎn)：Hyperloglog的大小 = 16384 * 6 / 8 * 1024 = 12K

3.3 Hyperloglog估算公式

五，Hyperloglog的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：內(nèi)存占用很小只有12K

缺點(diǎn)：存在誤差概率。不能存儲(chǔ)元素本身，只能統(tǒng)計(jì)集合基數(shù)值。

六，Hyperloglog適用場(chǎng)景

• 統(tǒng)計(jì)一個(gè)?APP?的日活、月活數(shù)；

• 統(tǒng)計(jì)一個(gè)頁(yè)面的每天被多少個(gè)不同賬戶訪問量（Unique Visitor，UV）；

• 統(tǒng)計(jì)用戶每天搜索不同詞條的個(gè)數(shù)；

• 統(tǒng)計(jì)注冊(cè) IP 數(shù)。

七，布隆過濾器，布谷鳥過濾器，Hyperloglog如何選擇

可以設(shè)置誤判率：布隆過濾器

可以進(jìn)行刪除操作：布谷鳥過濾器

占用空間小：Hyperloglog