以下内容来自公众号逆锋起笔&＃xff0c;关注每日干货及时送达
来源&＃xff1a;https://www.cnblogs.com/yjmyzz/p/12149737.html
当业务数据达到一定量级(比如&＃xff1a;mysql单表记录量>1千万)后&＃xff0c;通常会考虑“分库分表”将数据分散到不同的库或表中&＃xff0c;这样可以大大提高读/写性能。但是问题来了&＃xff0c;对于 select * from table limit offset , pagesize 这种分页方式&＃xff0c;原来一条语句就可以简单搞定的事情会变得很复杂&＃xff0c;本文将与大家一起探讨分库分表后"分页"面临的新问题。
| 分表对分页的影响
比如有一张表&＃xff0c;里面有8条记录(为简单起见&＃xff0c;假设该表上只有1个自增ID&＃xff09;&＃xff0c;数学上可以抽象成1个(有序)数列(注&＃xff1a;为方便讨论&＃xff0c;不加特殊说明的情况下&＃xff0c;文本中数列的顺序&＃xff0c;均指升序)。
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)
如果要取出上面红色标识的2,3这二条记录&＃xff0c;limit 1,2 就行了。
现在假如分成2张表&＃xff08;即&＃xff1a;原来的数列&＃xff0c;拆分成2个非空子数列&＃xff09;&＃xff0c;一般来讲&＃xff0c;有二种常用分法&＃xff1a;
分段法&＃xff08;比如&＃xff1a;有时间属性的数据&＃xff0c;类似订单这种&＃xff0c;可以按下单时间拆分&＃xff0c;每个月1张表&＃xff09;
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4)
(5&＃xff0c;6&＃xff0c;7&＃xff0c;8)
沿用之前的limit x,y的思路&＃xff0c;每个分表上 limit 1,2&＃xff0c;会得到如下2个子数列&＃xff1a;
(2&＃xff0c;3)
(6&＃xff0c;7)
然后在内存中合并排序&＃xff0c;再取前2条 (2&＃xff0c;3&＃xff0c;6&＃xff0c;7) &＃61;> (2&＃xff0c;3) &＃xff0c;貌似看上去也符合预期&＃xff08;这个思路也称为归并&＃xff09;&＃xff0c;但这只是假象。当要取的分页数据落在不同的子数列上时&＃xff0c;就能发现问题&＃xff1a;
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)
比如&＃xff0c;我们要从4个位置开始&＃xff0c;连续取2个元素&＃xff0c;即: limit 3,2
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4) &＃61;> limit 3,2 &＃61;>(4)
(5&＃xff0c;6&＃xff0c;7&＃xff0c;8) &＃61;> limit 3,2 &＃61;>(8)
最后合并出来的结果是(4&＃xff0c;8) 与正确结果 (4&＃xff0c;5)相比&＃xff0c;显然不对。
模余均摊法&＃xff08;比如&＃xff1a;字段值对2取模求余数&＃xff0c;根据余数决定分到哪个表&＃xff0c;该方法也简称为取余法&＃xff09;
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8)
归并排序的思路在分段法上行不通&＃xff0c;对于取模均摊同样也不行&＃xff0c;仍以 limit 1,2为例&＃xff0c;原始序列取出来的结果是(2&＃xff0c;3)&＃xff0c;如果用归并的思路&＃xff1a;
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7)&＃61;> limit 1,2 &＃61;>(3 ,5)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8)&＃61;> limit 1,2 &＃61;>(4, 6)
内存合并排序后&＃xff0c;取前2个&＃xff0c;最终结果为(3 , 4)。
结论&＃xff1a;不管分库分表采用什么分法&＃xff0c;简单归并的思路&＃xff0c;都无法正确解决分页问题。
| 全局法(limit x&＃43;y)
反思一下刚才的归并思路&＃xff0c;本质上我们在每个子数列&＃xff08;即&＃xff1a;分表&＃xff09;上limit x,y 时&＃xff0c;取出来的数据就有可能已经产生缺失了。网上有一篇广为流转的文章"业界难题-跨库分页”&＃xff0c;作者在文中提出了一个方案&＃xff1a;把范围扩大&＃xff0c;分表sql上的limit x,y 变成 limit 0, x&＃43;y &＃xff0c;这样改写后&＃xff0c;相当于分表中把"每页最后一条数据"之前的所有数据全都取出来了&＃xff08;当然&＃xff1a;这里面可能会有不需要的多余数据)&＃xff0c;然后内存中合并在一起&＃xff0c;再取x偏移量后的y条数据。
用前面的例子验证一下&＃xff1a;
原序列&＃xff1a;(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)&＃xff0c;需要取出limit 1,2 &＃xff0c;即&＃xff1a;(2&＃xff0c;3)
按分段法拆成2段&＃xff1a;
(1 , 2 , 3 , 4) &＃61;> limit 1,2 &＃61;>改写成 limit 0, 1&＃43;2 &＃61;> (1&＃xff0c;2&＃xff0c;3)
(5 , 6 , 7 , 8) &＃61;> limit 1,2 &＃61;>改写成 limit 0, 1&＃43;2 &＃61;> (5&＃xff0c;6&＃xff0c;7)
将子数列合并排序&＃61;> { 1&＃xff0c;2&＃xff0c;3&＃xff0c;5&＃xff0c;6&＃xff0c;7} &＃61;> 按原始偏移量 limit 1,2 &＃61;>{2&＃xff0c;3} 正确
如果原数列中要取的数据&＃xff0c;正好落在2个子数列上(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)&＃xff0c;需要取出limit 3,2 &＃xff0c;即&＃xff1a;(4&＃xff0c;5)
(1 , 2 , 3 , 4) &＃61;> limit 3,2 &＃61;>改写成 limit 0, 3&＃43;2 &＃61;> (1&＃xff0c;2&＃xff0c;3&＃xff0c;4)
(5 , 6 , 7 , 8) &＃61;> limit 3,2 &＃61;>改写成 limit 0, 3&＃43;2 &＃61;> (5&＃xff0c;6&＃xff0c;7&＃xff0c;8)
将子数列合并排序&＃61;> (1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8) &＃61;> 按原始偏移量 limit 3,2 &＃61;> (4&＃xff0c;5) 也符合预期。
取模均摊拆成2段
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7) &＃61;> limit 1,2 ->改写成 limit 0, 1&＃43;2 &＃61;> (1&＃xff0c;3 &＃xff0c;5)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8) &＃61;> limit 1,2 ->改写成 limit 0, 1&＃43;2&＃61;> (2&＃xff0c;4&＃xff0c;6)
将子序列合并&＃61;> (1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6) &＃61;> 按原始偏移量 limit 1,2 &＃61;>(2&＃xff0c;3) 正确
该方法缺点也很明显&＃xff1a;取出的记录太多了&＃xff0c;比如 limit 10000000,10 -> 改写后变成 limit 0, 10000010 遇到海量数据&＃xff0c;mysql中查询有可能直接超时&＃xff0c;这么多数据从db传到应用层&＃xff0c;网络开销也很大&＃xff0c;更不用说如果是java应用&＃xff0c;大量数据放到List或Map中&＃xff0c;容易出现OOM。&＃xff08;注&＃xff1a;一般情况下&＃xff0c;需要用分库分表的场景&＃xff0c;数据量必然很大&＃xff0c;所以这个方法&＃xff0c;实际中基本上没法用&＃xff09;。
| 二次查询法
这也是"业界难题-跨库分页”一文中提到的一个方法&＃xff0c;大致思路如下&＃xff1a;在某1页的数据均摊到各分表的前提下(注&＃xff1a;这个前提很重要&＃xff0c;也就是说不会有一个分表的数据特别多或特别少)&＃xff0c;换句话说&＃xff1a;这个方案不适用分段法&＃xff0c;按如下步骤操作&＃xff1a;
1&＃xff09;原sql中的limit offset,pagesize 改写成 limit offset/n ,pagesize (注&＃xff1a;n为分表个数&＃xff0c;如果offset/n除不尽&＃xff0c;向下取整&＃xff0c;避免最后的结果丢数据&＃xff09;-- 这个的意思&＃xff0c;其实就是假设原表这一页的数据&＃xff0c;会均分到各个分表(所以&＃xff0c;我一再强调&＃xff0c;前提是数据是均摊的&＃xff0c;如果某个分表的记录很少&＃xff0c;极端情况下&＃xff0c;甚至是空的&＃xff0c;这个就不对了&＃xff0c;最终结果会少数据)。
2&＃xff09;分表上&＃xff0c;执行改写后的sql&＃xff0c;得到一堆结果集&＃xff0c;然后找出这堆结果中的最小id (假设id是关键的排序字段)&＃xff0c;记为min_id -- 这一步的目的&＃xff0c;是为了找出最小的起始点&＃xff0c;保证第1页数据起点正确。
3&＃xff09;各分表上的sql&＃xff0c;where条件部分改写成 id between min_id and origin_max_id (注&＃xff1a;origin_max_id为上一步&＃xff0c;每个分表查询结果集中的最大值&＃xff0c;显然min_id&＃61;自身最小id的那张分表&＃xff0c;不用再重复查询) -- 这一步的目的在于&＃xff0c;因为步骤1&＃xff09;查出来的结果&＃xff0c;通常会比原表上该页的数据少&＃xff0c;所以这里重新将起始点设置到正确的位置&＃xff0c;即&＃xff1a;min_id&＃xff0c;再查1次&＃xff0c;相当于范围扩大了&＃xff0c;以保证数据不会丢。不过&＃xff0c;这里有一个可优化的地方&＃xff0c;仔细想想&＃xff0c;这1次查询出来的结果&＃xff0c;跟步骤1&＃xff09;中的查出来的结果&＃xff0c;必然有一部分是重复的&＃xff0c;因此改写部分&＃xff0c;只需要 id between min_id and origin_min_id就可以了(origin_min_id 即为原来分表结果上的最小id)。
4&＃xff09;将上一步查询出来的结果&＃xff0c;在内存中合并排序去重&＃xff08;注&＃xff1a;如果上一步采用了优化方案&＃xff0c;就应该是把1&＃xff09;与3&＃xff09;这二次查询的结果全取出来合并排序去重&＃xff09;&＃xff0c;然后从开始连续取pagesize条数据即可&＃xff08;注&＃xff1a;offset/n除不尽的话&＃xff0c;向下取整了&＃xff0c;也就是起始点可能向前多移了&＃xff0c;所以有可能开始的第1条记录&＃xff0c;其实是上1页的最后1条记录&＃xff0c;要追求精确的话&＃xff0c;可以在应用层记录上一页最后1条记录的id&＃xff0c;然后跟本次查询结果前1条记录对比&＃xff0c;如果发现是一样的&＃xff0c;开始取数据的位置&＃xff0c;就要向后移1位&＃xff0c;如果考虑id有重复的话&＃xff0c;就要根据情况多移几位&＃xff09;。
验证一下看看效果&＃xff1a;
场景1&＃xff08;前提&＃xff1a;取余法&＃xff09;
原序列&＃xff1a;(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)&＃xff0c;需要取出limit 2,2 &＃xff0c;即&＃xff1a;(3&＃xff0c;4)
第1次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7) -> limit 2,2 -> 改写成 limit 1,2 -> (3&＃xff0c;5)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8) -> limit 2,2 -> 改写成 limit 1,2 -> (4&＃xff0c;6)
最小值为3
第2次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7) -> between 3 and 5 -> (3&＃xff0c;5)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8) -> between 3 and 6 -> (4&＃xff0c;6)
将第2次查询的结果合并&＃xff1a;
(3&＃xff0c;4&＃xff0c;5&＃xff0c;6) ->取头开始&＃xff0c;取pageSize即2个元素 -> (3&＃xff0c;4) 正确
-----------------------------------------------------
场景2&＃xff08;前提&＃xff1a;取余法&＃xff09;
原序列&＃xff1a;(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)&＃xff0c;需要取出limit 1,2 &＃xff0c;即&＃xff1a;(2&＃xff0c;3)
第1次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7) -> limit 1,2 -> 改写成 limit 0,2 -> (1&＃xff0c;3) --注&＃xff1a;因为1/2除不尽&＃xff0c;这里向下取整了
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8) -> limit 1,2 -> 改写成 limit 0,2 -> (2&＃xff0c;4)
最小值为1
第2次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7) -> between 1 and 3 -> (1&＃xff0c;3)
(2&＃xff0c;4&＃xff0c;6&＃xff0c;8) -> between 1 and 4 -> (2&＃xff0c;4)
将上面的结果合并&＃xff1a;
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4) -> (2&＃xff0c;3) (注&＃xff1a;起始点&＃xff0c;第1次查询改写时&＃xff0c;向下取整了&＃xff0c;所以这里要向移1位&＃xff0c;从第2个数字开始取pagesize条数据)
--------------------------------------------------------
场景3&＃xff08;前提&＃xff1a;分段法&＃xff09;
为什么说分段法&＃xff0c;这个方案不适用&＃xff0c;可以看下面的分析&＃xff1a;
原序列&＃xff1a;(1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8)&＃xff0c;需要取出limit 2,2 &＃xff0c;即&＃xff1a;(3&＃xff0c;4)
第1次查询
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4) -> limit 2,2 -> limit 1,2 -> {2&＃xff0c;3} --注&＃xff1a;这里就已经把正确的数据给丢掉了。
(5&＃xff0c;6&＃xff0c;7&＃xff0c;8) -> limit 2,2 -> limit 1,2 -> {5&＃xff0c;6} --注&＃xff1a;这一段里根本就没有这一页的数据。
最小值2
第2次查询
(1&＃xff0c;2&＃xff0c;3&＃xff0c;4) -> between 2 and 3 -> {2&＃xff0c;3}
(5&＃xff0c;6&＃xff0c;7&＃xff0c;8) -> between 2 and 6 -> {5&＃xff0c;6}
(2&＃xff0c;3&＃xff0c;5&＃xff0c;6) -> (2&＃xff0c;3) 这个跟预期结果就对不上了。
-------------------------------------------------------
场景4&＃xff08;前提&＃xff1a;取余法&＃xff09;
取余法的前提下&＃xff0c;如果某个分表的数据&＃xff0c;被清掉一部分&＃xff0c;也就是某个分表数据偏少&＃xff0c;会发生什么&＃xff1f;
比如下面这个&＃xff0c;按奇数、偶数分成2个子序列&＃xff0c;但是偶数故意删除了几个&＃xff08;相当于现实业务中&＃xff0c;这个分表上的数据被干掉了一部分&＃xff09;。
原序列&＃xff1a;(1&＃xff0c;3&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8&＃xff0c;9&＃xff0c;11)&＃xff0c;需要取出limit 2,2 &＃xff0c;即&＃xff1a;(5&＃xff0c;6)
第1次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7&＃xff0c;9&＃xff0c;11) -> limit 2,2 -> 改写成limit 1,2 -> (3&＃xff0c;5)
(6&＃xff0c;8) -> limit 2,2 -> 改写成limit 1,2 -> (8)
第2次查询
(1&＃xff0c;3&＃xff0c;5&＃xff0c;7&＃xff0c;9&＃xff0c;11) -> between 3 and 5 -> (3&＃xff0c;5)
(6&＃xff0c;8) -> between 3 and 8 -> (6&＃xff0c;8)
合并后
(3&＃xff0c;5&＃xff0c;6&＃xff0c;8) -> (3&＃xff0c;5) 这跟预期结果也对不上。
| 禁止跳页
相当于只允许向上或向下翻页&＃xff0c;原理很简单&＃xff0c;比如&＃xff1a;下一页&＃xff0c;先记录上一页的最大id&＃xff0c;然后下一页时&＃xff0c;只需要 where id > 上一页最大id limit pagesize&＃xff0c; 每次只翻1页。显然&＃xff0c;这是一个牺牲用户体验的做法。
| 结论
分表分页不存在一个通用的解决方案&＃xff0c;要么性能有问题&＃xff08;比如:全局法 limit x&＃43;y&＃xff09;&＃xff0c;要么必须具备一定的前提条件(比如&＃xff1a;二次查询)&＃xff0c;或者产品设计上牺牲用户体验&＃xff0c;仍然是一个业内难题。
参考文章&＃xff1a;
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
https://mp.weixin.qq.com/s/h99sXP4mvVFsJw6Oh3aU5A
本文版权归作者和博客园共有&＃xff0c;欢迎转载&＃xff0c;但未经作者同意必须保留此段声明&＃xff0c;且在文章页面明显位置给出原文连接&＃xff0c;否则保留追究法律责任的权利。
逆锋起笔专注于程序员圈子&＃xff0c;你不但可以学习到java、python等主流技术干货&＃xff0c;还可以第一时间获悉最新技术动态、内测资格、BAT大佬的经验、精品视频教程、副业赚钱经验&＃xff0c;微信搜索readdot关注&＃xff01;
MySQL 8.0 可以操作 JSON 了&＃xff01;&＃xff01;
MySQL 大批量插入&＃xff0c;如何过滤掉重复数据&＃xff1f;
SQL 中如何给指定数据库创建只读用户&＃xff1f;
MySQL 5.7 vs 8.0&＃xff0c;哪个性能更牛&＃xff1f;
大厂 MySQL 规范&＃xff0c;从入门到精通&＃xff01;
点赞是最大的支持
京公网安备 11010802041100号