如何使用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中完成.

优点是您的数据库每半小时才被命中(对于昂贵的排名查询).缺点是您需要复制大量数据库.

Answer 1

我为视频聚合器实现了一个SQL版Reddit的排名算法,如下所示:

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 Hotness算法的更多信息

Answer 2

Reddit使用Pyrex,排序算法是Python C扩展,以提高性能.

因此,当记录更新时,您可以在SQL中执行相同操作,pex:何时投票为up或down.

您必须转换为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);
}

所以你必须在post表中存储ups,downs,date和hot函数结果.然后你可以在热门列中进行排序.

你可以在这里看到Reddit源代码:http://code.reddit.com/