redis 高级数据类型之 HyperLogLog 算法详细介绍_redis

大家好，我是腾意。

前面曾介绍过使用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地址，那时它的开销还会再翻上几倍！

表7-1　不同规模的网站在使用集合记录访客唯一IP时所需的内存数量

为了高效地解决计算唯一访客IP数量这类问题，研究人员开发了很多不同的方法，其中一个就是本章要介绍的HyperLogLog算法。

7.1　HyperLogLog简介

HyperLogLog是一个专门为了计算集合的基数而创建的概率算法，对于一个给定的集合，HyperLogLog可以计算出这个集合的近似基数：近似基数并非集合的实际基数，它可能会比实际的基数小一点或者大一点，但是估算基数和实际基数之间的误差会处于一个合理的范围之内，因此那些不需要知道实际基数或者因为条件限制而无法计算出实际基数的程序就可以把这个近似基数当作集合的基数来使用。

HyperLogLog的优点在于它计算近似基数所需的内存并不会因为集合的大小而改变，无论集合包含的元素有多少个，HyperLogLog进行计算所需的内存总是固定的，并且是非常少的。具体到实现上，Redis的每个HyperLogLog只需要使用12KB内存空间，就可以对接近：264个元素进行计数，而算法的标准误差仅为0.81%，因此它计算出的近似基数是相当可信的。

本章将对Redis中HyperLogLog的各个操作命令进行介绍，通过使用这些命令，用户可以：

对集合的元素进行计数。
获取集合当前的近似基数。
合并多个HyperLogLog，合并后的HyperLogLog记录了所有被计数集合的并集的近似基数。

在介绍HyperLogLog命令的同时，本章还会说明如何通过这些命令去实现一个只需要固定内存的唯一计数器，以及一个能够检测出重复信息的检查器。

7.2　PFADD：对集合元素进行计数

用户可以通过执行PFADD命令，使用HyperLogLog对给定的一个或多个集合元素进行计数：

PFADD hyperloglog element [element ...]

根据给定的元素是否已经进行过计数，PFADD命令可能返回0，也可能返回1：

如果给定的所有元素都已经进行过计数，那么PFADD命令将返回0，表示HyperLog-Log计算出的近似基数没有发生变化。
与此相反，如果给定的元素中出现了至少一个之前没有进行过计数的元素，导致HyperLogLog计算出的近似基数发生了变化，那么PFADD命令将返回1。

举个例子，通过执行以下命令，我们可以使用alphabets这个HyperLogLog对"a"、"b"、"c"这3个元素进行计数：

redis> PFADD alphabets "a" "b" "c"
(integer) 1

因为这是alphabets第一次对元素"a"、"b"、"c"进行计数，所以alphabets计算的近似基数将发生变化，并使PFADD命令返回1。

但是如果我们再次要求alphabets对元素"a"进行计数，那么这次PFADD命令将返回0，这是因为已经计数过的元素"a"并不会对alphabets计算的近似基数产生影响：

redis> PFADD alphabets "a"
(integer) 0

其他信息

复杂度：O（N），其中N为用户给定的元素数量。

版本要求：PFADD命令从Redis 2.8.9版本开始可用。

7.3　PFCOUNT：返回集合的近似基数

在使用PFADD命令对元素进行计数之后，用户可以通过执行PFCOUNT命令来获取HyperLogLog为集合计算出的近似基数：

PFCOUNT hyperloglog [hyperloglog ...]

比如，通过执行以下命令，我们可以获取到alphabets这个HyperLogLog计算出的近似基数：

redis> PFCOUNT alphabets
(integer) 3

PFCOUNT命令的返回值为3，这表示HyperLogLog算法认为alphabets目前已经计数过3个不同的元素。

另外，当用户给定的HyperLogLog不存在时，PFCOUNT命令将返回0作为结果：

redis> PFCOUNT not-exists-hyperloglog
(integer) 0

7.3.1　返回并集的近似基数

当用户向PFCOUNT传入多个HyperLogLog时，PFCOUNT命令将对所有给定的Hyper-LogLog执行并集计算，然后返回并集HyperLogLog计算出的近似基数。

比如，我们可以创建两个HyperLogLog，并分别使用这两个HyperLogLog去对两组字母进行计数：

redis> PFADD alphabets1 "a" "b" "c"
(integer) 1

redis> PFADD alphabets2 "c" "d" "e"
(integer) 1

然后使用以下PFCOUNT命令获取这两个HyperLogLog进行并集计算之后得出的近似基数：

redis> PFCOUNT alphabets1 alphabets2
(integer) 5

对多个HyperLogLog执行并集计算的效果与多个集合首先执行并集计算，然后再使用HyperLogLog去计算并集集合的近似基数的效果类似。比如，上面的PFCOUNT命令就类似于以下这两条命令：

redis> PFADD temp-hyperloglog "a" "b" "c" "c" "d" "e"
(integer) 1

redis> PFCOUNT temp-hyperloglog
(integer) 5

7.3.2　其他信息

复杂度：O（N），其中N为用户给定的HyperLogLog数量。

版本要求：PFCOUNT命令从Redis 2.8.9版本开始可用。

示例：优化唯一计数器

为了解决本章开头提到的唯一计数器的内存占用问题，我们可以使用HyperLogLog重新实现唯一计数器：无论被计数的元素有多少个，使用HyperLogLog实现的唯一计数器的内存开销总是固定的，并且因为每个HyperLogLog只占用12KB内存，所以即使程序使用多个HyperLogLog，也不会带来明显的内存开销。

代码清单7-1展示了使用HyperLogLog重新实现的唯一计数器。

代码清单7-1　使用HyperLogLog实现的唯一计数器：/hyperloglog/unique_counter.py

class UniqueCounter:

    def __init__(self, client, key):
        self.client = client
        self.key = key

    def count_in(self, item):
        """
        对给定元素进行计数
        """
        self.client.pfadd(self.key, item)

    def get_result(self):
        """
        返回计数器的值
        """
        return self.client.pfcount(self.key)

以下代码展示了这个唯一计数器的使用方法：

>>> from redis import Redis
>>> from unique_counter import UniqueCounter
>>> client = Redis(decode_responses=True)
>>> counter = UniqueCounter(client, 'unique-ip-counter')  # 创建一个唯一IP计数器
>>> counter.count_in('1.1.1.1')                # 对3个IP进行计数
>>> counter.count_in('2.2.2.2')
>>> counter.count_in('3.3.3.3')
>>> counter.get_result()                       # 获取计数结果
3
>>> counter.count_in('3.3.3.3')                # 尝试输入一个已经计数过的IP
>>> counter.get_result()                       # 计数器的结果没有发生变化
3

通过使用HyperLogLog实现的唯一计数器去取代使用集合实现的唯一计数器，可以大幅降低存储唯一访客IP所需的内存数量，表7-2展示了这一点。

表7-2　使用HyperLogLog实现的唯一计数器在记录唯一

与集合实现的唯一计数器相比，使用HyperLogLog实现的唯一计数器并不会因为被计数元素的增多而变大，因此它无论是对10万个、100万个还是1000万个唯一IP进行计数，计数器消耗的内存数量都不会发生变化。与此同时，这个新计数器即使在每天唯一IP数量达到1000万个的情况下，记录一年的唯一IP数量也只需要4.32MB内存，这比同等情况下使用集合去实现唯一计数器所需的内存要少得多。

示例：检测重复信息

在构建应用程序的过程中，我们经常需要与广告等垃圾信息做斗争。因为垃圾信息的发送者通常会使用不同的账号、在不同的地方发送相同的垃圾信息，所以寻找垃圾信息的一种比较简单、有效的方法就是找出那些重复的信息：如果两个不同的用户发送了完全相同的信息，或者同一个用户重复地发送了多次完全相同的信息，那么这些信息很有可能就是垃圾信息。

判断两段信息是否相同并不是一件容易的事情，如果使用一般的字符串比对函数（比如strcmp）来完成这一操作，那么每当有用户尝试执行信息发布操作时，程序就需要执行复杂度为O（N*M）的比对操作，其中N为信息的长度，M为系统目前已有的信息数量。

不难看出，随着系统存储的信息越来越多，这种比对操作将变得越来越慢，最终成为系统的瓶颈。

为了降低鉴别重复信息所需的复杂度，我们可以使用HyperLogLog来记录所有已发送的信息——每当用户发送一条信息时，程序就使用PFADD命令将这条信息添加到HyperLogLog中：

如果命令返回1，那么这条信息就是未出现过的新信息。
如果命令返回0，那么这条信息就是已经出现过的重复信息。

因为HyperLogLog使用的是概率算法，所以即使信息的长度非常长，HyperLogLog判断信息是否重复所需的时间也非常短。另外，因为HyperLogLog并不会随着被计数信息的增多而变大，所以程序可以把所有需要检测的信息都记录到同一个HyperLogLog中，这使得实现重复信息检测程序所需的空间极大地减少。代码清单7-2展示了这个使用HyperLogLog实现的重复信息检测程序。

代码清单7-2　使用HyperLogLog实现的重复信息检测程序：/hyperloglog/duplicate_checker.py

class DuplicateChecker:

    def __init__(self, client, key):
        self.client = client
        self.key = key

    def is_duplicated(self, content):
        """
        在信息重复时返回True，未重复时返回False
        """
        return self.client.pfadd(self.key, content) == 0

    def unique_count(self):
        """
        返回检查器已经检查过的非重复信息数量
        """
        return self.client.pfcount(self.key)

以下代码展示了如何使用DuplicateChecker程序检测并发现重复的信息：

>>> from redis import Redis
>>> from duplicate_checker import DuplicateChecker
>>> client = Redis(decode_responses=True)
>>> checker = DuplicateChecker(client, 'duplicate-message-checker')
>>> checker.is_duplicated("hello world!")      # 输入一些非重复信息
False
>>> checker.is_duplicated("good morning!")
False
>>> checker.is_duplicated("bye bye")
False
>>> checker.unique_count()                     # 查看目前非重复信息的数量
3
>>> checker.is_duplicated("hello world!")      # 发现重复信息
True

检测重复信息这个问题实际上就是算法中的“去重问题”，因此其他去重问题也可以使用DuplicateChecker程序中展示的方法来解决。

7.4　PFMERGE：计算多个HyperLogLog的并集

PFMERGE命令可以对多个给定的HyperLogLog执行并集计算，然后把计算得出的并集HyperLogLog保存到指定的键中：

PFMERGE destination hyperloglog [hyperloglog ...]

如果指定的键已经存在，那么PFMERGE命令将覆盖已有的键。PFMERGE命令在成功执行并集计算之后将返回OK作为结果。

HyperLogLog并集计算的近似基数接近于所有给定HyperLogLog的被计数集合的并集基数。举个例子，假如有h1、h2、h33个HyperLogLog，它们分别对集合s1、s2、s3进行计数，那么h1、h2、h3这3个HyperLogLog的并集所计算出的近似基数将接近于s1、s2、s3这3个集合的并集的基数。

以下代码展示了如何使用PFMERGE计算numbers1、numbers2和numbers3这3个HyperLogLog的并集，并将其存储到union-numbers键中：

redis> PFADD numbers1 128 256 512
(integer) 1

redis> PFADD numbers2 128 256 512
(integer) 1

redis> PFADD numbers3 128 512 1024
(integer) 1

redis> PFMERGE union-numbers numbers1 numbers2 numbers3
OK

redis> PFCOUNT union-numbers
(integer) 4

7.4.1　PFCOUNT与PFMERGE

PFCOUNT命令在计算多个HyperLogLog的近似基数时会执行以下操作：

1）在内部调用PFMERGE命令，计算所有给定HyperLogLog的并集，并将这个并集存储到一个临时的HyperLogLog中。

2）对临时HyperLogLog执行PFCOUNT命令，得到它的近似基数（因为这是针对单个HyperLogLog的PFCOUNT，所以这个操作不会引起循环调用）。

3）删除临时HyperLogLog。

4）向用户返回之前得到的近似基数。

举个例子，当我们执行以下命令的时候：

redis> PFCOUNT numbers1 numbers2 numbers3
(integer) 4

PFCOUNT将执行以下以下操作：

1）执行PFMERGEnumbers1numbers2numbers3，把3个给定HyperLogLog的并集结果存储到临时HyperLogLog中。

2）执行PFCOUNT，取得并集HyperLogLog的近似基数4。

3）执行DEL，删除临时HyperLogLog。

4）向用户返回之前得到的近似基数4。

基于上述原因，当程序需要对多个HyperLogLog调用PFCOUNT命令，并且这个调用可能会重复执行多次时，我们可以考虑把这一调用替换成相应的PFMERGE命令调用：通过把并集的计算结果存储到指定的HyperLogLog中而不是每次都重新计算并集，程序可以最大程度地减少不必要的并集计算。

7.4.2　其他信息

复杂度：O（N），其中N为用户给定的HyperLogLog数量。

版本要求：PFMERGE命令从Redis 2.8.9版本开始可用。

示例：实现每周/月度/年度计数器

本章前面介绍了如何使用PFADD命令和PFCOUNT命令实现HyperLogLog版本的唯一计数器，在学习了PFMERGE命令之后我们可以通过使用这个命令对多个HyperLogLog实现的唯一计数器执行并集计算，从而实现每周/月度/年度计数器：

通过对一周内每天的唯一访客IP计数器执行PFMERGE命令，我们可以计算出那一周的唯一访客IP数量。
通过对一个月内每天的唯一访客IP计数器执行PFMERGE命令，我们可以计算出那一个月的唯一访客IP数量。
年度甚至更长时间的唯一访客IP数量也可以按照类似的方法计算。

代码清单7-3展示了一个能够对多个唯一计数器执行并集计算，并将结果存储到指定键的程序。

代码清单7-3　唯一计数器合并程序：/hyperloglog/unique_counter_merger.py

class UniqueCounterMerger:

    def __init__(self, client):
        self.client = client

    def merge(self, destination, *hyperloglogs):
        self.client.pfmerge(destination, *hyperloglogs)

UniqueCounterMerger的定义非常简单，它使用类将PFMERGE命令封装了一下，以下代码展示了使用这个合并程序计算一周唯一访客IP数量的方法：

>>> from redis import Redis
>>> from unique_counter_merger import UniqueCounterMerger
>>> client = Redis(decode_responses=True)
>>> merger = UniqueCounterMerger(client)
>>> counters = [
...   'unique_ip_counter::8-10',  # 本周7天的计数器键名
...   'unique_ip_counter::8-11',
...   'unique_ip_counter::8-12',
...   'unique_ip_counter::8-13',
...   'unique_ip_counter::8-14',
...   'unique_ip_counter::8-15',
...   'unique_ip_counter::8-16'
... ]
>>> merger.merge('unique_ip_counter::No_33_week', *counters)  # 计算并存储本周的唯
一访客IP数量
>>> client.pfcount('unique_ip_counter::No_33_week')     # 获取本周的唯一访客IP数量
47463

7.5　重点回顾

HyperLogLog是一个概率算法，它可以对大量元素进行计数，并计算出这些元素的近似基数。
无论被计数的元素有多少个，HyperLogLog只使用固定大小的内存，其内存占用不会因为被计数元素增多而增多。
在有需要的情况下，用户可以使用PFMERGE命令代替针对多个HyperLogLog的PFCOUNT命令调用，从而避免重复执行相同的并集计算。
HyperLogLog不仅可以用于计数问题，还可以用于去重问题。

版权声明：如无特殊说明，文章均为本站原创，版权所有，转载需注明本文链接

本文链接：http://www.bianchengvip.com/article/redis-HyperLogLog/

redis 高级数据类型之 HyperLogLog 算法详细介绍

7.1 HyperLogLog简介

7.2 PFADD：对集合元素进行计数

7.3 PFCOUNT：返回集合的近似基数

7.3.1 返回并集的近似基数

7.3.2 其他信息