Redis的HyperLogLog（HLL）是一種高效的概率數據結構，也是一種基于字符串的數據結構，用于估計大數據集的唯一元素數量（基數統計）。它通過極低的內存占用（約 12KB）實現接近線性的時間復雜度，適用于海量數據去重計數場景（如統計獨立訪客數），但需容忍約0.81%的標準誤差。

有關hyperloglog類型的命令可以通過help @hyperloglog命令來查看。有關命令的使用可以通過help 命令來查看，例如help pfadd。

核心特性

低內存消耗：即使統計上億甚至幾十億的數量級，每個HyperLogLog鍵僅占用12KB內存，無論元素數量多少（極端情況下最多占用64KB）。

高效合并：支持多組HyperLogLog的合并去重（PFMERGE），并且復雜度也是O(1)，適合分布式統計（如多日數據合并為周/月統計）。

去重能力：自動忽略重復元素，多次添加同一元素不會影響結果。

計算復雜度低：其插入、查詢操作的復雜度都是O(1)，這使得它在處理大規模數據集時具有非常高的效率。

結果是估計值：雖然HyperLogLog提供的是基數估計值，但誤差非常小，標準誤差率可以控制在0.81%以內。

命令的使用

PFADD

PFADD：將一個或多個元素添加到HyperLogLog中，用于估算基數。

語法：

PFADD key element [element ...]

使用：

127.0.0.1:6379> pfadd visits:20990101 user1 user2
(integer) 1127.0.0.1:6379> pfadd visits:20990102 user2 user3
(integer) 1

PFCOUNT

PFCOUNT：返回一個或多個HyperLogLog的估算基數。。

語法：

PFCOUNT key [key ...]

使用：

# 統計單日獨立用戶
127.0.0.1:6379> pfcount visits:20990101
(integer) 2# 合并兩日數據
127.0.0.1:6379> pfcount visits:20990101 visits:20990102
(integer) 3

PFMERGE

PFMERGE：將一個或多個HyperLogLog合并到另一個HyperLogLog中，用于合并不同數據集的基數估算。

語法：

PFMERGE destkey sourcekey [sourcekey ...]

使用：

127.0.0.1:6379> pfmerge visits:week visits:20990101 visits:20990102
OK127.0.0.1:6379> pfcount visits:week
(integer) 3

實現原理

在Redis中，HyperLogLog的存儲也是個字符串，只不過這個字符串有個固定格式的頭部（16字節），包括魔術字符串、編碼方式、保留字段、緩存的基數以及數據字節等。

HyperLogLog的工作原理基于概率算法和哈希函數。它對要加入的每個新元素進行哈希處理，哈希值的一部分用于索引寄存器（將原始集合分成多個子集），另一部分用于計算哈希中最長的前導零序列。HyperLogLog根據寄存器數組中的值（這些寄存器被設置為迄今為止針對給定子集觀察到的最大連續零），計算出估計的基數，并應用修正公式來糾正估計誤差。

具體來說，Redis中HyperLogLog使用64bit的哈希函數，其中14bit用于寄存器索引，剩下的50bit用于計算前導0的個數。Redis中HLL有16384（2^14）個寄存器，其中存的值的范圍是0~50。

哈希與二進制轉換

每個元素通過哈希函數（如MurmurHash）轉換為固定長度（如64位）的二進制串。

作用：哈希保證元素分布均勻，避免數據傾斜導致的統計偏差。

分桶策略（Bucketing）

分桶規則：取哈希值前14位確定桶編號，一共2^14=16384個桶，后50位計算最長前導零數量。

基數估算公式

調和平均數：降低極端值影響，計算所有桶的調和均值 H：
$$H=\frac{m}{{\sum }_{i=1}^m\frac{1}{2^{k_i}}}$$

修正系數：最終基數估算值：
$$E=\alpha ?m?H$$

其中 α 為修正系數（如 m=16384 時 α≈0.7213）。

誤差控制與優化

標準誤差：1.04/√m，Redis實現誤差約0.81%。

小數據集修正：當估算值 E < 2.5m 時，使用線性計數（Linear Counting）優化結果。

為了節省內存空間，HyperLogLog內部會采用不同的編碼方式進行存儲：

• 稀疏編碼（默認）：應對數據量小的場景。
• 密集編碼：應對數據量大的場景。

適用場景

由于HyperLogLog具有高效存儲、概率估計和高速計算等特點，因此它非常適用于以下場景：

• 基數統計：網站UV統計、統計每日/月的獨立訪客數。

• 數據流量分析：例如分析用戶在某個時間段內訪問的不同頁面數、點擊不同廣告的用戶數等。

• 實時分析：高頻事件（如搜索關鍵詞）的去重計數。

• 大規模日志處理：快速估算日志中唯一IP或錯誤類型數量。

注意事項

• 誤差范圍：標準誤差約0.81%，實際誤差可能因數據分布略高。

• 非精確查詢：無法獲取具體元素或判斷元素是否存在。

• 小數據集優化：Redis在基數較小時使用稀疏存儲優化空間。

Java中的使用

package com.morris.redis.demo.hyperloglog;import org.redisson.Redisson;
import org.redisson.api.RHyperLogLog;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.StringCodec;
import org.redisson.config.Config;import java.util.Arrays;/*** redisson中hyperloglog的使用*/
public class RedissonHyperLogLogDemo {public static void main(String[] args) {// 配置Redisson客戶端Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");// 創建Redisson客戶端實例RedissonClient redisson = Redisson.create(config);// 創建hyperloglogRHyperLogLog<Object> hyperLogLog1 = redisson.getHyperLogLog("visits:20880101", StringCodec.INSTANCE);hyperLogLog1.add("user1");hyperLogLog1.addAll(Arrays.asList("user2", "user3"));RHyperLogLog<Object> hyperLogLog2 = redisson.getHyperLogLog("visits:20880102", StringCodec.INSTANCE);hyperLogLog2.add("user2");hyperLogLog2.addAll(Arrays.asList("user3", "user4"));System.out.println(hyperLogLog1.count()); // 3System.out.println(hyperLogLog1.countWith("visits:20880102")); // 4RHyperLogLog<Object> hyperLogLogWeek = redisson.getHyperLogLog("visits:week", StringCodec.INSTANCE);hyperLogLogWeek.mergeWith("visits:20880101", "visits:20880102");System.out.println(hyperLogLogWeek.count()); // 4// 關閉客戶端redisson.shutdown();}
}