面試官：MySQL 跨庫分頁、分表分頁之后，面臨的一些新問題

當(dāng)業(yè)務(wù)數(shù)據(jù)達(dá)到一定量級(jí)(比如：mysql單表記錄量 > 1千萬)后，通常會(huì)考慮“分庫分表”將數(shù)據(jù)分散到不同的庫或表中，這樣可以大大提高讀/寫性能。但是問題來了，對(duì)于select * from table limit offset , pagesize這種分頁方式，原來一條語句就可以簡單搞定的事情會(huì)變得很復(fù)雜，本文將與大家一起探討分庫分表后"分頁"面臨的新問題。

分表對(duì)分頁的影響

比如有一張表，里面有8條記錄(為簡單起見，假設(shè)該表上只有 1 個(gè)自增 ID），數(shù)學(xué)上可以抽象成 1 個(gè)(有序)數(shù)列(注：為方便討論，不加特殊說明的情況下，文本中數(shù)列的順序，均指升序)。

(1，2，3，4，5，6，7，8)

如果要取出上面紅色標(biāo)識(shí)的 2,3 這二條記錄，limit 1,2 就行了。

現(xiàn)在假如分成 2 張表（即：原來的數(shù)列，拆分成2個(gè)非空子數(shù)列），一般來講，有二種常用分法：

分段法

分段法（比如：有時(shí)間屬性的數(shù)據(jù)，類似訂單這種，可以按下單時(shí)間拆分，每個(gè)月1張表）

(1，2，3，4)

(5，6，7，8)

沿用之前的 limit x,y 的思路，每個(gè)分表上 limit 1,2，會(huì)得到如下 2 個(gè)子數(shù)列：

(2，3)

(6，7)

然后在內(nèi)存中合并排序，再取前 2 條(2，3，6，7) => (2，3)，貌似看上去也符合預(yù)期（這個(gè)思路也稱為歸并），但這只是假象。當(dāng)要取的分頁數(shù)據(jù)落在不同的子數(shù)列上時(shí)，就能發(fā)現(xiàn)問題：

(1，2，3，4，5，6，7，8)比如，我們要從 4 個(gè)位置開始，連續(xù)取2個(gè)元素，即: limit 3,2

(1，2，3，4)?=> limit 3,2?=>(4)

(5，6，7，8)?=> limit 3,2 =>(8)

最后合并出來的結(jié)果是(4，8) 與正確結(jié)果 (4，5)相比，顯然不對(duì)。

1.2 模余均攤法（比如：字段值對(duì)2取模求余數(shù)，根據(jù)余數(shù)決定分到哪個(gè)表，該方法也簡稱為取余法）

(1，3，5，7)

(2，4，6，8)

歸并排序的思路在分段法上行不通，對(duì)于取模均攤同樣也不行，仍以 limit 1,2為例，原始序列取出來的結(jié)果是(2，3)，如果用歸并的思路：

(1，3，5，7)=> limit 1,2 =>(3 ,5)

(2，4，6，8)=> limit 1,2 =>(4, 6)

內(nèi)存合并排序后，取前 2 個(gè)，最終結(jié)果為(3 , 4)

結(jié)論：不管分庫分表采用什么分法，簡單歸并的思路，都無法正確解決分頁問題。

全局法(limit x+y)

反思一下剛才的歸并思路，本質(zhì)上我們在每個(gè)子數(shù)列（即：分表）上limit x,y 時(shí)，取出來的數(shù)據(jù)就有可能已經(jīng)產(chǎn)生缺失了。這里提出了一個(gè)方案：把范圍擴(kuò)大，分表 sql 上的limit x,y變成limit 0, x+y，這樣改寫后，相當(dāng)于分表中把"每頁最后一條數(shù)據(jù)"之前的所有數(shù)據(jù)全都取出來了（當(dāng)然：這里面可能會(huì)有不需要的多余數(shù)據(jù))，然后內(nèi)存中合并在一起，再取 x 偏移量后的 y 條數(shù)據(jù)。

用前面的例子驗(yàn)證一下：

原序列：(1，2，3，4，5，6，7，8)，需要取出limit 1,2，即：(2，3)

按分段法拆成 2 段：

(1 ,? 2 , 3 , 4)?=> limit 1,2?=> 改寫成limit 0, 1+2?=> (1，2，3)

(5 , 6 , 7 , 8)?=> limit 1,2?=> 改寫成limit 0, 1+2?=> (5，6，7)

將子數(shù)列合并排序=>{ 1，2，3，5，6，7}=> 按原始偏移量limit 1,2 =>{2，3}正確

如果原數(shù)列中要取的數(shù)據(jù)，正好落在2個(gè)子數(shù)列上(1，2，3，4，5，6，7，8)，需要取出limit 3,2，即：(4，5)

(1 ,? 2 , 3 , 4)?=> limit 3,2 =>改寫成limit 0, 3+2?=> (1，2，3，4)

(5 , 6 , 7 , 8)?=> limit 3,2 =>改寫成limit 0, 3+2?=> (5，6，7，8)

將子數(shù)列合并排序=>(1，2，3，4，5，6，7，8)?=>按原始偏移量limit 3,2?=> (4，5)也符合預(yù)期。

取模均攤拆成 2 段

(1，3，5，7)?=> limit 1,2?->改寫成limit 0, 1+2?=> (1，3 ，5)

(2，4，6，8)?=> limit 1,2?->改寫成limit 0, 1+2=> (2，4，6)

將子序列合并=>(1，2，3，4，5，6)=> 按原始偏移量limit 1,2 =>(2，3)正確

該方法缺點(diǎn)也很明顯：取出的記錄太多了，比如 limit 10000000,10 ->?改寫后變成 limit 0, 10000010 遇到海量數(shù)據(jù)，mysql 中查詢有可能直接超時(shí)，這么多數(shù)據(jù)從db傳到應(yīng)用層，網(wǎng)絡(luò)開銷也很大，更不用說如果是 java 應(yīng)用，大量數(shù)據(jù)放到 List 或 Map 中，容易出現(xiàn) OOM。(注：一般情況下，需要用分庫分表的場景，數(shù)據(jù)量必然很大，所以這個(gè)方法，實(shí)際中基本上沒法用)

二次查詢法

這也是"業(yè)界難題-跨庫分頁”中提到的一個(gè)方法，大致思路如下：在某 1 頁的數(shù)據(jù)均攤到各分表的前提下(注：這個(gè)前提很重要，也就是說不會(huì)有一個(gè)分表的數(shù)據(jù)特別多或特別少)，換句話說：這個(gè)方案不適用分段法，按如下步驟操作：

1）原 sql 中的limit offset,pagesize改寫成limit offset/n ,pagesize(注：n為分表個(gè)數(shù)，如果 offset/n 除不盡，向下取整，避免最后的結(jié)果丟數(shù)據(jù)）-- 這個(gè)的意思，其實(shí)就是假設(shè)原表這一頁的數(shù)據(jù)，會(huì)均分到各個(gè)分表(所以，我一再強(qiáng)調(diào)，前提是數(shù)據(jù)是均攤的，如果某個(gè)分表的記錄很少，極端情況下，甚至是空的，這個(gè)就不對(duì)了，最終結(jié)果會(huì)少數(shù)據(jù))

2）分表上，執(zhí)行改寫后的 sql，得到一堆結(jié)果集，然后找出這堆結(jié)果中的最小 id (假設(shè) id 是關(guān)鍵的排序字段)，記為 min_id -- 這一步的目的，是為了找出最小的起始點(diǎn)，保證第1頁數(shù)據(jù)起點(diǎn)正確。

3）各分表上的 sql，where 條件部分改寫成id between min_id and origin_max_id?(注：origin_max_id 為上一步，每個(gè)分表查詢結(jié)果集中的最大值，顯然 min_id = 自身最小id的那張分表，不用再重復(fù)查詢) -- 這一步的目的在于，因?yàn)椴襟E1）查出來的結(jié)果，通常會(huì)比原表上該頁的數(shù)據(jù)少，所以這里重新將起始點(diǎn)設(shè)置到正確的位置，即：min_id，再查1次，相當(dāng)于范圍擴(kuò)大了，以保證數(shù)據(jù)不會(huì)丟。不過，這里有一個(gè)可優(yōu)化的地方，仔細(xì)想想，這1次查詢出來的結(jié)果，跟步驟1）中的查出來的結(jié)果，必然有一部分是重復(fù)的，因此改寫部分，只需要?id between min_id and origin_min_id就可以了(origin_min_id 即為原來分表結(jié)果上的最小 id)

4）將上一步查詢出來的結(jié)果，在內(nèi)存中合并排序去重（注：如果上一步采用了優(yōu)化方案，就應(yīng)該是把1）與3）這二次查詢的結(jié)果全取出來合并排序去重），然后從開始連續(xù)取pagesize條數(shù)據(jù)即可（注：offset/n除不盡的話，向下取整了，也就是起始點(diǎn)可能向前多移了，所以有可能開始的第1條記錄，其實(shí)是上1頁的最后1條記錄，要追求精確的話，可以在應(yīng)用層記錄上一頁最后1條記錄的id，然后跟本次查詢結(jié)果前1條記錄對(duì)比，如果發(fā)現(xiàn)是一樣的，開始取數(shù)據(jù)的位置，就要向后移1位，如果考慮id有重復(fù)的話，就要根據(jù)情況多移幾位）

驗(yàn)證一下看看效果：

場景1（前提：取余法）

原序列：(1，2，3，4，5，6，7，8)，需要取出limit?2,2，即：(3，4)

第1次查詢

(1，3，5，7)?->?limit?2,2?->?改寫成limit?1,2?-> (3，5)

(2，4，6，8)?->?limit?2,2->?改寫成limit?1,2?-> (4，6)

最小值為 3

第2次查詢

(1，3，5，7)?->?between?3?and?5?-> (3，5)

(2，4，6，8)?->?between?3?and?6?-> (4，6)

將第2次查詢的結(jié)果合并：

(3，4，5，6)?->取頭開始，取pageSize即2個(gè)元素 -> (3，4)?正確

場景2（前提：取余法）

原序列：(1，2，3，4，5，6，7，8)，需要取出limit?1,2，即：(2，3)

第1次查詢

(1，3，5，7)?->?limit?1,2?->?改寫成?limit?0,2?-> (1，3)

-- 注：因?yàn)?/2除不盡，這里向下取整了

(2，4，6，8)?->?limit?1,2?->?改寫成?limit?0,2?-> (2，4)

最小值為1

第2次查詢

(1，3，5，7)?->?between?1?and?3?-> (1，3)

(2，4，6，8)?->?between?1?and?4?-> (2，4)

將上面的結(jié)果合并：

(1，2，3，4)?->?(2，3)?(注：起始點(diǎn)，第1次查詢改寫時(shí)，向下取整了，所以這里要向移1位，從第2個(gè)數(shù)字開始取pagesize條數(shù)據(jù))

場景3（前提：分段法）

為什么說分段法，這個(gè)方案不適用，可以看下面的分析：

原序列：(1，2，3，4，5，6，7，8)，需要取出limit 2,2 ，即：(3，4)

第1次查詢

(1，2，3，4)?->?limit?2,2?->?limit?1,2?->?{2，3}-- 注：這里就已經(jīng)把正確的數(shù)據(jù)給丟掉了

(5，6，7，8)?->?limit?2,2?->?limit?1,2?->?{5，6}-- 注：這一段里根本就沒有這一頁的數(shù)據(jù)

最小值2

第2次查詢

(1，2，3，4)?->?between?2?and?3?->?{2，3}

(5，6，7，8)?->?between?2?and?6?->?{5，6}

(2，3，5，6)?->?(2，3)? 這個(gè)跟預(yù)期結(jié)果就對(duì)不上了。

場景4（前提：取余法）

取余法的前提下，如果某個(gè)分表的數(shù)據(jù)，被清掉一部分，也就是某個(gè)分表數(shù)據(jù)偏少，會(huì)發(fā)生什么？

比如下面這個(gè)，按奇數(shù)、偶數(shù)分成2個(gè)子序列，但是偶數(shù)故意刪除了幾個(gè)（相當(dāng)于現(xiàn)實(shí)業(yè)務(wù)中，這個(gè)分表上的數(shù)據(jù)被干掉了一部分）

原序列：(1，3，5，6，7，8，9，11)，需要取出limit?2,2，即：(5，6)

第1次查詢

(1，3，5，7，9，11)?->?limit?2,2->?改寫成limit?1,2?->?(3，5)

(6，8)?->?limit?2,2?->?改寫成limit?1,2?->?(8)

第2次查詢

(1，3，5，7，9，11)?->?between?3?and?5?->?(3，5)

(6，8)?->?between?3?and?8?->?(6，8)

合并后

(3，5，6，8)?->?(3，5)這跟預(yù)期結(jié)果也對(duì)不上。

禁止跳頁

相當(dāng)于只允許向上或向下翻頁，原理很簡單，比如：下一頁，先記錄上一頁的最大id，然后下一頁時(shí)，只需要 where id >? 上一頁最大id limit pagesize，?每次只翻1頁。顯然，這是一個(gè)犧牲用戶體驗(yàn)的做法。

結(jié)論：分表分頁不存在一個(gè)通用的解決方案，要么性能有問題（比如:全局法 limit x+y），要么必須具備一定的前提條件(比如：二次查詢)，或者產(chǎn)品設(shè)計(jì)上犧牲用戶體驗(yàn)，仍然是一個(gè)業(yè)內(nèi)難題。

參考文章

• https://juejin.im/post/5d1f52e46fb9a07eb3099bbf
• https://shardingsphere.apache.org/document/current/cn/features/sharding/use-norms/pagination
• https://stackoverflow.com/questions/3927537/how-do-you--implement-sorting-and-paging-on-distributed-data
• http://kmiku7.github.io/2019/08/01/Do-Pagination-With-Table-Database-Sharding
• https://segmentfault.com/a/1190000013225860