為什么需要研究跨庫分頁？

互聯(lián)網(wǎng)很多業(yè)務(wù)都有分頁拉取數(shù)據(jù)的需求，例如：

（1）微信消息過多時(shí)，拉取第 N 頁消息；

（2）京東下單過多時(shí)，拉取第 N 頁訂單；

（3）瀏覽 58 同城，查看第 N 頁帖子；

這些業(yè)務(wù)場(chǎng)景對(duì)應(yīng)的消息表，訂單表，帖子表分頁拉取需求，都有這樣一些共同的特點(diǎn)：

（1）有個(gè)業(yè)務(wù)主鍵 id, msg_id, order_id, tiezi_id；

（2）分頁按照非業(yè)務(wù)主鍵 id 來排序，業(yè)務(wù)中經(jīng)常按照時(shí)間 time 來排序 order by；

在數(shù)據(jù)量不大時(shí)，如何來實(shí)現(xiàn)跨庫分頁的需求呢？

（1）在排序字段 time 上建立索引；

（2）利用 SQL 提供的 offset/limit 就能實(shí)現(xiàn)；

例如：

select * from t_msg order by time offset 200 limit 100;

select * from t_order order by time offset 200 limit 100;

select * from t_tiezi order by time offset 200 limit 100;

畫外音：此處假設(shè)一頁數(shù)據(jù)為 100 條，均拉取第 3 頁數(shù)據(jù)。

為什么會(huì)有分庫的需求？

高并發(fā)大流量的互聯(lián)網(wǎng)架構(gòu)，一般通過服務(wù)層來訪問數(shù)據(jù)庫，隨著數(shù)據(jù)量的增大，數(shù)據(jù)庫需要進(jìn)行水平切分，分庫后將數(shù)據(jù)分布到不同的數(shù)據(jù)庫實(shí)例（甚至物理機(jī)器）上，以達(dá)到降低數(shù)據(jù)量，增加實(shí)例數(shù)的擴(kuò)容目的。

一旦涉及分庫，逃不開 “分庫依據(jù)” patition key，要使用哪一個(gè)字段來水平切分?jǐn)?shù)據(jù)庫呢？

大部分的業(yè)務(wù)場(chǎng)景，會(huì)使用業(yè)務(wù)主鍵 id。

確定了分庫依據(jù) patition key 后，接下來怎么確定分庫算法呢？

大部分的業(yè)務(wù)場(chǎng)景，會(huì)使用業(yè)務(wù)主鍵 id 取模的算法來分庫，這樣的好處是：

（1）即能夠保證每個(gè)庫的數(shù)據(jù)分布是均勻的；

（2）又能夠保證每個(gè)庫的請(qǐng)求分布是均勻的；

實(shí)在是簡(jiǎn)單實(shí)現(xiàn)負(fù)載均衡的好方法，此法在互聯(lián)網(wǎng)架構(gòu)中應(yīng)用頗多。

一個(gè)更具體的例子：

image

用戶庫 user，水平切分后變?yōu)閮蓚€(gè)庫：

（1）分庫依據(jù) patition key 是 uid；

（2）分庫算法是 uid 取模：uid%2 余 0 的數(shù)據(jù)會(huì)落到 db0，uid%2 余 1 的數(shù)據(jù)會(huì)落到 db1；

數(shù)據(jù)庫進(jìn)行了水平切分之后，如果業(yè)務(wù)要查詢 “最近注冊(cè)的第 3 頁用戶”，即跨庫分頁查詢，該如何實(shí)現(xiàn)呢？

單庫上，可以

select * from t_user order by time offset 200 limit 100;

變成兩個(gè)庫后，分庫依據(jù)是 uid，排序依據(jù)是 time，數(shù)據(jù)庫層失去了 time 排序的全局視野，數(shù)據(jù)分布在兩個(gè)庫上，此時(shí)該怎么辦呢？

如何滿足 “跨越多個(gè)水平切分?jǐn)?shù)據(jù)庫，且分庫依據(jù)與排序依據(jù)為不同屬性，并需要進(jìn)行分頁” 的查詢需求，實(shí)現(xiàn)：

select * from T order by time offset X limit Y;

這類跨庫分頁 SQL，是后文將要討論的技術(shù)問題。

方案一：全局視野法

image

如上圖所述，服務(wù)層通過 uid 取模將數(shù)據(jù)分布到兩個(gè)庫上去之后，每個(gè)數(shù)據(jù)庫都失去了全局視野，數(shù)據(jù)按照 time 局部排序之后，不管哪個(gè)分庫的第 3 頁數(shù)據(jù)，都不一定是全局排序的第 3 頁數(shù)據(jù)。

那到底哪些數(shù)據(jù)才是全局排序的第 3 頁數(shù)據(jù)呢？

需要分三種情況討論。

（1）極端情況，兩個(gè)庫的數(shù)據(jù)完全一樣

image

如果兩個(gè)庫的數(shù)據(jù)完全相同，只需要每個(gè)庫 offset 一半，再取半頁，就是最終想要的數(shù)據(jù)（如上圖中粉色部分?jǐn)?shù)據(jù)）。

（2）極端情況，結(jié)果數(shù)據(jù)來自一個(gè)庫

image

也可能兩個(gè)庫的數(shù)據(jù)分布及其不均衡，例如 db0 的所有數(shù)據(jù)的 time 都大于 db1 的所有數(shù)據(jù)的 time，則可能出現(xiàn)：一個(gè)庫的第 3 頁數(shù)據(jù)，就是全局排序后的第 3 頁數(shù)據(jù)（如上圖中粉色部分?jǐn)?shù)據(jù)）。

（3）一般情況，每個(gè)庫數(shù)據(jù)各包含一部分

image

正常情況下，全局排序的第 3 頁數(shù)據(jù)，每個(gè)庫都會(huì)包含一部分（如上圖中粉色部分?jǐn)?shù)據(jù)）。

由于不清楚到底是哪種情況，所以必須：

（1）每個(gè)庫都返回 3 頁數(shù)據(jù)；

（2）所得到的 6 頁數(shù)據(jù)在服務(wù)層進(jìn)行內(nèi)存排序，得到數(shù)據(jù)全局視野；

（3）再取第 3 頁數(shù)據(jù)，便能夠得到想要的全局分頁數(shù)據(jù)。

再總結(jié)一下這個(gè)方案的步驟：

（1）將 SQL 語句改寫，即

order by time offset X limit Y;

改寫成

order by time offset 0 limit X+Y;

（2）服務(wù)層將改寫后的 SQL 語句發(fā)往各個(gè)分庫；

（3）假設(shè)共分為 N 個(gè)庫，服務(wù)層將得到 N*(X+Y) 條數(shù)據(jù)；

（4）服務(wù)層對(duì)得到的 N*(X+Y) 條數(shù)據(jù)進(jìn)行內(nèi)存排序；

（5）內(nèi)存排序后再取偏移量 X 后的 Y 條記錄，就是全局視野所需的一頁數(shù)據(jù)；

全局視野法有什么優(yōu)點(diǎn)？

通過服務(wù)層修改 SQL 語句，擴(kuò)大數(shù)據(jù)召回量，能夠得到全局視野，業(yè)務(wù)無損，精準(zhǔn)返回所需數(shù)據(jù)。

全局視野法的缺點(diǎn)呢？

缺點(diǎn)顯而易見：

（1）每個(gè)分庫需要返回更多的數(shù)據(jù)，增大了網(wǎng)絡(luò)傳輸量（耗網(wǎng)絡(luò)）；

（2）除了數(shù)據(jù)庫按照 time 進(jìn)行排序，服務(wù)層還需要進(jìn)行二次排序，增大了服務(wù)層的計(jì)算量（耗 CPU）；

（3）最致命的，這個(gè)算法隨著頁碼的增大，性能會(huì)急劇下降，這是因?yàn)?SQL 改寫后每個(gè)分庫要返回 X+Y 行數(shù)據(jù)：返回第 3 頁，offset 中的 X=200；假如要返回第 100 頁，offset 中的 X=9900，即每個(gè)分庫要返回 100 頁數(shù)據(jù)，數(shù)據(jù)量和排序量都將大增，性能平方級(jí)下降。

“全局視野法” 雖然性能較差，但其業(yè)務(wù)無損，數(shù)據(jù)精準(zhǔn)，不失為一種方案，有沒有性能更優(yōu)的方案呢？

“任何脫離業(yè)務(wù)的架構(gòu)設(shè)計(jì)都是耍流氓”，技術(shù)方案需要折衷，在技術(shù)難度較大的情況下，業(yè)務(wù)需求的折衷能夠極大的簡(jiǎn)化技術(shù)方案。

方案二：禁止跳頁查詢法

在數(shù)據(jù)量很大，翻頁數(shù)很多的時(shí)候，很多產(chǎn)品并不提供 “直接跳到指定頁面” 的功能，而只提供 “下一頁” 的功能，這一個(gè)小小的業(yè)務(wù)折衷，就能極大的降低技術(shù)方案的復(fù)雜度。

image

如上圖，不能跳頁，那么第一次只能夠查第一頁：

（1）將查詢

order by time offset 0 limit 100;

改寫成

order by time where time>0 limit 100;

（2）上述改寫和 offset 0 limit 100 的效果相同，都是每個(gè)分庫返回了一頁數(shù)據(jù)（上圖中粉色部分）；

image

（3）服務(wù)層得到 2 頁數(shù)據(jù)，內(nèi)存排序，取出前 100 條數(shù)據(jù)，作為最終的第一頁數(shù)據(jù)，這個(gè)全局的第一頁數(shù)據(jù)，一般來說每個(gè)分庫都包含一部分?jǐn)?shù)據(jù)（如上圖粉色部分）；

這個(gè)方案也需要服務(wù)器內(nèi)存排序，豈不是和 “全局視野法” 一樣么？第一頁數(shù)據(jù)的拉取確實(shí)一樣，但每一次 “下一頁” 拉取的方案就不一樣了。

點(diǎn)擊 “下一頁” 時(shí)，需要拉取第二頁數(shù)據(jù)，在第一頁數(shù)據(jù)的基礎(chǔ)之上，能夠找到第一頁數(shù)據(jù) time 的最大值：

image

這個(gè)上一頁記錄的 time_max****，會(huì)作為第二頁數(shù)據(jù)拉取的查詢條件：

（1）將查詢

order by time offset 100 limit 100;

改寫成

order by time where time>$time_max limit 100;

image

（2）這下不是返回 2 頁數(shù)據(jù)了（“全局視野法，會(huì)改寫成 offset 0 limit 200”），每個(gè)分庫還是返回一頁數(shù)據(jù)（如上圖中粉色部分）；

image

（3）服務(wù)層得到 2 頁數(shù)據(jù)，內(nèi)存排序，取出前 100 條數(shù)據(jù)，作為最終的第 2 頁數(shù)據(jù)，這個(gè)全局的第 2 頁數(shù)據(jù)，一般來說也是每個(gè)分庫都包含一部分?jǐn)?shù)據(jù)（如上圖粉色部分）；

如此往復(fù)，查詢?nèi)忠曇暗?100 頁數(shù)據(jù)時(shí)，不是將查詢條件改寫為

offset 0 limit 9900+100;（返回 100 頁數(shù)據(jù)）

而是改寫為

time>$time_max99 limit 100;（仍返回一頁數(shù)據(jù)）

以保證數(shù)據(jù)的傳輸量和排序的數(shù)據(jù)量不會(huì)隨著不斷翻頁而導(dǎo)致性能下降。

方案三：允許數(shù)據(jù)精度損失法

“全局視野法” 能夠返回業(yè)務(wù)無損的精確數(shù)據(jù)，在查詢頁數(shù)較大，例如第 100 頁時(shí)，會(huì)有性能問題，此時(shí)業(yè)務(wù)上是否能夠接受，返回的 100 頁不是精準(zhǔn)的數(shù)據(jù)，而允許有一些數(shù)據(jù)偏差呢？

先來了解一下，數(shù)據(jù)庫分庫 - 數(shù)據(jù)均衡原理。

什么是，數(shù)據(jù)庫分庫 - 數(shù)據(jù)均衡原理？

使用 patition key 進(jìn)行分庫，在數(shù)據(jù)量較大，數(shù)據(jù)分布足夠隨機(jī)的情況下，各分庫所有非 patition key 屬性，在各個(gè)分庫上，數(shù)據(jù)分布的統(tǒng)計(jì)概率情況是一致的。

例如，在 uid 隨機(jī)的情況下，使用 uid 取模分兩庫，db0 和 db1：

（1）性別屬性，如果 db0 庫上的男性用戶占比 70%，則 db1 上男性用戶占比也應(yīng)為 70%；

（2）年齡屬性，如果 db0 庫上 18-28 歲少女用戶比例占比 15%，則 db1 上少女用戶比例也應(yīng)為 15%；

（3）時(shí)間屬性，如果 db0 庫上每天 10:00 之前登錄的用戶占比為 20%，則 db1 上應(yīng)該是相同的統(tǒng)計(jì)規(guī)律；

…

image

利用這一原理，要查詢?nèi)?100 頁數(shù)據(jù)，只要將：

offset 9900 limit 100;

改寫為

offset 4950 limit 50;

即每個(gè)分庫偏移一半（4950），獲取半頁數(shù)據(jù)（50 條），得到的數(shù)據(jù)集的并集，基本能夠認(rèn)為，是全局?jǐn)?shù)據(jù)的 offset 9900 limit 100 的數(shù)據(jù)，當(dāng)然，這一頁數(shù)據(jù)并不是精準(zhǔn)的。

根據(jù)實(shí)際業(yè)務(wù)經(jīng)驗(yàn)，用戶都要查詢第 100 頁網(wǎng)頁、帖子、郵件的數(shù)據(jù)了，這一頁數(shù)據(jù)的精準(zhǔn)性損失，業(yè)務(wù)上往往是可以接受的，但此時(shí)技術(shù)方案的復(fù)雜度大大降低了，既不需要返回更多的數(shù)據(jù)，也不需要進(jìn)行服務(wù)內(nèi)存排序了。

畫外音：如果業(yè)務(wù)能夠接受，這種方案的性能最好，強(qiáng)烈推薦。

方案四：二次查詢法

有沒有一種技術(shù)方案，即能夠滿足業(yè)務(wù)的精確需要，無需業(yè)務(wù)折衷，又高性能的方法呢？這就是接下來要介紹的終極武器，“二次查詢法”。

為了方便舉例，假設(shè)一頁只有 5 條數(shù)據(jù)，查詢第 200 頁的 SQL 語句為：

select * from T order by time offset 1000 limit 5;

步驟一：查詢改寫

select * from T order by time offset 1000 limit 5;

改寫為

select * from T order by time offset 500 limit 5;

并投遞給所有的分庫，注意，這個(gè) offset 的 500，來自于全局 offset 的總偏移量 1000，除以水平切分?jǐn)?shù)據(jù)庫個(gè)數(shù) 2。

畫外音：因?yàn)閿?shù)據(jù)量比較大，數(shù)據(jù)隨機(jī)性較強(qiáng)，不妨設(shè)仍然符合 “數(shù)據(jù)庫分庫 - 數(shù)據(jù)均衡定理”。

如果是 3 個(gè)分庫，則可以改寫為

select * from T order by time offset 333 limit 5;

假設(shè)這三個(gè)分庫返回的數(shù)據(jù) (time, uid) 如下：

image

可以看到，每個(gè)分庫都是返回的按照 time 排序的一頁數(shù)據(jù)。

步驟二：找到所返回 3 頁全部數(shù)據(jù)的最小值

第一個(gè)庫，5 條數(shù)據(jù)的 time 最小值是 1487501123；

第二個(gè)庫，5 條數(shù)據(jù)的 time 最小值是 1487501133；

第三個(gè)庫，5 條數(shù)據(jù)的 time 最小值是 1487501143；

image

故，三頁數(shù)據(jù)中，time 最小值來自第一個(gè)庫，time_min=1487501123，這個(gè)過程只需要比較各個(gè)分庫第一條數(shù)據(jù)，時(shí)間復(fù)雜度很低。

畫外音：這個(gè) time_min 非常重要，后文每一個(gè)步驟要都要用到 time_min。

步驟三：查詢二次改寫

第一次改寫的 SQL 語句是

select * from T order by time offset 333 limit 5;

第二次要改寫成一個(gè) between 語句：

• between 的起點(diǎn)是 time_min

• between 的終點(diǎn)是原來每個(gè)分庫各自返回?cái)?shù)據(jù)的最大值

第一個(gè)分庫，第一次返回?cái)?shù)據(jù)的最大值是 1487501523

所以查詢改寫為：

select * from T order by time where time between time_min and 1487501523;

第二個(gè)分庫，第一次返回?cái)?shù)據(jù)的最大值是 1487501323

所以查詢改寫為

select * from T order by time where time between time_min and 1487501323;

第三個(gè)分庫，第一次返回?cái)?shù)據(jù)的最大值是 1487501553

所以查詢改寫為

select * from T order by time where time between time_min and 1487501553;

相對(duì)第一次查詢，第二次查詢條件放寬了，故第二次查詢會(huì)返回比第一次查詢結(jié)果集更多的數(shù)據(jù)，假設(shè)這三個(gè)分庫返回的數(shù)據(jù) (time, uid) 如下：

image

可以看到：

分庫一的結(jié)果集，由于 time_min 來自原來的分庫一，所以分庫一的返回結(jié)果集和第一次查詢相同（所以其實(shí)這次訪問是可以省略的）；

分庫二的結(jié)果集，比第一次多返回了 1 條數(shù)據(jù)，頭部的 1 條記錄（time 最小的記錄）是新的（上圖中粉色記錄）；

分庫三的結(jié)果集，比第一次多返回了 2 條數(shù)據(jù)，頭部的 2 條記錄（time 最小的 2 條記錄）是新的（上圖中粉色記錄）；

步驟四：在每個(gè)結(jié)果集中虛擬一個(gè) time_min 記錄，找到 time_min 在全局的 offset

image

在第一個(gè)庫中，time_min 在第一個(gè)庫的 offset 是 333；

在第二個(gè)庫中，(1487501133, uid_aa) 的 offset 是 333（根據(jù)第一次查詢條件得出的），故虛擬 time_min 在第二個(gè)庫的 offset 是 331；

畫外音：從 333 往前推演。

在第三個(gè)庫中，(1487501143, uid_aaa) 的 offset 是 333（根據(jù)第一次查詢條件得出的），故虛擬 time_min 在第三個(gè)庫的 offset 是 330；

畫外音：從 333 往前推演。

綜上，time_min 在全局的 offset 是 333+331+330=994。

步驟五：既然得到了 time_min 在全局的 offset，就相當(dāng)于有了全局視野，根據(jù)第二次的結(jié)果集，就能夠得到全局 offset 1000 limit 5 的記錄

image

第二次查詢?cè)诟鱾€(gè)分庫返回的結(jié)果集是有序的，又知道了 time_min 在全局的 offset 是 994，一路排下來，容易知道全局 offset 1000 limit 5 的一頁記錄（上圖中黃色記錄）。

這種方法的優(yōu)點(diǎn)是：可以精確的返回業(yè)務(wù)所需數(shù)據(jù)，每次返回的數(shù)據(jù)量都非常小，不會(huì)隨著翻頁增加數(shù)據(jù)的返回量。

帥氣不帥氣?。?！

總結(jié)

今天介紹了解決 “跨 N 庫分頁” 這一難題的四種方法：

方法一：全局視野法

（1）SQL 改寫，將

order by time offset X limit Y;

改寫成

order by time offset 0 limit X+Y;

（2）服務(wù)層對(duì)得到的 N*(X+Y) 條數(shù)據(jù)進(jìn)行內(nèi)存排序，內(nèi)存排序后再取偏移量 X 后的 Y 條記錄；

這種方法隨著翻頁的進(jìn)行，性能越來越低。

方法二：禁止跳頁查詢法

（1）用正常的方法取得第一頁數(shù)據(jù)，并得到第一頁記錄的 time_max；

（2）每次翻頁，將

order by time offset X limit Y;

改寫成

order by time where time>$time_max limit Y;

以保證每次只返回一頁數(shù)據(jù)，性能為常量。

方法三：允許模糊數(shù)據(jù)法

（1）SQL 查詢改寫，將

order by time offset X limit Y;

改寫成

order by time offset X/N limit Y/N;

性能很高，但拼接的結(jié)果集不精準(zhǔn)。

方法四：二次查詢法

（1）SQL 改寫，將

order by time offset X limit Y;

改寫成

order by time offset X/N limit Y;

（2）多頁返回，找到最小值 time_min；

（3）between 二次查詢

order by time between time_min and time_max;

（4）設(shè)置虛擬 time_min，找到 time_min 在各個(gè)分庫的 offset，從而得到 time_min 在全局的 offset；

（5）得到了 time_min 在全局的 offset，自然得到了全局的 offset X limit Y；

文章比較長(zhǎng)，希望大家有收獲。

思路比結(jié)論更重要。

****架構(gòu)師之路** - 分享技術(shù)思路**

作者：58沈劍_架構(gòu)師之路
鏈接：https://juejin.cn/post/6908220694929080333
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。