业界难题-“跨库分页”的四种方案学习笔记

微信公共号 [架构师之路] 上看到一篇文章业界难题-“跨库分页”的四种方案，学习了下，一些笔记。

分页需求

互联网很多业务都有分页拉取数据的需求，例如：京东下单过多时，拉取第 N 页订单。

这些业务场景对应的分页拉取需求有这样一些特点：
（1）有一个业务主键, 例如 order_id
（2）分页排序是按照非业务主键来排序的，例如 time

在数据量不大时，可以通过在排序字段 time上建立索引，利用SQL提供的 offset/limit 功能就能满足分页查询需求：
select * from t_order order by time offset 200 limit 100
此处假设一页数据为 100 条，均拉取第 3 页数据

分库需求

随着数据量的增大，数据库需要进行水平切分，分库后将数据分布到不同的数据库实例（甚至物理机器）上。
一旦涉及分库，逃不开 “分库依据” partition key 的概念。
大部分的业务场景，会使用 业务主键 id 取模的算法来分库，这样即能够保证每个库的数据分布是均匀的，又能够保证每个库的请求分布是均匀的。

例如：
用户库 user，水平切分后变为两个库，分库依据 partition key 是 uid。
分库算法是 uid 取模：uid%2 余 0 的数据会落到 db0，uid%2 余 1 的数据会落到 db1。

业务主键 uid 取模的算法来分库

如果业务要查询 “最近注册的第3页用户”，该如何实现呢？
单库上，可以 select * from t_user order by time offset 200 limit 100

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

方案一全局视野法

全局视野法

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

必须每个库都返回全部 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 条记录，就是全局视野所需的一页数据

方案优点：能够得到全局视野，业务无损，精准返回所需数据。
方案缺点：

每个分库需要返回更多的数据

除了数据库按照 time 进行排序，服务层还需要进行二次排序
最致命的，这个算法随着页码的增大，性能会急剧下降

方案二业务折衷法

任何脱离业务的架构设计都是耍流氓，技术方案需要折衷，在技术难度较大的情况下，业务需求的折衷能够极大的简化技术方案。

业务折衷一：禁止跳页查询

在数据量很大，翻页数很多的时候，很多产品并不提供 “直接跳到指定页面” 的功能，而只提供 “下一页” 的功能，这一个小小的业务折衷，就能极大的降低技术方案的复杂度。

禁止跳页查询

如上图，不够跳页，那么第一次只能够查第一页：

将查询 order by time offset 0 limit 100，改写成 order by time where time>0 limit 100

服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第一页数据
点击 “下一页” 时，需要拉取第二页数据，在第一页数据的基础之上，能够找到第一页数据 time 的最大值 time_max
将查询改写成 order by time where time>$time_max limit 100
服务层得到 2 页数据，内存排序，取出前 100 条数据，作为最终的第 2 页数据
依次类推，即使点击 100 次 “下一页”，每次每个数据库也只是返回 100 条数据，服务层每次对 200 条数据做排序。以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。

业务折衷二：允许数据精度损失

使用 partition key 进行分库，在数据量较大，数据分布足够随机的情况下，各分库所有非 partition key 属性，在各个分库上的数据分布，统计概率情况是一致的。

利用这一原理，要查询全局 100 页数据，offset 9900 limit 100 改写为 offset 4950 limit 50，每个分库偏移 4950（一半），获取 50 条数据（半页），得到的数据集的并集，基本能够认为，是全局数据的 offset 9900 limit 100 的数据，当然，这一页数据的精度，并不是精准的。

根据实际业务经验，用户都要查询第 100 页网页、帖子、邮件的数据了，这一页数据的精准性损失，业务上往往是可以接受的，但此时技术方案的复杂度便大大降低了，既不需要返回更多的数据，也不需要进行服务内存排序了。

方案三二次查询法

有点复杂，详见原文。

引用：
业界难题-“跨库分页”的四种方案