首页 > MySQL教程 > 正文

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

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 中的排序反映的是过去的状态,而不是数据库的当前状态。

最后,我们把问题列表显示出来!


PythonTab微信公众号:

Python技术交流互助群 ( 请勿加多个群 ):

群1: 87464755

群2: 333646237

群3: 318130924

群4: 385100854

相关词搜索:分页

上一篇:MySQL 字符串截取相关函数总结
下一篇:最后一页