搜索关注微信公众号”捉虫大师”，后端技术分享，架构设计、性能优化、源码阅读、问题排查、踩坑实践。
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。
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号数据即是我们需要的。
此算法看起来很好，但如果数据量略有变化，例如：
[En]
This algorithm looks fine, but if the amount of data changes slightly, for example:
select c1 from tb1 order by c1 limit 9999999, 4
如果您仍然沿用上述方法，则需要到每个子库查询0-10000003数据，然后合并并丢弃0-9999998数据。
[En]
If you still follow the above method, you have to go to each sub-database to query 0-10000003 data, and then merge and discard 0-9999998 data.
这相当于丢弃了大约3倍的数据，而不管数据库是什么。这或多或少是浪费。
[En]
It is equivalent to discarding about 3 times as much data regardless of the database. This is more or less wasteful.
算法优化
- Step1：将这条语句拆分成3条语句发给3个分库：
- Step2：找出查询结果的最大和最小值，这里假设最小值为3，最大值为11
- Step3：以最小值和最大值为条件再次查询
假设我们获得的数据如图所示，那么在得出这些结果之前，我们是否很容易推断出我们有多少数据？
[En]
Assuming that the data we have obtained is as shown in the figure, is it easy to infer how much data we have before these results?
- Step4：反查出每一个返回结果的 offset，这里我们就能推断出分库1在最小值之前还有3333332条数据，分库2在最小值之前还有3333333条数据，分库3在最小值之前还有3333331条数据
此时，我们可以丢弃合并后的编号为0-9999998的数据。子库1、2、3丢弃最小值之前的数据，丢弃0-9999995号数据，然后丢弃三个最小值3，刚好达到9999998。所以数据9999999开始依次是4、5、5、6。
[En]
At this point, we can discard the merged data No. 0-9999998. Sub-libraries 1, 2 and 3 discard the data before the minimum value and discard the data No. 0-9999995, and then discard the three minimum values 3 just to reach 9999998. So data 9999999 starts to be 4, 5, 5, 6 in turn.
算法分析
效率
上面的例子说明了在优化之前：
[En]
The above example shows that before optimization:
- 1次查询，查询的数据总量大约 3kw，丢弃9999999条数据
优化后：
- 第1次查询，查询数据总量约 1kw
- 第2次查询，数据总量17
- 丢弃3条数据
从这个例子可以看出，查询的数据量大大减少，需要计算的丢弃数据量也大大减少。
[En]
As can be seen from this example, the amount of data queried is greatly reduced, and the amount of discarded data that needs to be calculated is also greatly reduced.
非理想情况
大家可以看到，上述例子都是很理想的。如果数据不是那么“理想”，结果会怎样？
[En]
Members may be able to see that the above examples are very ideal. If the data are not so “ideal”, what will be the outcome?
- Step4 中反查的最小值之前不够丢弃怎么办，比如：
- Step4 中反查的最小值之前的数据比需要丢弃的数据多怎么办？
可以看出，在这两种情况下，算法将不会再次工作。
[En]
It can be seen that in these two cases, the algorithm will not work again.
优化的前提
根据上述两个案例，可以得出结论，算法生效的前提是：
[En]
According to the above two cases, it can be concluded that the premise for the algorithm to take effect is:
数据（排序字段）在各个分库上的分布要均匀
实际上，我们可以做一个极端的假设，例如，只有第一个子数据库有数据，其他数据库没有数据，那么算法是无效的。
[En]
In fact, we can make an extreme assumption, for example, only the first sub-database has data, other databases do not have data, then the algorithm is invalid.
总结
这么来看，这个算法是不是很废？确实比较废，就连 Cobar 中也没有使用。
但在某些场景下还是有比较大的提升的，分库的数据大部分时候是按字段进行取模，所以可以认为几乎是 分布均匀的，此时如果 Order By / Limit 是比较 深度翻页的数据，可以采取此策略，但也要进行兜底，如果返回的数据不满足条件，继续退化为最初的算法，所以单次效率可能不高，但从统计值上来看其效率可能是更高的。
搜索关注微信公众号”捉虫大师”，后端技术分享，架构设计、性能优化、源码阅读、问题排查、踩坑实践。
Original: https://www.cnblogs.com/zhuochongdashi/p/15396751.html
Author: 捉虫大师
Title: Cobar提出的一种在分库场景下对Order By / Limit 的优化
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/508064/
转载文章受原作者版权保护。转载请注明原作者出处！