目錄

前言

HyperLogLog

---

前言

在學(xué)習(xí)HyperLogLog之前，我們需要先學(xué)習(xí)兩個(gè)概念

• UV：全稱(chēng)Unique Visitor，也叫獨(dú)立訪客量，是指通過(guò)互聯(lián)網(wǎng)訪問(wèn)、瀏覽這個(gè)網(wǎng)頁(yè)的自然人。1天內(nèi)同一個(gè)用戶(hù)多次訪問(wèn)該網(wǎng)站，只記錄1次。
• PV：全稱(chēng)Page View，也叫頁(yè)面訪問(wèn)量或點(diǎn)擊量，用戶(hù)每訪問(wèn)網(wǎng)站的一個(gè)頁(yè)面，記錄1次PV，用戶(hù)多次打開(kāi)頁(yè)面，則記錄多次PV。往往用來(lái)衡量網(wǎng)站的流量。

如果UV在服務(wù)端做會(huì)很麻煩，因?yàn)槊看味夹枰袛嘣撚脩?hù)是否已經(jīng)統(tǒng)計(jì)過(guò)了，因此需要保存統(tǒng)計(jì)過(guò)的用戶(hù)信息，如果都保存在Redis中，大型網(wǎng)站的數(shù)據(jù)量會(huì)非常大這種實(shí)現(xiàn)方案并不現(xiàn)實(shí)。因此，我們需要使用HyperLogLog算法。

HyperLogLog

該算法又可以叫做HLL算法，是從LogLog算法派生的概率算法，用于確定非常大的集合的基數(shù)，而不需要存儲(chǔ)其所有值，Redis中的HLL是基于String結(jié)構(gòu)實(shí)現(xiàn)的，單個(gè)HLL的內(nèi)存占用永遠(yuǎn)不會(huì)超過(guò)16k，相應(yīng)的代價(jià)是測(cè)量結(jié)果是概率性的，存在一定誤差，但是可以忽略不計(jì)。

對(duì)應(yīng)的命令如下

# 添加用戶(hù)ip
PFADD key element [element ...]
# 統(tǒng)計(jì)訪問(wèn)量，在存在多個(gè)key的情況下，會(huì)對(duì)多個(gè)key的訪問(wèn)用戶(hù)進(jìn)行去重后再統(tǒng)計(jì)
PFCOUNT key [key ...]
# 合并統(tǒng)計(jì)量
PFMERGE destkey sourcekey [sourcekey ...]

接下來(lái)我們對(duì)該方法進(jìn)行測(cè)試，首先我們對(duì) hll1 這個(gè)key進(jìn)行插入，插入結(jié)果如下

那么接下來(lái)插入key為 hll2 的數(shù)據(jù)，執(zhí)行結(jié)果結(jié)果如下

在 key 為 hll2 的數(shù)據(jù)完全包含了key為 hll1 的值時(shí)，我們對(duì)兩個(gè) key 進(jìn)行聯(lián)合統(tǒng)計(jì)，觀察輸出結(jié)果

可以看到，我們的統(tǒng)計(jì)結(jié)果是進(jìn)行了去重后再進(jìn)行統(tǒng)計(jì)的。那么接下來(lái)測(cè)試合并方法

hll2 的數(shù)據(jù)會(huì)合并到 hll1 中，該方法的存在，我們可以設(shè)置ip訪問(wèn)時(shí)設(shè)置 key 為年月日，這樣我們可以通過(guò)合并每天的key來(lái)統(tǒng)計(jì)每月的活躍人數(shù)。接下來(lái)我們測(cè)試HLL的內(nèi)存占用情況

首先是我們先獲取沒(méi)有存儲(chǔ)100w數(shù)據(jù)情況時(shí)的內(nèi)存使用情況，需要注意的時(shí)，該值為字節(jié)值，需要我們自己轉(zhuǎn)化為kb

測(cè)試代碼如下，我們需要?jiǎng)?chuàng)建100w的對(duì)象來(lái)模擬訪問(wèn)量通過(guò)HLL存儲(chǔ)，我們測(cè)試Redis的占用情況

@Test
public void test01() throws Exception {String[] str = new String[1000];int j =0;for (int i = 0; i < 1000000; i++) {j = i%1000;str[j] = "user"+i;if (j == 999){stringRedisTemplate.opsForHyperLogLog().add("hll1",str);}}Long count = stringRedisTemplate.opsForHyperLogLog().size("hll1");System.out.println(count);
}

執(zhí)行完測(cè)試代碼后的內(nèi)存占用情況以及統(tǒng)計(jì)結(jié)果如下，內(nèi)存占用變?yōu)?900992，統(tǒng)計(jì)次數(shù)為 1001788，可以看到存在一定誤差，但是對(duì)于100w數(shù)據(jù)來(lái)說(shuō)基本可以忽略不計(jì)。

計(jì)算添加完數(shù)據(jù)后的內(nèi)存占用（900992-886608）/1024 ≈ 14k。并且無(wú)論執(zhí)行多少次添加數(shù)據(jù)操作，只要對(duì)象不發(fā)生改變，永遠(yuǎn)統(tǒng)計(jì)到的數(shù)量為1001788。