我们想要更好的向用户展示 Reddit 的规模。为了这一点，投票和评论数是一个帖子最重要的指标。然而，在 Reddit 上有相当多的用户只浏览内容，既不投票也不评论。所以我们想要建立一个能够计算一个帖子浏览数的系统。这一数字会被展示给帖子的创作者和版主，以便他们更好的了解某个帖子的活跃程度。
在这篇文章中，我们将讨论如何实施计数。
计数方法
对于计数我们主要有四种需求：
计数必须是实时的或接近实时的，而不是每天或每小时汇总。
每个用户在短时间内多次访问，只能计算一次
显示的浏览量与真实浏览量间的误差允许在几个百分点内
系统要能在生产环境的规模上正常运行，在几秒钟内处理发生的事件
满足所有这四个要求比听起来更棘手。为了保持实时精确计数，我们需要知道特定用户是否曾访问过该帖子。要了解这些信息，我们需要存储先前访问过每个帖子的用户集合，然后在每次查看帖子时检查该集合。一个天真的实现方式就是将唯一的用户集作为散列表存储在内存中，以帖子 ID 为 key。
这种实现方式对于访问量低的帖子是可行的，但一旦一个帖子变得流行，访问量剧增时就很难控制了。有的帖子甚至有超过 100 万的独立访客！ 对于这样的帖子，存储独立访客的 ID 并且频繁查询某个用户是否之前曾访问过会给内存和 CPU 造成很大的负担。
由于我们无法提供确切的数据，我们研究了几种不同的基数估计算法。有两个符合我们需求的选项：
线性概率计数方法是非常准确的，但是随着被计数的集合的增加，所需内存会线性变大。
基于 HyperLogLog（简称 HLL）的计数方法。HLLs 随着设置大小而呈线性增长，但是精确度不如线性计数。
了解 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 的实现。
Twitter’s Algebird library, implemented in Scala。Algebird 有很好的文档，但对于 sparse 和 dense HLL 的实现细节不是很容易理解。
An implementation of HyperLogLog++ located in stream-lib, implemented in Java。stream-lib 中的代码有很好的文档，但是很难理解如何正确使用库并根据需要进行调整。
Redis’s HLL implementation (which we chose)。我们认为 Redis HLLs 的实施文档很好、容易配置，提供的相关 API 也很容易整合。作为一个额外的好处，使用 Redis 可以将计数应用程序的 CPU 和内存密集型部分（HLL计算）移动到专用服务器上，从而缓解了许多性能问题。
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 的用户提供更多的有用的反馈。
