一混稽、需求緣起

分頁需求

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

（1）微信消息過多時，拉取第N頁消息

（2）京東下單過多時匈勋，拉取第N頁訂單

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

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

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

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

在數(shù)據(jù)量不大時，可以通過在排序字段time上建立索引饿自，利用SQL提供的offset/limit功能就能滿足分頁查詢需求：

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ù)庫需要進行水平切分烛卧，分庫后將數(shù)據(jù)分布到不同的數(shù)據(jù)庫實例（甚至物理機器）上佛纫，以達到降低數(shù)據(jù)量，增加實例數(shù)的擴容目的唱星。

一旦涉及分庫雳旅，逃不開“分庫依據(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谆吴。

問題的提出

仍然是上述用戶庫的例子，如果業(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ù)為不同屬性骏令，并需要進行分頁”的查詢需求蔬捷，實現(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ù)層進行內(nèi)存排序，得到數(shù)據(jù)全局視野贰健，再取第3頁數(shù)據(jù)，便能夠得到想要的全局分頁數(shù)據(jù)恬汁。

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

（1）將order by time offset X limit Y伶椿，改寫成order by time offset 0 limit X+Y

（2）服務(wù)層將改寫后的SQL語句發(fā)往各個分庫：即例子中的各取3頁數(shù)據(jù)

（3）假設(shè)共分為N個庫辜伟，服務(wù)層將得到N*(X+Y)條數(shù)據(jù)：即例子中的6頁數(shù)據(jù)

（4）服務(wù)層對得到的N*(X+Y)條數(shù)據(jù)進行內(nèi)存排序，內(nèi)存排序后再取偏移量X后的Y條記錄脊另，就是全局視野所需的一頁數(shù)據(jù)

方案優(yōu)點：通過服務(wù)層修改SQL語句导狡，擴大數(shù)據(jù)召回量，能夠得到全局視野偎痛，業(yè)務(wù)無損旱捧，精準(zhǔn)返回所需數(shù)據(jù)。

方案缺點（顯而易見）：

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

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

（3）最致命的，這個算法隨著頁碼的增大反粥，性能會急劇下降卢肃，這是因為SQL改寫后每個分庫要返回X+Y行數(shù)據(jù)：返回第3頁，offset中的X=200才顿；假如要返回第100頁莫湘，offset中的X=9900，即每個分庫要返回100頁數(shù)據(jù)郑气，數(shù)據(jù)量和排序量都將大增幅垮，性能平方級下降。

三竣贪、業(yè)務(wù)折衷法

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

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

業(yè)務(wù)折衷一：禁止跳頁查詢

在數(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ù)，這個全局的第一頁數(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)致性能下降艾君。

業(yè)務(wù)折衷二：允許數(shù)據(jù)精度損失

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

數(shù)據(jù)庫分庫-數(shù)據(jù)均衡原理

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

例如尼啡，在uid隨機的情況下暂衡，使用uid取模分兩庫，db0和db1：

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

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

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

…

利用這一原理雌续，要查詢?nèi)?00頁數(shù)據(jù)斩个，offset 9900 limit 100改寫為offset 4950 limit 50，每個分庫偏移4950（一半）驯杜，獲取50條數(shù)據(jù)（半頁）受啥，得到的數(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ù)灭贷，也不需要進行服務(wù)內(nèi)存排序了温学。

四、終極武器-二次查詢法

有沒有一種技術(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料按。

如果是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ù)雜度很低

步驟三：查詢二次改寫

第一次改寫的SQL語句是select * 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)如下：

可以看到：

由于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

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

綜上塌碌，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ù)的返回量某弦。

不足是：需要進行兩次數(shù)據(jù)庫查詢桐汤。

五、總結(jié)

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

方法一：全局視野法

（1）將order by time offset X limit Y靶壮，改寫成order by time offset 0 limit X+Y

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

這種方法隨著翻頁的進行，性能越來越低腾降。

方法二：業(yè)務(wù)折衷法-禁止跳頁查詢

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

（2）每次翻頁，將order by time offset X limit Y螃壤，改寫成order by time where time>$time_max limit Y

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

方法三：業(yè)務(wù)折衷法-允許模糊數(shù)據(jù)

（1）將order by time offset X limit Y奸晴，改寫成order by time offset X/N limit Y/N

方法四：二次查詢法

（1）將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