Redis的HyperLogLog演算法怎麼用

你正在愉快地偷懶，但產品經理卻透過電子郵件向你發送了一份需求文件。公司需要長期統計網站每天的訪客IP，統計時間可能會持續數月甚至數年。

你看完需求就覺得這so easy 啊，使用Redis 的集合類型可以輕鬆實現這個功能：每天產生一個集合類型的鍵，使用SADD 儲存每天的訪客IP，使用SCARD 指令就可以輕鬆得到每天訪客IP 的數量。

你很快就敲完了程式碼並通過測試，這個功能就上線了。上線後運行一段時間發現 Redis 所在伺服器開始告警，原因是某些鍵的記憶體佔用過大，你看了一下發現這些鍵都是儲存訪客 IP 的集合鍵。你這才拍了一下腦袋，知道自己給自己挖了一個大坑。

假設儲存一個 IPv4 格式的 IP 位址最多需要 15 個位元組，網站每天最多有 100 萬個訪客造訪網站。這些集合鍵一個月就將使用 0.45 GB 的內存，一年將佔用 5.4 GB 的內存，這還只是估算了 IPv4 格式的情況下，若是 IPv6 格式將佔用更多的內存。雖然 SADD 和 SCARD 的時間複雜度都是 O(1)，但它們在記憶體消耗上是無法容忍的。

你在 Redis 的官方網站翻了翻，發現 Redis 還提供了一種資料類型 HyperLogLog，它既可以實現產品的需求還佔用更少的記憶體。

HyperLogLog 演算法

HyperLogLog 是一個專門為了計算集合的基數而創建的機率演算法，它可以計算出一個給定集合的近似基數。

近似基數並非集合的實際基數，它可能會比實際的基數小一點或大一點，但是估算基數和實際基數之間的誤差會處於一個合理的範圍之內，對於那些不要求十分精確的統計量就可以使用HyperLogLog 演算法。

HyperLogLog 的優點在於它計算近似基數所需的記憶體並不會因為集合的大小而改變，無論集合包含的元素有多少個，HyperLogLog 進行計算所需的記憶體總是固定的，而且是非常少的。

Redis 的每個 HyperLogLog 類型只需要使用 12KB 記憶體空間，就可以對接近​​：2⁶⁴ 個元素進行計數，而演算法的標準誤差僅為 0.81%。

如果使用 HyperLogLog 類型實現上述功能，每天有 100 萬個訪客的情況下，1 個月也只佔用 360KB 的記憶體。

PFADD

透過 PFADD 指令可以對給定的一個或多個集合元素進行計數。

PFADD key element [element...]

#根據給定的元素是否已經進行過計數，PFADD 指令可能回傳0，也可能回傳1：

• 如果給定的所有元素都已經進行過計數，那麼PFADD 指令將會傳回0，表示HyperLogLog 計算出的近似基數沒有改變。

• 如果給定的元素中出現了至少一個先前沒有進行過計數的元素，導致 HyperLogLog 計算的近似基數發生了變化，那麼 PFADD 指令將會傳回 1。

例如：

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

如果在呼叫該指令時僅指定key 而不指定元素也是可以的，如果key 存在，則不會有任何操作，如果不存在，則會建立一個資料結構（返回1）。

PFCOUNT

使用 PFCOUNT 指令可以取得基於 HyperLogLog 近似計算的集合基底數。若給定的 key 不存在將回傳 0。

PFCOUNT key [key...]

例如：

redis> PFCOUNT letters
(integer) 3

當向PFCOUNT 傳入多個HyperLogLog 時，PFCOUNT 指令將先對所有的HyperLogLog 求並集，然後傳回近似基數。

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

PFMERGE

PFMERGE 指令可以對多個 HyperLogLog 執行並集計算，然後把計算出來的並集 HyperLogLog 儲存到指定的鍵中。

PFMERGE destKey sourceKey [sourceKey...]

#如果指定的鍵已經存在，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 指令十分相似，實際上PFCOUNT 指令在計算多個HyperLogLog 的近似基底數時會執行以下操作：

• #在內部調用PFMERGE 指令，計算所有給定HyperLogLog 的並集，並將這個並集儲存到一個臨時的HyperLogLog 中。

• 對暫存 HyperLogLog 執行 PFCOUNT 指令，得到它的近似基數。

• 刪除臨時 HyperLogLog。

• 傳回所得的近似基數。

當程式需要對多個HyperLogLog 呼叫PFCOUNT 指令，而這個呼叫可能會重複執行多次時，可以考慮把這個呼叫替換成對應的PFMERGE 指令呼叫：透過把並集的計算結果儲存到指定的HyperLogLog 中而不是每次都重新計算並集，程式可以最大程度地減少不必要的並集計算。

業務場景

HyperLogLog 的特色十分適合：計數（月度、年度統計）、去重（垃圾簡訊偵測）等場景。

以上是Redis的HyperLogLog演算法怎麼用的詳細內容。更多資訊請關注PHP中文網其他相關文章！