我們先思考一個(gè)常見的業(yè)務(wù)問題：如果你負(fù)責(zé)開發(fā)維護(hù)一個(gè)大型的網(wǎng)站，有一天老板找產(chǎn)品經(jīng)理要網(wǎng)站每個(gè)網(wǎng)頁每天的 UV 數(shù)據(jù)，然后讓你來開發(fā)這個(gè)統(tǒng)計(jì)模塊，你會(huì)如何實(shí)現(xiàn)？

如果統(tǒng)計(jì) PV 那非常好辦，給每個(gè)網(wǎng)頁一個(gè)獨(dú)立的 Redis 計(jì)數(shù)器就可以了，這個(gè)計(jì)數(shù)器的 key 后綴加上當(dāng)天的日期。這樣來一個(gè)請(qǐng)求，incrby 一次，最終就可以統(tǒng)計(jì)出所有的 PV 數(shù)據(jù)。

但是 UV 不一樣，它要去重，同一個(gè)用戶一天之內(nèi)的多次訪問請(qǐng)求只能計(jì)數(shù)一次。這就要求每一個(gè)網(wǎng)頁請(qǐng)求都需要帶上用戶的 ID，無論是登陸用戶還是未登陸用戶都需要一個(gè)唯一 ID 來標(biāo)識(shí)。

你也許已經(jīng)想到了一個(gè)簡單的方案，那就是為每一個(gè)頁面一個(gè)獨(dú)立的 set 集合來存儲(chǔ)所有當(dāng)天訪問過此頁面的用戶 ID。當(dāng)一個(gè)請(qǐng)求過來時(shí)，我們使用 sadd 將用戶 ID 塞進(jìn)去就可以了。通過 scard 可以取出這個(gè)集合的大小，這個(gè)數(shù)字就是這個(gè)頁面的 UV 數(shù)據(jù)。沒錯(cuò)，這是一個(gè)非常簡單的方案。

但是，如果你的頁面訪問量非常大，比如一個(gè)爆款頁面幾千萬的 UV，你需要一個(gè)很大的 set 集合來統(tǒng)計(jì)，這就非常浪費(fèi)空間。如果這樣的頁面很多，那所需要的存儲(chǔ)空間是驚人的。為這樣一個(gè)去重功能就耗費(fèi)這樣多的存儲(chǔ)空間，值得么？其實(shí)老板需要的數(shù)據(jù)又不需要太精確，105w 和 106w 這兩個(gè)數(shù)字對(duì)于老板們來說并沒有多大區(qū)別，So，有沒有更好的解決方案呢？

這就是本節(jié)要引入的一個(gè)解決方案，Redis 提供了 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)就是用來解決這種統(tǒng)計(jì)問題的。HyperLogLog 提供不精確的去重計(jì)數(shù)方案，雖然不精確但是也不是非常不精確，標(biāo)準(zhǔn)誤差是 0.81%，這樣的精確度已經(jīng)可以滿足上面的 UV 統(tǒng)計(jì)需求了。

HyperLogLog 數(shù)據(jù)結(jié)構(gòu)是 Redis 的高級(jí)數(shù)據(jù)結(jié)構(gòu)，它非常有用，但是令人感到意外的是，使用過它的人非常少。

使用方法

HyperLogLog 提供了兩個(gè)指令 pfadd 和 pfcount，根據(jù)字面意義很好理解，一個(gè)是增加計(jì)數(shù)，一個(gè)是獲取計(jì)數(shù)。pfadd 用法和 set 集合的 sadd 是一樣的，來一個(gè)用戶 ID，就將用戶 ID 塞進(jìn)去就是。pfcount 和 scard 用法是一樣的，直接獲取計(jì)數(shù)值。

bash復(fù)制代碼127.0.0.1:6379>?pfadd?codehole?user1
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?1
127.0.0.1:6379>?pfadd?codehole?user2
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?2
127.0.0.1:6379>?pfadd?codehole?user3
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?3
127.0.0.1:6379>?pfadd?codehole?user4
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?4
127.0.0.1:6379>?pfadd?codehole?user5
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?5
127.0.0.1:6379>?pfadd?codehole?user6
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?6
127.0.0.1:6379>?pfadd?codehole?user7?user8?user9?user10
(integer)?1
127.0.0.1:6379>?pfcount?codehole
(integer)?10

簡單試了一下，發(fā)現(xiàn)還蠻精確的，一個(gè)沒多也一個(gè)沒少。接下來我們使用腳本，往里面灌更多的數(shù)據(jù)，看看它是否還可以繼續(xù)精確下去，如果不能精確，差距有多大。人生苦短，我用 Python！Python 腳本走起來！??

py復(fù)制代碼#?coding:?utf-8

import?redis

client?=?redis.StrictRedis()
for?i?in?range(1000):
????client.pfadd("codehole",?"user%d"?%?i)
????total?=?client.pfcount("codehole")
????if?total?!=?i+1:
????????print?total,?i+1
????????break

當(dāng)然 Java 也不錯(cuò)，大同小異，下面是 Java 版本：

java復(fù)制代碼public?class?PfTest?{
??public?static?void?main(String[]?args)?{
????Jedis?jedis?=?new?Jedis();
????for?(int?i?=?0;?i?<?1000;?i++)?{
??????jedis.pfadd("codehole",?"user"?+?i);
??????long?total?=?jedis.pfcount("codehole");
??????if?(total?!=?i?+?1)?{
????????System.out.printf("%d?%d\n",?total,?i?+?1);
????????break;
??????}
????}
????jedis.close();
??}
}

我們來看下輸出：

markdown復(fù)制代碼>?python?pftest.py
99?100

當(dāng)我們加入第 100 個(gè)元素時(shí)，結(jié)果開始出現(xiàn)了不一致。接下來我們將數(shù)據(jù)增加到 10w 個(gè)，看看總量差距有多大。

css復(fù)制代碼#?coding:?utf-8

import?redis

client?=?redis.StrictRedis()
for?i?in?range(100000):
????client.pfadd("codehole",?"user%d"?%?i)
print?100000,?client.pfcount("codehole")

Java 版：

java復(fù)制代碼public?class?JedisTest?{
??public?static?void?main(String[]?args)?{
????Jedis?jedis?=?new?Jedis();
????for?(int?i?=?0;?i?<?100000;?i++)?{
??????jedis.pfadd("codehole",?"user"?+?i);
????}
????long?total?=?jedis.pfcount("codehole");
????System.out.printf("%d?%d\n",?100000,?total);
????jedis.close();
??}
}

跑了約半分鐘，我們看輸出：

markdown復(fù)制代碼>?python?pftest.py
100000?99723

差了 277 個(gè)，按百分比是 0.277%，對(duì)于上面的 UV 統(tǒng)計(jì)需求來說，誤差率也不算高。然后我們把上面的腳本再跑一邊，也就相當(dāng)于將數(shù)據(jù)重復(fù)加入一邊，查看輸出，可以發(fā)現(xiàn)，pfcount 的結(jié)果沒有任何改變，還是 99723，說明它確實(shí)具備去重功能。

pfadd 這個(gè) pf 是什么意思？

它是 HyperLogLog 這個(gè)數(shù)據(jù)結(jié)構(gòu)的發(fā)明人 Philippe Flajolet 的首字母縮寫，老師覺得他發(fā)型很酷，看起來是個(gè)佛系教授。

pfmerge 適合什么場合用？

HyperLogLog 除了上面的 pfadd 和 pfcount 之外，還提供了第三個(gè)指令 pfmerge，用于將多個(gè) pf 計(jì)數(shù)值累加在一起形成一個(gè)新的 pf 值。

比如在網(wǎng)站中我們有兩個(gè)內(nèi)容差不多的頁面，運(yùn)營說需要這兩個(gè)頁面的數(shù)據(jù)進(jìn)行合并。其中頁面的 UV 訪問量也需要合并，那這個(gè)時(shí)候 pfmerge 就可以派上用場了。

注意事項(xiàng)

HyperLogLog 這個(gè)數(shù)據(jù)結(jié)構(gòu)不是免費(fèi)的，不是說使用這個(gè)數(shù)據(jù)結(jié)構(gòu)要花錢，它需要占據(jù)一定 12k 的存儲(chǔ)空間，所以它不適合統(tǒng)計(jì)單個(gè)用戶相關(guān)的數(shù)據(jù)。如果你的用戶上億，可以算算，這個(gè)空間成本是非常驚人的。但是相比 set 存儲(chǔ)方案，HyperLogLog 所使用的空間那真是可以使用千斤對(duì)比四兩來形容了。

不過你也不必過于擔(dān)心，因?yàn)?Redis 對(duì) HyperLogLog 的存儲(chǔ)進(jìn)行了優(yōu)化，在計(jì)數(shù)比較小時(shí)，它的存儲(chǔ)空間采用稀疏矩陣存儲(chǔ)，空間占用很小，僅僅在計(jì)數(shù)慢慢變大，稀疏矩陣占用空間漸漸超過了閾值時(shí)才會(huì)一次性轉(zhuǎn)變成稠密矩陣，才會(huì)占用 12k 的空間。

HyperLogLog 實(shí)現(xiàn)原理

HyperLogLog 的使用非常簡單，但是實(shí)現(xiàn)原理比較復(fù)雜，如果讀者沒有特別的興趣，下面的內(nèi)容暫時(shí)可以跳過不看。

為了方便理解 HyperLogLog 的內(nèi)部實(shí)現(xiàn)原理，我畫了下面這張圖

這張圖的意思是，給定一系列的隨機(jī)整數(shù)，我們記錄下低位連續(xù)零位的最大長度 k，通過這個(gè) k 值可以估算出隨機(jī)數(shù)的數(shù)量。 首先不問為什么，我們編寫代碼做一個(gè)實(shí)驗(yàn)，觀察一下隨機(jī)整數(shù)的數(shù)量和 k 值的關(guān)系。

py復(fù)制代碼import?math
import?random

#?算低位零的個(gè)數(shù)
def?low_zeros(value):
????for?i?in?xrange(1,?32):
????????if?value?>>?i?<<?i?!=?value:
????????????break
????return?i?-?1


#?通過隨機(jī)數(shù)記錄最大的低位零的個(gè)數(shù)
class?BitKeeper(object):

????def?__init__(self):
????????self.maxbits?=?0

????def?random(self):
????????value?=?random.randint(0,?2**32-1)
????????bits?=?low_zeros(value)
????????if?bits?>?self.maxbits:
????????????self.maxbits?=?bits


class?Experiment(object):

????def?__init__(self,?n):
????????self.n?=?n
????????self.keeper?=?BitKeeper()

????def?do(self):
????????for?i?in?range(self.n):
????????????self.keeper.random()

????def?debug(self):
????????print?self.n,?'%.2f'?%?math.log(self.n,?2),?self.keeper.maxbits


for?i?in?range(1000,?100000,?100):
????exp?=?Experiment(i)
????exp.do()
????exp.debug()

Java 版：

java復(fù)制代碼public?class?PfTest?{

??static?class?BitKeeper?{
????private?int?maxbits;

????public?void?random()?{
??????long?value?=?ThreadLocalRandom.current().nextLong(2L?<<?32);
??????int?bits?=?lowZeros(value);
??????if?(bits?>?this.maxbits)?{
????????this.maxbits?=?bits;
??????}
????}

????private?int?lowZeros(long?value)?{
??????int?i?=?1;
??????for?(;?i?<?32;?i++)?{
????????if?(value?>>?i?<<?i?!=?value)?{
??????????break;
????????}
??????}
??????return?i?-?1;
????}
??}

??static?class?Experiment?{
????private?int?n;
????private?BitKeeper?keeper;

????public?Experiment(int?n)?{
??????this.n?=?n;
??????this.keeper?=?new?BitKeeper();
????}

????public?void?work()?{
??????for?(int?i?=?0;?i?<?n;?i++)?{
????????this.keeper.random();
??????}
????}

????public?void?debug()?{
??????System.out.printf("%d?%.2f?%d\n",?this.n,?Math.log(this.n)?/?Math.log(2),?this.keeper.maxbits);
????}
??}

??public?static?void?main(String[]?args)?{
????for?(int?i?=?1000;?i?<?100000;?i?+=?100)?{
??????Experiment?exp?=?new?Experiment(i);
??????exp.work();
??????exp.debug();
????}
??}

}

運(yùn)行觀察輸出：

復(fù)制代碼36400?15.15?13
36500?15.16?16
36600?15.16?13
36700?15.16?14
36800?15.17?15
36900?15.17?18
37000?15.18?16
37100?15.18?15
37200?15.18?13
37300?15.19?14
37400?15.19?16
37500?15.19?14
37600?15.20?15

通過這實(shí)驗(yàn)可以發(fā)現(xiàn) K 和 N 的對(duì)數(shù)之間存在顯著的線性相關(guān)性：

ini
復(fù)制代碼N=2^K  # 約等于

如果 N 介于 2^K 和 2^(K+1) 之間，用這種方式估計(jì)的值都等于 2^K，這明顯是不合理的。這里可以采用多個(gè) BitKeeper，然后進(jìn)行加權(quán)估計(jì)，就可以得到一個(gè)比較準(zhǔn)確的值。

py復(fù)制代碼import?math
import?random

def?low_zeros(value):
????for?i?in?xrange(1,?32):
????????if?value?>>?i?<<?i?!=?value:
????????????break
????return?i?-?1


class?BitKeeper(object):

????def?__init__(self):
????????self.maxbits?=?0

????def?random(self,?m):
????????bits?=?low_zeros(m)
????????if?bits?>?self.maxbits:
????????????self.maxbits?=?bits


class?Experiment(object):

????def?__init__(self,?n,?k=1024):
????????self.n?=?n
????????self.k?=?k
????????self.keepers?=?[BitKeeper()?for?i?in?range(k)]

????def?do(self):
????????for?i?in?range(self.n):
????????????m?=?random.randint(0,?1<<32-1)
????????????#?確保同一個(gè)整數(shù)被分配到同一個(gè)桶里面，摘取高位后取模
????????????keeper?=?self.keepers[((m?&?0xfff0000)?>>?16)?%?len(self.keepers)]
????????????keeper.random(m)

????def?estimate(self):
????????sumbits_inverse?=?0??#?零位數(shù)倒數(shù)
????????for?keeper?in?self.keepers:
????????????sumbits_inverse?+=?1.0/float(keeper.maxbits)
????????avgbits?=?float(self.k)/sumbits_inverse??#?平均零位數(shù)
????????return?2**avgbits?*?self.k??#?根據(jù)桶的數(shù)量對(duì)估計(jì)值進(jìn)行放大


for?i?in?range(100000,?1000000,?100000):
????exp?=?Experiment(i)
????exp.do()
????est?=?exp.estimate()
????print?i,?'%.2f'?%?est,?'%.2f'?%?(abs(est-i)?/?i)

下面是 Java 版：

java復(fù)制代碼public?class?PfTest?{

??static?class?BitKeeper?{
????private?int?maxbits;

????public?void?random(long?value)?{
??????int?bits?=?lowZeros(value);
??????if?(bits?>?this.maxbits)?{
????????this.maxbits?=?bits;
??????}
????}

????private?int?lowZeros(long?value)?{
??????int?i?=?1;
??????for?(;?i?<?32;?i++)?{
????????if?(value?>>?i?<<?i?!=?value)?{
??????????break;
????????}
??????}
??????return?i?-?1;
????}
??}

??static?class?Experiment?{
????private?int?n;
????private?int?k;
????private?BitKeeper[]?keepers;

????public?Experiment(int?n)?{
??????this(n,?1024);
????}

????public?Experiment(int?n,?int?k)?{
??????this.n?=?n;
??????this.k?=?k;
??????this.keepers?=?new?BitKeeper[k];
??????for?(int?i?=?0;?i?<?k;?i++)?{
????????this.keepers[i]?=?new?BitKeeper();
??????}
????}

????public?void?work()?{
??????for?(int?i?=?0;?i?<?this.n;?i++)?{
????????long?m?=?ThreadLocalRandom.current().nextLong(1L?<<?32);
????????BitKeeper?keeper?=?keepers[(int)?(((m?&?0xfff0000)?>>?16)?%?keepers.length)];
????????keeper.random(m);
??????}
????}

????public?double?estimate()?{
??????double?sumbitsInverse?=?0.0;
??????for?(BitKeeper?keeper?:?keepers)?{
????????sumbitsInverse?+=?1.0?/?(float)?keeper.maxbits;
??????}
??????double?avgBits?=?(float)?keepers.length?/?sumbitsInverse;
??????return?Math.pow(2,?avgBits)?*?this.k;
????}
??}

??public?static?void?main(String[]?args)?{
????for?(int?i?=?100000;?i?<?1000000;?i?+=?100000)?{
??????Experiment?exp?=?new?Experiment(i);
??????exp.work();
??????double?est?=?exp.estimate();
??????System.out.printf("%d?%.2f?%.2f\n",?i,?est,?Math.abs(est?-?i)?/?i);
????}
??}

}

代碼中分了 1024 個(gè)桶，計(jì)算平均數(shù)使用了調(diào)和平均 (倒數(shù)的平均)。普通的平均法可能因?yàn)閭€(gè)別離群值對(duì)平均結(jié)果產(chǎn)生較大的影響，調(diào)和平均可以有效平滑離群值的影響。

觀察腳本的輸出，誤差率控制在百分比個(gè)位數(shù)：

復(fù)制代碼100000?97287.38?0.03
200000?189369.02?0.05
300000?287770.04?0.04
400000?401233.52?0.00
500000?491704.97?0.02
600000?604233.92?0.01
700000?721127.67?0.03
800000?832308.12?0.04
900000?870954.86?0.03
1000000?1075497.64?0.08

真實(shí)的 HyperLogLog 要比上面的示例代碼更加復(fù)雜一些，也更加精確一些。上面的這個(gè)算法在隨機(jī)次數(shù)很少的情況下會(huì)出現(xiàn)除零錯(cuò)誤，因?yàn)?maxbits=0 是不可以求倒數(shù)的。

pf 的內(nèi)存占用為什么是 12k？

我們在上面的算法中使用了 1024 個(gè)桶進(jìn)行獨(dú)立計(jì)數(shù)，不過在 Redis 的 HyperLogLog 實(shí)現(xiàn)中用到的是 16384 個(gè)桶，也就是 2^14，每個(gè)桶的 maxbits 需要 6 個(gè) bits 來存儲(chǔ)，最大可以表示 maxbits=63，于是總共占用內(nèi)存就是2^14 * 6 / 8 = 12k字節(jié)。