用 12k 內存去統計 2-64 個數據
一個關於統計學的問題
說Hyperloglog之前，我得先寫一些它的由來。設想一下，某某地方舉辦了一場技術交流活動，工作人員需要統計一下這個活動當天有多少的人蔘加？這個需求就是一個簡單的統計的需求，解決方法有很多種，例如：活動舉辦方在會場門口設置一個簽到處，每來一個參會者記錄一下，最後統計一下人數就可以了。這是一個很簡單問題，當時某一天作爲開發的我，接到一個來自產品需求，要我統計一下在雙十一1天內的某一個頁面的UV（Unique Visitors）？，那麼問題來了？怎麼解決？
瞭解這個問題之前先說一下uv統計標準：獨立訪客 UV 指不同的用戶，通過互聯網訪問同一個網頁或產品的獨立觸發用戶數。
假設一個場景: 今天爸爸、媽媽、兒子三人通過三個賬號訪問了某寶網頁，則UV=3， 這裏需要提一點：獨立UV是按瀏覽器cookie爲依據。只要cookie不清楚，3 個人在0:00—24:00內用同一個瀏覽器不同的賬號登陸，只會算作一個UV。
如圖 3 個不同賬戶但是通過同一臺電腦的瀏覽器訪問的，如果默認以cookie作爲標準的話，沒有清理cookie的話，那麼只會算一個uv。
uv 訪問記錄
那麼有開發經驗的肯定會說簡單啊，用hashmap或者用set集合... 看似是一個簡單問題，問題雖不難，但當參與問題中的變量達到一定數量級的時候，再簡單的問題都會變成一個難題。假設日活用戶達到百萬或千萬以上級別的話，我們採用 HashMap 的做法，就會導致程序中佔用大量的內存，並且都是在並行的操作記錄，還可能要考慮鎖顆粒度問題，顯然有經驗的老司機會直接否決🙅這種方案。
HyperLogLog
看了什麼的問題，那有木有什麼好的解決方案？有肯定是有的：B+ tree，Bitmap，在redis中就有造好的輪子的HyperLogLog概率數據結構算法，在redis中使用也就是3個api的事情：pfadd、pfcount、pfmerge。但是想深挖下去這個東西屬實有點複雜，會涉及到一些數學上的東西，正好筆者我也看了看實現，順便就寫了這篇文章，HyperLogLog這個是由下面👇這個肥宅在他的論文中提出的，對可能這就是國外搞學術的大佬吧，不過可惜的是大佬在 2011年3月22日就去世了，不過他留下的HyperLogLog還是很值得研究的。
Philippe Flajolet 教授
HLL的特點就是能花較低的內存佔用統計海量的數據，但是缺點也有代碼實現比較難，有一定的誤差，如果要統計的100%的準確性，還是要考慮其他方案或者通過數學計算算出誤差值（負載因子）。
在redis實現的HyperLogLog中能用12k內存就能統計2^64個數據，我表示很震撼。。。怎麼做到的？？？
挖槽這是怎麼做到的？看了一下那篇論文：http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
呵呵哈哈哈
伯努利試驗證明
在說HLL之前得先了解一下伯努利試驗!
!! 伯努利試驗是數學概率論中的一部分內容，它的典故來源於拋硬幣遊戲。實驗的內容：在同一個條件下重複地、各次之間相互獨立地進行的一種試驗，但是實驗的結果只要兩種結果，每次實驗結果只會是兩種結果中一個，然後在相同條件下重複做
n次的試驗稱爲n次獨立重複試驗，獨立性是隻各次試驗的結果不會受其他實驗結果的影響。
次數較少的實驗是沒有意義的，只要當實驗次數達到一定數量，就和微積分一樣，短時間是看不出來差異的，但是如果把時間線拉長，那麼差異就出來了。
結果是？
實驗過程：硬幣擁有正反兩面，一次的上拋至落下，最終出現正反面的概率各自都是50%，假設一直拋硬幣，直到它出現正面爲止，我們記錄爲一次完整的試驗，間中可能拋了一次就出現了正面，也可能拋了n次纔出現正面，不管拋出多少次，只要出現了正面，就記錄爲一次試驗。
重複不斷這個過程，假設這個多次爲n次，就意味着出現了n次的正面。假設每次伯努利試驗所經歷了的拋擲次數爲k，第一次伯努利試驗，次數設爲k1，以此類推，第n次對應的是kn，在實驗過程中肯定會出現拋出n才能出現一次正面，那麼稱這個爲k_max，代表拋了最多的次數。
經過反覆實驗得出結果：
-
N次實驗拋出的次數不會大於k_max -
N次實驗最少有一次的次數是k_max
當有了這些結論之後，發現在n和k_max中存在估算關聯：n = 2^(k_max)，當然需要大量的數據和實驗次數證明，如果需要深入挖掘其中的奧祕，那麼還會涉及到數學中的概率和統計的方法才能推導和驗證這種關聯關係。。。。
第一次: 拋了3次出正面，此時 k=3，n=1
第二次: 拋了2次出正面，此時 k=2，n=2
第三次: 拋了6次出正面，此時 k=6，n=3
第n 次：拋了20次出正面，此時我們估算， n = 2^20看上面的實驗如果套用這個估算關係公式的話，那麼結果是：上面例子中實驗組數共 3 組，那麼 k_max = 6，最終 n=3，我們放進估算公式中去，明顯：3 ≠ 2^6不成立的，但是證明了數據次數越少，意義就不大，發揮不了作用，就存在一定的誤差值。
通過上面一系列的推導，又會得出一個結論就是，如果我每輪實驗的次數越多，那麼結果偏差就會越小，但是還有有偏差的存在。那麼可不可以搞一個多輪的次數測試，例如搞1000次，然後再去取每輪的k_max，然後把k_max平攤到輪數上，就能算出n。
但是結果還是有偏差的，那怎麼辦？可以通過少量的測試觀察結果誤差，適當用修正因子做計算提高準確率，然後又演進出了一種LogLog的估算公式：
LogLog 估算公式
上面的DVLL對應的就是n，constant爲修正因子具體值是不定的，自定義設置，可以通過少量的測試觀察結果誤差，m代表的是試驗的輪數，頭上有一橫的 R 就是平均數：(k_max_1 + ... + k_max_m)/m。
小結
本文整理一下LogLog相關基礎理論，但是沒有寫完，後面更新下篇文章會講redis的hll具體實現細節，HyperLogLog是由Loglog優化改進過來的，所以本篇先寫到這。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/nBNnaP2i7lJV_vJzHN0zMg