2023-06-13：統(tǒng)計高并發(fā)網(wǎng)站每個網(wǎng)頁每天的 UV 數(shù)據(jù)，結(jié)合Redis你會如何實現(xiàn)？

答案2023-06-13：

選用方案：HyperLogLog

如果統(tǒng)計 PV （頁面瀏覽量）那非常好辦，可以考慮為每個網(wǎng)頁創(chuàng)建一個獨立的 Redis 計數(shù)器，并將日期添加為鍵（key）的后綴。當網(wǎng)頁收到請求時，對應(yīng)的計數(shù)器將被遞增。對于每天的訪問數(shù)據(jù)，您可以為該日期創(chuàng)建一個新的 Redis 計數(shù)器。

但是 UV（獨立訪客數(shù)） 不一樣，它要去重，確保同一用戶在一天之內(nèi)的多次訪問只被計數(shù)一次。為了實現(xiàn)這一點，每個請求都需要帶上一個唯一的用戶標識符（ID），以便對用戶進行去重。

一種簡單的實現(xiàn)方式是為每個頁面創(chuàng)建一個獨立的 Redis Set 集合，用于存儲當天訪問該頁面的用戶 ID。當有新的請求過來時，可以使用 Redis 的 SAdd 命令將用戶 ID 添加到集合中。通過 Redis 的 SCard 命令可以獲取集合大小，從而獲得該頁面的 UV 數(shù)據(jù)。

但是，如果你的頁面訪問量非常大，比如一個爆款頁面幾千萬的 UV，你需要一個很大的 set集合來統(tǒng)計，這就非常浪費空間。如果這樣的頁面很多，那所需要的存儲空間是驚人的。為這樣一個去重功能就耗費這樣多的存儲空間，值得么？其實需要的數(shù)據(jù)又不需要太精確，105w 和 106w 這兩個數(shù)字對于老板們來說并沒有多大區(qū)別，So，有沒有更好的解決方案呢？

這就是HyperLogLog的用武之地，Redis 提供了 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)就是用來解決這種統(tǒng)計問題的。雖然 HyperLogLog 提供的是不精確的去重計數(shù)方案，但誤差在一定范圍內(nèi)，例如 Redis 提供的 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)的標準誤差為 0.81%，這樣的精確度已經(jīng)可以滿足很多實際需求。

因此，對于大規(guī)模元素的去重計數(shù)問題，使用 HyperLogLog 的優(yōu)點在于在滿足精度要求的同時大大減少了存儲空間的占用。這種算法被廣泛用于大規(guī)模的在線去重計數(shù)場景中，例如計算裸訪客（naked visitors）和獨立 IP 訪問者等。在實際使用中，需要根據(jù)具體的應(yīng)用場景和數(shù)據(jù)特點選擇合適的參數(shù)（比如哈希函數(shù)、采樣次數(shù)等），以求得更好的精確度和性能表現(xiàn)。

HyperLogLog與集合方案對比

百萬級用戶訪問網(wǎng)站

HyperLogLog使用

操作命令

HyperLogLog提供了3個命令: pfadd、pfcount、pfmerge。

pfadd

pfadd key element [element …]

pfadd用于向HyperLogLog 添加元素,如果添加成功返回1:

pfadd u-9-30 u1 u2 u3 u4 u5 u6 u7 u8

pfcount

pfcount key [key …]

pfcount用于計算一個或多個HyperLogLog的獨立總數(shù)，例如u-9-30 的獨立總數(shù)為8:

如果此時向插入一些用戶，用戶并且有重復

如果我們繼續(xù)往里面插入數(shù)據(jù)，比如插入100萬條用戶記錄。內(nèi)存增加非常少，但是pfcount 的統(tǒng)計結(jié)果會出現(xiàn)誤差。

pfmerge

pfmerge destkey sourcekey [sourcekey ... ]

pfmerge可以求出多個HyperLogLog的并集并賦值給destkey，請自行測試。

可以看到，HyperLogLog內(nèi)存占用量小得驚人，但是用如此小空間來估算如此巨大的數(shù)據(jù)，必然不是100%的正確，其中一定存在誤差率。前面說過，Redis官方給出的數(shù)字是0.81%的失誤率。

HyperLogLog原理概述

基本原理

HyperLogLog 算法是基于概率論中的伯努利試驗，并結(jié)合了極大似然估算方法，并做了分桶優(yōu)化。

實際上，在大數(shù)據(jù)場景中，目前還沒有發(fā)現(xiàn)更好的高效算法來準確計算基數(shù)。因此，在不需要追求絕對準確性的情況下，使用概率算法是解決這一問題的一個不錯方案。概率算法不直接存儲數(shù)據(jù)集合本身，通過一定的概率統(tǒng)計方法來估算基數(shù)，這種方法可以大大節(jié)省內(nèi)存，同時保證誤差控制在一定范圍內(nèi)。目前用于基數(shù)計數(shù)的概率算法包括：

舉個例子來理解HyperLogLog 算法，有一天A和B玩打賭的游戲。

規(guī)則如下: 拋硬幣的游戲，每次拋的硬幣可能正面，可能反面，沒回合一直拋，直到每當拋到正面回合結(jié)束。

然后我跟B說，拋到正面最長的回合用到了7次，你來猜一猜，我用到了多少個回合做到的？

進行了n次實驗，比如上圖：

第一次試驗: 拋了3次才出現(xiàn)正面，此時 k=3，n=1

第二次試驗: 拋了2次才出現(xiàn)正面，此時 k=2，n=2

第三次試驗: 拋了4次才出現(xiàn)正面，此時 k=4，n=3

…………

第n 次試驗：拋了7次才出現(xiàn)正面，此時我們估算，k=7

B說大概你拋了128個回合。這個是怎么算的。

k是每回合拋到1所用的次數(shù)，我們已知的是最大的k值，可以用kmax表示。由于每次拋硬幣的結(jié)果只有0和1兩種情況，因此，能夠推測出kmax在任意回合出現(xiàn)的概率 ，并由kmax結(jié)合極大似然估算的方法推測出n的次數(shù)n = 2^(k_max) 。概率學把這種問題叫做伯努利實驗。

但是問題是，這種本身就是概率的問題，我跟B說，我只用到12次，并且有視頻為證。

所以這種預(yù)估方法存在較大誤差，為了改善誤差情況，HLL中引入分桶平均的概念。

同樣舉拋硬幣的例子，如果只有一組拋硬幣實驗，顯然根據(jù)公式推導得到的實驗次數(shù)的估計誤差較大；如果100個組同時進行拋硬幣實驗，受運氣影響的概率就很低了，每組分別進行多次拋硬幣實驗，并上報各自實驗過程中拋到正面的拋擲次數(shù)的最大值，就能根據(jù)100組的平均值預(yù)估整體的實驗次數(shù)了。

分桶平均的基本原理是將統(tǒng)計數(shù)據(jù)劃分為m個桶，每個桶分別統(tǒng)計各自的kmax,并能得到各自的基數(shù)預(yù)估值，最終對這些基數(shù)預(yù)估值求平均得到整體的基數(shù)估計值。LLC中使用幾何平均數(shù)預(yù)估整體的基數(shù)值，但是當統(tǒng)計數(shù)據(jù)量較小時誤差較大；HLL在LLC基礎(chǔ)上做了改進，采用調(diào)和平均數(shù)過濾掉不健康的統(tǒng)計值。

什么叫調(diào)和平均數(shù)呢？舉個例子

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

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

可見調(diào)和平均數(shù)比平均數(shù)的好處就是不容易受到大的數(shù)值的影響，比平均數(shù)的效果是要更好的。

結(jié)合Redis的實現(xiàn)理解原理

現(xiàn)在我們和前面的業(yè)務(wù)場景進行掛鉤：統(tǒng)計網(wǎng)頁每天的 UV 數(shù)據(jù)。

從前面的知識我們知道，伯努利實驗就是如果是出現(xiàn)1的時機越晚，就說明你要做更多的實驗，這個就好比你要中500萬的雙色球，你大概要買2000萬張不同的彩票（去重），而如果是換成 二進制來算，可能是 第幾十次才出現(xiàn)1。而你買一個中獎只有500塊的排列3（3個10進制數(shù)），而如果是換成 二進制來算，你只需要10次左右出現(xiàn)1。

1.轉(zhuǎn)為比特串

這里很重要的一點：hash函數(shù)，可以把不同的數(shù)據(jù)轉(zhuǎn)成盡量不重復的數(shù)據(jù)，這點就有點像去重。

如果是64位的二進制，是不是hash函數(shù)可以把 2的64次方個不同的數(shù)據(jù)轉(zhuǎn)成不一樣的二進制。這里就跟放入了2的64次方個元素一樣。

那么基于上面的估算結(jié)論，我們可以通過多次拋硬幣實驗的最大拋到正面的次數(shù)來預(yù)估總共進行了多少次實驗（多少個不同的數(shù)據(jù)），同樣存儲的時候也可以優(yōu)化，每次add一個元素時，只要算法最后出現(xiàn)1的位數(shù)，把這個位數(shù)做一個最大的替換久可以。（如果添加的元素比 記錄之前位數(shù)小則不記錄，只要大才記錄）

2.分桶

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

比如有4個桶的話，那么可以截取低2位作為分桶的依據(jù)。

比如

10010000 進入0號桶

10010001 進入1號桶

10010010 進入2號桶

10010011 進入3號桶

Redis 中的 HyperLogLog 實現(xiàn)

pfadd

當我們執(zhí)行這個操作時，lijin這個字符串就會被轉(zhuǎn)化成64個bit的二進制比特串。

這里很重要的一點：hash函數(shù)，可以把不同的數(shù)據(jù)轉(zhuǎn)成盡量不重復的數(shù)據(jù)，這點就有點像去重。

如果是64位的二進制，是不是hash函數(shù)可以把 2的64次方個不同的數(shù)據(jù)轉(zhuǎn)成不一樣的二進制。這里就跟放入了2的64次方個元素一樣。

那么基于上面的估算結(jié)論，我們可以通過多次拋硬幣實驗的最大拋到正面的次數(shù)來預(yù)估總共進行了多少次實驗（多少個不同的數(shù)據(jù)），同樣存儲的時候也可以優(yōu)化，每次add一個元素時，只要算法最后出現(xiàn)1的位數(shù)，把這個位數(shù)做一個最大的替換久可以。（如果添加的元素比 記錄之前位數(shù)小則不記錄，只要大才記錄）

0010....0001 64位

然后在Redis中要分到16384個桶中（為什么是這么多桶：第一降低誤判，第二，用到了14位二進制：2的14次方=16384）

怎么分？根據(jù)得到的比特串的后14位來做判斷即可。

根據(jù)上述的規(guī)則，我們知道這個數(shù)據(jù)要分到 1號桶，同時從左往右（低位到高位）計算第1個出現(xiàn)的1的位置，這里是第4位，那么就往這個1號桶插入4的數(shù)據(jù)（轉(zhuǎn)成二進制）

如果有第二個數(shù)據(jù)來了，按照上述的規(guī)則進行計算。

那么問題來了，如果分到桶的數(shù)據(jù)有重復了（這里比大小，大的替換小的）：

規(guī)則如下，比大小（比出現(xiàn)位置的大?。热缬袀€數(shù)據(jù)是最高位才出現(xiàn)1，那么這個位置算出來就是50，50比4大，則進行替換。1號桶的數(shù)據(jù)就變成了50（二進制是110010）

所以這里可以看到，每個桶的數(shù)據(jù)一般情況下6位存儲即可。

所以我們這里可以推算一下一個key的HyperLogLog只占據(jù)多少的存儲。

16384*6 /8/1024=12k。并且這里最多可以存儲多少數(shù)據(jù)，因為是64位嗎，所以就是2的64次方的數(shù)據(jù)，這個存儲的數(shù)據(jù)非常非常大的，一般用戶用long來定義，最大值也只有這么多。

pfcount

進行統(tǒng)計的時候，就是把16384桶，把每個桶的值拿出來，比如取出是 n,那么訪問次數(shù)（里面）就是2的n次方。

然后把每個桶的值做調(diào)和平均數(shù)，就可以算出一個算法值。

同時，在具體的算法實現(xiàn)上，HLL還有一個分階段偏差修正算法。我們就不做更深入的了解了。

const和m都是Redis里面根據(jù)數(shù)據(jù)做的調(diào)和平均數(shù)。