API 分頁探討：offset 來分頁真的有效率？

對(duì)于設(shè)計(jì)和實(shí)現(xiàn) API 來說，當(dāng)結(jié)果集包含成千上萬條記錄時(shí)，返回一個(gè)查詢的所有結(jié)果可能是一個(gè)挑戰(zhàn)，它給服務(wù)器、客戶端和網(wǎng)絡(luò)帶來了不必要的壓力，于是就有了分頁的功能。

通常我們通過一個(gè) offset 偏移量或者頁碼來進(jìn)行分頁，然后通過 API 實(shí)現(xiàn)類似請(qǐng)求：

GET?/api/products?page=10
{"items":?[...100?products]}

如果要繼續(xù)訪問后續(xù)數(shù)據(jù)，則修改分頁參數(shù)即可。

GET?/api/products?page=11
{"items":?[...another?100?products]}

在使用 offset 的情況下，通常使用 ?offset=1000 和 ?offset=1100 這種大家都熟悉的方法。它要么直接調(diào)用 OFFSET 1000 LIMIT 100 的 SQL 查詢數(shù)據(jù)庫，要么使用 LIMIT 乘以 page 作為查詢參數(shù)。

無論如何，「這是一個(gè)次優(yōu)的解決方案」，因?yàn)闊o論哪種數(shù)據(jù)庫都要跳過前面 offset 指定的 1000 行。而跳過額外的offset，不管是 PostgreSQL，ElasticSearch還是 MongoDB 都存在額外開銷，數(shù)據(jù)庫需要對(duì)它們進(jìn)行排序，計(jì)數(shù)，然后將前面不用的數(shù)據(jù)扔掉。

這是一種低效的方法，但由于它使用簡單，所以大家重復(fù)地用這個(gè)方法，也就是直接把 API 參數(shù)映射到數(shù)據(jù)庫查詢上。

那合適的方法是什么？介紹之前我們可以先看看數(shù)據(jù)庫的實(shí)現(xiàn)。在數(shù)據(jù)庫中有一個(gè)游標(biāo)（cursor）的概念，它是一個(gè)指向行的指針，然后可以告訴數(shù)據(jù)庫："在這個(gè)游標(biāo)之后返回 100 行"。這個(gè)指令對(duì)數(shù)據(jù)庫來說很容易，因?yàn)槟愫苡锌赡芡ㄟ^一個(gè)索引字段來識(shí)別這一行。然后就不需要去取和跳過前面那些沒用到的記錄了。

舉個(gè)例子。

GET?/api/products
{"items":?[...100?products],
?"cursor":?"qWe"}

API 返回一個(gè)無業(yè)務(wù)意義的字符串（游標(biāo)），你可以用它來檢索下一個(gè)頁面。

GET?/api/products?cursor=qWe
{"items":?[...100?products],
?"cursor":?"qWr"}

實(shí)現(xiàn)游標(biāo)有很多方法。一般來說，可以通過一些排序字段比如產(chǎn)品 id 來實(shí)現(xiàn)。在這種情況下，你可以用一些可逆算法對(duì)產(chǎn)品 id 進(jìn)行編碼。而在接收到一個(gè)帶有游標(biāo)的請(qǐng)求時(shí)，你會(huì)對(duì)它進(jìn)行解碼，并生成一個(gè)類似 WHERE id > :cursor LIMIT 100 的查詢。

下面是一個(gè)小小的性能對(duì)比，先看看 offset 是如何工作：

=#?explain?analyze?select?id?from?product?offset?10000?limit?100;
???????????????????????????????????????????????????????????QUERY?PLAN????????????????????????????????????????????????????????????
---------------------------------------------------------------------------------------------------------------------------------
?Limit??(cost=1114.26..1125.40?rows=100?width=4)?(actual?time=39.431..39.561?rows=100?loops=1)
???->??Seq?Scan?on?product??(cost=0.00..1274406.22?rows=11437243?width=4)?(actual?time=0.015..39.123?rows=10100?loops=1)
?Planning?Time:?0.117?ms
?Execution?Time:?39.589?ms

再看看 where (cursor) 語句如何工作：

=#?explain?analyze?select?id?from?product?where?id?>?10000?limit?100;
??????????????????????????????????????????????????????????QUERY?PLAN??????????????????????????????????????????????????????????
------------------------------------------------------------------------------------------------------------------------------
?Limit??(cost=0.00..11.40?rows=100?width=4)?(actual?time=0.016..0.067?rows=100?loops=1)
???->??Seq?Scan?on?product??(cost=0.00..1302999.32?rows=11429082?width=4)?(actual?time=0.015..0.052?rows=100?loops=1)
?????????Filter:?(id?>?10000)
?Planning?Time:?0.164?ms
?Execution?Time:?0.094?ms

這是幾個(gè)數(shù)量級(jí)的差異! 當(dāng)然，實(shí)際的差異取決于表的大小以及過濾器和存儲(chǔ)的實(shí)現(xiàn)。有一篇不錯(cuò)的文章 (1) 提供了更多的技術(shù)信息，里面有 ppt，性能比較見第 42 張幻燈片。

(1) https://use-the-index-luke.com/no-offset

當(dāng)然，用戶不會(huì)按 id 來檢索商品，而是會(huì)按一些相關(guān)性來查詢（然后按 id 作為關(guān)聯(lián)字段）。在現(xiàn)實(shí)世界中，需要根據(jù)你的業(yè)務(wù)來決定該怎么做。訂單可以按 id 排序（因?yàn)樗菃握{(diào)增加的）。購買清單可以按 wishlist 時(shí)間排序。在我們的案例中，產(chǎn)品來自 ElasticSearch，自然支持游標(biāo)的特性。

我們可以看到的一個(gè)不足是，使用無狀態(tài)的 API， 無法支持翻到“上一頁”這樣的功能。所以在面向用戶界面中，如果有 prev/next 或者 “直接進(jìn)入第10頁” 這樣的按鈕，就沒有辦法繞過前面提到的 offset/limit 這種實(shí)現(xiàn)。但是在其他情況下，使用基于游標(biāo)的分頁可以極大地提高性能，特別是在真正的大表和真正的深度分頁上。

英文原文：

https://solovyov.net/blog/2020/api-pagination-design/

HackerNews 評(píng)論：

https://news.ycombinator.com/item?id=25547716

HN網(wǎng)友 et1337：

使用游標(biāo)的另一個(gè)原因是避免由于并發(fā)編輯而導(dǎo)致元素重復(fù)或跳過的問題，比如你使用 offset 正在第 10 頁上，而有人在第 1 頁上刪除了一個(gè)項(xiàng)目，則整個(gè)列表會(huì)移動(dòng)，你可能會(huì)意外跳過第 11 頁上的一行數(shù)據(jù)。同樣，如果有人在第 1 頁上添加了一條記錄而你正在第 10 頁上，第 10 頁中的一項(xiàng)也會(huì)重復(fù)顯示在第 11 頁上。

游標(biāo)優(yōu)雅地回避了這些問題。

HN 網(wǎng)友 chrismorgan：

有時(shí)候，你需要一個(gè)游標(biāo)，這樣你就可以從你剛才的地方繼續(xù)前進(jìn)，而不用擔(dān)心新的記錄進(jìn)來擾亂你的分頁。

有時(shí)你想要基于位置的查詢，因?yàn)槟忝鞔_地希望所有的東西都是位置的。

有時(shí)你想把這兩種技術(shù)結(jié)合起來，例如，如果你跳到一個(gè)大的、不斷變化的列表中間，然后想在剛才的位置之后檢索下一批結(jié)果。

我喜歡 JMAP 最后的設(shè)計(jì)(https://tools.ietf.org/html/rfc8620#page-45)：你可以指定一個(gè)位置整數(shù)，或者一個(gè)錨 ID 和可選的 anchorOffset 整數(shù)。錨是游標(biāo)的一種實(shí)現(xiàn)，它使用結(jié)果集中一個(gè)實(shí)體 ID，而不是一個(gè)可以嵌入其他信息（比如 coroutine 地址）的不透明類型，，它有一個(gè)明顯的優(yōu)點(diǎn)，就是可以由客戶端控制。

HN 網(wǎng)友?vincnetas

我認(rèn)為作者在使用 OFFSET 時(shí)忽略了一些關(guān)鍵點(diǎn)。至少 postgres 文檔對(duì)此有明確的的說法（https://www.postgresql.org/docs/13/queries-limit.html）

When?using?LIMIT,?it?is?important?to?use?an?ORDER?BY?clause?that?constrains?the?result?rows?into?a?unique?order.?Otherwise?you?will?get?an?unpredictable?subset?of?the?query's?rows.?You?might?be?asking?for?the?tenth?through?twentieth?rows,?but?tenth?through?twentieth?in?what?ordering?

看起來作者提供的分頁查詢沒有考慮到排序，這意味著第 100 頁上的項(xiàng)目的 ID 大于 10000，但順序未定義。

explain?analyze?select?id?from?product?where?id?>?10000?limit?100

HN 網(wǎng)友 boulos

鑒于對(duì)“游標(biāo)”一詞的重用感到困惑，我更喜歡 Google 為分頁所使用的術(shù)語：頁面令牌和頁面大小，詳細(xì)可以參閱：

https://google.aip.dev/158