Redis的HyperLogLog算法怎么用

這篇文章主要介紹了Redis的HyperLogLog算法怎么用的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Redis的HyperLogLog算法怎么用文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

今天是周五，你正開(kāi)心的摸魚(yú)，產(chǎn)品經(jīng)理通過(guò)郵件給你發(fā)了一個(gè)需求文檔。需求大概是：公司要統(tǒng)計(jì)網(wǎng)站每天的訪(fǎng)客 IP，而且這個(gè)統(tǒng)計(jì)是一個(gè)長(zhǎng)期的行為，短則數(shù)月、長(zhǎng)則幾年。

你看完需求就覺(jué)得這 so easy 啊，使用 Redis 的集合類(lèi)型可以輕松實(shí)現(xiàn)這個(gè)功能：每天生成一個(gè)集合類(lèi)型的鍵，使用 SADD 存儲(chǔ)每天的訪(fǎng)客 IP，使用 SCARD 命令就可以輕松得到每天訪(fǎng)客 IP 的數(shù)量。

你很快就敲完了代碼并通過(guò)測(cè)試，這個(gè)功能就上線(xiàn)了。上線(xiàn)后運(yùn)行一段時(shí)間發(fā)現(xiàn) Redis 所在服務(wù)器開(kāi)始告警，原因是某些鍵的內(nèi)存占用過(guò)大，你看了一下發(fā)現(xiàn)這些鍵都是存儲(chǔ)訪(fǎng)客 IP 的集合鍵。你這才拍了一下腦袋，知道自己給自己挖了一個(gè)大坑。

假設(shè)存儲(chǔ)一個(gè) IPv4 格式的 IP 地址最多需要 15 個(gè)字節(jié)，網(wǎng)站每天最多有 100 萬(wàn)個(gè)訪(fǎng)客訪(fǎng)問(wèn)網(wǎng)站。這些集合鍵一個(gè)月就將使用 0.45 GB 的內(nèi)存，一年將占用 5.4 GB 的內(nèi)存，這還只是估算了 IPv4 格式的情況下，若是 IPv6 格式將占用更多的內(nèi)存。SADD 和 SCARD 的時(shí)間復(fù)雜度雖然都是 O(1)，但是它們對(duì)內(nèi)存的消耗是無(wú)法接受的。

你在 Redis 的官方網(wǎng)站翻了翻，發(fā)現(xiàn) Redis 還提供了一種數(shù)據(jù)類(lèi)型 HyperLogLog，它既可以實(shí)現(xiàn)產(chǎn)品的需求還占用更少的內(nèi)存。

HyperLogLog 算法

HyperLogLog 是一個(gè)專(zhuān)門(mén)為了計(jì)算集合的基數(shù)而創(chuàng)建的概率算法，它可以計(jì)算出一個(gè)給定集合的近似基數(shù)。

近似基數(shù)并非集合的實(shí)際基數(shù)，它可能會(huì)比實(shí)際的基數(shù)小一點(diǎn)或者大一點(diǎn)，但是估算基數(shù)和實(shí)際基數(shù)之間的誤差會(huì)處于一個(gè)合理的范圍之內(nèi)，對(duì)于那些不要求十分精確的統(tǒng)計(jì)就可以使用 HyperLogLog 算法。

HyperLogLog 的優(yōu)點(diǎn)在于它計(jì)算近似基數(shù)所需的內(nèi)存并不會(huì)因?yàn)榧系拇笮《淖?，無(wú)論集合包含的元素有多少個(gè)，HyperLogLog 進(jìn)行計(jì)算所需的內(nèi)存總是固定的，并且是非常少的。

Redis 的每個(gè) HyperLogLog 類(lèi)型只需要使用 12KB 內(nèi)存空間，就可以對(duì)接近：2⁶⁴ 個(gè)元素進(jìn)行計(jì)數(shù)，而算法的標(biāo)準(zhǔn)誤差僅為 0.81%。

如果使用 HyperLogLog 類(lèi)型實(shí)現(xiàn)上述功能，每天有 100 萬(wàn)個(gè)訪(fǎng)客的情況下，1 個(gè)月也僅僅占用 360KB 的內(nèi)存。

PFADD

通過(guò) PFADD 命令可以對(duì)給定的一個(gè)或多個(gè)集合元素進(jìn)行計(jì)數(shù)。

PFADD key element [element...]

根據(jù)給定的元素是否已經(jīng)進(jìn)行過(guò)計(jì)數(shù)，PFADD 命令可能返回 0，也可能返回 1：

• 如果給定的所有元素都已經(jīng)進(jìn)行過(guò)計(jì)數(shù)，那么 PFADD 命令將返回 0，表示 HyperLogLog 計(jì)算出的近似基數(shù)沒(méi)有發(fā)生變化。

• 如果給定的元素中出現(xiàn)了至少一個(gè)之前沒(méi)有進(jìn)行過(guò)計(jì)數(shù)的元素，導(dǎo)致 HyperLogLog 計(jì)算出的近似基數(shù)發(fā)生了變化，那么 PFADD 命令將返回 1。

例如：

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

如果在調(diào)用該命令時(shí)僅指定 key 而不指定元素也是可以的，如果 key 存在，則不會(huì)有任何操作，如果不存在，則會(huì)創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)（返回 1）。

PFCOUNT

通過(guò) PFCOUNT 命令可以獲取 HyperLogLog 為集合計(jì)算出的近似基數(shù)。若給定的 key 不存在將返回 0。

PFCOUNT key [key...]

例如：

redis> PFCOUNT letters
(integer) 3

當(dāng)向 PFCOUNT 傳入多個(gè) HyperLogLog 時(shí)，PFCOUNT 命令將先對(duì)所有的 HyperLogLog 求并集，然后返回近似基數(shù)。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

PFMERGE

PFMERGE 命令可以對(duì)多個(gè) HyperLogLog 執(zhí)行并集計(jì)算，然后把計(jì)算得出的并集 HyperLogLog 保存到指定的鍵中。

PFMERGE destKey sourceKey [sourceKey...]

如果指定的鍵已經(jīng)存在，PFMERGE 命令將覆蓋已有的鍵。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFMERGE res letters1 letters2
OK
redis> PFCOUNT res
(integer) 5

可以看到 PFMERGE 和 PFCOUNT 命令十分相似，實(shí)際上 PFCOUNT 命令在計(jì)算多個(gè) HyperLogLog 的近似基數(shù)時(shí)會(huì)執(zhí)行以下操作：

• 在內(nèi)部調(diào)用 PFMERGE 命令，計(jì)算所有給定 HyperLogLog 的并集，并將這個(gè)并集存儲(chǔ)到一個(gè)臨時(shí)的 HyperLogLog 中。

• 對(duì)臨時(shí) HyperLogLog 執(zhí)行 PFCOUNT 命令，得到它的近似基數(shù)。

• 刪除臨時(shí) HyperLogLog。

• 返回得到的近似基數(shù)。

當(dāng)程序需要對(duì)多個(gè) HyperLogLog 調(diào)用 PFCOUNT 命令，并且這個(gè)調(diào)用可能會(huì)重復(fù)執(zhí)行多次時(shí)，可以考慮把這一調(diào)用替換成相應(yīng)的 PFMERGE 命令調(diào)用：通過(guò)把并集的計(jì)算結(jié)果存儲(chǔ)到指定的 HyperLogLog 中而不是每次都重新計(jì)算并集，程序可以最大程度地減少不必要的并集計(jì)算。

業(yè)務(wù)場(chǎng)景

HyperLogLog 的特性十分適合：計(jì)數(shù)（月度、年度統(tǒng)計(jì)）、去重（垃圾短信檢測(cè)）等場(chǎng)景。

關(guān)于“Redis的HyperLogLog算法怎么用”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“Redis的HyperLogLog算法怎么用”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。