2023-06-13：統計高並行網站每個網頁每天的 UV 資料，結合Redis你會如何實現？

答案2023-06-13：

選用方案：HyperLogLog

如果統計 PV （頁面瀏覽量）那非常好辦，可以考慮為每個網頁建立一個獨立的 Redis 計數器，並將日期新增為鍵（key）的字尾。當網頁收到請求時，對應的計數器將被遞增。對於每天的存取資料，您可以為該日期建立一個新的 Redis 計數器。

但是 UV（獨立訪客數）不一樣，它要去重，確保同一使用者在一天之內的多次存取只被計數一次。為了實現這一點，每個請求都需要帶上一個唯一的使用者識別符號（ID），以便對使用者進行去重。

一種簡單的實現方式是為每個頁面建立一個獨立的 Redis Set 集合，用於儲存當天存取該頁面的使用者 ID。當有新的請求過來時，可以使用 Redis 的 SAdd 命令將使用者 ID 新增到集合中。通過 Redis 的 SCard 命令可以獲取集合大小，從而獲得該頁面的 UV 資料。

但是，如果你的頁面存取量非常大，比如一個爆款頁面幾千萬的 UV，你需要一個很大的 set集合來統計，這就非常浪費空間。如果這樣的頁面很多，那所需要的儲存空間是驚人的。為這樣一個去重功能就耗費這樣多的儲存空間，值得麼？其實需要的資料又不需要太精確，105w 和 106w 這兩個數位對於老闆們來說並沒有多大區別，So，有沒有更好的解決方案呢？

這就是HyperLogLog的用武之地，Redis 提供了 HyperLogLog 資料結構就是用來解決這種統計問題的。雖然 HyperLogLog 提供的是不精確的去重計數方案，但誤差在一定範圍內，例如 Redis 提供的 HyperLogLog 資料結構的標準誤差為 0.81%，這樣的精確度已經可以滿足很多實際需求。

因此，對於大規模元素的去重計數問題，使用 HyperLogLog 的優點在於在滿足精度要求的同時大大減少了儲存空間的佔用。這種演演算法被廣泛用於大規模的線上去重計數場景中，例如計算裸訪客（naked visitors）和獨立 IP 存取者等。在實際使用中，需要根據具體的應用場景和資料特點選擇合適的引數（比如雜湊函數、取樣次數等），以求得更好的精確度和效能表現。

HyperLogLog與集合方案對比

百萬級使用者存取網站

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的獨立總數，例如u-9-30 的獨立總數為8:

如果此時向插入一些使用者，使用者並且有重複

如果我們繼續往裡面插入資料，比如插入100萬條使用者記錄。記憶體增加非常少，但是pfcount 的統計結果會出現誤差。

pfmerge

pfmerge destkey sourcekey [sourcekey ... ]

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

可以看到，HyperLogLog記憶體佔用量小得驚人，但是用如此小空間來估算如此巨大的資料，必然不是100%的正確，其中一定存在誤差率。前面說過，Redis官方給出的數位是0.81%的失誤率。

HyperLogLog原理概述

基本原理

HyperLogLog 演演算法是基於概率論中的伯努利試驗，並結合了極大似然估算方法，並做了分桶優化。

實際上，在巨量資料場景中，目前還沒有發現更好的高效演演算法來準確計算基數。因此，在不需要追求絕對準確性的情況下，使用概率演演算法是解決這一問題的一個不錯方案。概率演演算法不直接儲存資料集合本身，通過一定的概率統計方法來估算基數，這種方法可以大大節省記憶體，同時保證誤差控制在一定範圍內。目前用於基數計數的概率演演算法包括：

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

規則如下: 拋硬幣的遊戲，每次拋的硬幣可能正面，可能反面，沒回合一直拋，直到每當拋到正面回合結束。

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

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

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

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

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

…………

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

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

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

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

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

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

分桶平均的基本原理是將統計資料劃分為m個桶，每個桶分別統計各自的kmax,並能得到各自的基數預估值，最終對這些基數預估值求平均得到整體的基數估計值。LLC中使用幾何平均數預估整體的基數值，但是當統計資料量較小時誤差較大；HLL在LLC基礎上做了改進，採用調和平均數過濾掉不健康的統計值。

什麼叫調和平均數呢？舉個例子

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

採用調和平均數的方式就是：
2/(1/1000 + 1/30000) ≈ 1935.484

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

結合Redis的實現理解原理

現在我們和前面的業務場景進行掛鉤：統計網頁每天的 UV 資料。

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

1.轉為位元串

這裡很重要的一點：hash函數，可以把不同的資料轉成儘量不重複的資料，這點就有點像去重。

如果是64位元的二進位制，是不是hash函數可以把 2的64次方個不同的資料轉成不一樣的二進位制。這裡就跟放入了2的64次方個元素一樣。

那麼基於上面的估算結論，我們可以通過多次拋硬幣實驗的最大拋到正面的次數來預估總共進行了多少次實驗（多少個不同的資料），同樣儲存的時候也可以優化，每次add一個元素時，只要演演算法最後出現1的位數，把這個位數做一個最大的替換久可以。（如果新增的元素比記錄之前位數小則不記錄，只要大才記錄）

2.分桶

分桶就是分多少輪。抽象到計算機儲存中去，就是儲存的是一個以單位是位元(bit)，長度為 L 的大陣列 S ，將 S 平均分為 m 組，注意這個 m 組，就是對應多少輪，然後每組所佔有的位元個數是平均的，設為 P。容易得出下面的關係：

比如有4個桶的話，那麼可以擷取低2位作為分桶的依據。

比如

10010000 進入0號桶

10010001 進入1號桶

10010010 進入2號桶

10010011 進入3號桶

Redis 中的 HyperLogLog 實現

pfadd

當我們執行這個操作時，lijin這個字串就會被轉化成64個bit的二進位制位元串。

這裡很重要的一點：hash函數，可以把不同的資料轉成儘量不重複的資料，這點就有點像去重。

如果是64位元的二進位制，是不是hash函數可以把 2的64次方個不同的資料轉成不一樣的二進位制。這裡就跟放入了2的64次方個元素一樣。

0010....0001 64位元

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

怎麼分？根據得到的位元串的後14位元來做判斷即可。

根據上述的規則，我們知道這個資料要分到 1號桶，同時從左往右（低位到高位）計算第1個出現的1的位置，這裡是第4位元，那麼就往這個1號桶插入4的資料（轉成二進位制）

如果有第二個資料來了，按照上述的規則進行計算。

那麼問題來了，如果分到桶的資料有重複了（這裡比大小，大的替換小的）：

規則如下，比大小（比出現位置的大小），比如有個資料是最高位才出現1，那麼這個位置算出來就是50，50比4大，則進行替換。1號桶的資料就變成了50（二進位制是110010）

所以這裡可以看到，每個桶的資料一般情況下6位儲存即可。

所以我們這裡可以推算一下一個key的HyperLogLog只佔據多少的儲存。

16384*6 /8/1024=12k。並且這裡最多可以儲存多少資料，因為是64位元嗎，所以就是2的64次方的資料，這個儲存的資料非常非常大的，一般使用者用long來定義，最大值也只有這麼多。

pfcount

進行統計的時候，就是把16384桶，把每個桶的值拿出來，比如取出是 n,那麼存取次數（裡面）就是2的n次方。

然後把每個桶的值做調和平均數，就可以算出一個演演算法值。

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

const和m都是Redis裡面根據資料做的調和平均數。