基數(shù)估算

HyperLogLog 是一種基數(shù)估算算法。所謂基數(shù)估算，就是估算在一批數(shù)據(jù)中，不重復(fù)元素的個(gè)數(shù)有多少。最常見的場景就是統(tǒng)計(jì)uv。
首先要說明，HyperLogLog實(shí)際上不會(huì)存儲(chǔ)每個(gè)元素的值，它使用的是概率算法，通過存儲(chǔ)元素的hash值的第一個(gè)1的位置，來計(jì)算元素?cái)?shù)量。這樣做存在誤差，不適合絕對準(zhǔn)確計(jì)數(shù)的場景。
redis中實(shí)現(xiàn)的HyperLogLog，只需要12K內(nèi)存，在標(biāo)準(zhǔn)誤差0.81%的前提下，能夠統(tǒng)計(jì)2的64次方個(gè)數(shù)據(jù)。

HyperLogLog 算法簡介

伯努利過程

在認(rèn)識(shí)為什么HyperLogLog能夠使用極少的內(nèi)存來統(tǒng)計(jì)巨量的數(shù)據(jù)之前，要先認(rèn)識(shí)下伯努利試驗(yàn)。

伯努利試驗(yàn)其實(shí)簡單來說，就是一個(gè)拋硬幣游戲

image

假設(shè)你拋了很多次硬幣，你告訴在這次拋硬幣的過程中最多只有兩次扔出連續(xù)的反面，讓我猜你總共拋了多少次硬幣，我敢打賭你拋硬幣的總次數(shù)不會(huì)太多，相反，如果你和我說最多出現(xiàn)了100次連續(xù)的反面，那么我敢肯定扔硬盤的總次數(shù)非常的多，甚至我還可以給出一個(gè)估計(jì)，這個(gè)估計(jì)要怎么給呢？其實(shí)是一個(gè)很簡單的概率問題，假設(shè)1代表拋出正面，0代表反面

image

上圖中以拋硬幣序列"1110100110"為例，其中最長的反面序列是"00"，我們順手把后面那個(gè)1也給帶上，也就是"001"，因?yàn)樗诵蛄兄凶铋L的一串0，所以在序列中肯定只出現(xiàn)過一次，而它在任意序列出現(xiàn)出現(xiàn)且僅出現(xiàn)一次的概率顯然是上圖所示的三個(gè)二分之一相乘，也就是八分之一，所以我可以給出一個(gè)估計(jì)值，你大概總共拋了8次硬幣。
很顯然，上面這種做法雖然能夠估計(jì)拋硬幣的總數(shù)，但是顯然誤差是比較大的，很容易受到突發(fā)事件（比如突然連續(xù)拋出好多0）的影響，HyperLogLog算法研究的就是如何減小這個(gè)誤差。

hyperloglog過程

過程簡單介紹

之前說過，HyperLogLog算法是用來計(jì)算基數(shù)的，這個(gè)拋硬幣的序列和基數(shù)有什么關(guān)系呢？比如在數(shù)據(jù)庫中，我只要在每次插入一條新的記錄時(shí)，計(jì)算這條記錄的hash，并且轉(zhuǎn)換成二進(jìn)制，就可以將其看成一個(gè)硬幣序列了，如下(0b前綴表示二進(jìn)制數(shù))：

image

根據(jù)上面拋硬幣的啟發(fā)我可以想到如下的估計(jì)基數(shù)的算法

輸入：一個(gè)集合
輸出：集合的基數(shù)
算法：
     max = 0
     對于集合中的每個(gè)元素：
               hashCode = hash(元素)
               num = hashCode二進(jìn)制表示中最前面連續(xù)的0的數(shù)量
               if num > max:
                   max = num
     最后的結(jié)果是2的(max + 1)次冪  

顯然這個(gè)算法是非常不準(zhǔn)確的，但是這個(gè)想法還是很有啟發(fā)性的，從這個(gè)簡單的想法跟隨下文一步一步優(yōu)化即可得到最終的比較高精度的HyperLogLog算法。

分桶

其實(shí)想要把結(jié)果更精確，有一個(gè)辦法就是求平均數(shù)，但是求平均數(shù)有個(gè)問題，比如我的工資1000塊，我同事的工資100000元一個(gè)月，那么我和同事的平均工資就是(100000 + 1000)/2，即50500元，顯然這離我的工資相差甚遠(yuǎn)，我肯定不服這個(gè)平均工資，用調(diào)和平均數(shù)就可以解決這一問題，調(diào)和平均數(shù)的結(jié)果會(huì)傾向于集合中比較小的數(shù)，x1到xn的調(diào)和平均數(shù)的公式如下

image

再用這個(gè)公式算一下我和同事的平均工資：

image

redis的分桶處理

1: redis在接收到字符串的時(shí)候，會(huì)就行hash運(yùn)算，得到64位比特串

image

2:HyperLogLog 將上文所說的 64 位比特串的低 14 位單獨(dú)拿出，它的值就對應(yīng)桶的序號(hào)，然后將剩下 50 位中第一次出現(xiàn) 1 的位置值設(shè)置到桶中。50位中出現(xiàn)1的位置值最大為50，所以每個(gè)桶中的 6 位數(shù)組正好可以表示該值。

3:在設(shè)置前，要設(shè)置進(jìn)桶的值是否大于桶中的舊值，如果大于才進(jìn)行設(shè)置，否則不進(jìn)行設(shè)置。示例如下圖所示。

image

此時(shí)為了性能考慮，是不會(huì)去統(tǒng)計(jì)當(dāng)前的基數(shù)的，而是將 HyperLogLog 頭的 card 屬性中的標(biāo)志位置為 1，表示下次進(jìn)行 pfcount 操作的時(shí)候，當(dāng)前的緩存值已經(jīng)失效了，需要重新統(tǒng)計(jì)緩存值。在后面 pfcount 流程的時(shí)候，發(fā)現(xiàn)這個(gè)標(biāo)記為失效，就會(huì)去重新統(tǒng)計(jì)新的基數(shù)，放入基數(shù)緩存。

在計(jì)算近似基數(shù)時(shí)，就分別計(jì)算每個(gè)桶中的值，帶入到上文將的 DV 公式中，進(jìn)行調(diào)和平均和結(jié)果修正，就能得到估算的基數(shù)值。

hyperloglog源碼分析

struct hllhdr {
    char magic[4];      /*魔法值 "HYLL" */
    uint8_t encoding;   /* 密集結(jié)構(gòu)或者稀疏結(jié)構(gòu) HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /*保留位, 全為0. Reserved for future use, must be zero. */
    uint8_t card[8];    /* 基數(shù)大小的緩存 Cached cardinality, little endian. */
    uint8_t registers[]; /* 數(shù)據(jù)字節(jié)數(shù)組Data bytes. */
};

其實(shí)registers就是我們上面所謂的桶，它有兩種存儲(chǔ)結(jié)構(gòu)，分別為密集存儲(chǔ)結(jié)構(gòu)和稀疏存儲(chǔ)結(jié)構(gòu)，兩種結(jié)構(gòu)只涉及存儲(chǔ)和桶的表現(xiàn)形式，從中我們可以看到 Redis 對節(jié)省內(nèi)存極致地追求。

密集存儲(chǔ)結(jié)構(gòu)

image

我們先來看密集存儲(chǔ)結(jié)構(gòu)，相對是比較簡單的，既然要有 2^14 個(gè) 6 bit的桶，那么我就真使用足夠多的 uint8_t 字節(jié)去表示，只是此時(shí)會(huì)涉及到字節(jié)位置和桶的轉(zhuǎn)換，因?yàn)樽止?jié)有 8 位，而桶只需要 6 位。

至于具體怎么轉(zhuǎn)換我們就先不說了，這個(gè)比較麻煩，感興趣的可以自己研究一下源碼

稀疏存儲(chǔ)結(jié)構(gòu)

HyperLogLog 的稀疏存儲(chǔ)結(jié)構(gòu)是為了節(jié)約內(nèi)存消耗，它不像密集存儲(chǔ)模式一樣，真正找了那么多個(gè)字節(jié)數(shù)組來表示2^14 個(gè)桶，而是使用特殊的字節(jié)結(jié)構(gòu)來表達(dá)。

image

Redis 為了方便表達(dá)稀疏存儲(chǔ)，它將上面三種字節(jié)表示形式分別賦予了一條指令。

• ZERO : 一字節(jié)，表示連續(xù)多少個(gè)桶計(jì)數(shù)為0，前兩位為標(biāo)志00，后6位表示有多少個(gè)桶，最大為64。
• XZERO : 兩個(gè)字節(jié)，表示連續(xù)多少個(gè)桶計(jì)數(shù)為0，前兩位為標(biāo)志01，后14位表示有多少個(gè)桶，最大為16384
• VAL : 一字節(jié)，表示連續(xù)多少個(gè)桶的計(jì)數(shù)為多少，前一位為標(biāo)志1，四位表示連桶內(nèi)計(jì)數(shù)，所以最大表示桶的計(jì)數(shù)為32。后兩位表示連續(xù)多少個(gè)桶。

image

所以，一個(gè)初始狀態(tài)的 HyperLogLog 對象只需要2 字節(jié)，也就是一個(gè) XZERO 來存儲(chǔ)其數(shù)據(jù)，而不需要消耗12K 內(nèi)存。當(dāng) HyperLogLog 插入了少數(shù)元素時(shí)，可以只使用少量的 XZERO、VAL 和 ZERO 進(jìn)行表示，如下圖所示。

image

Redis從稀疏存儲(chǔ)轉(zhuǎn)換到密集存儲(chǔ)的條件是：

• 任意一個(gè)計(jì)數(shù)值從 32 變成 33，因?yàn)?VAL 指令已經(jīng)無法容納，它能表示的計(jì)數(shù)值最大為 32
• 稀疏存儲(chǔ)占用的總字節(jié)數(shù)超過 3000 字節(jié)，這個(gè)閾值可以通過 hll_sparse_max_bytes 參數(shù)進(jìn)行調(diào)整

幾句嘮叨

大家好，我是小飯，一枚后端工程師。如果覺得文章對你有一點(diǎn)點(diǎn)幫助，歡迎分享給你的朋友，也給小飯點(diǎn)個(gè)贊，我的公眾號(hào)----程序員小飯，感興趣可以關(guān)注，這是小飯堅(jiān)持下去的動(dòng)力，謝謝大家，我們下次見！