Redis怎麼使用HyperLogLog實現

1. 概述

Redis 在2.8.9 版本增加了HyperLogLog 資料結構，用來做基數統計，其優點是在輸入元素的數量非常大時，計算基數所需的空間比較小並且一般比較恆定。

在 Redis 裡面，每個 HyperLogLog 鍵只需要花費 12 KB 記憶體就可以計算接近 2^64 個不同元素的基數。這和計算基數時，元素越多耗費記憶體越多的集合形成鮮明對比。但是，因為 HyperLogLog 只會根據輸入元素來計算基數，並不會儲存輸入元素本身，所以 HyperLogLog 不能像集合一樣會傳回輸入的各個元素。

2. 什麼是基數?

例如資料集{1, 3, 5, 7, 5, 7, 8}， 那麼這個資料集的基數集是{1, 3, 5 ,7, 8}, 基數(不重複元素)為5。基數估計就是在誤差可接受的範圍內，快速計算基數。

3. 指令

目前只有 PFADD、PFCOUNT 和 PFMERGE 三個指令被 HyperLogLog 支援。我們先來逐一介紹一下。

3.1 PFADD

最早可用版本：2.8.9。時間複雜度：O(1)。

PFADD 指令可以將元素(可以指定多個元素)加入到 HyperLogLog 資料結構中，儲存到第一個參數 key 指定的鍵中。若基數估計（評估的元素個數）發生變化，回傳1，否則傳回0，即在執行指令後確認基數估計是否已變化。如果指定的 key 不存在，那麼就建立一個空的 HyperLogLog 資料結構(即，指定字串長度以及編碼的 Redis String)。也可以呼叫不指定元素參數而只指定鍵的指令。如果鍵存在，不執行任何操作並傳回 0；如果鍵不存在，則會建立新的 HyperLogLog 資料結並且傳回 1。實質上只是產生一個新的 HyperLogLog 資料結構，而不儲存任何元素。

(1) 語法格式:

PFADD key element [element ...]

(2) 傳回值:

整數，如果至少有個元素被加回 1，否則回傳 0。

(3) Example:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

最早可用版本：2.8.9。時間複雜度：O(1)，對於多個比較大的key的時間複雜度是O(N)。

使用PFCOUNT指令可以得到一個HyperLogLog估算基數的值（也就是元素的數量）。如果鍵不存在，則指令傳回 0，否則傳回該鍵的基數估算值。對於多個鍵，傳回的是多個 HyperLogLog 並集的基數估算值，透過將多個 HyperLogLog 合併為一個臨時的 HyperLogLog 計算基數估算值。使用極少且一貫的記憶體量，HyperLogLog 可以計算集合的唯一元素數量。每個 HyperLogLog 只用 12K 加上鍵本身的幾個位元組。

(1) 語法格式:

PFCOUNT key [key ...]

(2) 傳回值:

整數，傳回指定HyperLogLog 的基數估算值，如果多個HyperLogLog 則傳回並集的基數估算值。

(3) Example:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) 限制:

HyperLogLog 回傳的結果並不精確，錯誤率大概在 0.81% 左右。

使用這個指令將會改變 HyperLogLog，並且使用 8 個位元組來儲存上一次計算的基數。所以，從技術角度來講，PFCOUNT 是一個寫指令。

(5) 效能問題

即使理論上處理一個密集型 HyperLogLog 需要花費較長時間，但是當只指定一個鍵時，PFCOUNT 指令仍然具有很高的效能。這是因為 PFCOUNT 會快取上一次計算的基數，而這個基數並不會一直變動，因為 PFADD 指令大多數情況下不會更新暫存器。所以才可以達到每秒上百次請求的效果。

當使用 PFCOUNT 指令處理多個鍵時，會對 HyperLogLog 進行合併操作，這一步非常耗時，更重要的是透過計算出來的並集的基數是不能快取的。使用多個按鍵時，PFCOUNT 的執行可能需要花費一些時間（通常為毫秒級），因此建議不要過度使用。

需要注意的是，該命令的單鍵和多鍵執行語義是不同的並且具有不同的性能。不建議過度使用多鍵執行語意。

3.3 PFMERGE

最早可用版本：2.8.9。時間複雜度：O(N)，N是要合併的HyperLogLog的數量。

多個 HyperLogLog 可以透過 PFMERGE 指令合併成一個 HyperLogLog。合併後的 HyperLogLog 的基數估算值是透過對所有給定 HyperLogLog 進行並集計算得出的。計算完的結果儲存到指定的鍵中。

語法格式:

PFMERGE destkey sourcekey [sourcekey ...]

傳回值:

傳回 OK。

Example:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

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