1樓：程式設計師歷小冰
具體可以看一下這篇文章
使用者日活月活怎麼統計 - Redis HyperLogLog 詳解
基本原理
HyperLogLog 是一種概率資料結構，它使用概率演算法來統計集合的近似基數。而它演算法的最本源則是伯努利過程。
伯努利過程就是乙個拋硬幣實驗的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。伯努利過程就是一直拋硬幣，直到落地時出現正面位置，並記錄下拋擲次數k。
比如說，拋一次硬幣就出現正面了，此時 k 為 1; 第一次拋硬幣是反面，則繼續拋，直到第三次才出現正面，此時 k 為 3。
對於 n 次伯努利過程，我們會得到 n 個出現正面的投擲次數值 $ k1, k2 ... kn $, 其中這裡的最大值是kmax。
根據一頓數學推導，我們可以得出乙個結論： $2^$ 來作為n的估計值。也就是說你可以根據最大投擲次數近似的推算出進行了幾次伯努利過程。
下面，我們就來講解一下 HyperLogLog 是如何模擬伯努利過程，並最終統計集合基數的。
HyperLogLog 在新增元素時，會通過Hash函式，將元素轉為64位位元串，例如輸入5，便轉為101(省略前面的0，下同)。這些位元串就類似於一次拋硬幣的伯努利過程。位元串中，0 代表了拋硬幣落地是反面，1 代表拋硬幣落地是正面，如果乙個資料最終被轉化了 10010000，那麼從低位往高位看，我們可以認為，這串位元串可以代表一次伯努利過程，首次出現 1 的位數為5，就是拋了5次才出現正面。
所以 HyperLogLog 的基本思想是利用集合中數字的位元串第乙個 1 出現位置的最大值來預估整體基數，但是這種預估方法存在較大誤差，為了改善誤差情況，HyperLogLog中引入分桶平均的概念，計算 m 個桶的調和平均值。
Redis 中 HyperLogLog 一共分了 2^14 個桶，也就是 16384 個桶。每個桶中是乙個 6 bit 的陣列，如下圖所示。
HyperLogLog 將上文所說的 64 位位元串的低 14 位單獨拿出，它的值就對應桶的序號，然後將剩下 50 位中第一次出現 1 的位置值設定到桶中。50位中出現1的位置值最大為50，所以每個桶中的 6 位陣列正好可以表示該值。
在設定前，要設定進桶的值是否大於桶中的舊值，如果大於才進行設定，否則不進行設定。示例如下圖所示。
此時為了效能考慮，是不會去統計當前的基數的，而是將 HyperLogLog 頭的 card 屬性中的標誌位置為 1，表示下次進行 pfcount 操作的時候，當前的快取值已經失效了，需要重新統計快取值。在後面 pfcount 流程的時候，發現這個標記為失效，就會去重新統計新的基數，放入基數快取。
在計算近似基數時，就分別計算每個桶中的值，帶入到上文將的 DV 公式中，進行調和平均和結果修正，就能得到估算的基數值。
HyperLogLog 物件中的 registers 陣列就是桶，它有兩種儲存結構，分別為密集儲存結構和稀疏儲存結構，兩種結構只涉及儲存和桶的表現形式，從中我們可以看到 Redis 對節省記憶體極致地追求。
我們先看相對簡單的密集儲存結構，它也是十分的簡單明瞭，既然要有 2^14 個 6 bit的桶，那麼我就真使用足夠多的 uint8_t 位元組去表示，只是此時會涉及到位元組位置和桶的轉換，因為位元組有 8 位，而桶只需要 6 位。
所以我們需要將桶的序號轉換成對應的位元組偏移量 offsetbytes 和其內部的位數偏移量 offsetbits。需要注意的是小端位元組序，高位在右側，需要進行倒轉。
當 offset_bits 小於等於2時，說明乙個桶就在該位元組內，只需要進行倒轉就能得到桶的值。
如果 offset_bits 大於 2 ，則說明乙個桶分布在兩個位元組內，此時需要將兩個位元組的內容都進行倒置，然後再進行拼接得到桶的值，如下圖所示。
HyperLogLog 的稀疏儲存結構是為了節約記憶體消耗，它不像密集儲存模式一樣，真正找了那麼多個位元組陣列來表示2^14 個桶，而是使用特殊的位元組結構來表達。
Redis 為了方便表達稀疏儲存，它將上面三種位元組表示形式分別賦予了一條指令。
ZERO : 一位元組，表示連續多少個桶計數為0，前兩位為標誌00，後6位表示有多少個桶，最大為64。
XZERO : 兩個位元組，表示連續多少個桶計數為0，前兩位為標誌01，後14位表示有多少個桶，最大為16384。
VAL : 一位元組，表示連續多少個桶的計數為多少，前一位為標誌1，四位表示連桶內計數，所以最大表示桶的計數為32。後兩位表示連續多少個桶。
所以，乙個初始狀態的 HyperLogLog 物件只需要2 位元組，也就是乙個 XZERO 來儲存其資料，而不需要消耗12K 記憶體。當 HyperLogLog 插入了少數元素時，可以只使用少量的 XZERO、VAL 和 ZERO 進行表示，如下圖所示。
Redis從稀疏儲存轉換到密集儲存的條件是：
任意乙個計數值從 32 變成 33，因為 VAL 指令已經無法容納，它能表示的計數值最大為 32
稀疏儲存占用的總位元組數超過 3000 位元組，這個閾值可以通過 hllsparsemax_bytes 引數進行調整。
redux原始碼中的isDispatching有什麼用？
阻止花式作死。如通過reducer內dispatch，再次觸發reducer。reducer dispatch reducer dispatch reducer reducer完成後更新state，reducer內連續dispatch是無法準確更新state的。next action next ac...
原始碼如何去學？
我好愛學習啊 想學原始碼的話，可以去原始碼學院看看，我聽過他們的公開課，老師講的挺不錯的，乾貨也多，據說老師都是從大廠裡面出來的，很有經驗，目前我還在學習中 路人甲的世界 在讀原始碼之前要確保你已經知道了這個軟體的 幾乎 所有細節與使用方法。如果軟體過於複雜，就唯讀你了解的那部分模組。邊讀邊寫注釋。...
怎麼閱讀Spring原始碼？
tageerxing Spring框架之beans原始碼完全解析 Spring框架之AOP原始碼完全解析 Spring框架之jdbc原始碼完全解析 Spring原始碼深度解析之資料庫連線JDBCSpring框架之jms原始碼完全解析 Spring框架之事務原始碼完全解析 Spring原始碼深度解析之...