HyperLogLog

HyperLogLog 是什么

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

Redis HyperLogLog 最佳实践

很难计算唯一项。通常这意味着以某种方式存储每个唯一项，然后调用此信息。使用 Redis 可以使用集合和单一命令完成此操作，但对于非常大的集合，存储和时间复杂度就非常高。HyperLogLog 提供了一个概率性方案。

HyperLogLog 在内部类似于布隆过滤器，因为它通过非加密哈希运行项目，并在位字段形式中设置位。与布隆过滤器不同，HyperLogLog 会保留项目的计数器，当先前未添加新项目时，该计数器会增加。在估算集合的唯一项目（基数）时，这会提供非常低的错误率。HyperLogLog 已经内置到 Redis 中。

Redis 中有三个 HyperLogLog 命令：PFADD、PFCOUNT 和 PFMERGE。假设你正在构建一个网络爬虫，并且你希望估算页面在给定日期爬取到的唯一 URL 的数量。对于每个页面，你可以运行类似于此的命令

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

PFCOUNT crawled:20171124
(整数) 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
(整数) 4
这是一个多键操作，因此在分片环境中请格外小心，以确保键最终位于同一分片上。