不積跬步，無以至千里；不積小流，無以成江海。
碼字不易，點贊再看。
場景分析
某天產品經理要我們統計網站每個頁面每天的 UV 數據？接到這個需求你該怎麼設計這個統計模塊
考慮到 UV 的特性 同一個用戶一天之內的多次訪問請求只能計數一次。所以請求到網頁的每一個用戶
都需要帶有唯一 ID 標識。
方案一
數據量比較低的情況下，通常是簡單的把所有數據存儲下來，直接count一下就是基數了
但隨著數據量的急劇增大，這種方式已經很難滿足需求。過大的數據量無論是在存儲還是在查詢方面都
存在巨大的挑戰，都沒法達到大數據時代的要求或者是性價比太低。
方案二用 set 記錄 當天訪問過此頁面的用戶 ID，當一個請求過來時，我們使用 sadd 將用戶 ID 塞進去。通過 scard 可以取出這個集合的大小，這個數字就是這個頁面的 UV 數據。
但是，如果你的頁面訪問量非常大，比如一個爆款頁面幾千萬的 UV，就需要一個很大的 set 集合來統計，這就非常 浪費空間。如果這樣的頁面很多，那所需要的存儲空間是驚人的。
為這樣一個去重功能就耗費這樣多的存儲空間，值得麼？這個數據真的需要非常精確嗎？1000w 和 1001w 對產品經理來說差別不是很大。。
So 推出今天的主咖 HyperLogLog
HyperLogLog 是什麼
HyperLogLog 與 布隆過濾器 都是針對 大數據 統計 存儲 應用場景下的 知名算法。
HyperLogLog 是在大數據的情況下關於 數據基數 的空間複雜度優化實現。可以使用 12KB 內存，就可以計算接近 2^64 個不同元素的 基數
HyperLogLog 提供 不精確 的 去重計數 方案，雖然不精確但是也不是非常不精確，標準誤差是 0.81%，誤差可以通過設置的 輔助計算因子 進行降低，這樣的精確度已經可以滿足上面的 UV 統計需求了。
基數
基數就是指一個集合中不同值的數目，比如[a,b,c,d]的基數就是4，[a,b,c,d,a]的基數還是4，因為a重複了一個，不算。基數也可以稱之為Distinct Value，簡稱DV。
HyperLogLog原理
給定一個集合 S，對集合中的每一個元素，我們做一個 哈希，假設生成一個 16 位的比特串，從所有生成的比特串中挑選出 前面 連續 0 次數(K) 最多 的比特串，假設為 0000000011010110，連續 0 的次數為 8，因此我們可以估計該集合 S 的基數介於 2^K 和 2^(K+1) 之間，用這種方式估計的值都等於 2^(K+1)，這明顯是不合理的。
因此在實際的 HyperLogLog 算法中，採取 分桶 平均原理了來消除誤差。
特點：犧牲了一定的準確度（在一些場景下是可以忽略的），但卻實現了空間複雜度上的極大的壓縮，可以說是性價比很高的。
2^(K+1)為什麼要加1呢？
這是一個數學細節，具體要看論文
簡單的理解:就是為了進行概率估計
Redis 中 HyperLogLog 用法
注意事項
HyperLogLog 它需要佔據 12k 的存儲空間，所以它 不適合 統計 單個 用戶相關的數據。如果你的用戶上億，可以算算，這個空間成本是非常大的。但是相比 set 存儲方案，HyperLogLog 所使用的空間小巫見大巫了。
不過你也不必過於擔心，因為 Redis 對 HyperLogLog 的存儲進行了 優化，在計數比較小時，它的存儲空間採用 稀疏矩陣 存儲，空間佔用很小，僅僅在計數慢慢變大，稀疏矩陣佔用空間漸漸超過了閾值時才會一次性轉變成 稠密矩陣，才會佔用 12k 的空間。
點關注 不迷路
以上就是這篇的全部內容，能看到這裡的都是 人才。
如果你從本篇內容有收穫，求 點贊，求 關注，求 轉發 ，讓更多的人學習到。
如果本文有任何錯誤，請批評指教，不勝感激 ！
