HyperLogLog

HyperLogLog 是一种概率数据结构，用于估计集合的基数。

HyperLogLog 是一种概率数据结构，用于估计集合的基数。作为一种概率数据结构，HyperLogLog 以牺牲完美准确性为代价，换取高效的空间利用率。

Redis HyperLogLog 实现最多使用 12 KB 并提供 0.81% 的标准误差。

计算唯一项目通常需要与要计算的项目数量成比例的内存，因为你需要记住过去已经看到的元素，以避免多次计算它们。然而，存在一组算法，它们以内存换取精度：它们返回一个带有标准误差的估计值，在Redis实现的HyperLogLog中，这个误差小于1%。这个算法的神奇之处在于，你不再需要使用与计算项目数量成比例的内存，而是可以使用一个恒定的内存量；在最坏的情况下是12k字节，或者如果你的HyperLogLog（从现在开始我们只称它们为HLL）看到的元素很少，内存使用量会少得多。

Redis中的HLLs，虽然在技术上是一种不同的数据结构，但被编码为Redis字符串，因此你可以调用GET来序列化一个HLL，并调用SET将其反序列化回服务器。

从概念上讲，HLL API 类似于使用集合来完成相同的任务。你会将每个观察到的元素SADD到一个集合中，并使用SCARD来检查集合中的元素数量，这些元素是唯一的，因为SADD不会重新添加已存在的元素。

虽然你实际上并没有添加项目到HLL中，因为数据结构只包含一个不包含实际元素的状态，但API是相同的：

每次看到一个新元素时，您可以使用PFADD将其添加到计数中。
当您想要检索使用PFADD命令添加的唯一元素的当前近似值时，您可以使用PFCOUNT命令。如果您需要合并两个不同的HLL，可以使用PFMERGE命令。由于HLL提供了唯一元素的近似计数，合并的结果将为您提供两个源HLL中唯一元素数量的近似值。

>_ Redis CLI

> PFADD bikes Hyperion Deimos Phoebe Quaoar
(integer) 1
> PFCOUNT bikes
(integer) 4
> PFADD commuter_bikes Salacia Mimas Quaoar
(integer) 1
> PFMERGE all_bikes bikes commuter_bikes
OK
> PFCOUNT all_bikes
(integer) 6

Python

"""
Code samples for HyperLogLog doc pages:
    https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/
"""

import redis

r = redis.Redis(decode_responses=True)


res1 = r.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar")
print(res1)  # >>> 1

res2 = r.pfcount("bikes")
print(res2)  # >>> 4

res3 = r.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar")
print(res3)  # >>> 1

res4 = r.pfmerge("all_bikes", "bikes", "commuter_bikes")
print(res4)  # >>> True

res5 = r.pfcount("all_bikes")
print(res5)  # >>> 6

Node.js

import assert from 'assert';
import { createClient } from 'redis';

const client = createClient();
await client.connect();


const res1 = await client.pfAdd('bikes', ['Hyperion', 'Deimos', 'Phoebe', 'Quaoar']);
console.log(res1);  // >>> true

const res2 = await client.pfCount('bikes');
console.log(res2);  // >>> 4

const res3 = await client.pfAdd('commuter_bikes', ['Salacia', 'Mimas', 'Quaoar']);
console.log(res3);  // >>> true

const res4 = await client.pfMerge('all_bikes', ['bikes', 'commuter_bikes']);
console.log(res4);  // >>> OK

const res5 = await client.pfCount('all_bikes');
console.log(res5);  // >>> 6

Java-Sync

package io.redis.examples;

import org.junit.Assert;
import org.junit.Test;
import redis.clients.jedis.UnifiedJedis;

public class HyperLogLogExample {

    public void run() {
        UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379");


        long res1 = jedis.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar");
        System.out.println(res1); // >>> 1

        long res2 = jedis.pfcount("bikes");
        System.out.println(res2); // >>> 4

        long res3 = jedis.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar");
        System.out.println(res3); // >>> 1

        String res4 = jedis.pfmerge("all_bikes", "bikes", "commuter_bikes");
        System.out.println(res4); // >>> OK


        long res5 = jedis.pfcount("all_bikes");
        System.out.println(res5); // >>> 6
    }
}

package example_commands_test

import (
	"context"
	"fmt"

	"github.com/redis/go-redis/v9"
)


func ExampleClient_pfadd() {
	ctx := context.Background()

	rdb := redis.NewClient(&redis.Options{
		Addr:     "localhost:6379",
		Password: "", // no password docs
		DB:       0,  // use default DB
	})


	res1, err := rdb.PFAdd(ctx, "bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // 1

	res2, err := rdb.PFCount(ctx, "bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // 4

	res3, err := rdb.PFAdd(ctx, "commuter_bikes", "Salacia", "Mimas", "Quaoar").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // 1

	res4, err := rdb.PFMerge(ctx, "all_bikes", "bikes", "commuter_bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // OK

	res5, err := rdb.PFCount(ctx, "all_bikes").Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res5) // 6

}


using NRedisStack.Tests;
using StackExchange.Redis;



public class Hll_tutorial
{

    public void run()
    {
        var muxer = ConnectionMultiplexer.Connect("localhost:6379");
        var db = muxer.GetDatabase();


        bool res1 = db.HyperLogLogAdd("{bikes}", new RedisValue[] { "Hyperion", "Deimos", "Phoebe", "Quaoar" });
        Console.WriteLine(res1);    // >>> True

        long res2 = db.HyperLogLogLength("{bikes}");
        Console.WriteLine(res2);    // >>> 4

        bool res3 = db.HyperLogLogAdd("commuter_{bikes}", new RedisValue[] { "Salacia", "Mimas", "Quaoar" });
        Console.WriteLine(res3);    // >>> True

        db.HyperLogLogMerge("all_{bikes}", "{bikes}", "commuter_{bikes}");
        long res4 = db.HyperLogLogLength("all_{bikes}");
        Console.WriteLine(res4);    // >>> 6

        // Tests for 'pfadd' step.


    }
}

这种数据结构的一些使用案例包括计算用户在搜索表单中每天执行的唯一查询次数、网页的唯一访问者数量以及其他类似情况。

Redis 也能够执行 HLL 的并集操作，请查看完整文档获取更多信息。

使用案例

网页的匿名唯一访问量（SaaS，分析工具）

这个应用程序回答以下问题：

这一天这个页面有多少次独立访问？
有多少唯一用户播放过这首歌？
有多少独立用户观看了这个视频？

注意：

在某些国家，存储IP地址或任何其他类型的个人标识符是违法的，这使得无法在您的网站上获取唯一的访问者统计信息。

每个页面（视频/歌曲）每个周期创建一个HyperLogLog，并且每次访问时都会将每个IP/标识符添加到其中。

基本命令

PFADD 向 HyperLogLog 添加一个项目。
PFCOUNT 返回集合中项目数量的估计值。
PFMERGE 将两个或多个 HyperLogLog 合并为一个。

查看HyperLogLog命令的完整列表。

性能

向HyperLogLog写入（PFADD）和从中读取（PFCOUNT）是在常数时间和空间内完成的。合并HLLs的时间复杂度是O(n)，其中n是草图的数量。

限制

HyperLogLog 可以估计最多有 18,446,744,073,709,551,616 (2^64) 个成员的集合的基数。

了解更多

Redis 新数据结构：HyperLogLog 包含有关该数据结构及其在 Redis 中实现的详细信息。
Redis HyperLogLog Explained 向您展示了如何使用 Redis HyperLogLog 数据结构来构建流量热图。

HyperLogLog

使用案例

基本命令

性能

限制

了解更多

本页内容