前言

在很久（好像也沒(méi)多久，4個(gè)月）之前救斑，我曾經(jīng)寫了一篇和主業(yè)無(wú)關(guān)的有點(diǎn)意思的小文章《基數(shù)估計(jì)探秘：Linear Counting與Flajolet-Martin算法》假勿。但是這篇文章講的兩個(gè)算法都已經(jīng)老掉牙了，實(shí)際應(yīng)用最廣泛的基數(shù)估計(jì)算法是HyperLogLog（HLL）算法。

最近筆者基于Flink搞了些從超大行為數(shù)據(jù)集計(jì)算UV的工作藻懒，用到了Redis的HyperLogLog，感覺(jué)是時(shí)候?qū)憘€(gè)續(xù)篇了视译。在讀本文之前嬉荆，強(qiáng)烈建議看官先讀之前的那篇，就算不深挖細(xì)節(jié)憎亚，也能夠獲得一些基數(shù)估計(jì)方面的背景知識(shí)员寇。

LogLog Counting（LLC）算法

等等，不是叫HyperLogLog么第美，怎么這里變LogLog了蝶锋？很簡(jiǎn)單，HLL是基于LLC的改進(jìn)什往，所以我們有必要了解LLC扳缕。該算法由M. Durand、P. Flajolet在2003年的論文《Loglog Counting of Large Cardinalities》中首次提出别威。下面看看這個(gè)算法是怎么操作的躯舔。

首先我們得有一個(gè)哈希函數(shù)H(x)，并且滿足如下條件：

• 哈希結(jié)果盡量服從均勻分布省古；
• 碰撞概率盡量兄嘧；
• 結(jié)果是長(zhǎng)度固定為L(zhǎng)的二進(jìn)制串豺妓。

然后定義符號(hào)ρ(y)惜互，它代表將數(shù)y表示成二進(jìn)制串后，從左向右讀遇到的第一個(gè)“1”的位置下標(biāo)（下標(biāo)從1開(kāi)始琳拭，忽略全0的情況）训堆，也就是前導(dǎo)0的個(gè)數(shù)+1。

LogLog Counting算法的流程如下：

1. 對(duì)每個(gè)待測(cè)集合中的元素x白嘁，計(jì)算它的哈希值y=H(x)坑鱼。
2. 將哈希值y通過(guò)它們的前k=logm個(gè)比特分組（即分桶），作為桶的編號(hào)絮缅，即一共有m個(gè)桶鲁沥。
3. 將y的后L - k個(gè)比特作為真正參與基數(shù)估計(jì)的串s，計(jì)算并記錄下所有桶內(nèi)的ρ(s)耕魄。
4. 令M[k]表示第k個(gè)桶內(nèi)所有元素中最大的那個(gè)ρ值黍析，那么該集合基數(shù)的估計(jì)量為：

? = α_m · m · 2^{ΣM[i] / m}

其中α_m是修正參數(shù)。有沒(méi)有覺(jué)得這個(gè)算法流程有點(diǎn)似曾相識(shí)的意思屎开？

實(shí)際上阐枣，它與前面說(shuō)過(guò)的Flajolet-Martin算法的PCSA變種非常相似马靠，也采用了分桶平均的思想，只不過(guò)在精確度方面又做了一些其他工作蔼两。因此與它相關(guān)的細(xì)節(jié)（比如為什么ρ_max可以作為估計(jì)量）可以參考上一篇文章甩鳄。

那么α是怎么來(lái)的呢？這個(gè)過(guò)程極其復(fù)雜额划，直接說(shuō)結(jié)論吧妙啃。根據(jù)之前對(duì)伯努利實(shí)驗(yàn)的分析，可以知道：

P_n{X=k} = (1 - 1/2^k)ⁿ - (1 - 1/2^k-1)ⁿ

它是一個(gè)無(wú)窮遞推數(shù)列俊戳，采用指數(shù)生成函數(shù)和泊松化的方法處理揖赴，得到估計(jì)量的泊松期望和方差如下：

進(jìn)而推出算法流程第4步的估計(jì)量。這是一個(gè)漸進(jìn)無(wú)偏估計(jì)量抑胎，其中：

這是LLC比F-M算法更精細(xì)的地方之一燥滑。

LLC的空間復(fù)雜度是多少呢？不難得知阿逃，在F-M算法中铭拧，我們可以用logN個(gè)比特來(lái)存儲(chǔ)哈希值，而LLC算法只存儲(chǔ)下標(biāo)（即ρ值）就夠用了恃锉，所以可以降低為log(logN)個(gè)比特搀菩。再加上分桶數(shù)為m，亦即它的空間復(fù)雜度是：

O[m · log(logN)]

這也就是LogLog Counting這個(gè)名字的由來(lái)破托。

根據(jù)論文中給出的數(shù)據(jù)肪跋，LLC的誤差在m不算太小（大于64）時(shí)土砂，大概是：

StdError ≈ 1.30 / √m

雖然LLC的誤差常數(shù)比F-M算法的還大（F-M是0.78）澎嚣，但是由于空間復(fù)雜度從log級(jí)別降低到了loglog級(jí)別，所以相同誤差下實(shí)際的空間開(kāi)銷要更小瘟芝。

分桶數(shù)m完全由可接受的精確度決定。但這個(gè)誤差的前提是實(shí)際基數(shù)N要遠(yuǎn)遠(yuǎn)大于分桶數(shù)m（因?yàn)?是漸近無(wú)偏的）褥琐，所以在集合比較小時(shí)锌俱，LLC算法的效果要打折扣，這點(diǎn)與F-M-PCSA是相同的敌呈。

LLC算法本質(zhì)上不是個(gè)新的算法贸宏，并且也從未大規(guī)模地使用過(guò)。它的主要意義有三：

• 與F-M算法相比磕洪，經(jīng)過(guò)了非常完備的實(shí)驗(yàn)分析與驗(yàn)證吭练；
• 在精確度和空間占用之間取得了更好的平衡；
• 作為后續(xù)HyperLogLog算法產(chǎn)生的基礎(chǔ)析显。

HyperLogLog（HLL）算法

HLL由四位大佬P. Flajolet鲫咽、é. Fusy、O. Gandouet、F. Meunier（全是法語(yǔ)名字）在2007年的論文《HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm》中提出分尸。從論文題目可以得知锦聊，這個(gè)算法已經(jīng)相當(dāng)優(yōu)化了。實(shí)際上它的算法流程與LLC仍然幾乎相同箩绍，那么它到底“hyper”在哪里呢孔庭？

一是分桶平均的時(shí)候，采用調(diào)和平均數(shù)材蛛。我們知道圆到，調(diào)和平均數(shù)的定義是：

n / [1/x₁ + 1/x₂ + ... + 1/x_n] = n / [Σ 1/x_i]

在LLC算法中，采用的是ρ_max的算術(shù)平均數(shù)卑吭，并且它是作為2的指數(shù)芽淡，所以本質(zhì)上是幾何平均數(shù)。但是幾何平均數(shù)受離群值（即偏離均值很大的值）的影響非常大陨簇，分桶的空桶越多吐绵，LLC的估計(jì)值就越不準(zhǔn)確。調(diào)和平均數(shù)就不太有這種困擾河绽，所以集合基數(shù)的估計(jì)量就會(huì)變成：

? = α_m · m² / Σ 2^-M[i]

修正參數(shù)是：

為了實(shí)際應(yīng)用起來(lái)方便己单，一般采用如下的近似值：

二是根據(jù)基數(shù)估計(jì)值的大小，采用不同的估計(jì)方法進(jìn)行修正耙饰。論文中給出了在常見(jiàn)情況——即被估集合的基數(shù)在億級(jí)別以下纹笼，m取值在2^{[4, 16]}區(qū)間——下的修正的算法，如下圖所示苟跪。

翻譯成人話：

• 在估計(jì)值? ≤ 5m/2時(shí)廷痘，使用前面講過(guò)的Linear Counting算法估計(jì)，因?yàn)樗诨鶖?shù)較小時(shí)偏差也較屑选笋额；
• 5m/2 < ? ≤ 2³²/30時(shí)，直接使用HLL的結(jié)果篷扩；
• ? > 2³²/30時(shí)兄猩，結(jié)果為-2³²log(1 - ? / 2³²)。

HLL算法的空間復(fù)雜度與LLC相同鉴未，而標(biāo)準(zhǔn)差為：

StdError ≈ 1.04 / √m

可見(jiàn)枢冤，HLL算法的精度確實(shí)比LLC更高。根據(jù)論文中的描述铜秆，估計(jì)億級(jí)別集合的基數(shù)淹真，在偏差大約2%的情況下，只需要耗費(fèi)大約1.5kB內(nèi)存连茧。

HLL算法在很多框架中都有實(shí)現(xiàn)核蘸，其中尤以Redis的實(shí)現(xiàn)方法最為有名巍糯，但它的代碼量極大，如果寫在文章里的話會(huì)特別冗長(zhǎng)值纱，所以只是簡(jiǎn)單說(shuō)說(shuō)吧鳞贷。

Redis使用了2¹⁴=16384個(gè)桶，按照上面的標(biāo)準(zhǔn)差虐唠，誤差為0.81%搀愧，精度相當(dāng)高。Redis使用一個(gè)long型哈希值的前14個(gè)比特用來(lái)確定桶編號(hào)疆偿，剩下的50個(gè)比特用來(lái)做基數(shù)估計(jì)咱筛。而2⁶=64，所以只需要用6個(gè)比特表示下標(biāo)值杆故，在一般情況下迅箩，一個(gè)HLL數(shù)據(jù)結(jié)構(gòu)占用內(nèi)存的大小為16384 * 6 / 8 = 12kB，Redis將這種情況稱為密集（dense）存儲(chǔ)处铛。

既然有了密集存儲(chǔ)饲趋，自然就會(huì)有稀疏（sparse）存儲(chǔ)。當(dāng)多數(shù)桶的值為全0時(shí)撤蟆，為了節(jié)省空間奕塑，Redis會(huì)將連續(xù)的全0桶壓縮成0桶計(jì)數(shù)值。該計(jì)數(shù)值可以用單字節(jié)或雙字節(jié)表示家肯，高2bit為標(biāo)志位龄砰，因此可以分別表示連續(xù)64個(gè)全0桶和連續(xù)16384個(gè)全0桶。

Redis在HLL稀疏存儲(chǔ)中用ZERO宏表示單字節(jié)全0桶讨衣，XZERO宏表示雙字節(jié)全0桶换棚，VAL表示中途的少數(shù)非0桶。舉個(gè)例子反镇，假設(shè)只有第10001個(gè)桶和第10047個(gè)桶的值為1固蚤，其余都為0，那么整個(gè)存儲(chǔ)布局就是：

XZERO (10000) | VAL (1) | ZERO (45) | VAL (1) | XZERO (6337)

只需要5字節(jié)就能存儲(chǔ)了歹茶。當(dāng)稀疏存儲(chǔ)的總大小超過(guò)hll_sparse_max_bytes參數(shù)指定的大邢ν妗（默認(rèn)為3kB）時(shí)，就會(huì)自動(dòng)轉(zhuǎn)換成密集存儲(chǔ)辆亏。Redis還會(huì)在HLL數(shù)據(jù)結(jié)構(gòu)的頭部信息中緩存上一次計(jì)算出來(lái)的基數(shù)估計(jì)值，這樣可以避免不必要的重算鳖目，提高效率扮叨。

除了插入元素的PFADD指令之外，Redis提供的計(jì)數(shù)指令PFCOUNT和合并指令PFMERGE都支持將多個(gè)HLL合并起來(lái)领迈。由于HLL的桶只存儲(chǔ)下標(biāo)值彻磁，因此合并時(shí)只需要按桶取最大值就可以了碍沐。Redis的HLL算法在上述標(biāo)準(zhǔn)算法的基礎(chǔ)上做了一點(diǎn)改進(jìn)，比如預(yù)打表計(jì)算2^-M[i]的值衷蜓，以及用多項(xiàng)式回歸修正結(jié)果等累提。

最后推薦一個(gè)國(guó)外大佬做的HLL算法的動(dòng)態(tài)Demo，簡(jiǎn)單直觀磁浇，有助于理解斋陪，下面給出截圖以及網(wǎng)頁(yè)地址。

http://content.research.neustar.biz/blog/hll.html

The End

晚安晚安置吓。