原文：http://mp.weixin.qq.com/s/h99sXP4mvVFsJw6Oh3aU5A

• 一、需求缘起
  • 分页需求
  • 分库需求
  • 问题的提出
• 二、全局视野法
• 三、业务折衷法
  • 业务折衷一：禁止跳页查询
  • 业务折衷二：允许数据精度损失
• 四、终极武器-二次查询法（笔记者认为有问题，但思想可以借鉴）
  • 步骤一：查询改写
  • 步骤二：找到所返回3页全部数据的最小值
  • 步骤三：查询二次改写
  • 步骤四：在每个结果集中虚拟一个time_min记录，找到time_min在全局的offset
  • 步骤五：既然得到了time_min在全局的offset，就相当于有了全局视野，根据第二次的结果集，就能够得到全局offset 1000 limit 5的记录
• 五、总结
  • 方法一：全局视野法
  • 方法二：业务折衷法禁止跳页查询
  • 方法三：业务折衷法-允许模糊数据
  • 方法四：二次查询法（笔记者认为有问题，但思想可以借鉴）

一、需求缘起

分页需求

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

1. 微信消息过多时，拉取第N页消息
2. 京东下单过多时，拉取第N页订单
3. 浏览58同城，查看第N页帖子

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

1. 有一个业务主键id, 例如msg_id, order_id, tiezi_id
2. 分页排序是按照非业务主键id来排序的，业务中经常按照时间time来排序order by

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

分库需求

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

一旦涉及分库，逃不开“分库依据”patition key的概念，使用哪一个字段来水平切分数据库呢：大部分的业务场景，会使用业务主键id。

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

问题的提出

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

二、全局视野法

必须每个库都返回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语句，扩大数据召回量，能够得到全局视野，业务无损，精准返回所需数据。

方案缺点（显而易见）：

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

三、业务折衷法

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

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

查询全局视野第100页数据时，不是将查询条件改写为offset 0 limit 9900+100（返回100页数据），而是改写为time>$time_max99 limit 100（仍返回一页数据），以保证数据的传输量和排序的数据量不会随着不断翻页而导致性能下降。

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

“全局视野法”能够返回业务无损的精确数据，在查询页数较大，例如第100页时，会有性能问题，此时业务上是否能够接受，返回的100页不是精准的数据，而允许有一些数据偏差呢？

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

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

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

四、终极武器-二次查询法（笔记者认为有问题，但思想可以借鉴）

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

步骤一：查询改写

将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

每个分库都是返回的按照time排序的一页数据。

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

第一个库，5条数据的time最小值是1487501123

第二个库，5条数据的time最小值是1487501133

第三个库，5条数据的time最小值是1487501143

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

步骤三：查询二次改写

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

第二次要改写成一个between语句，between的起点是time_min，between的终点是原来每个分库各自返回数据的最大值：

• 第一个分库，第一次返回数据的最大值是1487501523，所以查询改写为select * from T order by time where time between time_min and 1487501523
• 第二个分库，第一次返回数据的最大值是1487501323，所以查询改写为select * from T order by time where time between time_min and 1487501323
• 第三个分库，第一次返回数据的最大值是1487501553，所以查询改写为select * from T order by time where time between time_min and 1487501553

相对第一次查询，第二次查询条件放宽了，故第二次查询会返回比第一次查询结果集更多的数据，可以看到：

• 由于time_min来自原来的分库一，所以分库一的返回结果集和第一次查询相同（所以其实这次访问是可以省略的）；
• 分库二的结果集，比第一次多返回了1条数据，头部的1条记录（time最小的记录）是新的；
• 分库三的结果集，比第一次多返回了2条数据，头部的2条记录（time最小的2条记录）是新的；

步骤四：在每个结果集中虚拟一个time_min记录，找到time_min在全局的offset

• 在第一个库中，time_min在第一个库的offset是333
• 在第二个库中，(1487501133, uid_aa)的offset是333（根据第一次查询条件得出的），故虚拟time_min在第二个库的offset是331
• 在第三个库中，(1487501143, uid_aaa)的offset是333（根据第一次查询条件得出的），故虚拟time_min在第三个库的offset是330

综上，time_min在全局的offset是333+331+330=994

步骤五：既然得到了time_min在全局的offset，就相当于有了全局视野，根据第二次的结果集，就能够得到全局offset 1000 limit 5的记录

第二次查询在各个分库返回的结果集是有序的，又知道了time_min在全局的offset是994，一路排下来，容易知道全局offset 1000 limit 5的一页记录

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

不足：需要进行两次数据库查询。

五、总结

方法一：全局视野法

1. 将order by time offset X limit Y，改写成order by time offset 0 limit X+Y
2. 服务层对得到的N*(X+Y)条数据进行内存排序，内存排序后再取偏移量X后的Y条记录这种方法随着翻页的进行，性能越来越低。

方法二：业务折衷法禁止跳页查询

1. 用正常的方法取得第一页数据，并得到第一页记录的time_max
2. 每次翻页，将order by time offset X limit Y，改写成order by time where time>$time_max limit Y以保证每次只返回一页数据，性能为常量。

方法三：业务折衷法-允许模糊数据

1. 将order by time offset X limit Y，改写成order by time offset X/N limit Y/N

方法四：二次查询法（笔记者认为有问题，但思想可以借鉴）

1. 将order by time offset X limit Y，改写成order by time offset X/N limit Y
2. 找到最小值time_min
3. between二次查询，order by time between $time_min and $time_i_max
4. 设置虚拟time_min，找到time_min在各个分库的offset，从而得到time_min在全局的offset
5. 得到了time_min在全局的offset，自然得到了全局的offset X limit Y

---