一、背景

1. 分布式數(shù)據(jù)庫架構(gòu)

當(dāng)前分布式數(shù)據(jù)庫架構(gòu)有不少，但是總體架構(gòu)相差不大，主要組件都包含協(xié)調(diào)節(jié)點(diǎn)、數(shù)據(jù)分片、元數(shù)據(jù)節(jié)點(diǎn)、全局時(shí)鐘。一種常見的分布式架構(gòu)如下圖：

• gtm ：全局事務(wù)管理器(全局時(shí)鐘)，一主多備；
• catalog: 元數(shù)據(jù)管理，一主多備；
• group: 水平分片,每個(gè)group由一主多備數(shù)據(jù)存儲節(jié)點(diǎn)組成；
• proxy : 協(xié)調(diào)節(jié)點(diǎn)，無狀態(tài)，負(fù)責(zé)處理客戶端的請求，把請求按照分片規(guī)則發(fā)送到數(shù)據(jù)分片，匯總數(shù)據(jù)分片返回的數(shù)據(jù)，協(xié)同其它組件保證分布式事務(wù)的一致性。

2. 排序問題

分布式數(shù)據(jù)庫中排序也是一種重要的功能。一條查詢排序語句select *from t1 order by field1，需要查詢的數(shù)據(jù)可能會分布在不同的數(shù)據(jù)分片中。這就需要proxy對為不同數(shù)據(jù)分片返回的有序數(shù)據(jù)進(jìn)行重排序，然后后給client返回全局有序的數(shù)據(jù)。

當(dāng)相關(guān)的數(shù)據(jù)量不大時(shí)，proxy可把不同數(shù)據(jù)分片返回的數(shù)據(jù)保存在內(nèi)存中，然后對內(nèi)存中的數(shù)據(jù)重排序后返回給client。當(dāng)相關(guān)的數(shù)據(jù)量比較大時(shí)，如果把待重排序數(shù)據(jù)放到內(nèi)存中則可能會導(dǎo)致OOM，如果把待重排序數(shù)據(jù)暫存在proxy的磁盤中，則也有耗盡磁盤的風(fēng)險(xiǎn)并且會存在大量的磁盤IO。下面將介紹一種分布式數(shù)據(jù)庫排序及優(yōu)化方法。

二、解決方案

1. 排序方案介紹

為了提高分布式排序的性能，每個(gè)數(shù)據(jù)分片本身也要參與排序。這樣在proxy上得到分片返回的數(shù)據(jù)是有序的，proxy對有序的數(shù)據(jù)重排序可以采用歸并排序或者優(yōu)先級隊(duì)列排序方法，大大減輕proxy的壓力。

可以根據(jù)proxy內(nèi)存大小配置sort buffer大小，通常默認(rèn)為10M。如果一次查詢語句關(guān)聯(lián)N個(gè)數(shù)據(jù)分片，則需要到sort buffer按照N份進(jìn)行切分，每個(gè)數(shù)據(jù)分片對應(yīng)切分后的sort buffer大小為10M/N。

直接在內(nèi)存中進(jìn)行，具體步驟如下圖：

• client向proxy下發(fā)排序查詢語句 select *from t1 order by id。
• proxy根據(jù)分片鍵以及分片規(guī)則向相關(guān)的數(shù)據(jù)分片group1、group2下發(fā)排序查詢語句select *from t1 order by id。
• 數(shù)據(jù)分片在本地對數(shù)據(jù)進(jìn)行查詢排序后，發(fā)送有序數(shù)據(jù)到proxy。
• proxy把數(shù)據(jù)分片返回的有序數(shù)據(jù)存儲在數(shù)據(jù)分片對應(yīng)的sort buffer中，并對有序數(shù)據(jù)進(jìn)行歸并排序。
• proxy把歸并排序好的數(shù)據(jù)發(fā)送給client。

2. 排序方案缺陷

這種方法只能滿足小數(shù)據(jù)量排序，當(dāng)排序的數(shù)據(jù)量較大我們可以選擇調(diào)大proxy上的sort buffer。但是調(diào)大sort buffer會占用更多的內(nèi)存資源，所以不能無限制的調(diào)大sort buffer。

3. 排序優(yōu)化思路

把數(shù)據(jù)分片返回的有序數(shù)據(jù)保存到磁盤上，然后對磁盤數(shù)據(jù)進(jìn)行重排序。下面將介紹一種優(yōu)化方案，針對大數(shù)據(jù)量進(jìn)行分布式排序的方法。

三、優(yōu)化方案

1. 排序方案介紹

由于內(nèi)存的限制，在內(nèi)存中對大數(shù)據(jù)量數(shù)據(jù)進(jìn)行歸并排序方案不可行，針對這種情況需要把數(shù)據(jù)分片返回的數(shù)據(jù)暫存在磁盤中。具體優(yōu)化方案步驟如下圖：

(1) client向proxy下發(fā)排序查詢語句 select *from t1 order by id。

(2) proxy根據(jù)分片鍵向相關(guān)的數(shù)據(jù)分片group1、group2下發(fā)排序查詢語句select *from t1 order by id。

(3) 數(shù)據(jù)分片在本地對數(shù)據(jù)進(jìn)行查詢排序后，發(fā)送有序數(shù)據(jù)到proxy。

(4) proxy把數(shù)據(jù)分片返回的有序數(shù)據(jù)存儲在數(shù)據(jù)分片對應(yīng)的磁盤文件中。

(5) 使用優(yōu)先級隊(duì)列排序方法進(jìn)行重排序：

• 每個(gè)數(shù)據(jù)分片出一條數(shù)據(jù)構(gòu)建堆，heap包含的節(jié)點(diǎn)個(gè)數(shù)等于數(shù)據(jù)分片的個(gè)數(shù)。
• 為了避免優(yōu)先級隊(duì)列排序過程中從磁盤中逐條讀取數(shù)據(jù)造成的性能問題，proxy從磁盤文件中讀取數(shù)據(jù)預(yù)填充到數(shù)據(jù)分片對應(yīng)的sort buffer。
• 每個(gè)分片的sort buffer出一條數(shù)據(jù)構(gòu)造成一個(gè)heap。
• 從堆頂彈出數(shù)據(jù)發(fā)送給client。
• 堆頂數(shù)據(jù)彈出后，從已彈出節(jié)點(diǎn)對應(yīng)的sort buffer再讀取一條數(shù)據(jù)push到堆。
• 分片sort buffer中的數(shù)據(jù)取完后，需要繼續(xù)從對應(yīng)的磁盤文件中拉取數(shù)據(jù)，對sort buffer進(jìn)行填充。
• 直至取完所有數(shù)據(jù)發(fā)送到client。

2. 排序方案缺陷

proxy需要收集完所有相關(guān)數(shù)據(jù)分片的有序數(shù)據(jù)存入磁盤可以解決內(nèi)存不夠的問題，但是磁盤也是有限的，當(dāng)數(shù)據(jù)量太大在proxy上磁盤也可能無法容納需要排序的數(shù)據(jù)。

proxy上把數(shù)據(jù)存在磁盤，存在大量的磁盤IO。

以select * from t1 order by field1 limit 100w為例：如果本次查詢的數(shù)據(jù)在50個(gè)數(shù)據(jù)分片上，則proxy節(jié)點(diǎn)需要從每個(gè)數(shù)據(jù)分片上拉取100w數(shù)據(jù)然后保存到磁盤上。這樣需要保存5000W數(shù)據(jù)(100w*50)，而client只需要100w條數(shù)據(jù)，浪費(fèi)了很多網(wǎng)絡(luò)帶寬和磁盤IO。

3. 排序優(yōu)化思路

這種方法是proxy把相關(guān)數(shù)據(jù)分片的有序數(shù)據(jù)全部拉取到proxy上，然后再進(jìn)行排序。我們是否分批從數(shù)據(jù)分片拉取數(shù)據(jù)，批量數(shù)據(jù)處理后再從數(shù)據(jù)分片拉取下一批數(shù)據(jù)呢？下面將介紹一種分批排序的方法。

四、最終方案

1. 排序方案介紹

proxy上磁盤上不保存數(shù)據(jù)分片數(shù)據(jù)，一次從數(shù)據(jù)分片拉取固定大小的有序數(shù)據(jù)，proxy把拉取的數(shù)據(jù)填充到分片對應(yīng)的sort buffer，sort buffer中數(shù)據(jù)使用完后再次從對應(yīng)的數(shù)據(jù)分片上拉取。具體步驟如下圖：

(1) client向proxy下發(fā)排序查詢語句 select *from t1 order by id。

(2) proxy根據(jù)分片鍵向相關(guān)的數(shù)據(jù)分片group1、group2下發(fā)排序查詢語句select *from t1 order by id。

(3) 數(shù)據(jù)分片在本地對數(shù)據(jù)進(jìn)行查詢排序后，發(fā)送固定大小有序數(shù)據(jù)到proxy。

(4) proxy把數(shù)據(jù)分片返回的有序數(shù)據(jù)存儲在數(shù)據(jù)分片對應(yīng)的sort buffer中。

(5) 優(yōu)先級隊(duì)列排序：

• 每個(gè)數(shù)據(jù)分片對應(yīng)的sort buffer出一條數(shù)據(jù)構(gòu)建堆，堆節(jié)點(diǎn)的個(gè)數(shù)等于數(shù)據(jù)分片的個(gè)數(shù)；
• 從堆頂彈出數(shù)據(jù)發(fā)送給client；
• 堆頂數(shù)據(jù)彈出后，從已彈出節(jié)點(diǎn)對應(yīng)的sort buffer再讀取一條數(shù)據(jù)push到堆；
• 分片sort buffer中的數(shù)據(jù)取完后，需要繼續(xù)從對應(yīng)的數(shù)據(jù)分片節(jié)點(diǎn)中拉取數(shù)據(jù)，對sort buffer進(jìn)行填充；
• 直至取完所有數(shù)據(jù)發(fā)送到client。

2. 排序方案分析

針對優(yōu)化方案3.2存在的三個(gè)缺陷的解決情況：

(1) 缺陷1：proxy需要收集完所有相關(guān)數(shù)據(jù)分片的有序數(shù)據(jù)存入磁盤可以解決內(nèi)存不夠的問題，但是磁盤也是有限的，當(dāng)數(shù)據(jù)量太大在proxy上磁盤也可能無法容納需要排序的數(shù)據(jù)。

解決情況：從圖中可以看出proxy的磁盤上不保存數(shù)據(jù)分片的數(shù)據(jù)。

(2) 缺陷2 ：proxy上把數(shù)據(jù)存在磁盤，存在大量的磁盤IO。

解決情況：proxy的磁盤上不保存數(shù)據(jù)分片的數(shù)據(jù)，所以不存在磁盤壓力太大問題。

(3) 缺陷3：select * from t1 order by field1 limit 100w為例：如果本次查詢的數(shù)據(jù)在50個(gè)數(shù)據(jù)分片上，則proxy節(jié)點(diǎn)需要從每個(gè)數(shù)據(jù)分片上拉取100w數(shù)據(jù)然后保存到磁盤上，需要保存5000W數(shù)據(jù)(100w*50)，而client只需要100w條數(shù)據(jù)，浪費(fèi)了很多網(wǎng)絡(luò)帶寬和磁盤IO。

解決情況：每次從數(shù)據(jù)分片拉取固定大小的數(shù)據(jù)，邊排序邊給客戶端返回?cái)?shù)據(jù)，當(dāng)給客戶端返回的數(shù)據(jù)達(dá)到100W時(shí)則完成本次查詢，網(wǎng)絡(luò)帶寬浪費(fèi)得到大大改善。

假設(shè)proxy上數(shù)據(jù)分片對應(yīng)的sort buffer大小為2M，從數(shù)據(jù)分片拉取的數(shù)據(jù)量：

最壞情況：拉取的數(shù)據(jù)量為 2M*50+100W，并且不需要保存磁盤。

最好情況：數(shù)據(jù)分布很均勻，給client返回100w數(shù)據(jù)后，所有sort buffer分片對應(yīng)的數(shù)據(jù)正好基本取空(都剩下一條)，此時(shí)拉取的數(shù)據(jù)量為 100W+50。

3. 方案使用限制

(1) 數(shù)據(jù)分片節(jié)點(diǎn)本身支持排序，絕大多數(shù)數(shù)據(jù)分片都是支持排序的。

(2) 數(shù)據(jù)分片需要支持分批讀取。

以MySQL作為數(shù)據(jù)分片為例，則需要 proxy上可以使用流式查詢或者游標(biāo)查詢。另外有些分布式數(shù)據(jù)庫在設(shè)計(jì)時(shí)就考慮到一些分布式的問題，它們數(shù)據(jù)分片節(jié)點(diǎn)在查詢結(jié)束前一直保留上下文，它們的分批讀取性能更高，這里就不再舉例。