分庫分表後，如何優雅的實現高效分頁查詢？

分庫分表的一般做法

一般會使用三種算法：

哈希分庫分表： 根據分庫分表鍵算出一個哈希值，根據這個哈希值選擇一個數據庫。最常見的就是數字類型的字段作爲分庫分表鍵，然後取餘。比如在訂單表裏，可以按照買家的 ID 除以 8 的餘數進行分表

範圍分庫分表： 將某個數據按照範圍大小進行分段。比如說根據 ID，[0,1000)在一張表，[1000,2000)在另外一張表。最常見的應該是按照日期進行分庫分表，比如每個月一張表

中間表： 引入一箇中間表來記錄數據所在的目標表。一般是記錄主鍵到目標表的映射關係。

這三者並不互斥，也就是說可以考慮使用哈希分庫分表，同時引入一箇中間表；也可以先進行範圍分庫分表，再引入一箇中間表。

分庫分表中間件的形態

SDK 形態： 通過依賴的形式引入代碼裏，比如 Java 的依賴 ShardingSphere

Proxy 形態： 獨立部署的分庫分表中間件，對於所有的業務方來說，就像一個普通的數據庫，業務方的查詢發送過去後，就會執行分庫分表，發起實際的查詢，再把查詢結果返回給業務方。ShardingSphere 也支持這種形態。

Sidecar 形態： 提供了一個分庫分表的 Sidecar，但是現在並沒有非常成熟的產品

Sidecar 是一種分庫分表中間件的形態。它是一個理論上的概念，指的是一個獨立的組件，爲應用程序提供分庫分表的功能。在這種形態下，Sidecar 作爲應用程序的伴隨服務運行，類似於服務網格中的 Sidecar 容器，它與應用程序實例部署在一起，但作爲獨立的進程運行。

其中，SDK 形態的性能最好，但是和語言強耦合。

Proxy 形態性能最差，因爲所有的數據庫查詢都發送給它了，很容易成功性能瓶頸。尤其單機部署 Proxy 的話，還面臨着單節點故障的問題。優點是跟編程語言無關，部署一個 Proxy 之後可以給使用不同編程語言的業務使用。同時，業務方可以輕易地從單庫單表切換到分庫分表。

Sidecar 目前還沒有成熟的產品，但是從架構上來說它的性能應該介於 SDK 和 Proxy 之間，並且也沒有單體故障、集羣管理等煩惱。

面試準備

還需要弄清楚幾個問題：

• 公司是如何解決分庫分表中的分頁問題的？

• 有沒有因爲排序或分頁而引起的性能問題？最終怎麼解決的

還可以去看看公司的監控數據，注意下分頁查詢的響應時間。並且在業務高峯期或是頻繁執行分頁的時候，看看內存和 CPU 的使用率。這些數據可以作爲分頁查詢比較引起性能問題的證據。

面試策略上來說，最好把分頁查詢優化作爲你性能優化的一個舉措，可以進一步和前面的查詢優化、數據庫參數優化相結合，這樣方案會更完善，能力會更全面。

如果面試官問到了數據庫性能優化和數據庫分頁查詢，你都可以嘗試把話題引導到分頁查詢上。

基本思路

可以嘗試介紹一下是如何優化數據庫性能的，比如 SQL 本身優化、數據庫優化，然後羅列出準備的 SQL 案例，說明你在 SQL 優化方面做過哪些事情，比如優化過分庫分表的查詢，其中最典型的就是優化分頁查詢。

假設之前是全局查詢，現在採用禁用跨頁查詢的方案來優化

最開始我在公司監控慢查詢的時候，發現有一個分頁查詢非常慢。這個分頁查詢是按照更新時間降序來排序的。後來我發現那個分頁查詢用的是全局查詢法，因爲這個接口原本是提供給 Web 端用的，而 Web 端要支持跨頁查詢，所以只能使用全局查詢法。當查詢的頁數靠後的時候，響應時間就非常長。後來我們公司搞出 App 之後，類似的場景直接複用了這個接口。但是事實上在 App 上是沒有跨頁需求的。所以我就直接寫了一個新接口，這個接口要求分頁的時候帶上上一頁的最後一條數據的更新時間。也就是我用這個更新時間構造了一個查詢條件，只查詢早於這個時間的數據。那麼分頁查詢的時候 OFFSET 就永遠被我控制在 0 了，查詢的時間就非常穩定了。

最後你可以加一個總結。

分頁查詢在分庫分表裏面是一個很難處理的問題，要麼查詢可能有性能問題，比如說這裏使用的全局查詢法，要麼就是要求業務折中，比如說我優化後禁用了跨頁，以及要求數據平均分佈的平均分頁法，當然還有各方面都不錯，但是實現比較複雜的二次查詢法、中間表法。

當面試官追問你其中細節的時候，你就可以這樣來引導。

全局查詢

理論上說，分頁查詢要在全局有序的情況下進行，但是在分庫分表以後，要做到全局有序就很難了。假如說我們的數據庫order_tab是以buyer_id % 2來進行分表的，如果你要執行一個語句

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 2

實際執行查詢的時候，就要考慮各種數據的分佈情況。

符合條件的數據全部在某個表裏面。在這就是order_tab_0上有全部數據，或是order_tab_1上有全部數據。

偏移量中前面兩條全部在一張表，但是符合條件的數據在另外一張表

偏移量和數據在兩張表都有

在分庫分表中，一個 SELECT 語句生成的目標語句是這樣的：

SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0
SELECT * FROM order_tab ORDER BY id LIMIT 6 OFFSET 0

注意看 LIMIT 部分，被修改成了 0,6。通俗的說，如果一個分頁語句是 LIMIT x OFFSET y 的形式，那麼最終生成的目標語句就是 LIMIT x + y OFFSET 0。

LIMIT x OFFSET y => LIMIT x+y OFFSET 0

當分庫分表中間件拿到這兩個語句的查詢結果之後，就要在內存裏進行排序，再找出全局的LIMIT 4 OFFSET 2

可以先回答這種全局排序的思路，關鍵詞就是 LIMIT x + y OFFSET 0

分庫分表中間件一般採用的就是全局排序法。假如說我們要查詢的是 LIMIT X OFFSET y，那麼分庫分表中間件會把查詢改寫爲 LIMIT x+y OFFSET 0，然後把查詢請求發送給所有的目標表。在拿到所有的返回值後，在內存中排序，然後根據排序結果找出全局符合條件的目標數據。

接下來可以先從性能問題上刷一個亮點，抓住受影響的三個方面：網絡、內存和 CPU

這個解決方案的最大問題就是性能不好。

首先是網絡傳輸瓶頸，比如在LIMIT 10 OFFSET 1000這種場景下，如果沒有分庫分表，只需要傳輸 10 條數據；在分庫分表的情況下，如果命中了 N 個表，那麼需要傳輸的是(1000+10)*N條數據。而實際上最終我們只會用其中的 10 條數據，存在巨大的浪費。

其次是內存瓶頸。收到那麼多數據之後，中間件需要維持在內存中排序。

CPU 也會成爲瓶頸，因爲排序本身是一個 CPU 密集的操作。所以在 Proxy 形態的分庫分表中間件裏，分頁查詢一多，就容易把中間件的內存耗盡，引發 OOM，又或是 CPU 100%。

不過可以通過歸併排序來緩解這些問題。

關鍵在拿到數據之後，使用歸併排序的算法。

在分庫分表裏，可以使用歸併排序算法來給返回的結果排序，也就是說在改寫爲LIMIT x+y OFFSET 0之後，每個目標表返回的結果都是有序的，自然可以使用歸併排序。在歸併排序的過程中，我們可以逐條從返回結果中讀取，這意味着沒必要將所有的結果一次性放到內存中再排序。在分頁的場景下，取夠了數據可以直接返回，剩下的數據就可以丟棄了。

前面說了全局查詢這個方案的性能很差，那麼有沒有其他方案呢？

的確有，比如平均分頁、禁用跨頁查詢、換用其他中間件等。不過任何方案都不是十全十美的，這些方案也存在一些難點，有的是需要業務折中，有的處理過程非常複雜。我們先來看第一個需要業務折中的平均分頁方案

優化方案 1：平均分頁

看到分頁查詢的第一個念頭應該是：能不能在不同的表上平均分頁查詢數據，得到的結果合併在一起就是分頁的結果

例如，查詢中的語句是這樣的

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 2

因爲本身有兩張表，可以改成這樣

SELECT * FROM order_tab_0 ORDER BY id LIMIT 2 OFFSET 1
SELECT * FROM order_tab_1 ORDER BY id LIMIT 2 OFFSET 1

在每一張表都查詢從偏移量 1 開始的 2 條數據，那麼合併在一起就可以認爲從全局的偏移量 2 開始的 4 條數據。

圖裏我們能夠看出來，按照道理全局的 LIMIT 4 OFFSET 2 拿到的應該是 3、4、5、6 四條數據。但是這裏我們拿到的數據卻是 2、4、5、9。這也就是這個方案的缺陷：它存在精度問題。也就是說，它返回的數據並不一定是全局最精確的數據

那麼這個方案是不是就不能用了呢？並不是的，在一些對順序、精度要求不嚴格的場景下，還是可以用的。例如瀏覽頁面，你只需要返回足夠多的數據行，但是這些數據具體來自哪些表，用戶並不關心。

關鍵詞就是平均分頁

在一些可以接受分頁結果不精確的場景下，可以考慮平均分頁的做法。舉個例子來說，如果查詢的是 LIMIT 4 OFFSET 2，並且命中了兩張目標表，那麼就可以考慮在每個表上都查詢 LIMIT 2 OFFSET 1。這些結果合併在一起就是 LIMIT 4 OFFSET 2 的一個近似答案。這種做法對於數據分佈均勻的分庫分表效果很好，偏差也不大。

這個方案還有一個進階版本，就是根據數據分佈來決定如何取數據。

更加通用的做法是根據數據分佈來決定分頁在不同的表上各自取多少條數據。比如說一張表上面有 70% 的數據，但是另一張表上只有 30% 的數據，那麼在 LIMIT 10 OFFSET 100 的場景下，可以在 70% 的表裏取 LIMIT 7 OFFSET 70，在 30% 的表裏取 LIMIT 3 OFFSET 30。所以，也可以把前面平均分配的方案看作是各取 50% 的特例

那如何知道一張表上有 70% 的數據，另外一張表上有 30%。

在開發的時候先用 SQL 在不同的表上執行一下，看看同樣的 WHERE 條件下各自返回了多少數據，就可以推斷出來了。

不過實際上，能夠接受不精確的業務場景還是比較少的。所以我們還有一種業務折中的解決方案，它精確並且高效，也就是禁用跨頁查詢方案。

優化方案 2：禁用跨頁查詢

只允許用戶從第 0 頁開始，逐頁往後翻，不允許跨頁。

假如業務上分頁查詢是 50 條數據一頁，那麼發起的查詢依次是：

SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 0
SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 50
SELECT * FROM order_tab ORDER BY id LIMIT 50 OFFSET 100
...

不斷增長的只有偏移量，如何控制住這個偏移量呢？

答案是根據ORDER BY的部分來增加一個查詢條件。上述例子裏的order by是根據 id 升序排序的，只需要在 where 部分增加一個大於上次查詢的最大 id 的條件就可以了。max_id 是上一批次的最大 id

SELECT * FROM order_tab WHERE `id` > max_id ORDER BY id LIMIT 50 OFFSET 0

即使order by裏使用了多個列，規則也是一樣的

總體來看，回答要分成兩部分，第一部分介紹基本做法，關鍵詞是拿到上一批次的極值。

目前比較好的分頁做法是禁用跨頁查詢，然後在每一次查詢條件里加上上依次查詢的極值，也就是最大值或者最小值。比如說第一次查詢的時候ORDER BY ID LIMIT 10 OFFSET 0，那麼下一頁就可以改爲WHERE id > max_id ORDER BY ID LIMIT 10 OFFSET 0。在現在的手機 App 裏這個策略是非常好用的，因爲手機 App 都是下拉刷新，天然就不存在跨頁的問題。

第一部分提到了極值，面試官可能問你什麼時候用最大值，什麼時候用最小值，可以這樣說：

至於用最大值還是最小值，取決於 order by。總的原則就是升序用最大值，降序用最小值。如果 order by 裏面包含了多個列，那麼針對每一個列是升序還是降序，來確定使用最大值還是最小值。

這種方案並沒有徹底解決分庫分表查詢中的分頁問題，但是控制了偏移量，極大的減少了網絡通信的消耗和磁盤掃描的消耗。

優化方案 3：換用中間件

一種思路是使用 NoSQL 之類的來存儲數據，比如使用 Elasticsearch、ClickHouse；另一種思路是使用分佈式關係型數據庫，相當於把分頁的難題拋給了數據庫

優化方案 4：二次查詢（亮點）

先嚐試獲取某個數據的全局偏移量，再根據這個偏移量來計算剩下數據的偏移量。這裏用一個例子來闡述它的基本原理，再抽象出一般步驟。

假設我們的查詢是

SELECT * FROM order_tab ORDER BY id LIMIT 4 OFFSET 4

數據分佈如圖所示：

全局的LIMIT 4 OFFSET 4 是 5、6、7、8 四條數據

步驟 1：首次查詢

把 SQL 語句改寫成這樣：

SELECT * FROM order_tab_0 ORDER BY id LIMIT 4 OFFSET 2
SELECT * FROM order_tab_1 ORDER BY id LIMIT 4 OFFSET 2

我們只是把 OFFSET 平均分配了，但是 LIMIT 沒變

第一次查詢到的數據是這樣

order_tab_0 拿到了 4、6、10、12，而 order_tab_1 拿到了 7、8、9、11

步驟二：確認最小值

id 最小的是 4，來自order_tab_0

步驟三：二次查詢

這一次查詢需要利用上一步找出來的最小值以及各自分庫的最大值來構造 BETWEEN 查詢，改寫得到的 SQL 是：

SELECT * FROM order_tab_0 WHERE id BETWEEN 4 AND 12
SELECT * FROM order_tab_1 WHERE id BETWEEN 4 AND 11

結果：

• order_tab_0 返回 4、6、10、12。

• order_tab_1 返回 5、7、8、9、11，也就是多了 1 條數據，記住這一點。

取過來的所有數據排序之後就是 4、5、6、7、8、9、10、11、12

步驟四：計算最小值的全局偏移量

核心是：根據 BETWEEN 中多出來的數據量來推斷全局偏移量

現在我們知道 4 在order_tab_0中的偏移量是 2，也就是說比 4 小的數據有 2 條。

在 BETWEEN 查詢裏，order_tab_1返回的結果是 5,7,8,9,11，其中 7 在第一次查詢裏的偏移量是 2，所以 5 的偏移量是 1。也就是說，5 的前面只有一條比 4 小的數據。

那麼 4 在order_tab中的全局偏移量就是 1+2=3，也就是 4 前面有三條數據。

加上 4 本身，剛好構成了 OFFSET 4，因此從 5 開始取，往後取 4 條數據。

總結

簡化版本：

• 首次查詢，拿到最小值

• 二次查詢，確實最小值的全局偏移量

• 在二次查詢的結果里根據最小值取到符合偏移量的數據

抽象版本：

假設分庫分表共有 n 個表，查詢是LIMIT X OFFSET Y，那麼：

• 首先發送查詢語句 LIMIT X OFFSET Y/N 到所有的表

• 找到返回結果中的最小值（升序），記作 min

• 執行第二次查詢，關鍵是BETWEEN min AND max，其中 max 是第一次查詢的數據中每個表各自的最大值

• 根據 min、第一次查詢和第二次查詢的值來確定 min 的全局偏移量。總的來說，min 在某個表裏的偏移量這樣計算：如果第二次查詢比第一次查詢多了 K 條數據，偏移量就是 Y/N-K。然後把所有表的偏移量加在一起，就是 min 的全局偏移量

• 根據 min 的全局偏移量，在第二次查詢的結果裏面向後補足到 Y，得到第一條數據的位置，再取 X 條。

優化方案 5：引入中間表（亮點）

引入中間表的意思是額外存儲一份數據，只用來排序。這個方案裏面就是在中間表裏加上排序相關的列。

排序是一個非常常見的需求，那麼就可以考慮引入一箇中間表來輔助排序。比如說用更新時間來排序的時候，在中間表裏加上更新時間。查詢的時候先在中間表裏查到目標數據，再去目標表裏把全部數據都查詢出來。

有兩個明顯的缺陷：一是 WHERE 只能使用中間表上的列；二是維護中間表也會引起數據一致性問題。

那麼如何解決數據一致性問題呢？

比較簡單的做法就是業務保持雙寫，也就是寫入目標表也寫入中間表。不過這裏我更加建議使用 Canal 之類的框架來監聽 binlog，異步更新中間表。這樣做的好處是業務完全沒有感知，沒有什麼改造成本。更新的時候可以考慮引入重試機制，進一步降低失敗的幾率。

面試官可能進一步問你，如果更新中間表經過重試之後也失敗了，怎麼辦？

這時候並沒有更好的辦法，無非就是引入告警，然後人工介入處理。最後你可以再總結一下這個方案。

這個方案是一個依賴最終一致性的方案，在強調強一致性的場景下並不是很合適。

作者：LightOf_

來源：blog.csdn.net/LightOfNight/article/details/140475154

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/55It_L74_MhNA2iDx-HdRQ