像 Reddit、Hacker News 那样的特殊排序是如何实现的？

Question

想给自己的网站做一个热度排序，排序需要根据发帖时间t、帖子热度h综合判断f(t,h)，就像 Reddit 和 Hacker News 那样。如果每次请求都对整个数据库进行权值计算再进行排序有点太低效了。

现在仅能想到使用 Tricks：仅计算最近 1000 贴权值，然后将其缓存起来。（实际做起还会再考虑下细节，这里仅仅大概描述下意思）

Answer 1

你用“数据库”这个套子把自己装起来了，所以觉得这个问题很复杂。
的确，对于传统的关系型数据库而言，HackerNews的权重公式只能通过全表扫描来实现，对于MySQL甚至Oracle来说，几百万条记录足以让系统慢得像乌龟爬，但是你有没有想过如果不用关系型数据库呢？
首先，你不需要一个“完整”的顺序，因为用户看到的只有当前这一页，而且后端不一定只有一个“数据库”，向新闻这种相互之间没有关系的数据，很容易可以切分成许多小片，取出每个切片的topN再合并不是一个太耗时的操作。
其次，评分公式永远只是一个粗略估计，过于精确的值并没有太大意义，像(P-1)/(t+2)^G这种公式，你可以把它变成int(1000log(P)) - int(1000log(t+2)G))，其中int(1000log(P))、int(1000log(t+2)G))这种因子你可以事先穷举一个范围然后缓存起来，结合按照时间切片，你可以瞬间计算上千万个分数，完全不会拖慢服务。
对于新闻首页，你还可以缓存“顺序”，也就是说，每当有新的新闻产生或者有人投票时，重新计算比如前10页的新闻，因为绝大多数人其实不会往后翻太远，搜索之类特殊访问所占的比例也很低，所以缓存这个顺序就可以解决80~90%的PV，剩下的那一点点访问量再结合前面的作法就足够快了。

Answer 2

http://www.cnblogs.com/zhengyun_ustc/archive/2010/12/15/amir.html

善用百度、谷歌。

Answer 3

Redis中有一个 Sorted sets 类型， 很适合这种情景。

权重修改都放在Redis中，Sorted sets 的值为帖子的id或者其他唯一标识，数据库只做内容存储。

Sorted sets 命令足够满足你的上述需求。

Answer 4

原来是权重跟现在距离发帖时间的小时数有关，像这个吧：http://www.ruanyifeng.com/blog/2012/02/ranking_algorithm_hacker_news.html 。

我觉得这种只能每隔一小时计算一次，然后把结果缓存下来了。