千万条数据，Stack Overflow是如何实现快速分页的？

╰半橙微兮° 2022-05-25 00:08 155阅读 0赞

Stack Overflow 在分页机制中使用页码代替偏移量，页码指向基于 LIMIT 和 OFFSET 的查询。假设要对 1000 万条记录进行分页，跳到最后一页会非常慢，但 Stack Overflow 还是想办法实现了快速分页。

那么 Stack Overflow 是如何实现快速分页的呢？缓存热门查询并在应用程序代码中实现分页？还是使用了什么数据库黑魔法？

实际上，整个分页过程是非常复杂的。但我会尝试以一种简单的方式告诉你其中的原理，而不是写一个包含很多页内容的帖子。

假设

说到分页，基本上是围绕 pageNumber \* pageSize 而展开的。也就是说，要在已排好序的 n 条记录中获得当前的集合，可以将 pageNumber 乘以 pageSize，然后再加上 pageSize，就可以返回当前结果。在我们的例子中，它实际上是（pageNumber - 1）\* pageSize，因为页面 1 的索引是 0。

在排序问题上，我们不需要完全排序整个集合，而是对 pageNumber \* pageSize 条数据进行排序，这样就可以得到当前页面排好序的数据，而剩余部分可能只进行部分排序。与其排序整个集合并返回前 n 个结果，不如只对集合的前 n 个结果进行排序并返回这些结果。这样做很合理。

另外需要注意的是，最耗资源的查询总是那些中间页。获取最后 n 个页面与获得前 n 个页面一样容易：只需进行反向排序即可。比如，在按照日期降序排序时获取 pageNumber 1 与在按照日期升序排列时获取 pageNumber n-1 一样，都很容易。很多排序引擎（数据库、搜索引擎等）都使用了这种优化方式，我们也一样。

为了方便讨论，我们假定问题就是帖子，反之亦然，因为我会在文中交替使用这两个名词。

第 1 步：Tag Engine

我们有一个自己开发的.NET 应用程序，叫作 Tag Engine，它包含了帖子 ID 和元数据。我们把它看作是一个倒排索引，可以通过数据（如创建日期、标签、分数等）查找帖子 ID。

Tag Engine 主要负责基于某些限制条件做一些集合操作，比如它对一系列帖子 ID 集合进行交集、联合等操作，以便得到最终结果，并且还可以基于元数据在内存中进行排序。

我们使用 pageNumber 和 pageSize 以及一些限制条件（比如 Site ID，因为 Tag Engine 负责处理所有站点的查询）向 Tag Engine 发起查询。它在内存中进行集合操作（如联合和交集），然后对结果进行排序，返回相关的帖子 ID 子集。

Tag Engine 还会缓存查询结果（是集合，而不仅仅是请求的页面），并且可以根据由查询（页码、页面大小、排序方式等）哈希生成的缓存键从特定的缓存结果集中快速选择一个页面。这样极大提升了查询性能。

第 2 步：数据库

Tag Engine 不包含实际的数据，仅包含 ID 和元数据。因此，我们用帖子 ID 的结果集来查询数据库。查询看起来像这样：

Select p.*, pm.ViewCount, u.Id, u.ProfileImageUrl, ...
    
    From Posts p
    
    Join PostMetadata pm On p.Id = pm.PostId
    
    Left Join Users u On p.LastActivityUserId = u.Id
    
    Where p.Id In @Ids";

这里的 @Ids 是指 Tag Engine 中包含的 ID 列表。这个查询将返回实际的数据，但事情还没完。

步骤 3：半冗余的内存排序

如上所述，Tag Engine 可能会返回缓存的数据。然而，就其性质而言，缓存数据不能保证准确性（因为它们有可能是过去状态的快照）。相比之下，数据库始终具有最新的数据。

为了解决这个问题，我们在内存中再次对结果页面进行排序。

不过有一点比较让人头疼：最后一次内存排序基本上就是调用 List.Sort，并传进去一个排序函数。排序函数因用户查看不同的页面而有所不同：对于“Newest”页面，它会比较创建日期，而对于“Votes”，它会比较分数等。

如果我们没有做最后一步，帖子在页面上显示时可能会出现乱序，因为它们在 Tag Engine 中的排序反映的是过去的状态，而不是数据库的当前状态。

最后，我们把问题列表显示出来！

原文链接：https://meta.stackoverflow.com/questions/322164/how-does-stack-overflow-do-pagination