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

捉虫大师 等级 38 0 0
标签: cobarhttps算法

搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。 本文已收录 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 的优化

收藏
评论区

相关推荐

低开销获取时间戳
前言在前面文章中提了一句关于时间戳获取性能的问题 获取操作系统时间,在Java中直接调用 System.currentTimeMillis(); 就可以,但在Cobar中如果这么获取时间,就会导致性能损耗非常严重(怎么解决?去Cobar的github仓库上看看代码吧)。这个话题展开具体说说,我们在Java中获取时间戳的方法是System.currentTim
Cobar SQL审计的设计与实现
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 背景介绍 Cobar简介Cobar 是阿里开源的一款数据库中间件产品。在业务高速增长的情况下,数据库往往成为整个业务系统的瓶颈,数据库中间件的出现就是为了解决数据库瓶颈而产生的一种中间层产品。在软件工程中,没有什么问题是加一层中间层解决不了的,如果有,再
JAVA回调机制(CallBack)之小红是怎样买到房子的??
JAVA回调机制CallBack 序言最近学习java,接触到了回调机制(CallBack)。初识时感觉比较混乱,而且在网上搜索到的相关的讲解,要么一言带过,要么说的比较单纯的像是给CallBack做了一个定义。当然了,我在理解了回调之后,再去看网上的各种讲解,确实没什么问题。但是,对于初学的我来说,缺了一个循序渐进的过程。此处,将我对回调机制的个人理解,按
Cobar源码分析之AST
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 背景 CobarCobar是阿里开源的数据库中间件,关于它的介绍这里不再赘述,可以参考之前的文章 SQLSQL是一种领域语言(编程语言),常用于关系型数据库,方便管理结构化数据。数据库执行SQL时先对SQL进行词法分析、语法分析、语义分析生成抽象语法树(
MYSQL常用查询
一、MYSQL查询的五种子句 where(条件查询)、having(筛选)、group by(分组)、order by(排序)、limit(限制结果数) 【1】where: 比较运算符      > , < ,= , != (< >),>= , <= in(param1,p
MySQL ORDER BY主键id加LIMIT限制走错索引
### 背景及现象 * report\_product\_sales\_data表数据量2800万; * 经测试,在当前数据量情况下,order by主键id,limit最大到49的时候可以用到索引report\_product\_sales\_data\_hq\_code\_orgz\_id\_index,大于49时就走PRIMARY主键索引。
MySQL · 性能优化 · MySQL常见SQL错误用法
### 1\. LIMIT 语句 分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type, name, create\_time字段上加组合索引。这样条件排序都能有效的利用到索引,性能迅速提升。 SELECT * FROM operation WHERE ty
MySQL之查询语句的基本操作
一.查询语句的基本操作 ----------- 1.查询语句的基本操作 - select - from - where:约束条件 - group by:分组 - having:过滤 - distinct:去
MySql协议详解
MySql协议详解-HandShake握手篇 ---------------------- 各位有没有对Cobar、MyCat这些MySqlProxy感到新奇。反正笔者在遇到这些proxy时,感受到其对代码的无侵入兴感到大为惊奇。于是走上了研究MySql协议的不归路。现在我就在博客里面将其中所得分享出来,以飨大家。 ### HandShake协议 下图
Mysql Using FileSort问题
阅读更多 问题:明明order by的字段建立了索引,结果还是Using FileSort? Using filesort表示在索引之外,需要额外进行外部的排序动作。导致该问题的原因一般和order by有者直接关系,一般可以通过合适的索引来减少或者避免。  explain SELECT \* FROM table\_item WHERE user\_
Mysql order by与limit混用陷阱
在Mysql中我们常常用order by来进行排序,使用limit来进行分页,当需要先排序后分页时我们往往使用类似的写法select \* from 表名 order by 排序字段 limt M,N。但是这种写法却隐藏着较深的使用陷阱。在排序字段有数据重复的情况下,会很容易出现排序结果与预期不一致的问题。 比如现在有一张user表,表结构及数据如下:
mysql中间件(转)
**本文转自 [http://www.guokr.com/blog/475765/](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2F)** mysql-proxy是官方提供的mysql中间件产品可以实现负载平衡,读写分离,failover等,但其不支持大数据量的分库分表且性能较差。下面介绍
mysql笔记
如果需要查询 id 不是连续的一段,最佳的方法就是先找出 id ,然后用 in 查询 SELECT \* FROM table WHERE id IN(10000, 100000, 1000000...); 索引列上使用in速度是很快的 1.SELECT \* FROM table ORDER BY id LIMIT 1000000, 10;
sql server实现Mysql中的limit分页功能
没有使用ORM框架前,一直使用原生sql分页,突然想起来,便随手一记吧。。 首先,在mysql 中有一种常见的分页方式 * `LIMIT`总是设定为`pageSize`; * `OFFSET`计算公式为`pageSize * (pageIndex - 1)`。 SELECT id, name, gender, score FRO
Cobar提出的一种在分库场景下对Order By / Limit 的优化
搜索关注微信公众号"捉虫大师",后端技术分享,架构设计、性能优化、源码阅读、问题排查、踩坑实践。 本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。Cobar 虽然是一款“古老”的数据库中间件,但目前不少公司仍然在用它,且它包含了不少有意思的算法和实现,今天就来分享 Cobar 提出的一种在分库场景下对