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

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

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

背景

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

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

当我们把数据分布到不同的数据库上时, 再查询时如果是单条数据只要找到这条数据对应的库即可, 但如果是多条数据, 可能分布在不同的库上时, Cobar 就需要先查询, 再聚合. 图片

来个具体例子:

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

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

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

select c1 from tb1 order by c1 limit 9999999, 4

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

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

算法优化

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

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

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

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

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

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

算法分析

效率

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

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

优化后:

第 1 次查询, 查询数据总量约 1kw

第 2 次查询, 数据总量 17

丢弃 3 条数据

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

非理想情况

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

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

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

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

优化的前提

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

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

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

总结

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

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

来源: http://database.51cto.com/art/202110/685327.htm