Reddit 如何统计每个帖子的浏览量

（点击 上方公众号 ，可快速关注）

来源：Giraffe，

yemengying.com/2017/06/04/reddit-view-counting/

如有好文章投稿，请点击 → 这里了解详情

之前没听过也没了解过 HyperLogLog，通过翻译这篇文章正好简单学习下。欢迎指正错误~

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

在这篇博客中，我们将讨论我们是如何实现超大数据量的计数。

计数机制

对于计数系统我们主要有四种需求:

• 帖子浏览数必须是实时或者近实时的，而不是每天或者每小时汇总。

• 同一用户在短时间内多次访问帖子，只算一个浏览量

• 显示的浏览量与真实浏览量间允许有小百分之几的误差

• Reddit 是全球访问量第八的网站，系统要能在生产环境的规模上正常运行，仅允许几秒的延迟

要全部满足以上四个需求的困难远远比听上去大的多。为了实时精准计数，我们需要知道某个用户是否曾经访问过这篇帖子。想要知道这个信息，我们就要为每篇帖子维护一个访问用户的集合，然后在每次计算浏览量时检查集合。一个 naive 的实现方式就是将访问用户的集合存储在内存的 hashMap 中，以帖子 Id 为 key。

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

因为我们不能提供准确的计数，我们查看了几种不同的基数估计算法。有两个符合我们需求的选择：

• 一是线性概率计数法，很准确，但当计数集合变大时所需内存会线性变大。

• 二是基于 HyperLogLog (以下简称 HLL )的计数法。 HLL 空间复杂度较低，但是精确度不如线性计数。

下面看下 HLL 会节省多少内存。如果我们需要存储 100 万个独立访客的 ID, 每个用户 ID 8 字节长，那么为了存储一篇帖子的独立访客我们就需要 8 M的内存。反之，如果采用 HLL 会显著减少内存占用。不同的 HLL 实现方式消耗的内存不同。如果采用这篇文章的实现方法，那么存储 100 万个 ID 仅需 12 KB，是原来的 0.15%！！