Py学习  »  DATABASE

面试官:MySQL 跨库分页、分表分页之后,面临的一些新问题

IT牧场 • 2 年前 • 231 次点击  

点击下方“IT牧场”,选择“设为星标”

来源:cnblogs.com/yjmyzz/p/12149737.html

当业务数据达到一定量级(比如:mysql单表记录量 > 1千万)后,通常会考虑“分库分表”将数据分散到不同的库或表中,这样可以大大提高读/写性能。但是问题来了,对于select * from table limit offset , pagesize这种分页方式,原来一条语句就可以简单搞定的事情会变得很复杂,本文将与大家一起探讨分库分表后"分页"面临的新问题。

分表对分页的影响

比如有一张表,里面有8条记录(为简单起见,假设该表上只有 1 个自增 ID),数学上可以抽象成 1 个(有序)数列(注:为方便讨论,不加特殊说明的情况下,文本中数列的顺序,均指升序)。

(1,2,3,4,5,6,7,8)

如果要取出上面红色标识的 2,3 这二条记录,limit 1,2 就行了。

现在假如分成 2 张表(即:原来的数列,拆分成2个非空子数列),一般来讲,有二种常用分法:

分段法

分段法(比如:有时间属性的数据,类似订单这种,可以按下单时间拆分,每个月1张表)

(1,2,3,4)

(5,6,7,8)

沿用之前的 limit x,y 的思路,每个分表上 limit 1,2,会得到如下 2 个子数列:

(2,3)

(6,7)

然后在内存中合并排序,再取前 2 条(2,3,6,7) => (2,3),貌似看上去也符合预期(这个思路也称为归并),但这只是假象。当要取的分页数据落在不同的子数列上时,就能发现问题:

(1,2,3,4,5,6,7,8)比如,我们要从 4 个位置开始,连续取2个元素,即: limit 3,2

(1,2,3,4) => limit 3,2 =>(4)

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

最后合并出来的结果是(4,8) 与正确结果 (4,5)相比,显然不对。

1.2 模余均摊法(比如:字段值对2取模求余数,根据余数决定分到哪个表,该方法也简称为取余法)

(1,3,5,7)

(2,4,6,8)

归并排序的思路在分段法上行不通,对于取模均摊同样也不行,仍以 limit 1,2为例,原始序列取出来的结果是(2,3),如果用归并的思路:

(1,3,5,7)=> limit 1,2 =>(3 ,5)

(2,4,6,8)=> limit 1,2 =>(4, 6)

内存合并排序后,取前 2 个,最终结果为(3 , 4)

结论:不管分库分表采用什么分法,简单归并的思路,都无法正确解决分页问题。

全局法(limit x+y)

反思一下刚才的归并思路,本质上我们在每个子数列(即:分表)上limit x,y 时,取出来的数据就有可能已经产生缺失了。这里提出了一个方案:把范围扩大,分表 sql 上的limit x,y变成limit 0, x+y,这样改写后,相当于分表中把"每页最后一条数据"之前的所有数据全都取出来了(当然:这里面可能会有不需要的多余数据),然后内存中合并在一起,再取 x 偏移量后的 y 条数据。

用前面的例子验证一下:

原序列:(1,2,3,4,5,6,7,8),需要取出limit 1,2,即:(2,3)

按分段法拆成 2 段:

(1 ,  2 , 3 , 4) => limit 1,2 => 改写成limit 0, 1+2 => (1,2,3)

(5 , 6 , 7 , 8) => limit 1,2 => 改写成limit 0, 1+2 => (5,6,7)

将子数列合并排序=>{ 1,2,3,5,6,7}=> 按原始偏移量limit 1,2 =>{2,3}正确

如果原数列中要取的数据,正好落在2个子数列上(1,2,3,4,5,6,7,8),需要取出limit 3,2,即:(4,5)

(1 ,  2 , 3 , 4) => limit 3,2 =>改写成limit 0, 3+2 => (1,2,3,4)

(5 , 6 , 7 , 8) => limit 3,2 =>改写成limit 0, 3+2 => (5,6,7,8)

将子数列合并排序=>(1,2,3,4,5,6,7,8) =>按原始偏移量limit 3,2 => (4,5)也符合预期。

取模均摊拆成 2 段

(1,3,5,7) => limit 1,2 ->改写成limit 0, 1+2 => (1,3 ,5)

(2,4,6,8) => limit 1,2 ->改写成limit 0, 1+2=> (2,4,6)

将子序列合并=>(1,2,3,4,5,6)=> 按原始偏移量limit 1,2 =>(2,3)正确

该方法缺点也很明显:取出的记录太多了,比如 limit 10000000,10 -> 改写后变成 limit 0, 10000010 遇到海量数据,mysql 中查询有可能直接超时,这么多数据从db传到应用层,网络开销也很大,更不用说如果是 java 应用,大量数据放到 List 或 Map 中,容易出现 OOM。(注:一般情况下,需要用分库分表的场景,数据量必然很大,所以这个方法,实际中基本上没法用)

二次查询法

这也是"业界难题-跨库分页”中提到的一个方法,大致思路如下:在某 1 页的数据均摊到各分表的前提下(注:这个前提很重要,也就是说不会有一个分表的数据特别多或特别少),换句话说:这个方案不适用分段法,按如下步骤操作

1)原 sql 中的limit offset,pagesize改写成limit offset/n ,pagesize(注:n为分表个数,如果 offset/n 除不尽,向下取整,避免最后的结果丢数据)-- 这个的意思,其实就是假设原表这一页的数据,会均分到各个分表(所以,我一再强调,前提是数据是均摊的,如果某个分表的记录很少,极端情况下,甚至是空的,这个就不对了,最终结果会少数据)

2)分表上,执行改写后的 sql,得到一堆结果集,然后找出这堆结果中的最小 id (假设 id 是关键的排序字段),记为 min_id -- 这一步的目的,是为了找出最小的起始点,保证第1页数据起点正确。

3)各分表上的 sql,where 条件部分改写成id between min_id and origin_max_id (注:origin_max_id 为上一步,每个分表查询结果集中的最大值,显然 min_id = 自身最小id的那张分表,不用再重复查询) -- 这一步的目的在于,因为步骤1)查出来的结果,通常会比原表上该页的数据少,所以这里重新将起始点设置到正确的位置,即:min_id,再查1次,相当于范围扩大了,以保证数据不会丢。不过,这里有一个可优化的地方,仔细想想,这1次查询出来的结果,跟步骤1)中的查出来的结果,必然有一部分是重复的,因此改写部分,只需要 id between min_id and origin_min_id就可以了(origin_min_id 即为原来分表结果上的最小 id)

4)将上一步查询出来的结果,在内存中合并排序去重(注:如果上一步采用了优化方案,就应该是把1)与3)这二次查询的结果全取出来合并排序去重),然后从开始连续取pagesize条数据即可(注:offset/n除不尽的话,向下取整了,也就是起始点可能向前多移了,所以有可能开始的第1条记录,其实是上1页的最后1条记录,要追求精确的话,可以在应用层记录上一页最后1条记录的id,然后跟本次查询结果前1条记录对比,如果发现是一样的,开始取数据的位置,就要向后移1位,如果考虑id有重复的话,就要根据情况多移几位)

验证一下看看效果:

场景1(前提:取余法)

原序列:(1,2,3,4,5,6,7,8),需要取出limit 2,2,即:(3,4)

第1次查询

(1,3,5,7) -> limit 2,2 -> 改写成limit 1,2 -> (3,5)

(2,4,6,8) -> limit 2,2-> 改写成limit 1,2 -> (4,6)

最小值为 3

第2次查询

(1,3,5,7) -> between 3 and 5 -> (3,5)

(2,4,6,8) -> between 3 and 6 -> (4,6)

将第2次查询的结果合并:

(3,4,5,6)  ->取头开始,取pageSize即2个元素 -> (3,4) 正确


场景2(前提:取余法)

原序列:(1,2,3,4,5,6,7,8),需要取出limit 1,2,即:(2,3)

第1次查询

(1,3,5,7) -> limit 1,2 -> 改写成 limit 0,2 -> (1,3)

-- 注:因为1/2除不尽,这里向下取整了

(2,4,6,8) -> limit 1,2 -> 改写成 limit 0,2 -> (2,4)

最小值为1

第2次查询

(1,3,5,7) -> between 1 and 3 -> (1,3)

(2,4,6,8) -> between 1 and 4 -> (2,4)

将上面的结果合并:

(1,2,3,4) -> (2,3) (注:起始点,第1次查询改写时,向下取整了,所以这里要向移1位,从第2个数字开始取pagesize条数据)


场景3(前提:分段法)

为什么说分段法,这个方案不适用,可以看下面的分析:

原序列:(1,2,3,4,5,6,7,8),需要取出limit 2,2 ,即:(3,4)

第1次查询

(1,2,3,4) -> limit 2,2 -> limit 1,2 -> {2,3}-- 注:这里就已经把正确的数据给丢掉了

(5,6,7,8) -> limit 2,2 -> limit 1,2 -> {5,6}-- 注:这一段里根本就没有这一页的数据

最小值2

第2次查询

(1,2,3,4) -> between 2 and 3 -> {2,3}

(5,6,7,8) -> between 2 and 6 -> {5,6}

(2,3,5,6) -> (2,3)  这个跟预期结果就对不上了。


场景4(前提:取余法)

取余法的前提下,如果某个分表的数据,被清掉一部分,也就是某个分表数据偏少,会发生什么?

比如下面这个,按奇数、偶数分成2个子序列,但是偶数故意删除了几个(相当于现实业务中,这个分表上的数据被干掉了一部分)

原序列:(1,3,5,6,7,8,9,11),需要取出limit 2,2,即:(5,6)

第1次查询

(1,3,5,7,9,11) -> limit 2,2-> 改写成limit 1,2 -> (3,5)

(6,8) -> limit 2,2 -> 改写成limit 1,2 -> (8)

第2次查询

(1,3,5,7,9,11) -> between 3 and 5 -> (3,5)

(6,8) -> between 3 and 8 -> (6,8)

合并后

(3,5,6,8) -> (3,5)这跟预期结果也对不上。

禁止跳页

相当于只允许向上或向下翻页,原理很简单,比如:下一页,先记录上一页的最大id,然后下一页时,只需要 where id >  上一页最大id limit pagesize, 每次只翻1页。显然,这是一个牺牲用户体验的做法。

结论:分表分页不存在一个通用的解决方案,要么性能有问题(比如:全局法 limit x+y),要么必须具备一定的前提条件(比如:二次查询),或者产品设计上牺牲用户体验,仍然是一个业内难题。

参考文章

  • https://juejin.im/post/5d1f52e46fb9a07eb3099bbf
  • https://shardingsphere.apache.org/document/current/cn/features/sharding/use-norms/pagination
  • https://stackoverflow.com/questions/3927537/how-do-you--implement-sorting-and-paging-on-distributed-data
  • http://kmiku7.github.io/2019/08/01/Do-Pagination-With-Table-Database-Sharding
  • https://segmentfault.com/a/1190000013225860

干货分享

最近将个人学习笔记整理成册,使用PDF分享。关注我,回复如下代码,即可获得百度盘地址,无套路领取!

001:《Java并发与高并发解决方案》学习笔记;002:《深入JVM内核——原理、诊断与优化》学习笔记;003:《Java面试宝典》004:《Docker开源书》005:《Kubernetes开源书》006:《DDD速成(领域驱动设计速成)》007:全部008:加技术群讨论

加个关注不迷路

喜欢就点个"在看"呗^_^

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/122189
 
231 次点击