首页 > 图灵资讯 > java面试题>正文
分库分表下如何实现精准分页？
2024-06-11 13:08:13
前言
随着互联网的快速发展，各大互联网公司的业务数据也随之爆发式增长。在这个过程中，数据库面临着越来越大的压力，单表记录数量庞大已经成为常态。
为了应对这种挑战，分库分表成为了一种常见的解决方案。通过将数据分散存储到不同的库或表中，可以有效地提高数据库的读写性能，并且能够更好地支撑高并发大流量的业务场景。
然而，分库分表带来了新的问题，特别是在涉及到复杂的查询操作，比如分页查询时。
在接下来的讨论中，我们将重点探讨数据水平切分背景下的分页查询问题。
场景
互联网中许多业务都需要进行分页拉取数据，比如电商商城系统的订单列表、贴吧社区系统的帖子回复、以及手机APP消息列表等。
这些业务场景通常具有以下共性：数据量大、使用业务主键ID、分页排序通常不是按照主键排序，而是按照创建时间排序。
在数据量较小的情况下，可以通过在排序字段时间上建立索引，利用SQL提供的offset/limit功能来满足分页查询需求。
服务层通过 id 取模将数据分布到两个库上去之后，每个数据库都失去了全局视野，数据按照 time 局部排序之后，不管哪个分库的第 3 页数据，都不一定是全局排序的第 3 页数据。
场景一（极端情况）：两个库的数据完全一样
如果两个库的数据完全相同，只需要每个库 offset 一半，再取半页，就是最终想要的数据：
场景二（极端情况）：结果数据都来自同一个库
也可能两个库的数据分布及其不均衡，例如 db0 的所有数据的 time 都大于 db1 的所有数据的 time，则可能出现：一个库的第 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 页数据，数据量和排序量都将大增，性能平方级下降。
2. 业务折衷法
“全局视野法”虽然性能较差，但其业务无损，数据精准，但是它的性能不稳定，因此有没有性能更优的方案呢？ 有，继续往下看
方案一：禁止跳页查询
在数据量很大，翻页数很多的时候，很多产品并不提供“直接跳到指定页面”的功能，而只提供“下一页”的功能，这一个小小的业务折衷，就能极大的降低技术方案的复杂度。
假设现在不允许跳页，那么第一次只能够查第一页：
1.将查询 order by time offset 0 limit 100，改写成 order by time where time > 0 limit 100；
2.上述改写和 offset 0 limit 100 的效果相同，都是每个分库返回了一页数据；
3.服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第一页数据，这个全局的第一页数据，一般来说每个分库都包含一部分数据；
疑问：这个方案也需要服务器内存排序，岂不是和“全局视野法”一样么？
第一页数据的拉取确实一样，但每一次“下一页”拉取的方案就不一样了。
点击“下一页”时，需要拉取第二页数据，在第一页数据的基础之上，能够找到第一页数据 time 的最大值：
这个上一页记录的 time_max，会作为第二页数据拉取的查询条件：
1.将查询 order by time offset 100 limit 100，改写成 order by time where time > > $time_max limit 100；
2.这下不是返回 2 页数据了（“全局视野法，会改写成 offset 0 limit 200”），每个分库还是返回一页数据；
3.服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第 2 页数据，这个全局的第 2 页数据，一般来说也是每个分库都包含一部分数据；
4.如此往复，查询全局视野第 100 页数据时，不是将查询条件改写为 offset 0 limit 9900+100（返回 100 页数据），而是改写为 time > $time_max99 limit 100（每个分库还是返回一页数据），以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。
方案二：允许数据精度损失
“全局视野法”能够返回业务无损的精确数据，而如果说业务不需要非常精准的数据，那这个时候就能就可以换一种方案了。
数据库分库-数据均衡原理
使用 partition key 进行分库，在数据量较大，数据分布足够随机的情况下，各分库所有非 partition key 属性，在各个分库上的数据分布，统计概率情况是一致的。
例如，在 uid 随机的情况下，使用 uid 取模分两库，db0 和 db1：
1.性别属性，如果 db0 库上的男性用户占比 70%，则 db1 上男性用户占比也应为 70% ;
2.年龄属性，如果 db0 库上 18-28 岁少女用户比例占比 15%，则 db1 上少女用户比例也应为 15% ;
3.时间属性，如果 db0 库上每天 10:00 之前登录的用户占比为 20%，则 db1 上应该是相同的统计规律 ;
利用这一原理，要查询全局 100 页数据，offset 9900 limit 100 改写为 offset 4950 limit 50，每个分库偏移 4950（一半），获取 50 条数据（半页），得到的数据集的并集，基本能够认为，是全局数据的offset 9900 limit 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 个库）：adf
步骤四：分析二次查询结果
我们保持 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的消耗少。
随着互联网的快速发展，各大互联网公司的业务数据也随之爆发式增长。在这个过程中，数据库面临着越来越大的压力，单表记录数量庞大已经成为常态。
为了应对这种挑战，分库分表成为了一种常见的解决方案。通过将数据分散存储到不同的库或表中，可以有效地提高数据库的读写性能，并且能够更好地支撑高并发大流量的业务场景。
然而，分库分表带来了新的问题，特别是在涉及到复杂的查询操作，比如分页查询时。
在接下来的讨论中，我们将重点探讨数据水平切分背景下的分页查询问题。
场景
互联网中许多业务都需要进行分页拉取数据，比如电商商城系统的订单列表、贴吧社区系统的帖子回复、以及手机APP消息列表等。
这些业务场景通常具有以下共性：数据量大、使用业务主键ID、分页排序通常不是按照主键排序，而是按照创建时间排序。
在数据量较小的情况下，可以通过在排序字段时间上建立索引，利用SQL提供的offset/limit功能来满足分页查询需求。
SELECT * FROM `table` ORDER BY `time` LIMIT #{offset}, #{limit}1.
1. 全局视野法
| 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) |
场景一（极端情况）：两个库的数据完全一样
如果两个库的数据完全相同，只需要每个库 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) |
也可能两个库的数据分布及其不均衡，例如 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 页数据，每个库都会包含一部分：
| 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.将 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 页数据，数据量和排序量都将大增，性能平方级下降。
2. 业务折衷法
“全局视野法”虽然性能较差，但其业务无损，数据精准，但是它的性能不稳定，因此有没有性能更优的方案呢？ 有，继续往下看
方案一：禁止跳页查询
在数据量很大，翻页数很多的时候，很多产品并不提供“直接跳到指定页面”的功能，而只提供“下一页”的功能，这一个小小的业务折衷，就能极大的降低技术方案的复杂度。
假设现在不允许跳页，那么第一次只能够查第一页：
1.将查询 order by time offset 0 limit 100，改写成 order by time where time > 0 limit 100；
2.上述改写和 offset 0 limit 100 的效果相同，都是每个分库返回了一页数据；
3.服务层得到 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) |
1.将查询 order by time offset 100 limit 100，改写成 order by time where time > > $time_max limit 100；
2.这下不是返回 2 页数据了（“全局视野法，会改写成 offset 0 limit 200”），每个分库还是返回一页数据；
3.服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第 2 页数据，这个全局的第 2 页数据，一般来说也是每个分库都包含一部分数据；
4.如此往复，查询全局视野第 100 页数据时，不是将查询条件改写为 offset 0 limit 9900+100（返回 100 页数据），而是改写为 time > $time_max99 limit 100（每个分库还是返回一页数据），以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。
方案二：允许数据精度损失
“全局视野法”能够返回业务无损的精确数据，而如果说业务不需要非常精准的数据，那这个时候就能就可以换一种方案了。
数据库分库-数据均衡原理
使用 partition key 进行分库，在数据量较大，数据分布足够随机的情况下，各分库所有非 partition key 属性，在各个分库上的数据分布，统计概率情况是一致的。
例如，在 uid 随机的情况下，使用 uid 取模分两库，db0 和 db1：
1.性别属性，如果 db0 库上的男性用户占比 70%，则 db1 上男性用户占比也应为 70% ;
2.年龄属性，如果 db0 库上 18-28 岁少女用户比例占比 15%，则 db1 上少女用户比例也应为 15% ;
3.时间属性，如果 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) |
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 位数字来表示：
| 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 |
步骤二：找到返回 3 页全部数据的最小值
1.第一个库，5 条数据的 time 最小值是 10000123；
2.第二个库，5 条数据的 time 最小值是 10000133；
3.第三个库，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 |
步骤三：查询 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 个库）：adf
| 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 |
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 的记录。
| 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的消耗少。