唯一计数器

上一章《计数器》介绍了简单计数器的实现方式，它可以在用户每次执行特定动作之后更新计数值。对于记录下载次数、浏览次数这类场景，这种计数器已经可以满足需求。但由于这种计数器即使对于重复出现的对象或动作也会多次进行计数，所以它并不适用于某些场景。

举个例子，假如我们现在想要统计的是访问网站的用户数量而不是网站被浏览的次数，那么上一章介绍的计数器将无法满足要求：因为它无法判断访问网站的用户是否都是不同的用户，又或者是同一个用户重复访问了网站多次。

这时我们需要的就是唯一计数器，这种计数器对于每个特定的对象或动作只会计数一次。具体到统计用户数量的场景，这种计数器只会对每个不同的用户进行计数，而重复出现的同一个用户则不会被重复计数。

需求描述

你想要使用Redis构建唯一计数器，这种计数器对于每个特定对象或动作只会计数一次。

解决方案：使用集合键

实现唯一计数器的其中一种方法也是最直接的方法，就是使用Redis集合：通过将每个被计数的对象加入到集合中，程序可以轻而易举地获取集合包含的成员数量，并在有需要的时候快速地增删被计数的对象。

举个例子，如果我们现在想要使用Redis集合来统计访问网站的用户数量，那么只需要一直使用SADD命令将用户添加到某个集合当中即可。由于集合不会保留重复元素，所以只有未被计数过的用户会被添加到集合当中。之后，程序只需要使用SCARD命令就可以获取目前访问网站的用户数量，还可以在有需要的时候使用SREM命令从集合中移除指定的用户。

作为例子，以下命令序列展示了如何使用集合键VisitCounter记录访问网站的用户：

redis> SADD VisitCounter "Peter"    -- 将用户添加至集合
(integer) 1
redis> SADD VisitCounter "Jack" "Tom"
(integer) 2
redis> SADD VisitCounter "Tom"    -- 重复对象不会被计数
(integer) 0

然后我们就可以通过SCARD命令获取当前访客数量的统计数字，又或者从集合中移除特定的某个用户了：

redis> SCARD VisitCounter    -- 当前访客数量
(integer) 3
redis> SREM VisitCounter "Peter"    -- 从访客集合中移除指定用户
(integer) 1
redis> SCARD VisitCounter    -- 再次获取当前访客数量
(integer) 2

代码清单 CODE_UNIQUE_COUNTER 展示了基于上述原理实现的唯一计数器程序。

---

代码清单 CODE_UNIQUE_COUNTER 使用集合实现的唯一计数器 unique_counter.py

class UniqueCounter:

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

    def include(self, item):
        """
        尝试对给定元素进行计数。
        如果该元素之前没有被计数过，那么返回True，否则返回False。
        """
        return self.client.sadd(self.key, item) == 1

    def exclude(self, item):
        """
        尝试将被计数的元素移出计数器。
        移除成功返回True，因元素尚未被计数而导致移除失败则返回False。
        """
        return self.client.srem(self.key, item) == 1

    def count(self):
        """
        返回计数器当前已计数的元素数量。
        如果计数器为空，那么返回0作为结果。
        """
        return self.client.scard(self.key)

---

作为例子，以下代码展示了这个唯一计数器程序的使用方式：

>>> from redis import Redis
>>> from unique_counter import UniqueCounter
>>> client = Redis(decode_responses=True)
>>> counter = UniqueCounter(client, "VisitCounter")
>>> counter.include("Peter")  # 对元素进行计数
True
>>> counter.include("Jack")
True
>>> counter.include("Tom")
True
>>> counter.include("Tom")  # 重复元素不会被计数
False
>>> counter.count()  # 查看当前计数结果
3

解决方案：使用HyperLogLog键

使用集合实现的唯一计数器虽然能够满足需求，但它并非完美无缺：这个实现需要将被计数的所有元素都添加到集合里面，当需要计数的元素数量非常多，又或者需要进行大量计数的时候，使用集合实现的唯一计数器将消耗大量内存。

为了解决这个问题，我们可以修改唯一计数器的程序实现，改用HyperLogLog而不是集合作为底层结构：

• HyperLogLog跟集合一样，都可以对元素进行计数。

• HyperLogLog跟集合的不同之处在于，它返回的计数结果并不是准确的集合基数，而是跟基数八九不离十的一个估算基数。

• HyperLogLog的好处是它的内存占用量不会随着被计数元素的增多而增多，无论对多少元素进行计数，HyperLogLog的内存消耗都是固定的，并且是非常少的。

如果你的应用并不追求完全正确的计数结果，并且不需要准确知道某个元素是否已经被计数，那么完全可以使用HyperLogLog代替集合来实现唯一计数器。举个例子，如果你只想知道网站大概的访问人数，并且只关心这个计数结果，而不是想要知道某个具体的用户是否一定访问过网站，那么就可以使用HyperLogLog实现的计数器。

举个例子，通过使用以下命令序列，程序可以将给定的用户添加到由HyperLogLog键实现的计数器中，然后再获取当前的计数结果：

redis> PFADD HllVisitCounter "Peter" "Jack" "Tom"  -- 进行计数
(integer) 1
redis> PFADD HllVisitCounter "Peter"  -- 已计数的对象通常不会重复计数
(integer) 0
redis> PFCOUNT HllVisitCounter  -- 获取当前计数结果
(integer) 3

代码清单 CODE_HLL_UNIQUE_COUNTER 展示了基于上述原理实现的唯一计数器。

---

代码清单 CODE_HLL_UNIQUE_COUNTER 使用HyperLogLog实现的唯一计数器 hll_unique_counter.py

class HllUniqueCounter:

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

    def include(self, item):
        """
        尝试对给定元素进行计数。
        如果该元素之前没有被计数过，那么返回True，否则返回False。
        """
        return self.client.pfadd(self.key, item) == 1

    def exclude(self, item):
        """
        尝试将被计数的元素移出计数器。
        移除成功返回True，因元素尚未被计数而导致移除失败则返回False。
        """
        raise NotImplementedError

    def count(self):
        """
        返回计数器当前已计数的元素数量。
        如果计数器为空，那么返回0作为结果。
        """
        return self.client.pfcount(self.key)

---

因为HyperLogLog无法撤销对给定元素的计数，所以这个计数器也没有实现相应的exclude()方法。

作为例子，以下代码展示了这个计数器程序的使用方法：

>>> from redis import Redis
>>> from hll_unique_counter import HllUniqueCounter
>>> client = Redis(decode_responses=True)
>>> counter = HllUniqueCounter(client, "HllVisitCounter")
>>> counter.include("Peter")    # 计数元素
True
>>> counter.include("Jack")
True
>>> counter.include("Tom")
True
>>> counter.include("Tom")    # 已计数的元素没有被计数
False
>>> counter.count()    # 获取当前计数结果
3

可以看到，这个新的计数器实现使用起来就跟之前集合实现的计数器一样，并且返回的结果也完全一致。如果继续向这个新的计数器输入更多元素，那么它可能会多计数或少计数其中一些元素，但无论如何，这个计数器的计数结果仍然会处于合理范围之内。

重点回顾

• 唯一计数器跟简单计数器不一样，它对于每个特定对象或动作只会计数一次而不是多次。

• 实现唯一计数器的其中一种方法也是最直接的方法，就是使用Redis集合：通过将每个被计数的对象加入到集合中，程序可以轻而易举地获取集合包含的成员数量，并在有需要的时候快速地增删被计数的对象。

• 使用集合实现的唯一计数器虽然能够满足需求，但它并非完美无缺：集合实现的计数器需要将被计数的所有元素都添加到集合里面，当需要计数的元素数量非常多，又或者需要进行大量计数的时候，这种计数器将消耗大量内存。

• 一种更高效地实现唯一计数器的方法就是使用HyperLogLog：这种数据结构既可以对对象进行计数，又只需要少量内存。虽然HyperLogLog记录的计数并不是完全精确的，但这对于很多不需要精确计数结果的应用来说并不是一个问题。