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 是比較深度翻頁的數據，可以采取此策略，但也要進行兜底，如果返回的數據不滿足條件，繼續退化為最初的算法，所以單次效率可能不高，但從統計值上來看其效率可能是更高的。
