主页 > 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 中的排序反映的是曩昔的状况,而不是数据库的当时状况。

终究,咱们把问题列表显现出来!


上一篇:MySQL 字符串截取相关函数总结
下一篇:MYSQL错误代码:1248 Every derived table must have its own alias 处理

PythonTab微信大众号:

Python技能交流合作群 ( 请勿加多个群 ):

群1: 87464755

群2: 333646237

群3: 318130924

群4: 385100854