在排序问题上,我们不需要完全排序整个集合,而是对 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 列表。这个查询将返回实际的数据,但事情还没完。
千万条数据,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 的结果集来查询数据库。查询看起来像这样:
这里的 @Ids 是指 Tag Engine 中包含的 ID 列表。这个查询将返回实际的数据,但事情还没完。
步骤 3:半冗余的内存排序
如上所述,Tag Engine 可能会返回缓存的数据。然而,就其性质而言,缓存数据不能保证准确性(因为它们有可能是过去状态的快照)。相比之下,数据库始终具有最新的数据。
为了解决这个问题,我们在内存中再次对结果页面进行排序。
不过有一点比较让人头疼:最后一次内存排序基本上就是调用 List.Sort,并传进去一个排序函数。排序函数因用户查看不同的页面而有所不同:对于“Newest”页面,它会比较创建日期,而对于“Votes”,它会比较分数等。
如果我们没有做最后一步,帖子在页面上显示时可能会出现乱序,因为它们在 Tag Engine 中的排序反映的是过去的状态,而不是数据库的当前状态。
最后,我们把问题列表显示出来!
来自:聊聊架构