Redis 在 2.8.9 版本添加了 HyperLogLog 結(jié)構(gòu)。
Redis HyperLogLog 是用來做基數(shù)統(tǒng)計的算法。
什么是基數(shù)血公？
比如數(shù)據(jù)集 {1, 3, 5, 7, 5, 7, 8}忱叭， 那么這個數(shù)據(jù)集的基數(shù)集為 {1, 3, 5 ,7, 8}, 基數(shù)(不重復(fù)元素)為5。 基數(shù)估計就是在誤差可接受的范圍內(nèi)塌计，快速計算基數(shù)。
基數(shù)計數(shù)(cardinality counting)通常用來統(tǒng)計一個集合中不重復(fù)的元素個數(shù)侯谁，例如統(tǒng)計某個網(wǎng)站的UV锌仅，或者用戶搜索網(wǎng)站的關(guān)鍵詞數(shù)量。如果統(tǒng)計 PV 那非常好辦墙贱，給每個網(wǎng)頁一個獨(dú)立的 Redis 計數(shù)器就可以了热芹，這個計數(shù)器的 key 后綴加上當(dāng)天的日期。這樣來一個請求惨撇，INCRBY 一次伊脓，最終就可以統(tǒng)計出所有的 PV 數(shù)據(jù)。
但是 UV 不一樣魁衙，它要去重报腔，同一個用戶一天之內(nèi)的多次訪問請求只能計數(shù)一次。這就要求每一個網(wǎng)頁請求都需要帶上用戶的 ID剖淀，無論是登陸用戶還是未登陸用戶都需要一個唯一 ID 來標(biāo)識纯蛾。如果采用元素越多耗費(fèi)內(nèi)存就越多的集合（HashSet、B+ Tree纵隔、BitMap）來存儲已登錄的用戶ID翻诉，那么在輸入元素的數(shù)量或者體積非常大時查重時間（O(log n)）與內(nèi)存開銷（O(n)）都是十分巨大的。相比之下HyperLogLog 計算基數(shù)所需的空間總是固定的捌刮、并且是很小的碰煌。在 Redis 里面，每個 HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存绅作，就可以計算接近 2^64 個不同元素的基數(shù)芦圾。
但是，因?yàn)?HyperLogLog 只會根據(jù)輸入元素來計算基數(shù)棚蓄，而不會儲存輸入元素本身堕扶，所以 HyperLogLog 不能像集合那樣，返回輸入的各個元素梭依，也不能刪除元素，這一點(diǎn)和布隆過濾器非常相似典尾。
此外役拴，HyperLogLog 提供的是不準(zhǔn)確的去重計數(shù)方案，但是可以保證基數(shù)隨統(tǒng)計量單調(diào)遞增钾埂，并且標(biāo)準(zhǔn)誤差達(dá)到 0.81%河闰，這樣的精確度已經(jīng)可以滿足大部分統(tǒng)計需求了科平。
HyperLogLog有三個非常簡單的API：
- PFADD 將多個值存入指定的HyperLogLog
- PFCOUNT 獲取指定HyperLogLog的基數(shù)
- PFMERGE 合并多個HyperLogLog，合并前的結(jié)果和合并后的統(tǒng)計結(jié)果完全一致（取并集）姜性，不存在因合并導(dǎo)致的誤差
HyperLogLog原理
舉一個我們最熟悉的拋硬幣例子瞪慧，出現(xiàn)正反面的概率都是1/2，一直拋硬幣直到出現(xiàn)正面部念，記錄下投擲次數(shù)k弃酌，將這種拋硬幣多次直到出現(xiàn)正面的過程記為一次伯努利過程，對于n次伯努利過程儡炼，我們會得到n個出現(xiàn)正面的投擲次數(shù)值其中最大值記為k?max妓湘，那么可以得到下面結(jié)論：
- n次伯努利過程的投擲次數(shù)都不大于k?max
- ?n次伯努利過程，至少有一次投擲次數(shù)等于k?max
那么根據(jù)最大似然估計的原理乌询，我們可以反過來講：進(jìn)行了n次進(jìn)行拋硬幣實(shí)驗(yàn)榜贴，每次分別記錄下第一次拋到正面的拋擲次數(shù)k，那么可以用n次實(shí)驗(yàn)中最大的拋擲次數(shù)k?max來預(yù)估實(shí)驗(yàn)組數(shù)量n：
N=2^K
基于這個原理妹田，如果我們對存入HyperLogLog的值進(jìn)行hash運(yùn)算唬党，所得hash碼的二進(jìn)制位就可以看做一次伯努利過程。每一位上的0或1就可以看作每次投擲硬幣的結(jié)果鬼佣，那么第一次出現(xiàn)1的位置所對應(yīng)的索引就可以看作kmax驶拱，那么根據(jù)kmax就可以估算存入的數(shù)據(jù)基數(shù)。
但是如果 N 介于 2^K 和 2^(K+1) 之間沮趣，用這種方式估計的值都等于 2^K屯烦，所以用這樣的單一估計偶然性較大，導(dǎo)致誤差較大房铭，因此在實(shí)際的 HyperLogLog 算法中驻龟，會先分桶統(tǒng)計然后計算平均值來消除誤差。這里使用的平均值是調(diào)和平均 (倒數(shù)的平均)缸匪。普通的平均法可能因?yàn)閭€別離群值對平均結(jié)果產(chǎn)生較大的影響翁狐，調(diào)和平均可以有效平滑離群值的影響。
上述經(jīng)過分桶平均后的估計量看似已經(jīng)很不錯了凌蔬，不過通過數(shù)學(xué)分析可以知道這并不是基數(shù)n的無偏估計露懒，因此需要修正成無偏估計。當(dāng)HyperLogLog開始統(tǒng)計數(shù)據(jù)時砂心，統(tǒng)計數(shù)組中大部分位置都是空數(shù)據(jù)懈词，并且需要一段時間才能填滿數(shù)組，這種階段引入一種小范圍修正方法辩诞；當(dāng)統(tǒng)計數(shù)組已滿的時候坎弯，需要統(tǒng)計的數(shù)據(jù)基數(shù)很大，這時候hash空間會出現(xiàn)很多碰撞情況，這種階段引入一種大范圍修正方法抠忘。其中系數(shù)由統(tǒng)計數(shù)組的大小決定撩炊，最終算法用偽代碼可以表示為：
// m 為桶數(shù) b是m的以2為底的對數(shù)
m = 2^b
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中的實(shí)現(xiàn)細(xì)節(jié)
數(shù)據(jù)在存入時，value 會被 hash 成 64 位崎脉，即 64 bit 的比特字符串拧咳，前 14 位用來選擇這個 value 的比特串中從右往左第一個 1 出現(xiàn)的下標(biāo)位置數(shù)值要存到那個桶中去，即前 14 位用來分桶囚灼。之所以選 14位 來表達(dá)桶編號是因?yàn)槁嫦ィ至?16384 個桶，而 2^14 = 16384啦撮，剛好可以把每個編號都利用上谭网，不造成浪費(fèi)。假設(shè)一個字符串的前 14 位是：00 0000 0000 0010 (從右往左看) 赃春，其十進(jìn)制值為 2愉择。那么 index 將會被轉(zhuǎn)化后放到編號為 2 的桶。每個桶的index 需要 6 個 bits 來存儲织中，最大可以表示 index=63锥涕，于是總共占用內(nèi)存就是2^14 * 6 / 8 = 12k字節(jié)。
因?yàn)橥暾?value 比特字符串是 64 位形式狭吼，減去 14 后层坠，剩下 50 位，那么極端情況刁笙，出現(xiàn) 1 的位置破花，是在第 50 位，即位置是 50疲吸。此時 index = 50座每。此時先將 index 轉(zhuǎn)為 2 進(jìn)制，它是：110010 摘悴。因?yàn)?6384 個桶中峭梳，每個桶是 6 bit 組成的。剛好 110010 就被設(shè)置到了第 2 號桶中去了蹂喻。請注意葱椭，50 已經(jīng)是最壞的情況，且它都被容納進(jìn)去了口四。那么其他的不用想也肯定能被容納進(jìn)去孵运。
fpadd 的 key 可以設(shè)置多個 value。所以根據(jù)上面的做法蔓彩，不同的 value掐松，會被設(shè)置到不同桶中去踱侣，如果出現(xiàn)了在同一個桶的粪小，即前 14 位值是一樣的大磺，但是后面出現(xiàn) 1 的位置不一樣。那么比較原來的 index 是否比新 index 大探膊。是杠愧，則替換。否逞壁，則不變流济。最終，一個 key 所對應(yīng)的 16384 個桶都設(shè)置了很多的 value 了腌闯，每個桶有一個k_max绳瘟。此時調(diào)用 pfcount 時，按照前面介紹的估算方式姿骏，便可以計算出 key 的設(shè)置了多少次 value糖声，也就是統(tǒng)計值。value 被轉(zhuǎn)為 64 位的比特串分瘦，最終被按照上面的做法記錄到每個桶中去蘸泻。
此外，Redis 對 HyperLogLog 的存儲進(jìn)行了優(yōu)化嘲玫，在計數(shù)比較小時悦施，它的存儲空間采用稀疏矩陣存儲，空間占用很小去团，僅僅在計數(shù)慢慢變大抡诞，稀疏矩陣占用空間漸漸超過了閾值時才會一次性轉(zhuǎn)變成稠密矩陣，才會占用 12k 的空間土陪。
