第 6 章 HyperLogLog
第 4 章曾介绍过使用 Redis 集合构建唯一计数器，并将这个计数器用于计算网站的唯一访客 IP。虽然使用 Redis 集合实现唯一计数器能够在功能上满足我们的要求，但是如果考虑得更长远一些，就会发现这个使用 Redis 集合实现的唯一计数器有一个明显的缺陷：随着被计数元素的不断增多，唯一计数器占用的内存也会越来越大；计数器越多，它们的体积越大，这一情况就会越严峻。
以计算唯一访客 IP 为例：
-
存储一个 IPv4 格式的 IP 地址最多需要 15 个字节（比如 "127.234.122.101"）。
-
根据网站的规模不同，每天出现的唯一 IP 可能会有数十万、数百万甚至数千万个。
-
为了记录网站在不同时期的访客，并进行相关的数据分析，网站可能需要持续地记录每天的唯一访客IP数量，短则几个月，长则数年。
综合以上条件，如果一个网站想要长时间记录访客的 IP，就必须创建多个唯一计数器。如果网站的访客比较多，那么它创建的每个唯一计数器都将包含大量元素，并因此占用相当一部分内存。
表7-1展示了不同规模的网站在不同时间段中，存储唯一访客 IP 所需的最大内存。可以看到，当网站的唯一访客数量达到1000万时，网站每个月就要花费4.5GB内存去存储唯一访客的IP，对于记录唯一访客IP数量这个简单的功能来说，这样的内存开销实在让人难以接受，并且这还只是存储IPv4地址的开销，随着IPv6地址的逐渐普及，计数器将来可能需要存储IPv6地址，那时它的开销还会再翻上几倍！
Figure 1. 表7-1 不同规模的网站在使用集合记录访客唯一IP时所需的内存数量
为了高效地解决计算唯一访客 IP 数量这类问题，研究人员开发了很多不同的方法，其中一个就是本章要介绍的 HyperLogLog 算法。