当前位置：首页 > article >正文

【redis】数据类型之hyperloglog

article 2025/2/26 19:49:34

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) 1

127.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
OK

127.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：
$\frac{m}{\sum_{i=1}^{m} \frac{1}{2^{k_i}}}$

修正系数：最终基数估算值：
$\alpha \cdot m \cdot 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);

        // 创建hyperloglog
        RHyperLogLog<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()); // 3
        System.out.println(hyperLogLog1.countWith("visits:20880102")); // 4

        RHyperLogLog<Object> hyperLogLogWeek = redisson.getHyperLogLog("visits:week", StringCodec.INSTANCE);
        hyperLogLogWeek.mergeWith("visits:20880101", "visits:20880102");
        System.out.println(hyperLogLogWeek.count()); // 4

        // 关闭客户端
        redisson.shutdown();
    }
}