我们想更好地向用户展示Reddit有多大。为此，投票数和评论数是帖子最重要的指标。然而，Reddit上有相当一部分用户只浏览内容，既不投票也不评论。所以我们想建立一个系统，可以统计一个帖子的浏览量。此数字显示给帖子创建者和版主，以便他们可以更好地了解帖子的活跃程度。在这篇博客中，我们将讨论如何实现对超大数据量的计数。统计机制我们对统计系统有四个主要要求：帖子浏览量必须是实时或接近实时的，而不是每天或每小时汇总。同一用户在短时间内多次访问同一个帖子，只计算一次浏览量。显示视图与实际视图之间存在百分之几的小误差。Reddit是世界上访问量第八大的网站。系统必须能够在生产环境中正常运行大规模运行，只允许几秒的延迟来满足以上四个要求，远比听起来困难。为了实时准确统计，我们需要知道用户是否访问过这个帖子。为了了解这些信息，我们为每个帖子维护一个访问用户的集合，然后在每次统计浏览量时检查该集合。一个天真的实现是将访问用户的集合存储在内存中的hashMap中，以帖子Id作为键。这种实现方式适用于低流量的帖子，但一旦帖子变得流行，就很难控制流量何时达到峰值。有些帖子甚至有超过100万独立访问者！对于此类帖子，存储唯一的访问者ID并频繁查询用户之前是否访问过可能会占用大量内存和CPU。因为我们无法提供准确的计数，所以我们研究了几种不同的基数估计算法。有两种方案可以满足我们的需求：一种是线性概率计数法，这种方法非常准确，但是当计数集变大时，需要的内存会线性增加。二是基于HyperLogLog（以下简称HLL）的计数方式。HLL的空间复杂度较低，但不如线性计数精确。让我们看看HLL将节省多少内存。如果我们需要存储100万个独立访问者的ID，每个用户ID的长度为8个字节，那么我们需要8M的内存来存储一个帖子的独立访问者。相反，如果使用HLL，内存占用将显着减少。不同的HLL实现消耗不同的内存量。如果采用本文的实现方式，那么存储100万个ID只需要12KB，是原始值的0.15%！！BigDataCounting:Howtocountthebilliondistinctobjectsusingonly1.5KBofMemory–HighScalability–这篇文章很好地总结了上面的算法。许多HLL实现结合了上述两种算法。当集合较小时使用线性计数，当集合大小达到一定阈值时切换到HLL。前者通常称为“稀疏”（sparse）HLL，后者称为“密集”（dense）HLL。这两种算法的这种组合实现有很大的好处，因为它保证了小型和大型集的准确性，同时保持适度的内存增长。既然我们已经决定使用HLL算法，但是在选择具体的实现方式时，我们考虑了以下三种不同的实现方式。因为我们的数据工程团队使用的是Java和Scala，所以我们只考虑Java和Scala的实现。Twitter的Algebird，在Scala中实现。Algebird有很好的文档，但是他们对稀疏和密集HLL的实现细节不是很了解。stream-lib中提供的HyperLogLog++是用Java实现的。stream-lib中的代码文档是完整的，但是如何正确使用它并对其进行改造以满足我们的需要，理解起来有点困难。RedisHLL实现，这是我们最终选择的。我们认为Redis中HLL的实现是有据可查的，易于配置，并且提供的相关API也易于集成。还有一个好处就是我们可以使用专用的服务器部署来降低性能压力。Reddit的数据管道依赖于Kafka。当用户访问博客时，会触发一个事件，该事件会被发送到事件收集服务器并持久化到Kafka中。之后，计数系统依次运行这两个组件，一个接一个。在我们的计数系统架构中，第一部分是Kafka消费者，我们称之为Nazar。Nazar会从Kafka中读取每一个事件，并通过一系列配置好的规则来判断该事件是否需要统计。我们取这个名字只是因为Nazar是一个眼睛形状的护身符，而“Nazar”系统就像一只眼睛，可以保护我们的计数系统免受恶意行为者的侵害。我们不计入事件的原因之一是同一用户在短时间内重复访问。Nazar会修改事件，添加一个booleanflag表示是否应该统计，然后将事件放回Kafka。现在是系统的第二部分。我们称第二个Kafka消费者为Abacus，用于计算真实的页面浏览量，并将计算结果展示在网站或客户端上。Abacus从Kafka中读取Nazar处理过的事件，根据Nazar的处理结果决定是跳过这个事件还是加入计数。如果Nazar中的处理结果是计数可以加，那么Abacus会先检查这个事件关联的帖子在Redis中是否已经有了HLL计数器。如果它已经存在，Abacus将向Redis发送一个PFADD请求。如果没有，Abacus会向Cassandra集群（Cassandra用来持久化HLL计数器和计数值）发送请求，然后向Redis发送SET请求。这通常发生在用户访问较旧的帖子时，此时Redis中该帖子的计数器可能已过期。在Redis中存储计数器过期的旧帖子的查看计数。Abacus会周期性的将Redis中的所有HLL和每篇博文的view写入Cassandra集群。为避免集群过载，我们以10秒的间隔批量写入。下图展示了事件流的大致流程：总结我们希望浏览量可以让发帖人了解帖子的总浏览量，也可以帮助版主快速定位到自己社区中访问量高的帖子。未来，我们计划利用数据管道的实时潜力为Reddit用户提供更有用的反馈。
