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