Reddit帝国建立在一个有瑕疵的算法之上

Reddit的源码中存在一个bug。这个bug目前还存在他们的平台产品之中,并且已经存在了多年。这个bug与应用于整个站点最重要的算法之一有关——针对“热点”链接受欢迎度的排序算法。这个bug也导致了真实显见的负面影响,并且这个问题多次报告给Reddit的技术组,但是一直没有被修复。

 

缺陷

Reddit需要判断当前哪篇文章比较热门。新文章比旧文章更热门一些,拥有更多正面投票的文章比有很少投票的文章更好,而大部分投负面票的文章则垫底。这些规则比较容易计算。针对发布时间和投票可以确定一个确切的数值,然后与一个常量系数,就能计算出每篇文章的的受欢迎程度1

魔鬼在于细节,根据GitHub中的源码,目前的实现是这样的。

seconds是根据时间变化的变量,基于Unix时间戳。这样做合情理,时间总是累加的,所以每一个新文章发布都较之前发布的文章在时间上拥有更高的分数值。

投票部分计算根据公式有两个部分,sign变量简单地记录总投票数是正面还是反面的。如果文章收到的正面评分比负面评分更多,sign就是1;如果负面评分更多,sign的值就是-1.其他变量,order是投票分数绝对值的取log102对数。

真正的问题是,和许多问题一样,从两个角色的交换。

这里我们计算得到了最终的分数。Seconds是一个很大的正值,而order总是返回为正——由于这里使用了的绝对值,所以,尽管如一个负数-389也会得到和order值为389一样的结果,我们需要通过sign来调整我们的结果,这样,负面意见的文章会被排在后面。但是这里的代码使用了sign乘于时间seconds,而不是sign乘于order。

而对于正面评价的文章,则没有影响,由于符号位为1,所以order和seconds相加,计算没有问题。

对于负面评价文章又发生了什么呢?sign值为-1,所以值比较大的seconds变量会变为负值,而使用一个正面评价的order值与之相加,因此会导致几个问题。

假设两篇文章,相距5秒发布。每一个都收到两个父母评价,seconds对于新文章值更大一些,但是因为sign为负值,新的文章评分反而比旧的文章低。

假定还有两篇文章同时发布,一篇文章收到了10个差评,另外一篇文章收到五个差评。由于seconds一样,符号值sign都是-1,但是得到-10评价的文章order值更高。所以,-10评分的文章反而排序在得到-5评分的文章前面,尽管人们讨厌它两倍。

现在假定一篇文章在一年前发布,另外一篇文章刚刚才发布。去年发布的文章有两个正面评分,今天刚发布的文章有两个差评。这里有点不同——今天发布的文章可能得到了差评开始,不过也可能接下来收到好评。不过,在当前的实现3中,由于今天文章有两个差评,从而导致其热度评分反而比去年的文章更低。

 

后续

这并不是一个假设的漏洞,我好奇地去看了一些Reddit的公共库的代码是否也应用在他们当前的产品中,我找到近期发布的一些不太活跃的文章,给它差评使得它的总分是负分。就是这样的文章,不但跌出了第一页(这一页当中还有几个月前的文章),这个是热度排序算法的结果。我觉得这个结果比较糟糕,又移除了我的差评,但是这个文章并没有恢复到排名之中4

事实上,通过操作查询字符串,你可以发现一个奇怪的陷阱,糟糕的文章在莫名的角落缓慢地腐化5(译者:我猜作者的意思应该是让人讨厌的文章总数显示在显眼的地方)。下面的截图来自iphone版的subReddit这些不幸的文章。

这些文章是一些伤心的、害怕、孤独的文章。但是在显著位置,并且按时间顺序排列,就如预料的一样。

这个缺陷为一些故意破坏这个系统的人提供了一扇门。假设有一个subReddit,/r/BirdPics,投票给一些鸟类图片6。攻击者不喜欢海雀,并且希望把所有的海雀图片都驱逐出首页,这个攻击者可以对每一张海雀图片都给差评,不过这也可能被那些喜欢海雀的人给好评而消弱。平均来说,任何时刻查看首页的人的大概是350人,为了阻止这种恶意差评需要许多的评价较量。

不过,攻击者可以小心留意那些最近发布的图片,这个时候一旦有海雀图片被发布,攻击者立即给他一个差评。如果攻击者先投票,那么这篇文章总分就是一个差评并且会被逐出首页,在首页上再也看不到这篇文章。攻击者唯一需要担心的是有人会去查看最新排序文章列表,这里投票并不影响排序。我们假定350人中只有10人会去查看最新文章列表,因此攻击者只需用使用10个虚假账号来应对这些人,而不是需要近300个账号来对付首页上的所有人。就这样,攻击者可以清除subreddit上的所有海雀图片,这些海雀就再也没人注意。

 

补救措施

我不是第一个发现这个问题的人,Jonathan Rochkind在他的发表的一篇言辞详尽的话题中谈及了该问题。不过一位Reddit的开发者告诉他,他弄错了,当前的算法没有问题。

我在开发者社区发布了一篇请求修复该bug的文章,也被一个开发者告知,就是这样设计的。我不懂,也没有得到一个令人满意的解释,在何种意义上这种荒谬的行为将是“就是这样设计”的。但很明显,Reddit对解决这个问题不感兴趣,这一行为可能会持续许多年。

 

结局

程序员往往围绕着规则的一致性寻找公平正义。这也是为什么我们中的许多人发现世俗领域关系或政治如此棘手的,以及为什么我们中的许多人第一时间被计算机科学吸引。在计算机世界,一切都是严格确定的。如果发生了一些未定义的事情,那也只是因为我们对系统的理解不完整7。对于正确性,capital-R就是一个可理解的系统并且精确执行。

我们拥有这样的世界观,而一个明显的bug被散播看起来是不公正的。我和其他发现这个问题的开发者看起来对这个算法的理解比那些Reddit回应我们的员工更深入一些。对于这个没有被修补令人惊讶且违反直觉的行为,我们肯定是对的。我们是对的,而Reddit搞错了。因为Reddit是一个流行站点,并且拥有大量的用户,以及大量的现金。这些都建立在一个明显错误的组件之上。

这里的道德是什么?也许就是一个没有有效测试使得这个系统不能被理解,或者最终变为一个“可以工作,但是停止问问题”的系统。也许追求完美是好的一面的敌人,更糟反而更好8,这样的分歧使我远离喋喋不休的争吵9。也许好产品和好的技术实现存在一定的距离,而硬性的数据总是能保证正面的体验。

也许这没有道德,是Reddit搞砸了。这原本会伤及它自身,但是没有,也可能不会。他们错了,但是没有导致实际的错误,因为没有一个大写W Wrong。我们都应当编写有责任的代码,这里没有一个数学上帝可以有一天评判Reddit在做算法时的罪行。世界就是一个有缺陷的世界,曾经是,也一直都会如此。

 

脚注:

  1. 这个想法简单而有效,你可以根据这个算法构建不同的站点,但是使用不同的常量。如果你想要一个站点展现一些很旧的文章,可以将时间变量的权重调低。需要一个twitter站点,将vote变量的权重设置为0.
  2. 这个对数计算使得对Reddit的投票在权重上相差悬殊。1个投票和11个投票的差距比10001个投票和10011个投票的差距要大得多。
  3. 这个计算使得时间seconds的值很大,相对于order始终拥有更大的值。在Reddit的实现中是这样。
  4. 通过测试,我无法确定是投票统计的波动导致评分变化究竟发生了什么。我现在知道了,这个是一个投票混淆算法,有点类似反垃圾邮件功能。
  5. 我不能提供关于这个缺陷的持久化链接,这个索引好像一天后就会失效,不过这也容易找到。首先,查找最近负面评分的文章,记录下它的ID值,这个可以从URL中找到,比如:http://www.reddit.com/r/birdpics/comments/1s33tt/fear_the_shrike/,我们可以得到ID值1s33tt。然后,插入下面的链接,取代必要的部分:http://www.reddit.com/r/SUBREDDIT/?count=9999&after=t3_ID,。我们的URL会变成http://www.reddit.com/r/birdpics/?count=9999&after=t3_1s33tt。这里ID值被t3_前缀展开,然后你可以随意改变count值,这个值可以手动调节。
  6. 这个当然存在,见:链接
  7. 我怀疑,这也是为什么海森伯格测不准是计算机科学家最害怕也最讨厌的问题了。参见:释放Zalgo
  8. “糟糕反而更好”来自于Richard Gabriel关于研究C的兴起和Lisp的衰微的开创性文章。这篇文章和后续的一些续篇是关于计算科学迄今最好的一些文章。
  9. 你能猜出这些类比我是针对哪一个错误的吗?
收藏 2 评论

关于作者:周昌鸿

IT工作者,程序员,业余诗人,半宅男 (新浪微博:@双尾) 个人主页 · 我的文章 · 4

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部