分佈式數據庫排序及優化

作者：vivo 互聯網數據庫團隊 - Xia Qianyong

一、背景

1.1 分佈式數據庫架構

當前分佈式數據庫架構有不少，但是總體架構相差不大，主要組件都包含協調節點、數據分片、元數據節點、全局時鐘。一種常見的分佈式架構如下圖：

圖片

• gtm ：全局事務管理器 (全局時鐘)，一主多備；

• catalog: 元數據管理，一主多備；

• group: 水平分片, 每個 group 由一主多備數據存儲節點組成；

• proxy : 協調節點，無狀態，負責處理客戶端的請求，把請求按照分片規則發送到數據分片，彙總數據分片返回的數據，協同其它組件保證分佈式事務的一致性。

1.2 排序問題

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

當相關的數據量不大時，proxy 可把不同數據分片返回的數據保存在內存中，然後對內存中的數據重排序後返回給 client。當相關的數據量比較大時，如果把待重排序數據放到內存中則可能會導致 OOM，如果把待重排序數據暫存在 proxy 的磁盤中，則也有耗盡磁盤的風險並且會存在大量的磁盤 IO。下面將介紹一種分佈式數據庫排序及優化方法。

二、解決方案

2.1 排序方案介紹

爲了提高分佈式排序的性能，每個數據分片本身也要參與排序。這樣在 proxy 上得到分片返回的數據是有序的，proxy 對有序的數據重排序可以採用歸併排序或者優先級隊列排序方法，大大減輕 proxy 的壓力。

可以根據 proxy 內存大小配置 sort buffer 大小，通常默認爲 10M。如果一次查詢語句關聯 N 個數據分片，則需要到 sort buffer 按照 N 份進行切分，每個數據分片對應切分後的 sort buffer 大小爲 10M/N。

直接在內存中進行，具體步驟如下圖：

圖片

• client 向 proxy 下發排序查詢語句 select *from t1 order by id。

• proxy 根據分片鍵以及分片規則向相關的數據分片 group1、group2 下發排序查詢語句 select *from t1 order by id。

• 數據分片在本地對數據進行查詢排序後，發送有序數據到 proxy。

• proxy 把數據分片返回的有序數據存儲在數據分片對應的 sort buffer 中，並對有序數據進行歸併排序。

• proxy 把歸併排序好的數據發送給 client。

2.2 排序方案缺陷

這種方法只能滿足小數據量排序，當排序的數據量較大我們可以選擇調大 proxy 上的 sort buffer。但是調大 sort buffer 會佔用更多的內存資源，所以不能無限制的調大 sort  buffer。

2.3 排序優化思路

把數據分片返回的有序數據保存到磁盤上，然後對磁盤數據進行重排序。下面將介紹一種優化方案，針對大數據量進行分佈式排序的方法。

三、優化方案

3.1 排序方案介紹

由於內存的限制，在內存中對大數據量數據進行歸併排序方案不可行，針對這種情況需要把數據分片返回的數據暫存在磁盤中。具體優化方案步驟如下圖：

圖片

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

2）proxy 根據分片鍵向相關的數據分片 group1、group2 下發排序查詢語句 select *from t1 order by id。

3）數據分片在本地對數據進行查詢排序後，發送有序數據到 proxy。

4）proxy 把數據分片返回的有序數據存儲在數據分片對應的磁盤文件中。

5）使用優先級隊列排序方法進行重排序：

• 每個數據分片出一條數據構建堆，heap 包含的節點個數等於數據分片的個數。

• 爲了避免優先級隊列排序過程中從磁盤中逐條讀取數據造成的性能問題，proxy 從磁盤文件中讀取數據預填充到數據分片對應的 sort buffer。

• 每個分片的 sort buffer 出一條數據構造成一個 heap。

• 從堆頂彈出數據發送給 client。

• 堆頂數據彈出後，從已彈出節點對應的 sort buffer 再讀取一條數據 push 到堆。

• 分片 sort buffer 中的數據取完後，需要繼續從對應的磁盤文件中拉取數據，對 sort buffer 進行填充。

• 直至取完所有數據發送到 client。

3.2 排序方案缺陷

• proxy 需要收集完所有相關數據分片的有序數據存入磁盤可以解決內存不夠的問題，但是磁盤也是有限的，當數據量太大在 proxy 上磁盤也可能無法容納需要排序的數據。

• proxy 上把數據存在磁盤，存在大量的磁盤 IO。

• 以 select * from t1 order by field1 limit 100w 爲例：如果本次查詢的數據在 50 個數據分片上，則 proxy 節點需要從每個數據分片上拉取 100w 數據然後保存到磁盤上。這樣需要保存 5000W 數據 (100w*50)，而 client 只需要 100w 條數據，浪費了很多網絡帶寬和磁盤 IO。

3.3 排序優化思路

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

四、最終方案

4.1 排序方案介紹

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

圖片

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

2）proxy 根據分片鍵向相關的數據分片 group1、group2 下發排序查詢語句 select *from t1 order by id。

3）數據分片在本地對數據進行查詢排序後，發送固定大小有序數據到 proxy。

4）proxy 把數據分片返回的有序數據存儲在數據分片對應的 sort buffer 中。

5）優先級隊列排序。

• 每個數據分片對應的 sort buffer 出一條數據構建堆，堆節點的個數等於數據分片的個數.

• 從堆頂彈出數據發送給 client.

• 堆頂數據彈出後，從已彈出節點對應的 sort buffer 再讀取一條數據 push 到堆.

• 分片 sort buffer 中的數據取完後，需要繼續從對應的數據分片節點中拉取數據，對 sort buffer 進行填充.

• 直至取完所有數據發送到 client.

4.2 排序方案分析

針對優化方案 3.2 存在的三個缺陷的解決情況。

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

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

缺陷 2 ：proxy 上把數據存在磁盤，存在大量的磁盤 IO。

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

缺陷 3：select * from t1 order by field1 limit 100w 爲例：如果本次查詢的數據在 50 個數據分片上，則 proxy 節點需要從每個數據分片上拉取 100w 數據然後保存到磁盤上，需要保存 5000W 數據 (100w*50)，而 client 只需要 100w 條數據，浪費了很多網絡帶寬和磁盤 IO。

解決情況：每次從數據分片拉取固定大小的數據，邊排序邊給客戶端返回數據，當給客戶端返回的數據達到 100W 時則完成本次查詢，網絡帶寬浪費得到大大改善。

假設 proxy 上數據分片對應的 sort buffer 大小爲 2M，從數據分片拉取的數據量：

• 最壞情況：拉取的數據量爲 2M*50+100W，並且不需要保存磁盤。

• 最好情況：數據分佈很均勻，給 client 返回 100w 數據後，所有 sort buffer 分片對應的數據正好基本取空 (都剩下一條)，此時拉取的數據量爲 100W+50。

4.3 方案使用限制

1）數據分片節點本身支持排序，絕大多數數據分片都是支持排序的。

2）數據分片需要支持分批讀取。

以 MySQL 作爲數據分片爲例，則需要 proxy 上可以使用流式查詢或者遊標查詢。另外有些分佈式數據庫在設計時就考慮到一些分佈式的問題，它們數據分片節點在查詢結束前一直保留上下文，它們的分批讀取性能更高，這裏就不在舉例。

五、參考文獻

1.JDBC 操作 MySQL（3）—查詢

2.MySQL JDBC StreamResult 通信原理淺析

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/42t4S93sJhXC2r_7DvYSZA