分表分页/跨库分页 难玩却不代表没有玩法
白菜Java自习室 涵盖核心知识
分库分表难题（一） 分表分页/跨库分页 难玩却不代表没有玩法 分库分表难题（二） 跨库/跨实例 Join 连接 不是非得依赖中间件
1. 数据水平切分
互联网很多业务都有分页拉取数据的需求，例如：
- 电商商城系统运营端，分页拉取订单列表查看；
- 贴吧社区系统看帖子，分页拉取帖子的回复；
- 手机APP右上角的小红点，点开拉取消息列表；
这些业务场景如果用数据库去实现，往往有着这样一些共性：
- 数据量往往比较大；
- 一般都会设计业务主键ID；
- 分页排序并非按主键排序，而是按照创建时间排序；
在数据量不大时，可以通过在排序字段 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 页数据。
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1 | db1-page1 |
| db0-page2 | db1-page2 |
| db0-page3 | db1-page3 |
| ... (order by time) | ... (order by time) |
（1） 极端情况，两个库的数据完全一样
如果两个库的数据完全相同，只需要每个库 offset 一半，再取半页，就是最终想要的数据（如图所示）：
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1 | db1-page1 |
| db0-page2 | db1-page2 |
| db0-page3（取一半） | db1-page3（取一半） |
| ... (order by time) | ... (order by time) |
（2） 极端情况，结果数据都来自同一个库
也可能两个库的数据分布及其不均衡，例如 db0 的所有数据的 time 都大于 db1 的所有数据的 time，则可能出现：一个库的第 3 页数据，就是全局排序后的第 3 页数据（如图所示）：
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1 | db1-page1 |
| db0-page2 | db1-page2 |
| db0-page3（同一个库） | db1-page3 |
| ... (order by time) | ... (order by time) |
（3） 一般情况，每个库数据各包含一部分
正常情况下，全局排序的第 3 页数据，每个库都会包含一部分（如图所示）：
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1 | db1-page1 |
| db0-page2（包含部分） | db1-page2 |
| db0-page3 | db1-page3（包含部分） |
| ... (order by time) | ... (order by time) |
由于不清楚到底是哪种情况，所以 必须每个库都返回 3 页数据，所得到的 6 页数据在服务层进行内存排序，得到数据全局视野，再取第 3 页数据，便能够得到想要的全局分页数据。
总结一下这个方案的步骤：
- 将
order by time offset X limit Y，改写成order by time offset 0 limit X+Y；- 服务层将改写后的 SQL 语句发往各个分库：即例子中的各取 3 页数据；
- 假设共分为 N 个库，服务层将得到 N*(X+Y) 条数据：即例子中的 6 页数据；
- 服务层对得到的 N*(X+Y) 条数据进行内存排序，内存排序后再取偏移量 X 后的 Y 条记录，就是全局视野所需的一页数据。
方案优点：
- 通过服务层修改 SQL 语句，扩大数据召回量，能够得到全局视野，业务无损，精准返回所需数据。
方案缺点（显而易见）：
- 每个分库需要返回更多的数据，增大了网络传输量（耗网络）；
- 除了数据库按照 time 进行排序，服务层还需要进行二次排序，增大了服务层的计算量（耗CPU）；
- 最致命的，这个算法随着页码的增大，性能会急剧下降，这是因为 SQL 改写后每个分库要返回 X+Y 行数据：返回第 3 页，offset 中的 X=200；假如要返回第 100 页，offset 中的 X=9900，即每个分库要返回 100 页数据，数据量和排序量都将大增，性能平方级下降。
3. 业务折衷法
“全局视野法”虽然性能较差，但其业务无损，数据精准，不失为一种方案，有没有性能更优的方案呢？ “任何脱离业务的架构设计都是耍流氓”，技术方案需要折衷，在技术难度较大的情况下，业务需求的折衷能够极大的简化技术方案。
（1） 业务折衷一：禁止跳页查询
在数据量很大，翻页数很多的时候，很多产品并不提供“直接跳到指定页面”的功能，而只提供“下一页”的功能，这一个小小的业务折衷，就能极大的降低技术方案的复杂度。
如图所示，不允许跳页，那么第一次只能够查第一页：
- 将查询
order by time offset 0 limit 100，改写成order by time where time > 0 limit 100;- 上述改写和
offset 0 limit 100的效果相同，都是每个分库返回了一页数据（如图所示）；- 服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第一页数据，这个全局的第一页数据，一般来说每个分库都包含一部分数据（如图所示）；
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1（第一页） | db1-page1（第一页） |
| db0-page2 | db1-page2 |
| db0-page3 | db1-page3 |
| ... (order by time) | ... (order by time) |
疑问：这个方案也需要服务器内存排序，岂不是和“全局视野法”一样么？第一页数据的拉取确实一样，但每一次“下一页”拉取的方案就不一样了。
点击“下一页”时，需要拉取第二页数据，在第一页数据的基础之上，能够找到第一页数据 time 的最大值：
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1（time 最大值） | db1-page1 |
| db0-page2 | db1-page2（time 最大值） |
| db0-page3 | db1-page3 |
| ... (order by time) | ... (order by time) |
这个上一页记录的 time_max，会作为第二页数据拉取的查询条件：
- 将查询
order by time offset 100 limit 100，改写成order by time where time > > $time_max limit 100；- 这下不是返回 2 页数据了（“全局视野法，会改写成
offset 0 limit 200”），每个分库还是返回一页数据（如图所示）；- 服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第 2 页数据，这个全局的第 2 页数据，一般来说也是每个分库都包含一部分数据（如图所示）；
- 如此往复，查询全局视野第 100 页数据时，不是将查询条件改写为
offset 0 limit 9900+100（返回 100 页数据），而是改写为time > $time_max99 limit 100（每个分库还是返回一页数据），以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。
（2） 业务折衷二：允许数据精度损失
“全局视野法”能够返回业务无损的精确数据，在查询页数较大，例如第 100 页时，会有性能问题，此时业务上是否能够接受，返回的 100 页不是精准的数据，而允许有一些数据偏差呢？
数据库分库-数据均衡原理
使用 patition key 进行分库，在数据量较大，数据分布足够随机的情况下，各分库所有非 patition key 属性，在各个分库上的数据分布，统计概率情况是一致的。
例如，在 uid 随机的情况下，使用 uid 取模分两库，db0 和 db1：
- 性别属性，如果 db0 库上的男性用户占比 70%，则 db1 上男性用户占比也应为 70% ;
- 年龄属性，如果 db0 库上 18-28 岁少女用户比例占比 15%，则 db1 上少女用户比例也应为 15% ;
- 时间属性，如果 db0 库上每天 10:00 之前登录的用户占比为 20%，则 db1 上应该是相同的统计规律 ;
| database1 (id%2=0) | database2 (id%2=1) |
|---|---|
| db0-page1 | db1-page1 |
| db0-page2 | db1-page2 |
| db0-page3（取一半） | db1-page3（取一半） |
| ... (order by time) | ... (order by time) |
利用这一原理，要查询全局 100 页数据，
offset 9900 limit 100改写为offset 4950 limit 50，每个分库偏移 4950（一半），获取 50 条数据（半页），得到的数据集的并集，基本能够认为，是全局数据的offset 9900 limit 100的数据，当然，这一页数据的精度，并不是精准的。
根据实际业务经验，用户都要查询第 100 页网页、帖子、邮件的数据了，这一页数据的精准性损失，业务上往往是可以接受的，但此时技术方案的复杂度便大大降低了，既不需要返回更多的数据，也不需要进行服务内存排序了。
4. 二次查询法（推荐）
有没有一种技术方案，即能够满足业务的精确需要，无需业务折衷，又高性能的方法呢？这就是接下来要介绍的终极武器：“二次查询法”。
为了方便举例，假设一页只有 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 位数字来表示（如图所示）：
| database1 (id%3=0) | database2 (id%3=1) | database3 (id%3=2) |
|---|---|---|
| 10000123 | 10000133 | 10000143 |
| 10000223 | 10000233 | 10000243 |
| 10000323 | 10000333 | 10000343 |
| 10000423 | 10000433 | 10000443 |
| 10000523 | 10000533 | 10000543 |
可以看到，每个分库都是返回的按照 time 排序的一页数据。
步骤二：找到返回 3 页全部数据的最小值
- 第一个库，5 条数据的 time 最小值是 10000123；
- 第二个库，5 条数据的 time 最小值是 10000133；
- 第三个库，5 条数据的 time 最小值是 10000143；
| database1 (id%3=0) | database2 (id%3=1) | database3 (id%3=2) |
|---|---|---|
| 10000123（最小值） | 10000133 | 10000143 |
| 10000223 | 10000233 | 10000243 |
| 10000323 | 10000333 | 10000343 |
| 10000423 | 10000433 | 10000443 |
| 10000523 | 10000533 | 10000543 |
这三页数据中，time 最小值来自第一个库，time_min = 10000123，这个过程只需要比较各个分库第一条数据，时间复杂度很低。
步骤三：查询 SQL 二次改写
第一次改写的 SQL 语句是 select * from T order by time offset 333 limit 5 ；
第二次要改写成一个 between 语句，between 的起点是 time_min，between 的终点是原来每个分库各自返回数据的最小值（between 是指 >= 和 <=）：
- 第一个分库，time_min 位于第一个分库，直接不用查询了。
- 第二个分库，改写为
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；
第二次查询，假设这三个分库返回的数据如下（当然我们只需要查询 2 个库）：
| database1 (id%3=0) | database2 (id%3=1) | database3 (id%3=2) |
|---|---|---|
| - | - | 10000141 |
| - | 10000132 | 10000142 |
| 10000123 | 10000133 | 10000143 |
步骤四：分析二次查询结果
我们保持 time 排序不变，把二次查询的结果集拼起来，得到一个最新的结果集（如图所示）：
| database1 (id%3=0) | database2 (id%3=1) | database3 (id%3=2) |
|---|---|---|
| - | - | 10000141（第二次） |
| - | 10000132（第二次） | 10000142（第二次） |
| 10000123 | 10000133 | 10000143 |
| 10000223 | 10000233 | 10000243 |
| 10000323 | 10000333 | 10000343 |
| 10000423 | 10000433 | 10000443 |
| 10000523 | 10000533 | 10000543 |
现在我们来做一个简单的思维推理：
- 我们最初的需求是要
select * from T order by time offset 1000 limit 5；- 然后因为分库的原因，我们分别对 3 个分库中
select * from T order by time offset 333 limit 5;- 此时我们得到最小值 time_min，所以可以先假设这 3 个分库中比 time_min 小的结果，一共有 333 * 3 = 999 个（SQL 语句第 1 个结果的 offset 是 0， offset = 333 其实是第 334 个结果），所以假设 time_min 的 offset = 999；
- 如果不进行二次查询，我们无法得到 offset = 1000 ~ 1004 的结果，因为我无法确定在 time_min（10000123） 和（10000133）之间，time_min（10000123） 和（10000143）之间是否存在其它结果，并不能得到全局视野；
- 进行二次查询，第二个分库，改写为
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，得到全局视野，我们就能在内存中排序进行标号；- 进行二次查询以前，假设比 time_min 小的结果一共有 999 个，由于二次查询出了结果，（10000132，10000141，10000142）三个结果是算在我们假设的 999 个之中的，也就是这三个结果需要后移，此时 time_min 的 offset = 996 = 999 - 3；
步骤五：全局视野结果标号
得到了 time_min 在全局的 offset，就相当于有了全局视野，根据总共二次的结果集，就能够得到全局offset 1000 limit 5 的记录。
| database1 (id%3=0) | database2 (id%3=1) | database3 (id%3=2) |
|---|---|---|
| - | - | 10000141（offset=999） |
| - | 10000132（offset=997） | 10000142（offset=1000） |
| 10000123（offset=996） | 10000133（offset=998） | 10000143（offset=1001） |
| 10000223（offset=1002） | 10000233（offset=1003） | 10000243（offset=1004） |
| 10000323（offset=......） | 10000333 | 10000343 |
| 10000423 | 10000433 | 10000443 |
| 10000523 | 10000533 | 10000543 |
方案优点：
- 可以精确的返回业务所需数据，每次返回的数据量都非常小，不会随着翻页增加数据的返回量。
方案缺点：
- 需要进行两次数据库查询，对数据库存在一定的消耗，但比全局视野法的网络和CPU的消耗少。
分库分表难题（一） 分表分页/跨库分页 难玩却不代表没有玩法 分库分表难题（二） 跨库/跨实例 Join 连接 不是非得依赖中间件
转载自:https://juejin.cn/post/6981996965353488415