Cobar提出的一種在分庫場景下對Order By / Limit 的優化
搜索關注微信公眾號”捉蟲大師”，後端技術分享，架構設計、性能優化、源碼閱讀、問題排查、踩坑實踐。
本文已收錄 //github.com/lkxiaolou/lkxiaolou 歡迎star。
Cobar 雖然是一款「古老」的資料庫中間件，但目前不少公司仍然在用它，且它包含了不少有意思的演算法和實現，今天就來分享 Cobar 提出的一種在分庫場景下對 Order By / Limit 的優化。
原演算法描述參考： //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 是比較深度翻頁的數據，可以採取此策略，但也要進行兜底，如果返回的數據不滿足條件，繼續退化為最初的演算法，所以單次效率可能不高，但從統計值上來看其效率可能是更高的。
搜索關注微信公眾號”捉蟲大師”，後端技術分享，架構設計、性能優化、源碼閱讀、問題排查、踩坑實踐。
