StackOverflow 网站快速分页的“魔法”

21CTO社区导读：众所周知，Stack Overflow是一个全球知名的技术问答网站。它的每篇问题答案都很多，特别是浏览问题列表时，越往后翻页速度会越慢。Stack Overflow技术团队在内容分页上下了不少功夫，本篇就来看一看他们是怎样来处理的。

分页原理

和大部分网站的分页系统一样，StackOverflow的分页也使用了偏移量，重要的点包括LIMIT和OFFSET来进行查询。但是如果对10亿+条记录查询，如果要翻到最后一页，将会变得异常缓慢。但是如今的StackOverflow网站问题列表却处理得很快。

那么，StackOverflow是怎样让分页做得如此快？是在代码中对经常查询的查询分页用了缓存？是在数据库中使用了“黑魔法”？

和任何实际的技术实践一样，分页过程是有一定的复杂度的。我们尝试用一种简单方式来说明其中的原理，而不是来写一个包含很多页内容的帖子。

一个假设

提到分页，无论是用什么数据库：MySQL、Oracle还是MS SQL Server，都是围绕pageNumber * pageSize这个公式展开的。也就是在已经排序了的n条记录中获得当前的记录集合，将pageNumber * pageSize，然后再加上pageSize，然后就会返回当前页码的结果。在我们的例子中，它实际上是（pageNumber - 1）*pageSize的结果，因为第一页的索引值是从0开始编号的。

在排序这个问题上，程序员无需完全排序整个数据集合，而是对 pageNumber*pageSize 数据集进行排序，如此就可以得到当前页已经排好顺序的数据，余下的只作部分排序。

将整个数据集合排序并返回前n条结果，不如只对集合的前n条进行排序并返回这些结果集。实践证明，这样做是最合理的。

此外需要大家注意的是，最消耗资源的查询（query）是那些中间页。取得最后N个页面与获得前N个页面一样方便：只需进行反向排序就可以。例如，按照日期排序获取 pageNumber+1 与在按照日期升序排列时获取 pageNumber n-1是相同，都很容易 。很多基于排序的引擎，比如数据库、搜索引擎等都使用了此种优化方式，StackOverflow网站也是如此。

下面我们就开始讨论这个话题，为了方便描述，我们假设问题就是帖子，反之亦是如此。我们会在文中交替使用这两个名词。

第一步：Tag Engine（标签引擎）

StackOverflow 有一个自己开发的.NET应用程序。这个应用程序会获得岾子Id和meta元数据。我们可以把它看作是一个倒排索引，通过创建日期、tag标签、分数等数据能够查找到帖子的ID。这个应用，StackOverflow技术团队将其命名为：Tag Engine。

Tag Engine主要基于某些限制条件做一些集合操作。比如它对一组帖子ID集合进行交集、JOIN 联合查询等操作，从而得到最终结果，另外它还可以基于meta data在内存中进行排序。

Tag Engine还会缓存查询结果，这些结果是数据集，而不仅仅是请求的页面。Tag Engine还可以根据查询类型，如页码（pageNumber）、页面尺寸（pageSize）和排序方式等哈希key并缓存下来，这样有外部查询时就会从特定的缓存结果集中快速返回一个结果页面，从而能够大大提升查询之性能。

第二步：数据库（Database）

Tag Engine并不包含实际的数据实体，只包含贴子ID和Meta元数据。因此，我们用帖子ID的结果集来与数据库联合查询。这样就好玩多了，SQL查询看起来像这样：

SELECT p.*,pm.ViewCount,u.Id,u.ProfileImageUrl,...

FROM Posts p

JOIN PostMetadata pm On p.Id = pm.PostId

LETF JOIN Users u On p.LastActivityUserId = u.Id

WHERE p.Id IN @Ids";

说明一下，这里的@Ids 指的是Tag Engine中包含的ID列表。这个查询将返回实际的数据，故事还没有讲完。

第三步：半冗余的内存排序

如前面我们所述，Tag Engine可能返回的是缓存数据。但是缓存的问题也出现了，它并不能保证是最新最准确的数据，很有可能是过去一段时间的状态快照。

因此，数据库中的内容始终是最新鲜的数据，也是最靠谱真实的数据。

针对此问题的解决，我们需要在内存中对结果页面进行再次排序。

有一点会让人感觉到麻烦：最后一次的内存排序基本上就是调用List.Sort，并传递进去一个排序函数。排序函数因用户查看不同的页面而有所不同：

对于最新的Newest页面，会比较创建的日期，而对于投票数，它会比较分数等。

如果我们还没有做最后一步，帖子在页面上的显示就有可能出现混乱排序的情况。这是因为它们在Tag Engine中的排序是过去一段时间的状态，并不是数据库中的当前状态。

最后，我们将StackOverflow的问题列表页显示给用户。

作者：Haney

译者：洛逸

地址：https://meta.stackoverflow.com/questions/322164/how-does-stack-overflow-do=pagination