Reddit和Hacker News的排名算法是如何使用的？

Question

最近我一直在研究排名算法，特别是Reddit和Hacker News使用的算法。这些算法本身很简单，但我不太明白它们是如何被使用的。

我可以做的一件事是直接在SQL中实现该算法，这样每次用户访问显示排名帖子的页面时，会运行类似以下代码：

SELECT thing1, thing2 FROM table
ORDER BY ranking_algorithm DESC
LIMIT page*20, 20

在SO上有几个类似的问题，但唯一给出的答案是将排名算法放入SQL查询中。然后线程就死了...

把算法放到SQL查询中在小规模上是没问题的，但如果网站有大量用户和大量帖子呢？这意味着每当任何用户打开显示排名帖子的页面时，都会运行该查询。这肯定不够有效率。

现在，Reddit和Hacker News并没有在SQL查询中运行它们的排名算法，而是分别使用Python和Ark。那么它们究竟是如何使用的？

一个可能的解决方案是从每篇文章中获取所有相关信息，并将其存储在Web服务器上的某个数据结构中。然后对该数据结构进行排名和排序。

每次有人打开显示排名帖子的页面时，您只需访问数据结构，检索正确范围的帖子，并显示它们。

然后，每隔半小时左右，您就可以从服务器检索最新的信息，对其进行排名、排序并更新数据结构。

其他较少消耗资源的查询，比如检索并显示特定帖子的所有信息，或者显示最新的帖子（而不是最佳评分），可以在每次打开相关页面时使用SQL完成。

优点是您的数据库仅在每半小时进行一次昂贵的排名查询。缺点是您需要有大量数据库副本。

- Morglor

Answer 1

我为一个视频聚合网站实现了一个类似于Reddit排名算法的SQL版本，如下：

SELECT id, title
FROM videos
ORDER BY 
    LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total)   
    + (UNIX_TIMESTAMP(created_at) / 300000) DESC
LIMIT 50

cached_votes_total是一个触发器在每次新增投票时更新的。它在我们当前的网站上运行得足够快，但我计划添加一个排名值列，并使用相同的触发器更新它，就像更新cached_votes_total列一样。经过这种优化后，对于大多数规模的网站来说，速度应该已经足够快了。

编辑：更多信息请参见SQL Reddit 热度算法

- Chris Broski

---

如果有人想了解更多信息（以及更好的代码），我写了一篇关于SQL热度排名的博客。链接在这里：http://blog.glocal.com/2012/12/tuning-your-own-reddit-style-ranking.html - Chris Broski

我的博客文章链接已经失效，所以我稍作编辑并将其移至此处：SQL中的Reddit热度算法。 - Chris Broski

你的帖子链接已经失效了，有没有其他地方可以找到备份？ - Alex Booker

@Petrichor，我刚刚迁移了服务器，看起来我的设置没有正确传播。请尝试访问此链接：http://restfulmvc.com/reddit-algorithm.shtml - Chris Broski

Answer 2

Reddit使用Pyrex，该排序算法是Python C扩展，以提高性能。

因此，在SQL中，当记录被更新时，您可以执行相同的操作，例如：当进行点赞或踩票时。

您需要将以下伪代码翻译为您的SQL引擎语法：

function hot(ups, downs, date){
    score = ups - downs;
    order = log(max(abs(score), 1), 10);
    if (score>0){
        sign = 1;
    } else {
        if (score<0){
            sign = -1;
        } else {
            sign = 0;
        }
    }
    td = date - datetime(1970,1,1);
    seconds = td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000) - 1134028003;

    return round(order + sign * seconds / 45000, 7);
}

因此，您必须在帖子表中存储点赞数、踩数、日期和热度函数结果。然后，您可以按照热度列进行排序。

您可以在此处查看Reddit源代码：http://code.reddit.com/

- Andrés Morales

---

s是什么？我在代码片段中没有看到它被定义。 - Sebastian Hoitz

那么你的答案是在有踩/顶操作时运行该函数吗？Hotscore 是时间的函数，即使没有投票，分数也会改变。 - Ced

你是在谈论Hacker News算法吗？在Reddit算法中，随着时间的推移，分数不会减少，但新的故事将比旧的故事获得更高的分数。 - Andrés Morales

@Kijote，如果您在开头提到我的名字并通知我，那么您的评论可能会为我节省很多工作。出于某种原因，我认为他们git中的日期是Java System.currentTimeMilli()的Python等效项。无论如何，谢谢。顺便说一句（我知道这有点宽泛），您更喜欢Reddit算法还是Hacker's News？ - Ced

@Ced 抱歉没回。我还没有分析过 Hacker News 的算法，但我猜想它会多次进行计算。如果我没错的话，我认为像 Reddit 算法一样仅计算一次评分更好（只有一个数据库记录受到影响，而不是多次更新）。再次声明，这只是我的猜测，我还没有分析那个源代码。 - Andrés Morales