一撬码、需求緣起

分頁需求

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

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

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

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

這些業(yè)務場景對應的消息表玄窝，訂單表牵寺，帖子表分頁拉取需求有這樣一些特點：

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

（2）分頁排序是按照非業(yè)務主鍵id來排序的，業(yè)務中經(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ù)據(jù)為100條，均拉取第3頁數(shù)據(jù)俩块。

分庫需求

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

一旦涉及分庫，逃不開“分庫依據(jù)”patition key的概念盲厌，使用哪一個字段來水平切分數(shù)據(jù)庫呢：大部分的業(yè)務場景署照，會使用業(yè)務主鍵id。

確定了分庫依據(jù)patition key后吗浩，接下來要確定的是分庫算法：大部分的業(yè)務場景建芙，會使用業(yè)務主鍵id取模的算法來分庫，這樣即能夠保證每個庫的數(shù)據(jù)分布是均勻的拓萌，又能夠保證每個庫的請求分布是均勻的岁钓，實在是簡單實現(xiàn)負載均衡的好方法，此法在互聯(lián)網(wǎng)架構中應用頗多。

舉一個更具體的例子：

用戶庫user屡限，水平切分后變?yōu)閮蓚€庫品嚣，分庫依據(jù)patition key是uid，分庫算法是uid取模：uid%2余0的數(shù)據(jù)會落到db0钧大，uid%2余1的數(shù)據(jù)會落到db1翰撑。

問題的提出

仍然是上述用戶庫的例子，如果業(yè)務要查詢“最近注冊的第3頁用戶”啊央，該如何實現(xiàn)呢眶诈？單庫上，可以

select * from t_user order by time offset 200 limit 100

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

如何滿足“跨越多個水平切分數(shù)據(jù)庫趣苏，且分庫依據(jù)與排序依據(jù)為不同屬性狡相，并需要進行分頁”的查詢需求，實現(xiàn) select * from T order by time offset X limit Y的跨庫分頁SQL食磕，是本文將要討論的技術問題尽棕。

二、全局視野法

如上圖所述彬伦，服務層通過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ù)（如上圖中粉色部分數(shù)據(jù)）蜗帜。

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

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

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

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

由于不清楚到底是哪種情況舷胜，所以必須每個庫都返回3頁數(shù)據(jù)，所得到的6頁數(shù)據(jù)在服務層進行內(nèi)存排序活翩，得到數(shù)據(jù)全局視野烹骨，再取第3頁數(shù)據(jù)，便能夠得到想要的全局分頁數(shù)據(jù)材泄。

再總結一下這個方案的步驟：

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

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

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

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

方案優(yōu)點：通過服務層修改SQL語句，擴大數(shù)據(jù)召回量簿废，能夠得到全局視野空入，業(yè)務無損，精準返回所需數(shù)據(jù)族檬。

方案缺點（顯而易見）：

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

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

（3）最致命的扫尖，這個算法隨著頁碼的增大白对，性能會急劇下降低散，這是因為SQL改寫后每個分庫要返回X+Y行數(shù)據(jù)：返回第3頁捌浩，offset中的X=200；假如要返回第100頁孤澎，offset中的X=9900沉颂，即每個分庫要返回100頁數(shù)據(jù)条摸，數(shù)據(jù)量和排序量都將大增，性能平方級下降铸屉。

三钉蒲、業(yè)務折衷法

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

“任何脫離業(yè)務的架構設計都是耍流氓”钙蒙，技術方案需要折衷茵瀑，在技術難度較大的情況下，業(yè)務需求的折衷能夠極大的簡化技術方案仪搔。

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

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

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

（1）將查詢order by time offset 0 limit 100昌阿，改寫成order by time where time>0 limit 100

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

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

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

點擊“下一頁”時，需要拉取第二頁數(shù)據(jù)荆针，在第一頁數(shù)據(jù)的基礎之上敞嗡，能夠找到第一頁數(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）服務層得到2頁數(shù)據(jù)，內(nèi)存排序键畴，取出前100條數(shù)據(jù)最盅，作為最終的第2頁數(shù)據(jù)突雪，這個全局的第2頁數(shù)據(jù)，一般來說也是每個分庫都包含一部分數(shù)據(jù)（如上圖粉色部分）涡贱；

如此往復咏删，查詢?nèi)忠曇暗?00頁數(shù)據(jù)時，不是將查詢條件改寫為offset 0 limit 9900+100（返回100頁數(shù)據(jù)）问词，而是改寫為time>$time_max99 limit 100（仍返回一頁數(shù)據(jù)）督函，以保證數(shù)據(jù)的傳輸量和排序的數(shù)據(jù)量不會隨著不斷翻頁而導致性能下降。

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

“全局視野法”能夠返回業(yè)務無損的精確數(shù)據(jù)激挪，在查詢頁數(shù)較大辰狡，例如第100頁時，會有性能問題垄分，此時業(yè)務上是否能夠接受宛篇，返回的100頁不是精準的數(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上男性用戶占比也應為70%

（2）年齡屬性砸逊，如果db0庫上18-28歲少女用戶比例占比15%璧南，則db1上少女用戶比例也應為15%

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

…

利用這一原理司倚，要查詢?nèi)?00頁數(shù)據(jù)，offset 9900 limit 100改寫為offset 4950 limit 50篓像，每個分庫偏移4950（一半）动知，獲取50條數(shù)據(jù)（半頁），得到的數(shù)據(jù)集的并集员辩，基本能夠認為盒粮，是全局數(shù)據(jù)的offset 9900 limit 100的數(shù)據(jù)，當然奠滑，這一頁數(shù)據(jù)的精度丹皱，并不是精準的妒穴。

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

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

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

為了方便舉例，假設一頁只有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荧呐，除以水平切分數(shù)據(jù)庫個數(shù)2。

如果是3個分庫纸镊，則可以改寫為select * from T order by time offset 333 limit 5

假設這三個分庫返回的數(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ù)鞠柄，時間復雜度很低

步驟三：查詢二次改寫

第一次改寫的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

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

可以看到：

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

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

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

步驟四：在每個結果集中虛擬一個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莽囤，就相當于有了全局視野，根據(jù)第二次的結果集切距，就能夠得到全局offset 1000 limit 5的記錄

第二次查詢在各個分庫返回的結果集是有序的朽缎，又知道了time_min在全局的offset是994，一路排下來谜悟，容易知道全局offset 1000 limit 5的一頁記錄（上圖中黃色記錄）话肖。

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

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

五是钥、總結

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

方法一：全局視野法

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

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

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

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

（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è)務折衷法-允許模糊數(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）設置虛擬time_min践磅，找到time_min在各個分庫的offset，從而得到time_min在全局的offset

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