為什么需要研究跨庫(kù)分頁(yè)？

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

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

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

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

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

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

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

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

（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è)一頁(yè)數(shù)據(jù)為100條，均拉取第3頁(yè)數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

單庫(kù)上，可以

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

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

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

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

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

方案一：全局視野法

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

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

需要分三種情況討論。

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

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

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

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

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

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

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

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

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

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

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

（1）將SQL語(yǔ)句改寫，即

order by time offset?X?limit?Y;

改寫成

order by time offset?0?limit?X+Y;

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

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

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

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

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

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

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

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

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

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

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

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

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

方案二：禁止跳頁(yè)查詢法

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

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

（1）將查詢

order by time offset 0 limit 100;

改寫成

order by time where time>0 limit 100;

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

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

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

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

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

（1）將查詢

order by time offset 100 limit 100;

改寫成

order by time where time>$time_max limit 100;

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

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

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

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

而是改寫為

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

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

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

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

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

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

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

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

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

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

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

…

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

offset 9900 limit 100;

改寫為

offset 4950 limit 50;

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

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

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

方案四：二次查詢法

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

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

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;

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

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

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

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

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

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

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

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

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

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

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

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

步驟三：查詢二次改寫

第一次改寫的SQL語(yǔ)句是

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

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

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

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

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

所以查詢改寫為：

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

第二個(gè)分庫(kù)，第一次返回?cái)?shù)據(jù)的最大值是1487501323所以查詢改寫為

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

第三個(gè)分庫(kù)，第一次返回?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è)分庫(kù)返回的數(shù)據(jù)(time, uid)如下：

可以看到：

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

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

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

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

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

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

畫外音：從333往前推演。

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

畫外音：從333往前推演。?

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

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

?

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

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

帥氣不帥氣！！！

總結(jié)

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

方法一：全局視野法

（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條記錄；

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

方法二：禁止跳頁(yè)查詢法

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

（2）每次翻頁(yè)，將

order by time offset X limit Y;

改寫成

order by time where?time>$time_max?limit Y;

以保證每次只返回一頁(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）多頁(yè)返回，找到最小值time_min；

（3）between二次查詢

order by time between $time_min and $time_i_max;

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

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

?

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

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

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的炸！业界难题，跨库分页的几种常见方案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。