分表分页/跨库分页 难玩却不代表没有玩法

分库分表难题（一） 分表分页/跨库分页 难玩却不代表没有玩法
分库分表难题（二） 跨库/跨实例 Join 连接  不是非得依赖中间件

1. 数据水平切分

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

1. 电商商城系统运营端，分页拉取订单列表查看；
2. 贴吧社区系统看帖子，分页拉取帖子的回复；
3. 手机APP右上角的小红点，点开拉取消息列表；

这些业务场景如果用数据库去实现，往往有着这样一些共性：

1. 数据量往往比较大；
2. 一般都会设计业务主键ID；
3. 分页排序并非按主键排序，而是按照创建时间排序；

在数据量不大时，可以通过在排序字段 time 上建立索引，利用 SQL 提供的 offset/limit 功能就能满足分页查询需求：

SELECT * FROM `table` ORDER BY `time` LIMIT #{offset}, #{limit}

分库分表需求

当业务数据达到一定量级（比如：MySql单表记录量大于1千万）后，通常会考虑“分库分表”将数据分散到不同的库或表中（数据的水平切分），这样可以大大提高读/写性能。

高并发大流量的互联网架构，一般通过服务层来访问数据库，随着数据量的增大，数据库需要进行水平切分，分库后将数据分布到不同的数据库实例（甚至物理机器）上，以达到降低数据量，增加实例数的扩容目的。一旦涉及分库，逃不开“分库依据”（patition key） 的概念，使用哪一个字段来水平切分数据库呢：大部分的业务场景，会使用业务主键ID。

确定了分库依据（patition key）后，接下来要确定的是分库算法：大部分的业务场景，会使用 业务主键ID取模的算法 来分库，这样 既能够保证每个库的数据分布是均匀的，又能够保证每个库的请求分布是均匀的，实在是简单实现负载均衡的好方法，此法在互联网架构中应用颇多。

但是问题来了，对于 SELECT * FROM table ORDER BY time LIMIT #{offset}, #{limit} 这种分页方式，原来一条语句就可以简单搞定的事情会变得很复杂，本文将与大家一起探讨分库分表后”分页”面临的新问题。

注意：本文主要探讨“分页”面临的问题（数据水平切分场景），上边只是举了个最简单的分库分表算法例子，实际生产环境中会复杂的多，需要根据具体业务需求来确定分库分表方案。

2. 全局视野法

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

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

如果两个库的数据完全相同，只需要每个库 offset 一半，再取半页，就是最终想要的数据（如图所示）：

（2） 极端情况，结果数据都来自同一个库

也可能两个库的数据分布及其不均衡，例如 db0 的所有数据的 time 都大于 db1 的所有数据的 time，则可能出现：一个库的第 3 页数据，就是全局排序后的第 3 页数据（如图所示）：

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

正常情况下，全局排序的第 3 页数据，每个库都会包含一部分（如图所示）：

由于不清楚到底是哪种情况，所以 必须每个库都返回 3 页数据，所得到的 6 页数据在服务层进行内存排序，得到数据全局视野，再取第 3 页数据，便能够得到想要的全局分页数据。

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

1. 将 order by time offset X limit Y，改写成 order by time offset 0 limit X+Y；
2. 服务层将改写后的 SQL 语句发往各个分库：即例子中的各取 3 页数据；
3. 假设共分为 N 个库，服务层将得到 N*(X+Y) 条数据：即例子中的 6 页数据；
4. 服务层对得到的 N*(X+Y) 条数据进行内存排序，内存排序后再取偏移量 X 后的 Y 条记录，就是全局视野所需的一页数据。

方案优点：

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

方案缺点（显而易见）：

• 每个分库需要返回更多的数据，增大了网络传输量（耗网络）；
• 除了数据库按照 time 进行排序，服务层还需要进行二次排序，增大了服务层的计算量（耗CPU）；
• 最致命的，这个算法随着页码的增大，性能会急剧下降，这是因为 SQL 改写后每个分库要返回 X+Y 行数据：返回第 3 页，offset 中的 X=200；假如要返回第 100 页，offset 中的 X=9900，即每个分库要返回 100 页数据，数据量和排序量都将大增，性能平方级下降。

3. 二次查询法（推荐）

有没有一种技术方案，即能够满足业务的精确需要，无需业务折衷，又高性能的方法呢？这就是接下来要介绍的终极武器：“二次查询法”。

为了方便举例，假设一页只有 5 条数据，查询第 200 页的 SQL 语句为 select * from T order by time offset 1000 limit 5;

步骤一：查询 SQL 改写

将 select * from T order by time offset 1000 limit 5改写为 select * from T order by time offset 500 limit 5, 并投递给所有的分库，注意，这个 offset 的 500，来自于全局offset的总偏移量 1000，除以水平切分数据库个数 2。

如果是 3 个分库，则可以改写为 select * from T order by time offset 333 limit 5，为了更加直观一点，我们按照 3 个分库的例子来演示，并且 time 用简单的 8 位数字来表示（如图所示）：

可以看到，每个分库都是返回的按照 time 排序的一页数据。

步骤二：找到返回 3 页全部数据的最小值

1. 第一个库，5 条数据的 time 最小值是 10000123；
2. 第二个库，5 条数据的 time 最小值是 10000133；
3. 第三个库，5 条数据的 time 最小值是 10000143；

这三页数据中，time 最小值来自第一个库，time_min = 10000123，这个过程只需要比较各个分库第一条数据，时间复杂度很低。

步骤三：查询 SQL 二次改写

第一次改写的 SQL 语句是 select * from T order by time offset 333 limit 5；

第二次要改写成一个 between 语句，between 的起点是 time_min，between 的终点是原来每个分库各自返回数据的最小值（between 是指 >= 和 <=）：

1. 第一个分库，time_min 位于第一个分库，直接不用查询了。
2. 第二个分库，改写为 select * from T order by time where time between time_min and 10000133；
3. 第三个分库，改写为 select * from T order by time where time between time_min and 10000143；

第二次查询，假设这三个分库返回的数据如下（当然我们只需要查询 2 个库）：

步骤四：分析二次查询结果

我们保持 time 排序不变，把二次查询的结果集拼起来，得到一个最新的结果集（如图所示）：

现在我们来做一个简单的思维推理：

1. 我们最初的需求是要 select * from T order by time offset 1000 limit 5；
2. 然后因为分库的原因，我们分别对 3 个分库中 select * from T order by time offset 333 limit 5;
3. 此时我们得到最小值 time_min，所以可以先假设这 3 个分库中比 time_min 小的结果，一共有 333 * 3 = 999 个（SQL 语句第 1 个结果的 offset 是 0， offset = 333 其实是第 334 个结果），所以假设 time_min 的 offset = 999；
4. 如果不进行二次查询，我们无法得到 offset = 1000 ~ 1004 的结果，因为我无法确定在 time_min（10000123） 和（10000133）之间，time_min（10000123） 和（10000143）之间是否存在其它结果，并不能得到全局视野；
5. 进行二次查询，第二个分库，改写为 select * from T order by time where time between time_min and 10000133，第三个分库，改写为 select * from T order by time where time between time_min and 10000143，得到全局视野，我们就能在内存中排序进行标号；
6. 进行二次查询以前，假设比 time_min 小的结果一共有 999 个，由于二次查询出了结果，（10000132，10000141，10000142）三个结果是算在我们假设的 999 个之中的，也就是这三个结果需要后移，此时 time_min 的 offset = 996 = 999 – 3；

步骤五：全局视野结果标号

得到了 time_min 在全局的 offset，就相当于有了全局视野，根据总共二次的结果集，就能够得到全局offset 1000 limit 5 的记录。

方案优点：

• 可以精确的返回业务所需数据，每次返回的数据量都非常小，不会随着翻页增加数据的返回量。

方案缺点：

• 需要进行两次数据库查询，对数据库存在一定的消耗，但比全局视野法的网络和CPU的消耗少。

分库分表难题（一） 分表分页/跨库分页 难玩却不代表没有玩法
分库分表难题（二） 跨库/跨实例 Join 连接  不是非得依赖中间件