好文分享 Reddit 访客计数方案

MyDataFlow · 发布于 2017年11月27日 · 1131 次阅读
96

原文介绍了全球访问量第八的网站Reddit的文章浏览计数方案。

Reddit想要更好的向Reddit用户展示文章传播度,因此投票数量和评论数将是一条文章的主要指标。但是Reddit有许多用户观看后并不会进行投票和评论。因此我们想构建一个文章浏览计数器。这个数量将展示给文章的创建者或者版主,这样可以让他们更好的对某个文章欢迎度进行评估。

因此Reddit提出了他们的文章技术系统应该满足下面四个需求

  1. 计数必须是实时的,而非小时或者整日的汇总
  2. 在一个时间段内,一个用户只会记录一次
  3. 显示的计数和真实的计数的误差在可控的范围内。
  4. 系统必须是可以实时扩展的并且需要在秒级上处理事件

为了实时精准计数,简答方案就是为每篇帖子维护一个访问用户的集合,然后在每次计算浏览量时检查集合。但是,这种实现方式对于访问量低的帖子是可行的,但一旦一个帖子变得流行,访问量剧增时就很难控制了。甚至有的帖子有超过 100 万的独立访客! 对于这样的帖子,存储独立访客的 ID 并且频繁查询某个用户是否之前曾访问过会给内存和 CPU 造成很大的负担。

因此Reddit在下面两种方案中做出了选择:

  • 线性概率计数法,很准确,但当计数集合变大时所需内存会线性变大。
  • 基于 HyperLogLog (以下简称 HLL )的计数法。 HLL 空间复杂度较低,但是精确度不如线性计数。

最终Reddit选择了HLL方案,并在文章中介绍了实现的细节

暂无回复。
需要 登录/注册 后方可回复, 如果你还没有账号请点击这里 注册