1. 概述

Redis 在 2.8.9 版本添加了 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)，用來做基數(shù)統(tǒng)計，其優(yōu)點是在輸入元素的數(shù)量非常大時，計算基數(shù)所需的空間比較小并且一般比較恒定。

在 Redis 里面，每個 HyperLogLog 鍵只需要花費 12 KB 內(nèi)存就可以計算接近 2^64 個不同元素的基數(shù)。這和計算基數(shù)時，元素越多耗費內(nèi)存越多的集合形成鮮明對比。但是，因為 HyperLogLog 只會根據(jù)輸入元素來計算基數(shù)，并不會儲存輸入元素本身，所以 HyperLogLog 不能像集合那樣能返回輸入的各個元素。

2. 什么是基數(shù)?

比如數(shù)據(jù)集 {1, 3, 5, 7, 5, 7, 8}， 那么這個數(shù)據(jù)集的基數(shù)集為 {1, 3, 5 ,7, 8}, 基數(shù)(不重復(fù)元素)為5。基數(shù)估計就是在誤差可接受的范圍內(nèi)，快速計算基數(shù)。

3. 命令

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

3.1 PFADD

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

PFADD 命令可以將元素(可以指定多個元素)添加到 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)中，存儲到第一個參數(shù) key 指定的鍵中。命令執(zhí)行之后，如果基數(shù)估計(評估的元素個數(shù))發(fā)生變化就返回 1，否則返回 0。如果指定的 key 不存在，那么就創(chuàng)建一個空的 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)(即，指定字符串長度以及編碼的 Redis String)。也可以調(diào)用不指定元素參數(shù)而只指定鍵的命令。如果鍵存在，不執(zhí)行任何操作并返回 0；如果鍵不存在，則會創(chuàng)建一個新的 HyperLogLog 數(shù)據(jù)結(jié)并且返回 1。本質(zhì)上只是創(chuàng)建一個新的 HyperLogLog 數(shù)據(jù)結(jié)，不存儲任何元素。

(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。時間復(fù)雜度：O(1)，對于多個比較大的key的時間復(fù)雜度是O(N)。

PFCOUNT 命令返回指定 HyperLogLog 的基數(shù)估算值(元素個數(shù))。對于單個鍵，該命令返回的是該鍵的基數(shù)估算值，如果該鍵不存在，則返回 0。對于多個鍵，返回的是多個 HyperLogLog 并集的基數(shù)估算值，通過將多個 HyperLogLog 合并為一個臨時的 HyperLogLog 計算基數(shù)估算值。HyperLogLog 只使用很少且恒定的內(nèi)存來計算集合的不同元素個數(shù)。每個 HyperLogLog 只用 12K 加上鍵本身的幾個字節(jié)。

(1) 語法格式:

PFCOUNT key [key ...]

(2) 返回值:

整數(shù)，返回指定 HyperLogLog 的基數(shù)估算值，如果多個 HyperLogLog 則返回并集的基數(shù)估算值。

(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 返回的結(jié)果并不精確，錯誤率大概在 0.81% 左右。

該命令會修改 HyperLogLog，會使用8個字節(jié)來存儲上一次計算的基數(shù)。所以，從技術(shù)角度來講，PFCOUNT 是一個寫命令。

(5) 性能問題

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

當使用 PFCOUNT 命令處理多個鍵時，會對 HyperLogLog 進行合并操作，這一步非常耗時，更重要的是通過計算出來的并集的基數(shù)是不能緩存的。因此當使用多個鍵時，PFCOUNT 可能需要花費一些時間(毫秒數(shù)量級)，因此不建議過多使用。

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

3.3 PFMERGE

最早可用版本：2.8.9。時間復(fù)雜度：O(N)，N是要合并的HyperLogLog的數(shù)量。

PFMERGE 命令將多個 HyperLogLog 合并為一個 HyperLogLog。合并后的 HyperLogLog 的基數(shù)估算值是通過對所有給定 HyperLogLog 進行并集計算得出的。計算完的結(jié)果保存到指定的鍵中。

語法格式:

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

到此這篇關(guān)于Redis如何使用HyperLogLog的實現(xiàn)的文章就介紹到這了,更多相關(guān)Redis HyperLogLog內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論