Cobar提出的一种在分库场景下对Order By / Limit 的优化

捉虫大师
• 阅读 533

搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。 本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。

Cobar 虽然是一款“古老”的数据库中间件,但目前不少公司仍然在用它,且它包含了不少有意思的算法和实现,今天就来分享 Cobar 提出的一种在分库场景下对 Order By / Limit 的优化。

原算法描述参考: https://github.com/alibaba/cobar/blob/master/doc/cobarSolution.ppt

背景

Cobar 最重要的功能就是分库分表,通常读取性能瓶颈可以通过增加从库或缓存来解决。

但写入性能在 MySQL 上只能通过分库分表来提升。

当我们把数据分布到不同的数据库上时,再查询时如果是单条数据只要找到这条数据对应的库即可,但如果是多条数据,可能分布在不同的库上时,Cobar 就需要先查询,再聚合。 Cobar提出的一种在分库场景下对Order By / Limit 的优化

来个具体例子:

Cobar提出的一种在分库场景下对Order By / Limit 的优化

如果我们要查询 tb1 表的 c1 字段,且取 c1 正序的下标(从0开始)为4、5的数据。假设分了三个库,我们为了取到正确数据,需要去这三个分库都取下标0-5的数据,假设取到如下数据:

Cobar提出的一种在分库场景下对Order By / Limit 的优化

取到3堆已排序的数据,对这3堆数据从小开始丢弃0、1、2、3号数据,保留第4、5号数据即是我们需要的。

Cobar提出的一种在分库场景下对Order By / Limit 的优化

这个算法看起来没啥问题,但如果数据量稍微变化一下,比如:

select c1 from tb1 order by c1 limit 9999999, 4

如果还按照上述的方法来做,首先得去每个分库查询 0 - 10000003的数据,然后再合并丢弃0-9999998号数据。

相当于丢弃了大约不分库时3倍的数据。这多少显得有点浪费了。

算法优化

  • Step1:将这条语句拆分成3条语句发给3个分库:

Cobar提出的一种在分库场景下对Order By / Limit 的优化

  • Step2:找出查询结果的最大和最小值,这里假设最小值为3,最大值为11

Cobar提出的一种在分库场景下对Order By / Limit 的优化

  • Step3:以最小值和最大值为条件再次查询

Cobar提出的一种在分库场景下对Order By / Limit 的优化

假设我们取得的数据如图,那么我们是不是很容易推断出这些结果之前还有多少数据?

  • Step4:反查出每一个返回结果的 offset,这里我们就能推断出分库1在最小值之前还有3333332条数据,分库2在最小值之前还有3333333条数据,分库3在最小值之前还有3333331条数据

Cobar提出的一种在分库场景下对Order By / Limit 的优化

这时,我们就可以丢弃合并后的0-9999998号数据了,分库1、2、3将最小值之前的数据都丢弃共丢弃了0-9999995号数据,再丢弃3个最小值3刚好够到了9999998,所以9999999号数据开始依次是4、5、5、6

Cobar提出的一种在分库场景下对Order By / Limit 的优化

算法分析

效率

以上例来说明,未优化前:

  • 1次查询,查询的数据总量大约 3kw,丢弃9999999条数据

优化后:

  • 第1次查询,查询数据总量约 1kw
  • 第2次查询,数据总量17
  • 丢弃3条数据

从这个例子可以看出,查询的数据量大大减少,需要计算丢弃的量也大大减少

非理想情况

可能大家能看出来,上述例子是非常理想的情况,如果数据没这么“理想”,结局又是怎样?

  • Step4 中反查的最小值之前不够丢弃怎么办,比如:

Cobar提出的一种在分库场景下对Order By / Limit 的优化

  • Step4 中反查的最小值之前的数据比需要丢弃的数据多怎么办?

Cobar提出的一种在分库场景下对Order By / Limit 的优化

可以看出,如果是这两种情况,这种算法就没法再次生效了。

优化的前提

根据上述两种情况来看,可以总结出该算法生效的前提是:

数据(排序字段)在各个分库上的分布要均匀

其实可以做个极端的假设,比如只有第一个分库上有数据,其他数据库没有数据,那么这个算法就失效了

总结

这么来看,这个算法是不是很废?确实比较废,就连 Cobar 中也没有使用。

但在某些场景下还是有比较大的提升的,分库的数据大部分时候是按字段进行取模,所以可以认为几乎是分布均匀的,此时如果 Order By / Limit 是比较深度翻页的数据,可以采取此策略,但也要进行兜底,如果返回的数据不满足条件,继续退化为最初的算法,所以单次效率可能不高,但从统计值上来看其效率可能是更高的。


搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。

Cobar提出的一种在分库场景下对Order By / Limit 的优化

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
捉虫大师 捉虫大师
2年前
大厂偏爱的Agent技术究竟是个啥
搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。hello大家好,我是小楼,今天给大家分享一个关于Agent技术的话题,也是后端启示录的第3篇文章。通过本文你可以了解到如下内容:什么是Agent技术为了解释什么是Agent技术,我在网上搜了一圈,但没有找到想要的结果。反倒是搜到了不少JavaAgent技术,
捉虫大师 捉虫大师
2年前
小白也能看懂的dubbo3应用级服务发现详解
搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。本文已收录https://github.com/lkxiaolou/lkxiaolou欢迎star。dubbo是一款开源的RPC框架,主要有3个角色:提供者(provider)、消费者(consumer)、注册中心(registry)提供者启动时向
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
捉虫大师 捉虫大师
2年前
Cobar SQL审计的设计与实现
本文已收录https://github.com/lkxiaolou/lkxiaolou欢迎star。背景介绍Cobar简介Cobar是阿里开源的一款数据库中间件产品。在业务高速增长的情况下,数据库往往成为整个业务系统的瓶颈,数据库中间件的出现就是为了解决数据库瓶颈而产生的一种中间层产品。在软件工程中,没有什么问题是加一层中间层解决不了的,如果有,再
捉虫大师 捉虫大师
2年前
案例分享 | dubbo 2.7.12 bug导致线上故障
本文已收录https://github.com/lkxiaolou/lkxiaolou欢迎star。搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。背景最近某天的深夜,刚洗完澡就接到业务方打来电话,说他们的dubbo服务出故障了,要我协助排查一下。电话里,询问了他们几点是线上有损故障吗?——是止损
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
3个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这