Redis如何使用HyperLogLog的實現

2022-06-02 14:06:33

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. 命令

HyperLogLog 目前只支援 3 個命令，PFADD、PFCOUNT、PFMERGE。我們先來逐一介紹一下。

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的數量。

PFMERGE 命令將多個 HyperLogLog 合併為一個 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的實現的文章就介紹到這了,更多相關Redis HyperLogLog內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！