又是一年招聘季，整理一些面試題，為自己也為大家整理點資料，希望大家成功上岸。這些整理的是針對面試。因平台單日有釋出數量限制，超出限制的隻能粉絲檢視，需要的請關注後自行擷取，謝謝。
統計高并發網站每個網頁每天的 UV 資料，結合Redis你會如何實作？
選用方案：HyperLogLog
如果統計 PV 那非常好辦，給每個網頁一個獨立的 Redis 計數器就可以了，這個計數器的 key 字尾加上當天的日期。這樣來一個請求，incrby 一次，最終就可以統計出所有的 PV 資料。
但是 UV 不一樣，它要去重，同一個使用者一天之内的多次通路請求隻能計數一次。這就要求每一個網頁請求都需要帶上使用者的 ID，無論是登陸使用者還是未登陸使用者都需要一個唯一 ID 來辨別。
一個簡單的方案，那就是為每一個頁面一個獨立的 set 集合來存儲所有當天通路過此頁面的使用者 ID。當一個請求過來時，我們使用 sadd 将使用者 ID 塞進去就可以了。通過 scard 可以取出這個集合的大小，這個數字就是這個頁面的 UV 資料。
但是，如果你的頁面通路量非常大，比如一個爆款頁面幾千萬的 UV，你需要一個很大的 set集合來統計，這就非常浪費空間。如果這樣的頁面很多，那所需要的存儲空間是驚人的。為這樣一個去重功能就耗費這樣多的存儲空間，值得麼？其實需要的資料又不需要太精确，105w 和 106w 這兩個數字對于老闆們來說并沒有多大差別，So，有沒有更好的解決方案呢？
這就是HyperLogLog的用武之地，Redis 提供了 HyperLogLog 資料結構就是用來解決這種統計問題的。HyperLogLog 提供不精确的去重計數方案，雖然不精确但是也不是非常不精确，Redis官方給出标準誤差是0.81%，這樣的精确度已經可以滿足上面的UV 統計需求了。
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
規則如下: 抛硬币的遊戲，每次抛的硬币可能正面，可能反面，每回合一直抛，直到每當抛到正面回合結束。
進行了n次實驗，比如上圖：
第一次試驗: 抛了3次才出現正面，此時 k=3，n=1
第二次試驗: 抛了2次才出現正面，此時 k=2，n=2
第三次試驗: 抛了4次才出現正面，此時 k=4，n=3
…………
第n 次試驗：抛了7次才出現正面，此時我們估算，k=7
大概抛了128個回合。這個是怎麼算的。
k是每回合抛到1所用的次數，我們已知的是最大的k值，可以用kmax表示。由于每次抛硬币的結果隻有0和1兩種情況，是以，能夠推測出kmax在任意回合出現的機率 ，并由kmax結合極大似然估算的方法推測出n的次數n = 2^(k_max) 。機率學把這種問題叫做伯努利實驗。
但是問題是，這種本身就是機率的問題，隻用到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。
- 轉為比特串
這裡很重要的一點：hash函數，可以把不同的資料轉成盡量不重複的資料，這點就有點像去重。
如果是64位的二進制，是不是hash函數可以把 2的64次方個不同的資料轉成不一樣的二進制。這裡就跟放入了2的64次方個元素一樣。
那麼基于上面的估算結論，我們可以通過多次抛硬币實驗的最大抛到正面的次數來預估總共進行了多少次實驗（多少個不同的資料），同樣存儲的時候也可以優化，每次add一個元素時，隻要算法最後出現1的位數，把這個位數做一個最大的替換就可以。（如果添加的元素比記錄之前位數小則不記錄，隻要大才記錄）
- 分桶
分桶就是分多少輪。抽象到計算機存儲中去，就是存儲的是一個以機關是比特(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次方個元素一樣。
那麼基于上面的估算結論，我們可以通過多次抛硬币實驗的最大抛到正面的次數來預估總共進行了多少次實驗（多少個不同的資料），同樣存儲的時候也可以優化，每次add一個元素時，隻要算法最後出現1的位數，把這個位數做一個最大的替換久可以。（如果添加的元素比 記錄之前位數小則不記錄，隻要大才記錄）
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裡面根據資料做的調和平均數。