神奇的HyperLogLog算法
2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>
原文鏈接：http://rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html?utm_source=tuicool&utm_medium=referral
神奇的HyperLogLog算法
?
基數(shù)計(jì)數(shù)基本概念
基數(shù)計(jì)數(shù)(cardinality counting)通常用來統(tǒng)計(jì)一個(gè)集合中不重復(fù)的元素個(gè)數(shù)，例如統(tǒng)計(jì)某個(gè)網(wǎng)站的UV，或者用戶搜索網(wǎng)站的關(guān)鍵詞數(shù)量。數(shù)據(jù)分析、網(wǎng)絡(luò)監(jiān)控及數(shù)據(jù)庫(kù)優(yōu)化等領(lǐng)域都會(huì)涉及到基數(shù)計(jì)數(shù)的需求。 要實(shí)現(xiàn)基數(shù)計(jì)數(shù)，最簡(jiǎn)單的做法是記錄集合中所有不重復(fù)的元素集合S_uS?u??，當(dāng)新來一個(gè)元素x_ix?i??，若S_uS?u??中不包含元素x_ix?i??，則將x_ix?i??加入S_uS?u??，否則不加入，計(jì)數(shù)值就是S_uS?u??的元素?cái)?shù)量。這種做法存在兩個(gè)問題：
大數(shù)據(jù)量背景下，要實(shí)現(xiàn)基數(shù)計(jì)數(shù)，首先需要確定存儲(chǔ)統(tǒng)計(jì)數(shù)據(jù)的方案，以及如何根據(jù)存儲(chǔ)的數(shù)據(jù)計(jì)算基數(shù)值；另外還有一些場(chǎng)景下需要融合多個(gè)獨(dú)立統(tǒng)計(jì)的基數(shù)值，例如對(duì)一個(gè)網(wǎng)站分別統(tǒng)計(jì)了三天的UV，現(xiàn)在需要知道這三天的UV總量是多少，怎么融合多個(gè)統(tǒng)計(jì)值。
基數(shù)計(jì)數(shù)方法
B樹
B樹最大的優(yōu)勢(shì)是插入和查找效率很高，如果用B樹存儲(chǔ)要統(tǒng)計(jì)的數(shù)據(jù)，可以快速判斷新來的數(shù)據(jù)是否已經(jīng)存在，并快速將元素插入B樹。要計(jì)算基數(shù)值，只需要計(jì)算B樹的節(jié)點(diǎn)個(gè)數(shù)。 將B樹結(jié)構(gòu)維護(hù)到內(nèi)存中，可以快速統(tǒng)計(jì)和計(jì)算，但依然存在問題，B樹結(jié)構(gòu)只是加快了查找和插入效率，并沒有節(jié)省存儲(chǔ)內(nèi)存。例如要同時(shí)統(tǒng)計(jì)幾萬(wàn)個(gè)鏈接的UV，每個(gè)鏈接的訪問量都很大，如果把這些數(shù)據(jù)都維護(hù)到內(nèi)存中，實(shí)在是夠嗆。
bitmap
bitmap可以理解為通過一個(gè)bit數(shù)組來存儲(chǔ)特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)，每一個(gè)bit位都能獨(dú)立包含信息，bit是數(shù)據(jù)的最小存儲(chǔ)單位，因此能大量節(jié)省空間，也可以將整個(gè)bit數(shù)據(jù)一次性load到內(nèi)存計(jì)算。 如果定義一個(gè)很大的bit數(shù)組，基數(shù)統(tǒng)計(jì)中每一個(gè)元素對(duì)應(yīng)到bit數(shù)組的其中一位，例如bit數(shù)組?001101001001101001代表實(shí)際數(shù)組[2,3,5,8][2,3,5,8]。新加入一個(gè)元素，只需要將已有的bit數(shù)組和新加入的數(shù)字做按位或?(or)(or)計(jì)算。bitmap中1的數(shù)量就是集合的基數(shù)值。
bitmap有一個(gè)很明顯的優(yōu)勢(shì)是可以輕松合并多個(gè)統(tǒng)計(jì)結(jié)果，只需要對(duì)多個(gè)結(jié)果求異或就可以。也可以大大減少存儲(chǔ)內(nèi)存，可以做個(gè)簡(jiǎn)單的計(jì)算，如果要統(tǒng)計(jì)1億個(gè)數(shù)據(jù)的基數(shù)值，大約需要內(nèi)存： 100000000/8/1024/1024?\approx≈?12M
如果用32bit的int代表每個(gè)統(tǒng)計(jì)數(shù)據(jù)，大約需要內(nèi)存：
32*100000000/8/1024/1024?\approx≈?381M
bitmap對(duì)于內(nèi)存的節(jié)約量是顯而易見的，但還是不夠。統(tǒng)計(jì)一個(gè)對(duì)象的基數(shù)值需要12M，如果統(tǒng)計(jì)10000個(gè)對(duì)象，就需要將近120G了，同樣不能廣泛用于大數(shù)據(jù)場(chǎng)景。
概率算法
實(shí)際上目前還沒有發(fā)現(xiàn)更好的在大數(shù)據(jù)場(chǎng)景中準(zhǔn)確計(jì)算基數(shù)的高效算法，因此在不追求絕對(duì)準(zhǔn)確的情況下，使用概率算法算是一個(gè)不錯(cuò)的解決方案。概率算法不直接存儲(chǔ)數(shù)據(jù)集合本身，通過一定的概率統(tǒng)計(jì)方法預(yù)估基數(shù)值，這種方法可以大大節(jié)省內(nèi)存，同時(shí)保證誤差控制在一定范圍內(nèi)。目前用于基數(shù)計(jì)數(shù)的概率算法包括:
- Linear Counting(LC)：早期的基數(shù)估計(jì)算法，LC在空間復(fù)雜度方面并不算優(yōu)秀，實(shí)際上LC的空間復(fù)雜度與上文中簡(jiǎn)單bitmap方法是一樣的（但是有個(gè)常數(shù)項(xiàng)級(jí)別的降低），都是O(N_{max})O(N?max??)；
- LogLog Counting(LLC)：LogLog Counting相比于LC更加節(jié)省內(nèi)存，空間復(fù)雜度只有O(log_2(log_2(N_{max})))O(log?2??(log?2??(N?max??)))
- HyperLogLog Counting(HLL)：HyperLogLog Counting是基于LLC的優(yōu)化和改進(jìn)，在同樣空間復(fù)雜度情況下，能夠比LLC的基數(shù)估計(jì)誤差更小。
下面將著重講HLL的原理和計(jì)算過程。
HyperLogLog的驚人表現(xiàn)
上面我們計(jì)算過用bitmap存儲(chǔ)1一億個(gè)統(tǒng)計(jì)數(shù)據(jù)大概需要12M內(nèi)存；而在HLL中，只需要不到1K內(nèi)存就能做到；redis中實(shí)現(xiàn)的HyperLogLog，只需要12K內(nèi)存，在標(biāo)準(zhǔn)誤差0.81%的前提下，能夠統(tǒng)計(jì)2^{64}2?64??個(gè)數(shù)據(jù)。首先容我感嘆一下數(shù)學(xué)的強(qiáng)大和魅力，那么概率算法是怎樣做到如此節(jié)省內(nèi)存的，又是怎樣控制誤差的呢？
首先簡(jiǎn)單展示一下HLL的基本做法，HLL中實(shí)際存儲(chǔ)的是一個(gè)長(zhǎng)度為mm的大數(shù)組SS，將待統(tǒng)計(jì)的數(shù)據(jù)集合劃分成mm組，每組根據(jù)算法記錄一個(gè)統(tǒng)計(jì)值存入數(shù)組中。數(shù)組的大小mm由算法實(shí)現(xiàn)方自己確定，redis中這個(gè)數(shù)組的大小是16834，mm越大，基數(shù)統(tǒng)計(jì)的誤差越小，但需要的內(nèi)存空間也越大。
這里有個(gè)HLL demo可以看一下HLL到底是怎么做到這種超乎想象的事情的。
看到這里心里應(yīng)該有無數(shù)個(gè)問號(hào)，這樣真的就能統(tǒng)計(jì)到上億條數(shù)據(jù)的基數(shù)了嗎？我總結(jié)一下，先拋出三個(gè)疑問：
hyperloglog原理理解
舉一個(gè)我們最熟悉的拋硬幣例子，出現(xiàn)正反面的概率都是1/2，一直拋硬幣直到出現(xiàn)正面，記錄下投擲次數(shù)kk，將這種拋硬幣多次直到出現(xiàn)正面的過程記為一次伯努利過程，對(duì)于nn次伯努利過程，我們會(huì)得到nn個(gè)出現(xiàn)正面的投擲次數(shù)值k_1k?1??,k_2k?2??……k_nk?n??，其中最大值記為k_{max}k?max??，那么可以得到下面結(jié)論：
對(duì)于第一個(gè)結(jié)論，nn次伯努利過程的拋擲次數(shù)都不大于k_{max}k?max??的概率用數(shù)學(xué)公式表示為：?
P_n(X \le k_{max})=(1-1/2^{k_{max}})^nP?n??(X≤k?max??)=(1?1/2?k?max????)?n??
第二個(gè)結(jié)論至少有一次等于k_{max}k?max??的概率用數(shù)學(xué)公式表示為：?
P_n(X \ge k_{max})=1-(1-1/2^{k_{max}-1})^nP?n??(X≥k?max??)=1?(1?1/2?k?max???1??)?n??
當(dāng)n\ll 2^{k_{max}}n?2?k?max????時(shí)，P_n(X \ge k_{max})\approx0P?n??(X≥k?max??)≈0，即當(dāng)nn遠(yuǎn)小于2^{k_{max}}2?k?max????時(shí)，上述第一條結(jié)論不成立；?
當(dāng)n\gg 2^{k_{max}}n?2?k?max????時(shí)，P_n(X \le k_{max})\approx0P?n??(X≤k?max??)≈0，即當(dāng)nn遠(yuǎn)大于2^{k_{max}}2?k?max????時(shí)，上述第二條結(jié)論不成立。 因此，我們似乎就可以用2^{k_{max}}2?k?max????的值來估計(jì)nn的大小。
以上結(jié)論可以總結(jié)為：進(jìn)行了nn次進(jìn)行拋硬幣實(shí)驗(yàn)，每次分別記錄下第一次拋到正面的拋擲次數(shù)kk，那么可以用n次實(shí)驗(yàn)中最大的拋擲次數(shù)k_{max}k?max??來預(yù)估實(shí)驗(yàn)組數(shù)量nn：?\hat{n} = 2^{k_{max}}?n?^??=2?k?max????可以通過一組小實(shí)驗(yàn)驗(yàn)證一下這種估計(jì)方法是否基本合理。
回到基數(shù)統(tǒng)計(jì)的問題，我們需要統(tǒng)計(jì)一組數(shù)據(jù)中不重復(fù)元素的個(gè)數(shù)，集合中每個(gè)元素的經(jīng)過hash函數(shù)后可以表示成0和1構(gòu)成的二進(jìn)制數(shù)串，一個(gè)二進(jìn)制串可以類比為一次拋硬幣實(shí)驗(yàn)，1是拋到正面，0是反面。二進(jìn)制串中從低位開始第一個(gè)1出現(xiàn)的位置可以理解為拋硬幣試驗(yàn)中第一次出現(xiàn)正面的拋擲次數(shù)kk，那么基于上面的結(jié)論，我們可以通過多次拋硬幣實(shí)驗(yàn)的最大拋到正面的次數(shù)來預(yù)估總共進(jìn)行了多少次實(shí)驗(yàn)，同樣可以可以通過第一個(gè)1出現(xiàn)位置的最大值k_{max}k?max??來預(yù)估總共有多少個(gè)不同的數(shù)字（整體基數(shù)）。
這種通過局部信息預(yù)估整體數(shù)據(jù)流特性的方法似乎有些超出我們的基本認(rèn)知，需要用概率和統(tǒng)計(jì)的方法才能推導(dǎo)和驗(yàn)證這種關(guān)聯(lián)關(guān)系。HyperLogLog核心在于觀察集合中每個(gè)數(shù)字對(duì)應(yīng)的比特串，通過統(tǒng)計(jì)和記錄比特串中最大的出現(xiàn)1的位置來估計(jì)集合整體的基數(shù)，可以大大減少內(nèi)存耗費(fèi)。
現(xiàn)在回到第二節(jié)中關(guān)于HyperLogLog的第一個(gè)疑問，為什么要統(tǒng)計(jì)hash值中第一個(gè)1出現(xiàn)的位置？
第一個(gè)1出現(xiàn)的位置可以類比為拋硬幣實(shí)驗(yàn)中第一次拋到正面的拋擲次數(shù)，根據(jù)拋硬幣實(shí)驗(yàn)的結(jié)論，記錄每個(gè)數(shù)據(jù)的第一個(gè)出現(xiàn)的位置kk，就可以通過其中最大值{k_{max}}k?max??推導(dǎo)出數(shù)據(jù)集合的基數(shù)：\hat{n} = 2^{k_{max}}?n?^??=2?k?max????。
hyperloglog算法講解
分桶平均
HLL的基本思想是利用集合中數(shù)字的比特串第一個(gè)1出現(xiàn)位置的最大值來預(yù)估整體基數(shù)，但是這種預(yù)估方法存在較大誤差，為了改善誤差情況，HLL中引入分桶平均的概念。?
同樣舉拋硬幣的例子，如果只有一組拋硬幣實(shí)驗(yàn)，運(yùn)氣較好，第一次實(shí)驗(yàn)過程就拋了10次才第一次拋到正面，顯然根據(jù)公式推導(dǎo)得到的實(shí)驗(yàn)次數(shù)的估計(jì)誤差較大；如果100個(gè)組同時(shí)進(jìn)行拋硬幣實(shí)驗(yàn)，同時(shí)運(yùn)氣這么好的概率就很低了，每組分別進(jìn)行多次拋硬幣實(shí)驗(yàn)，并上報(bào)各自實(shí)驗(yàn)過程中拋到正面的拋擲次數(shù)的最大值，就能根據(jù)100組的平均值預(yù)估整體的實(shí)驗(yàn)次數(shù)了。
分桶平均的基本原理是將統(tǒng)計(jì)數(shù)據(jù)劃分為mm個(gè)桶，每個(gè)桶分別統(tǒng)計(jì)各自的{k_{max}}k?max??并能得到各自的基數(shù)預(yù)估值?\hat{n}?n?^???，最終對(duì)這些?\hat{n}?n?^???求平均得到整體的基數(shù)估計(jì)值。LLC中使用幾何平均數(shù)預(yù)估整體的基數(shù)值，但是當(dāng)統(tǒng)計(jì)數(shù)據(jù)量較小時(shí)誤差較大；HLL在LLC基礎(chǔ)上做了改進(jìn)，采用調(diào)和平均數(shù)，調(diào)和平均數(shù)的優(yōu)點(diǎn)是可以過濾掉不健康的統(tǒng)計(jì)值，具體的計(jì)算公式為：
回到第二節(jié)中關(guān)于HLL的第二個(gè)疑問，為什么要有分桶數(shù)組??？分桶數(shù)組是為了消減因偶然性帶來的誤差，提高預(yù)估的準(zhǔn)確性。那么分桶數(shù)組的大小怎么確定呢？?
這是由算法實(shí)現(xiàn)方自己設(shè)定的，例如上面HLL demo中，設(shè)定統(tǒng)計(jì)數(shù)組的大小，如果函數(shù)得到的比特串是32位，需要其中6()位定位分桶數(shù)組中的桶的位置，還剩下26位（需要記錄的出現(xiàn)1的位置的最大值是26），那么數(shù)組中每個(gè)桶需要5()位記錄1第一次出現(xiàn)的位置，整個(gè)統(tǒng)計(jì)數(shù)組需要花費(fèi)的內(nèi)存為：?
?
也就是用32bit的內(nèi)存能夠統(tǒng)計(jì)的基數(shù)數(shù)量為。
偏差修正
上述經(jīng)過分桶平均后的估計(jì)量看似已經(jīng)很不錯(cuò)了，不過通過數(shù)學(xué)分析可以知道這并不是基數(shù)n的無偏估計(jì)。因此需要修正成無偏估計(jì)。這部分的具體數(shù)學(xué)分析在“Loglog Counting of Large Cardinalities”中。
其中系數(shù)由統(tǒng)計(jì)數(shù)組的大小??決定，具體的公式為：
根據(jù)論文中分析結(jié)論，HLL與LLC一樣是漸進(jìn)無偏估計(jì)，漸進(jìn)標(biāo)準(zhǔn)誤差表示為：
因此，統(tǒng)計(jì)數(shù)組大小??越大，基數(shù)統(tǒng)計(jì)的標(biāo)準(zhǔn)誤差越小，但需要的存儲(chǔ)空間也越大，在?的情況下，HLL的標(biāo)準(zhǔn)誤差為1.1%。
雖然調(diào)和平均數(shù)能夠適當(dāng)修正算法誤差，但作者給出一種分階段修正算法。當(dāng)HLL算法開始統(tǒng)計(jì)數(shù)據(jù)時(shí)，統(tǒng)計(jì)數(shù)組中大部分位置都是空數(shù)據(jù)，并且需要一段時(shí)間才能填滿數(shù)組，這種階段引入一種小范圍修正方法；當(dāng)HLL算法中統(tǒng)計(jì)數(shù)組已滿的時(shí)候，需要統(tǒng)計(jì)的數(shù)據(jù)基數(shù)很大，這時(shí)候hash空間會(huì)出現(xiàn)很多碰撞情況，這種階段引入一種大范圍修正方法。最終算法用偽代碼可以表示為如下。
?m = 2^b # with b in [4...16]
if m == 16:
alpha = 0.673
elif m == 32:
alpha = 0.697
elif m == 64:
alpha = 0.709
else:
alpha = 0.7213/(1 + 1.079/m)
registers = [0]*m # initialize m registers to 0
###########################################################################
# Construct the HLL structure
for h in hashed(data):
register_index = 1 + get_register_index( h,b ) # binary address of the rightmost b bits
run_length = run_of_zeros( h,b ) # length of the run of zeroes starting at bit b+1
registers[ register_index ] = max( registers[ register_index ], run_length )
##########################################################################
# Determine the cardinality
DV_est = alpha * m^2 * 1/sum( 2^ -register ) # the DV estimate
if DV_est < 5/2 * m: # small range correction
V = count_of_zero_registers( registers ) # the number of registers equal to zero
if V == 0: # if none of the registers are empty, use the HLL estimate
DV = DV_est
else:
DV = m * log(m/V) # i.e. balls and bins correction
if DV_est <= ( 1/30 * 2^32 ): # intermediate range, no correction
DV = DV_est
if DV_est > ( 1/30 * 2^32 ): # large range correction
DV = -2^32 * log( 1 - DV_est/2^32)
redis中hyperloglog實(shí)現(xiàn)
redis正是基于以上的HLL算法實(shí)現(xiàn)的HyperLogLog結(jié)構(gòu)，用于統(tǒng)計(jì)一組數(shù)據(jù)集合中不重復(fù)的數(shù)據(jù)個(gè)數(shù)。 redis中統(tǒng)計(jì)數(shù)組大小設(shè)置為，hash函數(shù)生成64位bit數(shù)組，其中??位用來找到統(tǒng)計(jì)數(shù)組的位置，剩下50位用來記錄第一個(gè)1出現(xiàn)的位置，最大位置為50，需要?位記錄。
那么統(tǒng)計(jì)數(shù)組需要的最大內(nèi)存大小為：??基數(shù)估計(jì)的標(biāo)準(zhǔn)誤差為。可以學(xué)習(xí)一下redis中HyperLogLog的源碼實(shí)現(xiàn)。
參考閱讀
Redis new data structure: the HyperLogLog
HyperLogLog — Cornerstone of a Big Data Infrastructure
解讀Cardinality Estimation算法（第四部分：HyperLogLog Counting及Adaptive Counting）
轉(zhuǎn)載于:https://my.oschina.net/u/2330181/blog/1926470
總結(jié)
以上是生活随笔為你收集整理的神奇的HyperLogLog算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 云计算之KVM虚拟化实战
- 下一篇： 第58件事 借势文案创作实例