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

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

• 微信消息過多時，拉取第N頁消息;
• 京東下單過多時，拉取第N頁訂單;
• 瀏覽58同城，查看第N頁帖子。

[[265204]]

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

• 有個業(yè)務(wù)主鍵id, msg_id, order_id, tiezi_id;
• 分頁按照非業(yè)務(wù)主鍵id來排序，業(yè)務(wù)中經(jīng)常按照時間time來排序order by。

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

• 在排序字段time上建立索引;
• 利用SQL提供的offset/limit就能實現(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ù)。

為什么會有分庫的需求?

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

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

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

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

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

• 即能夠保證每個庫的數(shù)據(jù)分布是均勻的;
• 又能夠保證每個庫的請求分布是均勻的。

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

一個更具體的例子：

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

• 分庫依據(jù)patition key是uid;
• 分庫算法是uid取模：uid%2余0的數(shù)據(jù)會落到db0，uid%2余1的數(shù)據(jù)會落到db1。

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

單庫上，可以：

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

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

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

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

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

方案一：全局視野法

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

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

需要分三種情況討論。

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

 

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

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

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

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

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

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

• 每個庫都返回3頁數(shù)據(jù);
• 所得到的6頁數(shù)據(jù)在服務(wù)層進(jìn)行內(nèi)存排序，得到數(shù)據(jù)全局視野;
• 再取第3頁數(shù)據(jù)，便能夠得到想要的全局分頁數(shù)據(jù)。

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

(1) 將SQL語句改寫，即：

order by time offset X limit Y; 

改寫成：

order by time offset 0 limit X+Y; 

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

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

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

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

全局視野法有什么優(yōu)點?

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

全局視野法的缺點呢?

缺點顯而易見：

• 每個分庫需要返回更多的數(shù)據(jù)，增大了網(wǎng)絡(luò)傳輸量(耗網(wǎng)絡(luò));
• 除了數(shù)據(jù)庫按照time進(jìn)行排序，服務(wù)層還需要進(jìn)行二次排序，增大了服務(wù)層的計算量(耗CPU);
• 最致命的，這個算法隨著頁碼的增大，性能會急劇下降，這是因為SQL改寫后每個分庫要返回X+Y行數(shù)據(jù)：返回第3頁，offset中的X=200;假如要返回第100頁，offset中的X=9900，即每個分庫要返回100頁數(shù)據(jù)，數(shù)據(jù)量和排序量都將大增，性能平方級下降。

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

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

方案二：禁止跳頁查詢法

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

如上圖，不能跳頁，那么只能夠查初始頁：

(1)將查詢

order by time offset 0 limit 100; 

改寫成：

order by time where time>0 limit 100; 

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

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

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

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

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

(1)將查詢

order by time offset 100 limit 100; 

改寫成

order by time where time>$time_max limit 100; 

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

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

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

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

而是改寫為

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

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

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

“全局視野法”能夠返回業(yè)務(wù)無損的精確數(shù)據(jù)，在查詢頁數(shù)較大，例如第100頁時，會有性能問題，此時業(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屬性，在各個分庫上，數(shù)據(jù)分布的統(tǒng)計概率情況是一致的。

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

• 性別屬性，如果db0庫上的男性用戶占比70%，則db1上男性用戶占比也應(yīng)為70%;
• 年齡屬性，如果db0庫上18-28歲少女用戶比例占比15%，則db1上少女用戶比例也應(yīng)為15%;
• 時間屬性，如果db0庫上每天10:00之前登錄的用戶占比為20%，則db1上應(yīng)該是相同的統(tǒng)計規(guī)律;
• …

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

offset 9900 limit 100; 

改寫為

offset 4950 limit 50; 

即每個分庫偏移一半(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ù)實際業(yè)務(wù)經(jīng)驗，用戶都要查詢第100頁網(wǎng)頁、帖子、郵件的數(shù)據(jù)了，這一頁數(shù)據(jù)的精準(zhǔn)性損失，業(yè)務(wù)上往往是可以接受的，但此時技術(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; 

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

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

如果是3個分庫，則可以改寫為：

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

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

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

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

• 5條數(shù)據(jù)的time最小值是1487501123;
• 第二個庫，5條數(shù)據(jù)的time最小值是1487501133;
• 第三個庫，5條數(shù)據(jù)的time最小值是1487501143;

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

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

步驟三：查詢二次改寫

改寫的SQL語句是

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

第二次要改寫成一個between語句：

• between的起點是time_min
• between的終點是原來每個分庫各自返回數(shù)據(jù)的值

分庫，返回數(shù)據(jù)的值是1487501523

所以查詢改寫為：

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

第二個分庫，返回數(shù)據(jù)的值是1487501323

所以查詢改寫為

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

第三個分庫，返回數(shù)據(jù)的值是1487501553

所以查詢改寫為

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

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

可以看到：

• 分庫一的結(jié)果集，由于time_min來自原來的分庫一，所以分庫一的返回結(jié)果集和初始查詢相同(所以其實這次訪問是可以省略的);
• 分庫二的結(jié)果集，比初始多返回了1條數(shù)據(jù)，頭部的1條記錄(time最小的記錄)是新的(上圖中粉色記錄);
• 分庫三的結(jié)果集，比初始多返回了2條數(shù)據(jù)，頭部的2條記錄(time最小的2條記錄)是新的(上圖中粉色記錄);

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

在初始庫中，time_min在庫里的offset是333;

在第二個庫中，(1487501133, uid_aa)的offset是333(根據(jù)初始查詢條件得出的)，故虛擬time_min在第二個庫的offset是331;

畫外音：從333往前推演。

在第三個庫中，(1487501143, uid_aaa)的offset是333(根據(jù)初始查詢條件得出的)，故虛擬time_min在第三個庫的offset是330;

畫外音：從333往前推演。

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

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

第二次查詢在各個分庫返回的結(jié)果集是有序的，又知道了time_min在全局的offset是994，一路排下來，容易知道全局offset 1000 limit 5的一頁記錄(上圖中記錄)。

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

帥氣不帥氣!!!

總結(jié)

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

方法一：全局視野法

(1)SQL改寫，將

order by time offset X limit Y; 

改寫成

order by time offset 0 limit X+Y; 

(2)服務(wù)層對得到的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_i_max; 

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

(5)得到了time_min在全局的offset，自然得到了全局的offset X limit Y;

文章比較長，希望大家有收獲。

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】

戳這里，看該作者更多好文