Reddit如何实现大规模的帖子浏览计数,reddit算法-ESG跨境

Reddit如何实现大规模的帖子浏览计数,reddit算法

Reddit是如何实现大规模的帖子浏览计数的

浏览计数有四个主要要求，满足这四个要求比听起来要复杂得多。

克里希南·钱德拉

我们希望更好地向我们的用户传达Reddit的规模。到目前为止，投票分数和评论数是一个具体帖子活动的主要指标。然而，Reddit有许多访问者在没有投票或评论的情况下阅读内容。我们希望建立一个系统，可以捕捉阅读的帖子数量。然后把这个量展示给内容创作者和版主，让他们更好地了解具体帖子上的活动。

在本文中，我们将讨论如何实现大规模计数。

计数方法

浏览计数有四个主要要求:

计数必须是实时或接近实时的。而不是每天或每小时的总数。

每个用户在短时间内只能计数一次。

显示的数量和实际数量之间的误差在百分之几。

系统必须能够在生产环境中运行，并在事件发生后几秒钟内处理事件。

满足这四个要求比听起来要复杂得多。为了实时保持准确的计数，我们需要知道特定的用户是否曾经访问过这个帖子。为了了解这些信息，我们需要存储以前访问过每个帖子的用户组，然后在每次处理对该帖子的新访问时检查这个用户组。这个解决方案的一个原始实现是将这个唯一的用户集合作为哈希表存储在内存中，并将帖子ID作为键名。

这种方法适用于浏览量较少的文章，但一旦文章流行起来，读者数量迅速增加，这种方法就很难推广。有几个受欢迎的帖子拥有超过一百万的独立读者对于这种帖子来说，对内存和CPU的影响很大，因为所有的id都要存储起来，要经常搜索收藏，看看有没有人访问过。

由于我们无法提供准确的计数，我们研究了几种不同的基数估计[1]算法。我们考虑了两个非常符合我们预期的选项:

☉线性概率计数法，这种方法非常精确，但是要计数的集合越大，线性需要的内存就越多。

基于超对数的☉计数方法[2](HLL)。HLL随着设定的大小而增长，但它不能提供与线性计数器相同的精度。

要想知道HLL到底节省了多少空间，看看本文顶部的r/pics帖子。它拥有超过一百万的独立用户。如果我们存储100万个唯一用户ID，每个用户ID的长度为8个字节，那么我们需要8兆的内存来计算一篇帖子的唯一用户数相比之下，使用HLL计数将占用更少的内存。每个实现中的内存量是不同的，但是对于这个实现[3]，我们可以仅使用12千字节的空间来计算超过一百万个id，这将是原始空间使用量的0.15%

(这篇关于高可伸缩性的文章[4]很好地概述了以上两种算法。)

许多HLL实现使用上述两种方法的组合，也就是说，从小集合的线性计数开始，一旦大小达到特定点就切换到HLL。前者通常被称为“稀疏”的HLL表达式，而后者被称为“密集”的HLL表达式。混合方法非常有利，因为它可以提供准确的结果，同时保持适度的内存占用。这个方法在Google的HyperLogLog++论文中有更详细的描述[5]。

尽管HLL算法是相当标准的，我们考虑在我们的实现中使用三种变体。请注意，对于内存HLL实现，我们只关注Java和Scala实现，因为我们在数据工程团队主要使用Java和Scala。

☉Twitter的☉·阿尔吉伯德图书馆，用Scala实现。Algebird有很好的文档，但是稀疏和密集HLL表达式的实现细节不容易理解。

☉hyperlog log ++在streamlib中的实现，用Java实现。streamlib中的代码有很好的文档记录，但要理解如何正确使用这个库并调整它以满足我们的需求有些困难。

☉Redis(我们选择的)的☉ HLL实现。我们相信Redis的HLL实现是有据可查的，并且易于配置，所提供的与HLL相关的API也易于集成。作为一个额外的好处，使用Redis通过将计数应用程序(HLL计算)的CPU和内存密集型部分转移到专用服务器上，缓解了我们的许多性能问题。

Reddit的数据管道主要围绕阿帕奇卡夫卡[6]。当用户查看帖子时，事件被触发并发国际快递事件收集器服务器，该服务器批量处理事件并将其保存到Kafka。

从这里开始，浏览计数系统有两个按顺序运行的组件。我们计数架构的第一部分是一个叫Nazar[7]的Kafka消费者，他会从Kafka读取每一个事件，并通过我们编制的一套规则来决定一个事件是否应该被计数。我们给它起这个名字是因为纳扎尔是保护你远离邪恶的眼睛护身符，纳扎尔系统是可以保护我们远离不良因素的“眼睛”。Nazar使用Redis来保持状态，并跟踪浏览不应被计算的潜在原因。我们可能无法统计事件的一个原因是同一用户在短时间内重复浏览的结果。Nazar随后会更改事件，添加一个布尔标志来指示是否应该计数，然后发回Kafka事件。

这是这个项目的第二部分。我们有第二个Kafka消费者，叫做Abacus[8]，它实际上是对浏览进行计数，并使计数在网站和客户端上可见。Abacus读取Nazar输出的卡夫卡事件。然后，根据Nazar的决定，它将计算或跳过这一浏览。如果事件被标记为计数，Abacus首先检查Redis中是否有HLL计数器已经有与事件对应的帖子。如果计数器已经在Redis中，那么Abacus向Redis发快递PFADD[9]请求。如果计数器不在Redis中，那么Abacus向Cassandra cluster发快递一个请求。我们使用这个集群来保存HLL计数器和原始计数，并向Redis发快递一个SET[10]请求来添加一个过滤器。这通常发生在人们查看被Redis删除的旧帖子时。

为了维护Redis中可能被删除的旧帖子，Abacus会定期将Redis的完整HLL过滤器和每个帖子的计数记录到Cassandra cluster中。卡珊德拉以10秒为一批进行写作，以避免超载。以下是高级事件流程图。

特别声明：以上文章内容仅代表作者本人观点，不代表ESG跨境电商观点或立场。如有关于作品内容、版权或其它问题请于作品发表后的30日内与ESG跨境电商联系。