[[428269]]

本文轉(zhuǎn)載自微信公眾號(hào)「捉蟲(chóng)大師」，作者捉蟲(chóng)大師。轉(zhuǎn)載本文請(qǐng)聯(lián)系捉蟲(chóng)大師公眾號(hào)。

Cobar 雖然是一款“古老”的數(shù)據(jù)庫(kù)中間件，但目前不少公司仍然在用它，且它包含了不少有意思的算法和實(shí)現(xiàn)，今天就來(lái)分享 Cobar 提出的一種在分庫(kù)場(chǎng)景下對(duì) Order By / Limit 的優(yōu)化。

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

背景

Cobar 最重要的功能就是分庫(kù)分表，通常讀取性能瓶頸可以通過(guò)增加從庫(kù)或緩存來(lái)解決。

但寫(xiě)入性能在 MySQL 上只能通過(guò)分庫(kù)分表來(lái)提升。

當(dāng)我們把數(shù)據(jù)分布到不同的數(shù)據(jù)庫(kù)上時(shí)，再查詢(xún)時(shí)如果是單條數(shù)據(jù)只要找到這條數(shù)據(jù)對(duì)應(yīng)的庫(kù)即可，但如果是多條數(shù)據(jù)，可能分布在不同的庫(kù)上時(shí)，Cobar 就需要先查詢(xún)，再聚合。圖片

來(lái)個(gè)具體例子：

如果我們要查詢(xún) tb1 表的 c1 字段，且取 c1 正序的下標(biāo)(從0開(kāi)始)為4、5的數(shù)據(jù)。假設(shè)分了三個(gè)庫(kù)，我們?yōu)榱巳〉秸_數(shù)據(jù)，需要去這三個(gè)分庫(kù)都取下標(biāo)0-5的數(shù)據(jù)，假設(shè)取到如下數(shù)據(jù)：

取到3堆已排序的數(shù)據(jù)，對(duì)這3堆數(shù)據(jù)從小開(kāi)始丟棄0、1、2、3號(hào)數(shù)據(jù)，保留第4、5號(hào)數(shù)據(jù)即是我們需要的。

這個(gè)算法看起來(lái)沒(méi)啥問(wèn)題，但如果數(shù)據(jù)量稍微變化一下，比如：

select c1 from tb1 order by c1 limit 9999999, 4

如果還按照上述的方法來(lái)做，首先得去每個(gè)分庫(kù)查詢(xún) 0 - 10000003的數(shù)據(jù)，然后再合并丟棄0-9999998號(hào)數(shù)據(jù)。

相當(dāng)于丟棄了大約不分庫(kù)時(shí)3倍的數(shù)據(jù)。這多少顯得有點(diǎn)浪費(fèi)了。

算法優(yōu)化

Step1：將這條語(yǔ)句拆分成3條語(yǔ)句發(fā)給3個(gè)分庫(kù)：

• Step2：找出查詢(xún)結(jié)果的最大和最小值，這里假設(shè)最小值為3，最大值為11

Step3：以最小值和最大值為條件再次查詢(xún)

假設(shè)我們?nèi)〉玫臄?shù)據(jù)如圖，那么我們是不是很容易推斷出這些結(jié)果之前還有多少數(shù)據(jù)?

• Step4：反查出每一個(gè)返回結(jié)果的 offset，這里我們就能推斷出分庫(kù)1在最小值之前還有3333332條數(shù)據(jù)，分庫(kù)2在最小值之前還有3333333條數(shù)據(jù)，分庫(kù)3在最小值之前還有3333331條數(shù)據(jù)

這時(shí)，我們就可以丟棄合并后的0-9999998號(hào)數(shù)據(jù)了，分庫(kù)1、2、3將最小值之前的數(shù)據(jù)都丟棄共丟棄了0-9999995號(hào)數(shù)據(jù)，再丟棄3個(gè)最小值3剛好夠到了9999998，所以9999999號(hào)數(shù)據(jù)開(kāi)始依次是4、5、5、6

算法分析

效率

以上例來(lái)說(shuō)明，未優(yōu)化前：

• 1次查詢(xún)，查詢(xún)的數(shù)據(jù)總量大約 3kw，丟棄9999999條數(shù)據(jù)

優(yōu)化后：

• 第1次查詢(xún)，查詢(xún)數(shù)據(jù)總量約 1kw
• 第2次查詢(xún)，數(shù)據(jù)總量17
• 丟棄3條數(shù)據(jù)

從這個(gè)例子可以看出，查詢(xún)的數(shù)據(jù)量大大減少，需要計(jì)算丟棄的量也大大減少

非理想情況

可能大家能看出來(lái)，上述例子是非常理想的情況，如果數(shù)據(jù)沒(méi)這么“理想”，結(jié)局又是怎樣?

• Step4 中反查的最小值之前不夠丟棄怎么辦，比如：

• Step4 中反查的最小值之前的數(shù)據(jù)比需要丟棄的數(shù)據(jù)多怎么辦?

可以看出，如果是這兩種情況，這種算法就沒(méi)法再次生效了。

優(yōu)化的前提

根據(jù)上述兩種情況來(lái)看，可以總結(jié)出該算法生效的前提是：

數(shù)據(jù)(排序字段)在各個(gè)分庫(kù)上的分布要均勻

其實(shí)可以做個(gè)極端的假設(shè)，比如只有第一個(gè)分庫(kù)上有數(shù)據(jù)，其他數(shù)據(jù)庫(kù)沒(méi)有數(shù)據(jù)，那么這個(gè)算法就失效了

總結(jié)

這么來(lái)看，這個(gè)算法是不是很廢?確實(shí)比較廢，就連 Cobar 中也沒(méi)有使用。

但在某些場(chǎng)景下還是有比較大的提升的，分庫(kù)的數(shù)據(jù)大部分時(shí)候是按字段進(jìn)行取模，所以可以認(rèn)為幾乎是分布均勻的，此時(shí)如果 Order By / Limit 是比較深度翻頁(yè)的數(shù)據(jù)，可以采取此策略，但也要進(jìn)行兜底，如果返回的數(shù)據(jù)不滿(mǎn)足條件，繼續(xù)退化為最初的算法，所以單次效率可能不高，但從統(tǒng)計(jì)值上來(lái)看其效率可能是更高的。