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

栏目: IT资讯 · 发布时间: 5年前

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

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

来自:聊聊架构


【声明】文章转载自:开源中国社区 [http://www.oschina.net]


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

支持向量机

支持向量机

邓乃扬、田英杰 / 科学出版社 / 2009-8 / 48.00元

《支持向量机:理论、算法与拓展》以分类问题(模式识别、判别分析)和回归问题为背景,介绍支持向量机的基本理论、方法和应用。特别强调对所讨论的问题和处理方法的实质进行直观的解释和说明,因此具有很强的可读性。为使具有一般高等数学知识的读者能够顺利阅读,书中首先介绍了最优化的基础知识。《支持向量机:理论、算法与拓展》可作为理工类、管理学等专业的高年级本科生、研究生和教师的教材或教学参考书,也可供相关领域的......一起来看看 《支持向量机》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具