1. 概述

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

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

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

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

3. 命令

HyperLogLog 目前只支持 3 個(gè)命令，PFADD、PFCOUNT、PFMERGE。我們先來(lái)逐一介紹一下。

3.1 PFADD

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

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

(1) 語(yǔ)法格式:

PFADD key element [element ...]

(2) 返回值:

整型，如果至少有個(gè)元素被添加返回 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。時(shí)間復(fù)雜度：O(1)，對(duì)于多個(gè)比較大的key的時(shí)間復(fù)雜度是O(N)。

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

(1) 語(yǔ)法格式:

PFCOUNT key [key ...]

(2) 返回值:

整數(shù)，返回指定 HyperLogLog 的基數(shù)估算值，如果多個(gè) 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é)果并不精確，錯(cuò)誤率大概在 0.81% 左右。

該命令會(huì)修改 HyperLogLog，會(huì)使用8個(gè)字節(jié)來(lái)存儲(chǔ)上一次計(jì)算的基數(shù)。所以，從技術(shù)角度來(lái)講，PFCOUNT 是一個(gè)寫(xiě)命令。

(5) 性能問(wèn)題

即使理論上處理一個(gè)密集型 HyperLogLog 需要花費(fèi)較長(zhǎng)時(shí)間，但是當(dāng)只指定一個(gè)鍵時(shí)，PFCOUNT 命令仍然具有很高的性能。這是因?yàn)?PFCOUNT 會(huì)緩存上一次計(jì)算的基數(shù)，并且這個(gè)基數(shù)并不會(huì)一直變動(dòng)，因?yàn)?PFADD 命令大多數(shù)情況下不會(huì)更新寄存器。所以才可以達(dá)到每秒上百次請(qǐng)求的效果。

當(dāng)使用 PFCOUNT 命令處理多個(gè)鍵時(shí)，會(huì)對(duì) HyperLogLog 進(jìn)行合并操作，這一步非常耗時(shí)，更重要的是通過(guò)計(jì)算出來(lái)的并集的基數(shù)是不能緩存的。因此當(dāng)使用多個(gè)鍵時(shí)，PFCOUNT 可能需要花費(fèi)一些時(shí)間(毫秒數(shù)量級(jí))，因此不建議過(guò)多使用。

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

3.3 PFMERGE

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

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

語(yǔ)法格式:

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