分页分库问题

本文主要是介绍分页分库问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分页身影多如狗

当你使用淘宝、京东购物的时候,是否浏览到某一个地方,网页突然重新加载等待了一番？
当你晚上躲在小被窝看小说的时候, 是否有时候你需要下拉刷新一把, 有的小说只需要按个箭头跳到下一个章节？

没错儿,这就是随处可见的分页技术！

这些场景对应的产品推荐表、帖子表、标签等都是分页信息拉取技术问题范围,其特点就是：

需要访问的消息量太大了,如果一次都给你,那只能让你feel到等女友化妆出门的感觉；

聪明的猿哥哥帮你想了个办法,他不会一次性把所有消息都给你,你只需稍等片刻就可以先看到一些猿哥哥觉得你比较关注的东西,如果觉得不够,就再给你一些,也有可能你厌烦了猿哥哥的消息,悻悻而去

换成SQL语言,可以这么表达一下：

select * from T order by ID limit X, Y
select * from T order by ID limit Y offset X

使用ID字段建立一个排序索引,然后获取跳过X条数据获取接下来的Y条数据

但真正到业务上实现的时候也许更加复杂：

可能对time对排序开销非常大,不得不减小一次排序的记录数（实际上就又牵扯到分库问题）
有些数据库或者搜索引擎可能会提前为ID字段索引
甚至有些系统可能会为已经索引好的信息内容进行预加载（缓存到内存）
…

分库问题遍地走

简单业务或数据了较小的业务表可能大概一般不需要关注分库问题,但在大型互联网架构平台上,为了应对复杂的庞大的数据冲击以及访问体验, 单单提供更强劲的硬件是不行的（也收获不大）,往往要对数据处理逻辑在设计上做出优化。

例如,庞大的数据量进行水平切分,按照一定的逻辑分不到不同的数据库或其他存储载体中去。

提到分库,逃不开“分库依据”（partition key）这个概念,大部分的业务场景,都会选择业务主键id来处理这个问题。

这就涉及到了分库算法,大部分的做法就是使用id来做取模或者hash来保证数据均匀的分布到不同的存储载体中去。

还是SQL的例子：

select * from T order by ID limit Y offset X

分库之后,这个问题发生了变化,因为ID被hash到不同的库表中去了,利用ID进行全局数据的查询就失去了视野。

比如,我们有一些数据,暂且嘉定为：（1,2,3,4,5,6,7,8）

现在我们要取出2,3这两个数据,只需要limit 1,2就行了

现在假设按2取模分成了两段数据：（1,3,5,7）、（2,4,6,8）

(1,3,5,7)=> limit 1,2 =>(3,5)
(2,4,6,8)=> limit 1,2 =>(4,6)

然后内存合并排序后取前两个的到了（3,4）,不是我们想要的结果,有人说了,你不能仍然简单的在分表中使用limit 1,2了。

是的,那这个问题就麻烦一些了,我是否应该先limit 0, 1+2呢？

(1,3,5,7)=> limit 0,3 =>(1,3,5)
(2,4,6,8)=> limit 0,3 =>(2,4,6)

然后内存中合并使用limit 1,2的到了（3,4）,这样倒是满足了。

也就是说：每个库都必须返回 X+Y 个数据，所得到的 M*(X+Y) 在服务层进行内存排序，然后再取总的偏移量X后的Y条记录。

但再想一想,如果我们的数据量仍然比较大,（1,2,…10亿）

而我们可能需要的到10亿-1这个数所在的页,资源消耗是不是很大呢？

我们也可以看看业界对这个问题都是怎么考虑的

关于如何解决这个问题,业界一般有下列几种方案。

1. 全局视野法

也就是我们上面讨论的方法。

服务层通过id取模将数据分布到两个库上去之后，每个数据库都失去了全局视野，数据按照某个partition id局部排序之后，不管哪个分库的第n页数据，都不一定是全局排序的第n页数据。极端情况下，甚至所有的结果数据只来自某一个库；也有可能两个库的数据分布及其不均衡，一些结果数据来自第一个库的后半段，而另一些数据来自另一个库的前半段。

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

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

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

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

方案缺点：

每个分库需要返回更多的数据，占用网络带宽
需要服务层的计算
这个算法随着页码的增大（即X的增大），性能平方级下降。

2. 业务折衷法

“全局视野法”虽然性能较差，但其业务无损，数据精准，不失为一种方案，有没有性能更优的方案呢？

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

业务折衷1: 禁止跳页查询

只能查第一页，如果想要得到的数据不在两个分表的第一页，那就算了…
个人感觉神经大条的想法，但可能在某些场景也很实用, 比如限定查找销量排名前5的商品, 其他的不需要看；也可能根据需要最多再多指定一些页面, 比如我通过谷歌浏览器查找某个信息, 当查到第三个页的时候还没有看到想要的信息，那我就不再看了。

业务折衷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上应该是相同的统计规律

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

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

这种情况下，只能limit 0, x；

3. 二次查询法-推荐

假设一页只有5条数据
假设原始表T的数据按照PID分成了3个分库
假设要查询第200个页面, 也就是原有序表的offset为995的数据
步骤：

查询改写: 将select * from T order by PID offset 995 limit 5 改写为 select * from T order by offset ceil(995/3)=332 limit 5
找出3个子序列页面数据的最小值, 假设分别为100234、112121、101546, 再找到这3个子序列最小值的最小值100234
找到3个子序列页面数据的最大值, 假设分别为114567、123465、119987
查询二次改写: 第二次要改写成一个between语句，between的起点是100234，between的终点各个分库页面的最大值
即:
对于第1个分库(5条数据): select * from T order by offset 100234 and 114567
对于第1个分库(10条数据):: select * from T order by offset 100234 and 123465
对于第2个分库(7条数据): select * from T order by offset 100234 and 119987
即：
相对于第一次查询, 第二次查询的条件放宽了, 故第二次查询会比第一次查询返回更多的分页数据
在每个新的分页结果中虚拟一个PID-min记录(也就是100234), 找到它在全局的offset
例如：
对于第1个分库: 假设100234在第一个库的offset是332
对于第2个分库: 假设100234在第一个库的offset是328
对于第3个分库: 假设100234在第一个库的offset是330
综上: 100234在全局的offset就是332+328+330=990
既然100234在全局的offset为990, 也就是相当于有了全局视野, 根据第二次的分页结果集合, 计算排序就能得到全局offset=995的一页记录