前言
我們先思考一個常見的業(yè)務問題:如果你負責開發(fā)維護一個大型的網(wǎng)站查蓉,有一天老板找產(chǎn)品經(jīng)理要網(wǎng)站每個網(wǎng)頁每天的 UV 數(shù)據(jù),然后讓你來開發(fā)這個統(tǒng)計模塊榜贴,你會如何實現(xiàn)豌研?
統(tǒng)計uv的常用方法以及優(yōu)缺點
其實要是單純的統(tǒng)計pv是比較好辦的,直接用redis的incr就行唬党,但是uv的話鹃共,它要去重,同一個用戶一天之內(nèi)的多次訪問請求只能計數(shù)一次驶拱。這就要求每一個網(wǎng)頁請求都需要帶上用戶的 ID霜浴,無論是登陸用戶還是未登陸用戶都需要一個唯一 ID 來標識。
set
比較容易想到的是為每一個頁面一個獨立的 set 集合來存儲所有當天訪問過此頁面的用戶 ID蓝纲。當一個請求過來時阴孟,我們使用 sadd 將用戶 ID 塞進去就可以了。通過 scard 可以取出這個集合的大小税迷,這個數(shù)字就是這個頁面的 UV 數(shù)據(jù)永丝。沒錯,這是一個非常簡單的方案箭养。
但是类溢,如果你的頁面訪問量非常大,比如一個爆款頁面幾千萬的 UV露懒,你需要一個很大的 set 集合來統(tǒng)計闯冷,這就非常浪費空間。如果這樣的頁面很多懈词,那所需要的存儲空間是驚人的蛇耀。
hash
hash和set在處理uv的問題上其實類似,把用戶id作為hash的key的確可以去重坎弯,但是如果訪問量大了之后也會消耗很大的內(nèi)存空間
bitmap
bitmap同樣是一種可以統(tǒng)計基數(shù)的方法纺涤,可以理解為用bit數(shù)組存儲元素,例如01101001抠忘,表示的是[1,2,4,8]撩炊,bitmap中1的個數(shù)就是基數(shù)。bitmap也可以輕松合并多個集合崎脉,只需要將多個數(shù)組進行異或操作就可以了拧咳。bitmap相比于Set,Hash也大大節(jié)省了內(nèi)存囚灼,我們來粗略計算一下骆膝,統(tǒng)計1億個數(shù)據(jù)的基數(shù)祭衩,需要的內(nèi)存是:100000000/8/1024/1024 ≈ 12M。
雖然bitmap在節(jié)省空間方面已經(jīng)有了不錯的表現(xiàn)阅签,但是如果需要統(tǒng)計1000個對象掐暮,就需要大約12G的內(nèi)存,顯然這個結果仍然不能令我們滿意政钟。在這種情況下路克,HyperLogLog將會出來拯救我們。
HyperLogLog
這就是本節(jié)要引入的一個解決方案养交,Redis 提供了 HyperLogLog 數(shù)據(jù)結構就是用來解決這種統(tǒng)計問題的精算。HyperLogLog 提供不精確的去重計數(shù)方案,雖然不精確但是也不是非常不精確层坠,標準誤差是 0.81%殖妇,這樣的精確度已經(jīng)可以滿足上面的 UV 統(tǒng)計需求了刁笙。
HyperLogLog 數(shù)據(jù)結構是 Redis 的高級數(shù)據(jù)結構破花,它非常有用,但是令人感到意外的是疲吸,使用過它的人非常少座每。
使用方法
Redis 的位數(shù)組是自動擴展,如果設置了某個偏移位置超出了現(xiàn)有的內(nèi)容范圍摘悴,就會自動將位數(shù)組進行零擴充峭梳。
命令
HyperLogLog 提供了兩個指令 pfadd 和 pfcount,根據(jù)字面意義很好理解蹂喻,一個是增加計數(shù)葱椭,一個是獲取計數(shù)。
具體實現(xiàn)
pfadd 用法和 set 集合的 sadd 是一樣的口四,來一個用戶 ID孵运,就將用戶 ID 塞進去就是。pfcount 和 scard 用法是一樣的蔓彩,直接獲取計數(shù)值治笨。關鍵是它非常省空間,載統(tǒng)計海量uv的時候赤嚼,只占用了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
簡單試了一下旷赖,發(fā)現(xiàn)還蠻精確的,一個沒多也一個沒少更卒。接下來我們使用腳本等孵,往里面灌更多的數(shù)據(jù),看看它是否還可以繼續(xù)精確下去蹂空,如果不能精確流济,差距有多大锐锣。
我們將數(shù)據(jù)增加到 10w 個,看看總量差距有多大绳瘟。
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 個,按百分比是 0.277%糖声,對于上面的 UV 統(tǒng)計需求來說斤彼,誤差率也不算高。然后我們把上面的腳本再跑一邊蘸泻,也就相當于將數(shù)據(jù)重復加入一邊琉苇,查看輸出,可以發(fā)現(xiàn)悦施,pfcount 的結果沒有任何改變并扇,還是 99723,說明它確實具備去重功能抡诞。