炸！业界难题，跨库分页的几种常见方案

为什么需要研究跨库分页?

互联网很多业务都有分页拉取数据的需求，例如：

微信消息过多时，拉取第N页消息;

京东下单过多时，拉取第N页订单;

浏览58同城，查看第N页帖子;

这些业务场景对应的消息表，订单表，帖子表分页拉取需求，都有这样一些共同的特点：

有个业务主键id, msg_id, order_id, tiezi_id;

分页按照非业务主键id来排序，业务中经常按照时间time来排序order by;

在数据量不大时，如何来实现跨库分页的需求呢?

在排序字段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; 

画外音：此处假设一页数据为100条，均拉取第3页数据。

为什么会有分库的需求?

高并发大流量的互联网架构，一般通过服务层来访问数据库，随着数据量的增大，数据库需要进行水平切分，分库后将数据分布到不同的数据库实例(甚至物理机器)上，以达到降低数据量，增加实例数的扩容目的。

一旦涉及分库，逃不开“分库依据” patition key，要使用哪一个字段来水平切分数据库呢?

大部分的业务场景，会使用业务主键id。

确定了分库依据 patition key 后，接下来怎么确定分库算法呢?

大部分的业务场景，会使用业务主键id取模的算法来分库，这样的好处是：

即能够保证每个库的数据分布是均匀的;

又能够保证每个库的请求分布是均匀的;

实在是简单实现负载均衡的好方法，此法在互联网架构中应用颇多。

一个更具体的例子：

用户库user，水平切分后变为两个库：

分库依据patition key是uid;

分库算法是uid取模：uid%2余0的数据会落到db0，uid%2余1的数据会落到db1;

数据库进行了水平切分之后，如果业务要查询“最近注册的第3页用户”，即跨库分页查询，该如何实现呢?

单库上，可以

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

变成两个库后，分库依据是uid，排序依据是time，数据库层失去了time排序的全局视野，数据分布在两个库上，此时该怎么办呢?

如何满足“跨越多个水平切分数据库，且分库依据与排序依据为不同属性，并需要进行分页”的查询需求，实现：

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

这类跨库分页SQL，是后文将要讨论的技术问题。

方案一：全局视野法

如上图所述，服务层通过uid取模将数据分布到两个库上去之后，每个数据库都失去了全局视野，数据按照time局部排序之后，不管哪个分库的第3页数据，都不一定是全局排序的第3页数据。

那到底哪些数据才是全局排序的第3页数据呢?

需要分三种情况讨论。

(1) 极端情况，两个库的数据完全一样

如果两个库的数据完全相同，只需要每个库offset一半，再取半页，就是最终想要的数据(如上图中粉色部分数据)。

(2) 极端情况，结果数据来自一个库

也可能两个库的数据分布及其不均衡，例如db0的所有数据的time都大于db1的所有数据的time，则可能出现：一个库的第3页数据，就是全局排序后的第3页数据(如上图中粉色部分数据)。

(3)一般情况，每个库数据各包含一部分

正常情况下，全局排序的第3页数据，每个库都会包含一部分(如上图中粉色部分数据)。

由于不清楚到底是哪种情况，所以必须：

每个库都返回3页数据;

所得到的6页数据在服务层进行内存排序，得到数据全局视野;

再取第3页数据，便能够得到想要的全局分页数据。

再总结一下这个方案的步骤：

(1) 将SQL语句改写，即

order by time offset X limit Y; 

改写成

order by time offset 0 limit X+Y; 

(2)服务层将改写后的SQL语句发往各个分库;

(3)假设共分为N个库，服务层将得到N*(X+Y)条数据;

(4)服务层对得到的N*(X+Y)条数据进行内存排序;

(5)内存排序后再取偏移量X后的Y条记录，就是全局视野所需的一页数据;

全局视野法有什么优点?

通过服务层修改SQL语句，扩大数据召回量，能够得到全局视野，业务无损，精准返回所需数据。

全局视野法的缺点呢?

缺点显而易见：

每个分库需要返回更多的数据，增大了网络传输量(耗网络);

除了数据库按照time进行排序，服务层还需要进行二次排序，增大了服务层的计算量(耗CPU);