相关文章

更多

最近更新

更多

Redis HyperLogLog 基数统计详解

2019-04-11 21:57|来源: 网路

Redis HyperLogLog

Redis 在 2.8.9 版本添加了 HyperLogLog 结构。

Redis HyperLogLog 是用来做基数统计的算法,HyperLogLog 的优点是,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定 的、并且是很小的。

在 Redis 里面,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个不同元素的基 数。这和计算基数时,元素越多耗费内存就越多的集合形成鲜明对比。

但是,因为 HyperLogLog 只会根据输入元素来计算基数,而不会储存输入元素本身,所以 HyperLogLog 不能像集合那样,返回输入的各个元素。


什么是基数?

比如数据集 {1, 3, 5, 7, 5, 7, 8}, 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内,快速计算基数。


实例

以下实例演示了 HyperLogLog 的工作过程:

redis 127.0.0.1:6379> PFADD w3ckey "redis"
1) (integer) 1
redis 127.0.0.1:6379> PFADD w3ckey "mongodb"
1) (integer) 1
redis 127.0.0.1:6379> PFADD w3ckey "mysql"
1) (integer) 1
redis 127.0.0.1:6379> PFCOUNT w3ckey
(integer) 3



Redis HyperLogLog 命令

下表列出了 redis HyperLogLog 的基本命令:

序号 命令及描述
1 PFADD key element [element ...]
添加指定元素到 HyperLogLog 中。
2 PFCOUNT key [key ...]
返回给定 HyperLogLog 的基数估算值。
3 PFMERGE destkey sourcekey [sourcekey ...]
将多个 HyperLogLog 合并为一个 HyperLogLog

相关问答

更多

HyperLogLog在redis有什么使用原理

Redis是一个开源的使用C语言编写、开源、支持网络、可基于内存亦可持久化的日志型、高性能的Key-Value数据库,并提供多种语言的API。   它通常被称为数据结构服务器,因为值(value)可以是 字符串(String)、哈希(Map)、 列表(list)、集合(sets) 和 有序集合(sorted sets)等类型。   Redis 与其他 key - value 缓存产品有以下三个特点:   Redis支持数据的持久化,可以将内存中的数据保持在磁盘中,重启的时候可以再次加载进行使用。 ...

如何在redis中统计某些key的数量

自己用一个变量做计数器

LogLog和HyperLogLog算法用于计算大的基数(LogLog and HyperLogLog algorithms for counting of large cardinalities)

这里是基于较新文章的更新版本的算法: var pow_2_32 = 0xFFFFFFFF + 1; function HyperLogLog(std_error) { function log2(x) { return Math.log(x) / Math.LN2; } function rank(hash, max) { var r = 1; while ((hash & 1) == ...

这可以用于redis(Could this be used for redis)

我不认为Redis是做你想做的最好的工具。 Redis很棒,但不是一个键/值存储服务器。 虽然您可以在键中搜索模式并使索引执行花哨的东西(特别是在您的情况下的日期间隔),但它会导致制作和使用混乱的数据库。 我之前使用过nodejs + redis,对于pub / sub功能来说,它很不错。 但是在你的情况下你会更好用sql。 或者检查mongoDB,它非常强大,易于使用mongoose。 I don't think Redis is the best tool to do what you wan ...

clickhouse是否可以直接通过插入查询存储HyperLogLog / uniqState()状态?(Is it possible in clickhouse to store a HyperLogLog / uniqState() state directly trough an insert query?)

所以我只使用clickhouse查询就实现了这一壮举。 它工作得很好! CREATE TABLE demo_db.aggregates ( name String, date Date, ids AggregateFunction(uniq, UInt8) ) ENGINE = MergeTree(date, date, 8192) //So here the declaration of a set of ids in the insert query will lea ...

Redshift的Postgresql-hll(或其他Hyperloglog数据类型/结构)(Postgresql-hll (or another Hyperloglog data type/structure) for Redshift)

Redshift,虽然技术上是postgresql派生的,但是在十年前就已经分道扬.. 它仍然使用与postgres相同的线路协议,但它的代码分歧很大。 在其他不兼容性中,它不再允许自定义数据类型。 这意味着您希望使用的插件类型不可行。 但是,正如您所指出的,如果您能够获取所有原始数据,则可以使用内置的近似功能。 Redshift, while technically postgresql-derived, was forked over ten years ago. It still speak ...

交叉计数的数据结构(DataStructure for Intersection Counts)

检查使用MinHash扩充HyperLogLog 。 Check out augmenting HyperLogLog with MinHash.

加快我对HyperLogLog算法的实施(Speeding up my implementation of HyperLogLog algorithm)

a表示任意的零填充二进制数据。 在这里,您将该数据视为ASCII文本,但它只能包含1和0 ! 这是低效的,因为a5最终使用五个字节。 最简单,最有效的解决方案是为每个计数器存储一个8位数,然后: my @buckets = unpack 'C1024', $bitstring 。 如果你只想在每个计数器上存储5位,那么你最终会节省很少的内存而非常麻烦。 你必须使用像这样疯狂的东西来进行往返转换: my $bitstring = pack "(b5)1024", map { sprintf "%b" ...

Redis Hyperloglog - PFCOUNT副作用(Redis Hyperloglog - PFCOUNT side effect)

HyperLogLog对象的标题如下: struct hllhdr { char magic[4]; /* "HYLL" */ uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* Reserved for future use, must be zero. */ uint8_t card[8]; /* Cached cardinality, little ...

Redis上的HyperLogLog实现无法识别(HyperLogLog Implementation on Redis Not Recognized)

发出r.execute_command("PFADD", "key", 1, 2, 3)以查看您的服务器是否支持该命令。 如果此命令运行正常,则问题出在redis-py 。 编辑 http://redis.io/commands/pfadd已添加到Redis 2.8.9中,您的版本比此版本旧。 您可以使用早期版本支持的http://redis.io/commands/sadd来完成您的工作。 检查此链接并尝试set命令。 他们计算成员的速度较慢,但具有确定性。 Issue a r.execute_ ...