HyperLogLog

一般评估一个网站的访问量，有几个主要的参数：

一般来说，pv或者uv的统计，可以自己来做，也可以借助第三方工具，比如： cnzz，友盟等。

如果自己实现，pv比较简单，可以直接通过Redis 计数器实现。但是 uv不一样，uv涉及到另一个问题： 去重。

首先需要在前端给每一个用户生成一个唯一 id，无论是登录用户还是未登录用户，都要有一个唯一id，这个 id 伴随着请求一起到达后端，在后端我们通过 set 集合中的 sadd 命令来存储这个 id，最后通过 scard 统计集合大小，进而得出 uv 数据。

如果是千万级别的 UV，需要的存储空间就非常惊人。而且，像 UV 统计这种，一般也不需要特别精确，800w 的 uv 和 803w 的 uv，其实差别不大。所以，我们要介绍今天的主角---HyperLogLog。

Redis 中提供的 HyperLogLog 就是专门用来解决这个问题的，HyperLogLog 提供了一套不怎么精确但是够用的去重方案，会有误差，官方给出的误差数据是 0.81%，这个精确度，统计 UV 够用了。

HyperLogLog 主要提供了两个命令：pfadd 和 pfcount。

pfadd 用来添加记录，类似于 sadd ，添加过程中，重复的记录会自动去重。

pfcount 则用来统计数据。

数据量少的时候看不出来误差。

在 Java 中，我们多添加几个元素：

理论值是1001，而实际运行值为 994 ，有误差，但可以在接收到范围内。

除了 pfadd 和 pfcount 之外，还有一个命令， pfmerge， 合并多个统计结果，在合并的过程中，会自动去重多个集合中重复的元素。

原文链接

我们想要更好的向用户展示 Reddit 的规模。为了这一点，投票和评论数是一个帖子最重要的指标。然而，在 Reddit 上有相当多的用户只浏览内容，既不投票也不评论。所以我们想要建立一个能够计算一个帖子浏览数的系统。这一数字会被展示给帖子的创作者和版主，以便他们更好的了解某个帖子的活跃程度。

在这篇文章中，我们将讨论如何实施计数。

对于计数我们主要有四种需求：

满足所有这四个要求比听起来更棘手。为了保持实时精确计数，我们需要知道特定用户是否曾访问过该帖子。要了解这些信息，我们需要存储先前访问过每个帖子的用户集合，然后在每次查看帖子时检查该集合。一个天真的实现方式就是将唯一的用户集作为散列表存储在内存中，以帖子 ID 为 key。

这种实现方式对于访问量低的帖子是可行的，但一旦一个帖子变得流行，访问量剧增时就很难控制了。有的帖子甚至有超过 100 万的独立访客！ 对于这样的帖子，存储独立访客的 ID 并且频繁查询某个用户是否之前曾访问过会给内存和 CPU 造成很大的负担。

由于我们无法提供确切的数据，我们研究了几种不同的基数估计算法。有两个符合我们需求的选项：

了解 HLLs 会节省多少内存。如果我们不得不存储 100 万个唯一的用户 ID，并且每个用户 ID 是一个8字节的长度，那么我们将需要 8M 的内存来计算单个帖子的唯一用户数！相比之下，使用 HLL 进行计数将占用较少的内存。不同的 HLL 实现方式消耗的内存不同。但是在这种实现的情况下，存储超过 100 万个 ID 仅需 12 KB，是原来的 0.15%！

Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory 这篇文章对上述两种算法都有很好的概述。

许多 HLL 的实现都是结合了上面两种算法。在集合小的时候采用线性计数，当集合大小到达一定的阈值后切换到 HLL。前者通常被称为 ”稀疏“(sparse) HLL，后者被称为”稠密“(dense) HLL。这种结合了两种算法的实现有很大的好处，因为它对于小集合和大集合都能够保证精确度，同时保证了适度的内存增长。这种方法更详细地描述参看 Google 论文 。

现在我们已经确定要采用 HLL 算法了，不过在选择具体的实现时，我们考虑了以下三种不同的实现。因为我们的数据工程团队使用 Java 和 Scala，所以我们只考虑 Java 和 Scala 的实现。

Reddit 的数据管道依赖于 Apache Kafka 。当用户查看帖子时，事件将被触发并发送到事件收集服务器，该服务器将事件分批并将其持久化在 Kafka 中。

之后，计数系统会按顺序依次运行两个组件。我们的计数架构的第一部分是一个称之为 Nazar 的 Kafka 的消费者。Nazar 将从 Kafka 中读取每个事件，并通过一系列配置规则来判断该事件是否需要被计数。Nazar 使用 Redis 维持状态，并跟踪不应该被计数的潜在原因。其中一个我们不将一个事件计数在内的原因就是同一个用户在很短时间内重复访问。在将事件发送回 Kafka 之前，Nazar 会更改事件，并添加一个布尔标志，表示是否应该计数。

下面就是系统的第二部分。我们将第二个 Kafka 的消费者称为 Abacus，用来进行真正的计数，并将计算结果显示在网站或客户端。Abacus 从 Kafka 中读取经过 Nazar 处理过的事件，并根据 Nazar 的处理结果决定是跳过这个事件还是将其加入计数。如果事件被标记为计数，则 Abacus 首先检查 Redis 中是否存在与事件相对应的帖子的 HLL 计数器。如果已经存在，Abacus 会给 Redis 发送一个 PFADD 请求。如果不存在，那么 Abacus 会给 Cassandra 集群（用来持久化 HLL 计数器和计数值）发送一个请求，然后再向 Redis 发送请求。这通常发生在人们访问较老帖子的时候，这时该帖子的计数器很可能已经在 Redis 中过期了。

为了维护 Redis 中计数器过期的老帖子的计数，Abacus 会定期向 Redis 发出完整的 HLL 计数器以及每个帖子的计数到 Cassandra 集群。为了避免集群过载，我们以 10 秒为周期批量写入。

事件流程图：

我们希望浏览量可以让发帖者了解帖子全部的访问量，也帮助版主快速定位自己社区中高访问量的帖子。在未来，我们计划利用数据管道在实时方面的潜力来为 Reddit 的用户提供更多的有用的反馈。

---