[[416080]]

前言

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

統(tǒng)計(jì)uv的常用方法以及優(yōu)缺點(diǎn)

其實(shí)要是單純的統(tǒng)計(jì)pv是比較好辦的，直接用redis的incr就行，但是uv的話，它要去重，同一個(gè)用戶一天之內(nèi)的多次訪問請(qǐng)求只能計(jì)數(shù)一次。這就要求每一個(gè)網(wǎng)頁(yè)請(qǐng)求都需要帶上用戶的 ID，無(wú)論是登陸用戶還是未登陸用戶都需要一個(gè)唯一 ID 來(lái)標(biāo)識(shí)。

set

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

但是，如果你的頁(yè)面訪問量非常大，比如一個(gè)爆款頁(yè)面幾千萬(wàn)的 UV，你需要一個(gè)很大的 set 集合來(lái)統(tǒng)計(jì)，這就非常浪費(fèi)空間。如果這樣的頁(yè)面很多，那所需要的存儲(chǔ)空間是驚人的。

hash

hash和set在處理uv的問題上其實(shí)類似，把用戶id作為hash的key的確可以去重，但是如果訪問量大了之后也會(huì)消耗很大的內(nèi)存空間

bitmap

bitmap同樣是一種可以統(tǒng)計(jì)基數(shù)的方法，可以理解為用bit數(shù)組存儲(chǔ)元素，例如01101001，表示的是[1,2,4,8]，bitmap中1的個(gè)數(shù)就是基數(shù)。bitmap也可以輕松合并多個(gè)集合，只需要將多個(gè)數(shù)組進(jìn)行異或操作就可以了。bitmap相比于Set，Hash也大大節(jié)省了內(nèi)存，我們來(lái)粗略計(jì)算一下，統(tǒng)計(jì)1億個(gè)數(shù)據(jù)的基數(shù)，需要的內(nèi)存是：100000000/8/1024/1024 ≈ 12M。

雖然bitmap在節(jié)省空間方面已經(jīng)有了不錯(cuò)的表現(xiàn)，但是如果需要統(tǒng)計(jì)1000個(gè)對(duì)象，就需要大約12G的內(nèi)存，顯然這個(gè)結(jié)果仍然不能令我們滿意。在這種情況下，HyperLogLog將會(huì)出來(lái)拯救我們。

HyperLogLog

這就是本節(jié)要引入的一個(gè)解決方案，Redis 提供了 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)就是用來(lái)解決這種統(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)，它非常有用，但是令人感到意外的是，使用過(guò)它的人非常少。

使用方法

Redis 的位數(shù)組是自動(dòng)擴(kuò)展，如果設(shè)置了某個(gè)偏移位置超出了現(xiàn)有的內(nèi)容范圍，就會(huì)自動(dòng)將位數(shù)組進(jìn)行零擴(kuò)充。

命令

HyperLogLog 提供了兩個(gè)指令 pfadd 和 pfcount，根據(jù)字面意義很好理解，一個(gè)是增加計(jì)數(shù)，一個(gè)是獲取計(jì)數(shù)。

具體實(shí)現(xiàn)

pfadd 用法和 set 集合的 sadd 是一樣的，來(lái)一個(gè)用戶 ID，就將用戶 ID 塞進(jìn)去就是。pfcount 和 scard 用法是一樣的，直接獲取計(jì)數(shù)值。關(guān)鍵是它非常省空間，載統(tǒng)計(jì)海量uv的時(shí)候，只占用了12k的空間

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 

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

我們將數(shù)據(jù)增加到 10w 個(gè)，看看總量差距有多大。

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(); 
  } 
} 

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

> python pftest.py 
100000 99723 

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