HyperLogLog

什么是 HyperLogLog

HyperLogLog 是一种概率性数据结构，用于估计多重集合或数据流中唯一元素的数量。其基本思想是计算大型数据集中唯一元素的数量。想象一下，你有一个装满不同颜色糖果的罐子，但你不知道罐子里有多少种不同的颜色。如果你想估计罐子里有多少种不同的颜色，你可以抽取少量糖果样本，然后将这些信息推断到整个罐子。这类似于 HyperLogLog 如何使用一组哈希函数和桶来利用少量内存估计大型数据集中的唯一元素数量。HyperLogLog 可以通过分析映射到不同桶的唯一哈希值来估计大型数据集中的唯一元素数量，就像你可以通过少量样本估计罐子里不同糖果的颜色数量一样。

Redis HyperLogLog 最佳实践

唯一项目很难计数。通常这意味着存储每个唯一项目，然后以某种方式检索这些信息。使用 Redis，可以通过使用集合和单个命令来实现这一点，但是对于非常大的集合来说，其存储和时间复杂度都非常高。HyperLogLog 提供了一种概率性的替代方案。

HyperLogLog 在内部类似于布隆过滤器（Bloom filter），因为它通过非密码学哈希处理项目并以位域形式设置位。与布隆过滤器不同，HyperLogLog 会维护一个项目计数器，当添加之前未添加过的新项目时，该计数器会递增。这在估计集合中唯一项目（基数）时提供了非常低的错误率。HyperLogLog 直接内置在 Redis 中。

Redis 中有三个 HyperLogLog 命令：PFADD、PFCOUNT 和 PFMERGE。假设你正在构建一个网络爬虫，并且你想估计一天内页面爬取的唯一 URL 数量。对于每个页面，你可以运行如下命令：

PFADD crawled:20171124 “http://www.google.com/”
(integer) 1
PFADD crawled:20171124 “http://www.redis.com/”
(integer) 1
PFADD crawled:20171124 “http://www.redis.io/”
(integer) 1
PFADD crawled:20171125 “http://www.redisearch.io/”
(integer) 1
PFADD crawled:20171125 “http://www.redis.io/”
(integer) 1
上述每个键都按日期索引。要查看 2017-11-24 爬取的页面数量，我们可以运行以下命令：

PFCOUNT crawled:20171124
(integer) 3
要查看 2017-11-24 和 2017-11-25 爬取的页面总数，我们可以使用 PFMERGE 生成一个包含这两个计数合并结果的新键。注意，由于 https://redis.ac.cn/ 被添加到这两个键中，它不会被重复计数。

PFMERGE crawled:20171124-25 crawled:20171124 crawled:20171125
OK
PFCOUNT crawled:20171124-25
(integer) 4
这是一个多键操作，因此在分片环境中请注意确保您的键最终位于同一分片上。