轉(zhuǎn)載自?千萬條數(shù)據(jù)，Stack Overflow是如何實(shí)現(xiàn)快速分頁的

Stack Overflow 在分頁機(jī)制中使用頁碼代替偏移量，頁碼指向基于 LIMIT 和 OFFSET 的查詢。假設(shè)要對(duì) 1000 萬條記錄進(jìn)行分頁，跳到最后一頁會(huì)非常慢，但 Stack Overflow 還是想辦法實(shí)現(xiàn)了快速分頁。

那么 Stack Overflow 是如何實(shí)現(xiàn)快速分頁的呢？緩存熱門查詢并在應(yīng)用程序代碼中實(shí)現(xiàn)分頁？還是使用了什么數(shù)據(jù)庫黑魔法？

實(shí)際上，整個(gè)分頁過程是非常復(fù)雜的。但我會(huì)嘗試以一種簡單的方式告訴你其中的原理，而不是寫一個(gè)包含很多頁內(nèi)容的帖子。

假設(shè) ?

說到分頁，基本上是圍繞 pageNumber * pageSize 而展開的。也就是說，要在已排好序的 n 條記錄中獲得當(dāng)前的集合，可以將 pageNumber 乘以 pageSize，然后再加上 pageSize，就可以返回當(dāng)前結(jié)果。在我們的例子中，它實(shí)際上是（pageNumber - 1）* pageSize，因?yàn)轫撁?1 的索引是 0。

在排序問題上，我們不需要完全排序整個(gè)集合，而是對(duì) pageNumber * pageSize 條數(shù)據(jù)進(jìn)行排序，這樣就可以得到當(dāng)前頁面排好序的數(shù)據(jù)，而剩余部分可能只進(jìn)行部分排序。與其排序整個(gè)集合并返回前 n 個(gè)結(jié)果，不如只對(duì)集合的前 n 個(gè)結(jié)果進(jìn)行排序并返回這些結(jié)果。這樣做很合理。

另外需要注意的是，最耗資源的查詢總是那些中間頁。獲取最后 n 個(gè)頁面與獲得前 n 個(gè)頁面一樣容易：只需進(jìn)行反向排序即可。比如，在按照日期降序排序時(shí)獲取 pageNumber 1 與在按照日期升序排列時(shí)獲取 pageNumber n-1 一樣，都很容易。很多排序引擎（數(shù)據(jù)庫、搜索引擎等）都使用了這種優(yōu)化方式，我們也一樣。

為了方便討論，我們假定問題就是帖子，反之亦然，因?yàn)槲視?huì)在文中交替使用這兩個(gè)名詞。

第 1 步：Tag Engine

我們有一個(gè)自己開發(fā)的.NET 應(yīng)用程序，叫作 Tag Engine，它包含了帖子 ID 和元數(shù)據(jù)。我們把它看作是一個(gè)倒排索引，可以通過數(shù)據(jù)（如創(chuàng)建日期、標(biāo)簽、分?jǐn)?shù)等）查找帖子 ID。

Tag Engine 主要負(fù)責(zé)基于某些限制條件做一些集合操作，比如它對(duì)一系列帖子 ID 集合進(jìn)行交集、聯(lián)合等操作，以便得到最終結(jié)果，并且還可以基于元數(shù)據(jù)在內(nèi)存中進(jìn)行排序。

我們使用 pageNumber 和 pageSize 以及一些限制條件（比如 Site ID，因?yàn)?Tag Engine 負(fù)責(zé)處理所有站點(diǎn)的查詢）向 Tag Engine 發(fā)起查詢。它在內(nèi)存中進(jìn)行集合操作（如聯(lián)合和交集），然后對(duì)結(jié)果進(jìn)行排序，返回相關(guān)的帖子 ID 子集。

Tag Engine 還會(huì)緩存查詢結(jié)果（是集合，而不僅僅是請(qǐng)求的頁面），并且可以根據(jù)由查詢（頁碼、頁面大小、排序方式等）哈希生成的緩存鍵從特定的緩存結(jié)果集中快速選擇一個(gè)頁面。這樣極大提升了查詢性能。

第 2 步：數(shù)據(jù)庫

Tag Engine 不包含實(shí)際的數(shù)據(jù)，僅包含 ID 和元數(shù)據(jù)。因此，我們用帖子 ID 的結(jié)果集來查詢數(shù)據(jù)庫。查詢看起來像這樣：

Select p.*, pm.ViewCount, u.Id, u.ProfileImageUrl, ...From Posts pJoin PostMetadata pm On p.Id = pm.PostIdLeft Join Users u On p.LastActivityUserId = u.IdWhere p.Id In @Ids";

這里的 @Ids 是指 Tag Engine 中包含的 ID 列表。這個(gè)查詢將返回實(shí)際的數(shù)據(jù)，但事情還沒完。

步驟 3：半冗余的內(nèi)存排序

如上所述，Tag Engine 可能會(huì)返回緩存的數(shù)據(jù)。然而，就其性質(zhì)而言，緩存數(shù)據(jù)不能保證準(zhǔn)確性（因?yàn)樗鼈冇锌赡苁沁^去狀態(tài)的快照）。相比之下，數(shù)據(jù)庫始終具有最新的數(shù)據(jù)。

為了解決這個(gè)問題，我們在內(nèi)存中再次對(duì)結(jié)果頁面進(jìn)行排序。

不過有一點(diǎn)比較讓人頭疼：最后一次內(nèi)存排序基本上就是調(diào)用 List.Sort，并傳進(jìn)去一個(gè)排序函數(shù)。排序函數(shù)因用戶查看不同的頁面而有所不同：對(duì)于“Newest”頁面，它會(huì)比較創(chuàng)建日期，而對(duì)于“Votes”，它會(huì)比較分?jǐn)?shù)等。

如果我們沒有做最后一步，帖子在頁面上顯示時(shí)可能會(huì)出現(xiàn)亂序，因?yàn)樗鼈冊?Tag Engine 中的排序反映的是過去的狀態(tài)，而不是數(shù)據(jù)庫的當(dāng)前狀態(tài)。

最后，我們把問題列表顯示出來！

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

總結(jié)

以上是生活随笔為你收集整理的千万条数据，Stack Overflow是如何实现快速分页的的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。