基于節點負載的數據動態分區①

孟令伍, 楊陽朝, 黃曉明, 練麗萍

1(南京萊斯網信技術研究院有限公司, 南京 210014)

2(深圳市網聯安瑞網絡科技有限公司, 深圳 518038)

3(中電科新型智慧城市研究院有限公司, 深圳 518026)

1 引言

大數據[1]的發展, 帶動了各種分布式計算、存儲框架的發展. 其中Spark、Flink等作為開源主流的分布式計算框架, HBase、MemSQL、Elasticsearch等作為開源主流的分布式存儲框架. 但是計算存儲框架都存在分區不合理引發數據傾斜[2,3]而導致的集群負載不均衡現象, 大大降低了應用的分析性能. 因此, 為了提高集群數據分析性能, 有必要對數據分區策略進行研究, 最終提高數據分析的響應速度, 快速為企業提供決策, 增加效益.

分布式存儲框架Elasticsearch[4]采用主從結構, 使用路由 Hash[5]作為存儲方式, 以數據分區Shards作為物理分區, 底層依托Lucene倒排索引結構, 并且支持文本分詞, 非常適合關鍵詞搜索分析. Spark 同樣采用主從結構, Master 節點(主節點)管理整個集群的資源,Worker 節點(從節點)管理各計算節點的資源, 定期向Master 節點匯報節點資源情況, 并啟動 Executor 進行計算.

Spark-Elasticsearch[6]集成的應用場景, 采用local方式讀取數據分析的方式, 通過Elasticsearch Spark Connect組件將二者集成, Spark中Master與Elasticsearch中主節點連接起來, 然后Spark的Worker節點可以通過Master節點獲取到Elasticsearch中主節點的元數據信息, 其元數據信息包括數據有哪些分區及各分區存儲在哪些節點上, 從而實現程序進行數據分析過程中,Spark的Worker節點利用esRDD接口本地化并行地從Elasticsearch存儲節點進行數據讀寫、計算分析, 如圖1所示. Elasticsearch中最小物理分區是Shard, 目前每個節點默認分配相同的Shard數, 這會因為集群節點資源的異構性[7]導致節點處理能力的不同而引發節點之間數據傾斜問題. 由于此框架中Spark采用local分析數據的方式, 即數據在哪個節點上面, 就在相應節點上進行分析處理, Elasticsearch中的Shard數目直接反映 Spark 中的 RDD task 數目, 即任務量與分區數呈正相關關系, 如果采用默認分區方式會導致嚴重負載不均衡現象, 如很多分區塊分布在負載高的數據節點上進行處理分析, 那么會拖慢整個作業完成效率, 因為Spark 任務調度結束是所有task都完成的時刻. 現實應用中, 數據傾斜問題普遍存在, 由其引起的處理節點負載不均衡是 Spark-Elasticsearch集成框架應用不可避免的問題.

圖1 Spark讀Elasticsearch中數據機制圖

有關動態分區解決負載均衡性的相關研究中, 李想等人[8]提出一種改進的遺傳算法的數據分配策略,采用自適應交叉和變異算子策略. 王曉燕等人[9]采用Nash-Pareto優化均衡策略協同自動數據分布. 王新友等人[7]設計一種基于時間序列模型二次指數平滑法對引航事故進行預測, 減少引航事故的發生. 楊華芬[10]提出一種基于優化FA模型的動態遷移算法, 首先構建動態遷移框架, 確定數據中心和網絡節點的拓撲結構, 然后利用FA仿生群智能算法在數據中心區域范圍內更新個體的位置并尋找最優解, 最后引入適應度函數和自適應慣性權重優化算法并擴大尋優范圍, 實現大數據遷移成本最小化. 劉琨[11]采用一次平滑預測算法+客觀熵值法權重模型, 通過確定節點負載情況來進行虛擬機資源遷移達到負載均衡效果. 陳濤等人[12]提出一種數據分布算法CCHDP, 將聚類算法和一致性Hash方法結合, 根據設備可用資源權重自適應調節分配數據. 宋懷明等人[13]設計了自適應散列和直方圖相結合的數據分布策略, 動態調整節點負載均衡性. 王晶等人[14]設計了一種基于動態閾值的遷移時機判決算法與基于負載類型感知的選擇算法相結合的虛擬機動態遷移策略, 最終根據虛擬機與目的節點的資源匹配度與遷移代價選擇目的節點, 對高負載與低負載節點的虛擬機動態調整, 從而優化節點資源配置問題.

針對Spark-Elasticsearch集成框架進行數據分析的應用場景, 需要提出Elasticsearch分區策略來改善負載均衡性, 提高應用的響應速度. 因此本文提出一種基于節點負載的數據動態分區機制和策略. 基于節點負載的數據動態分區機制包括負載監測采集、預測、數據預分區、數據遷移等模塊； 基于節點負載的數據分區策略采用二次平滑法預測節點負載, 結合了 AHP 和熵值指標權重法, 能夠根據不同的數據分析應用得到相應的分區策略, 動態地調整系統的負載均衡性, 提高應用的響應速度.

2 基于節點負載的數據動態分區機制和策略

針對Spark-Elasticsearch集成框架的應用場景, 即采用local方式讀取數據分析的方式, 需要有效地將數據進行分布來提高系統的負載均衡性, 通過提高并行度來降低應用的響應時間. Spark的Worker節點local方式并行地從Elasticsearch存儲節點進行數據讀寫、計算分析, 如圖2所示. Elasticsearch中最小的物理單元是Shard, 而Elasticsearch中的Shards數目直接反映Spark中的RDD task數目.

圖2 Spark-Elasticsearch集成框架圖

因為Spark并行訪問Elasticsearch中的每個分區中的數據, 并將每個分區中的數據轉化成自身的一個RDD分區, 由于Spark中的一個RDD分區對應一個task, 而task需要CPU來處理, 為了減少CPU資源的上下文切換, 充分利用CPU資源, 則Elasticsearch中的Shards數目的設置要適中, 不能過小或過大, 經相關技術人員進行長時間的研究測試, 一般選擇可用CPU核數的2-3倍； 同時每個Shards中的數據需近似相等,來提高task的并行度.

在數據預分區階段, Elasticsearch的數據分布默認是每個節點的分區數目相同, 而這樣會因為集群中每個節點資源的異構性導致節點處理能力的不同而引起節點之間的數據傾斜現象, 引發集群負載不均衡的問題. 集群節點偶然會出現負載瞬時高低峰值的情況而影響數據分區決策的擬定； 同時由于任務類型的不同,如計算型、內存性、網絡傳輸等任務類型會導致每種指標的權重不同, 需要確定每種指標權重來擬定數據分區策略； 如果數據已經分配完, 但集群在應用過程中可能會因為負載不均衡問題導致任務執行阻塞, 也可能因為節點的增刪操作引發負載不均衡等問題, 在現實應用中都可能遇到.

因此, 為了解決上述問題, 需要設計相應的數據動態分區機制和策略來改善系統的負載均衡性來提高應用的響應速度.

2.1 數據動態分區機制

為了動態調整集群負載均衡性來提高應用的響應速度, 提出了基于節點負載的數據動態分區機制, 如圖3所示, 該機制包括集群節點資源的監測、采集, 數據的預分區、遷移等模塊. 整個Spark-Elasticsearch集成集群一直處于應用使用中, 監測模塊定時讀取從節點中各個指標的負載信息, 動態地顯示CPU、內存和帶寬的利用率等信息； 然后通過資源采集模塊將負載信息緩存起來, 并定期持久化到MySQL中, 為負載預測提供指標實時負載信息； 接著如果有大量數據進行導入時, 需要對每個節點的每種指標進行預測, 再通過指標權重判定方法獲得每種指標的權重, 接著再依據負載預測后的指標信息與每種指標的權重值來獲得每個節點的處理能力, 最后根據每個節點的處理能力進行數據分布, 完成數據的預分區； 如果集群在實際應用中出現嚴重的負載不均衡問題, 如達到了設定負載閾值, 則將高低負載節點加入到源、目標機隊列中, 并結合遷移策略進行分區塊的遷移.

圖3 基于節點負載的數據動態分區機制流程圖

2.2 數據動態分區策略

本文基于節點負載來進行數據有效地分布, 要解決如下問題:

(1)初始情況下, 面對大量數據的導入, 數據預分區根據什么原則進行數據分布.

(2)可能因為某些應用執行完或者預分區不合理情況導致集群負載不均衡現象, 通過數據遷移調整負載.

本節通過動態分區策略來改善系統負載均衡性,提高應用的響應速度. 采用二次平滑法預測節點負載,結合了 AHP 和熵值指標權重法, 能夠根據不同的數據分析應用得到相應的分區策略, 動態地調整系統的負載均衡性, 提高應用的響應速度.

2.2.1 數據預分區策略

(1)負載預測

因數據預分區不合理、節點的宕機刪除節點、增加節點進行水平擴展及出現負載極其不均衡問題等,都需要進行分區塊的遷移來平衡負載量, 采用二次指數平滑法負載預測模塊來決定遷移量.

其中,n代表取的周期數,j代表第j個周期. 預測機制的流程如圖4所示, 通過調整平滑系數α值來計算偏方差S, 取S最小時對應的平滑系數α值.n、d的值由用戶設定.

圖4 預測機制流程圖

(2)指標權重判定方法

因為Spark-Elasticsearch集成框架環境下的應用場景, 內存變化波動較小, 帶寬和CPU變化波動較大,如果只考慮客觀熵值法則會影響內存的權重判定, 如果只考慮主觀AHP權重法會忽略某些指標的重要性.因此, 本文通過基于二次平滑負載預測法+主客觀AHP與熵值指標權重集成法結合的指標權重判定方法算出每個節點的整體負載值, 最終再根據整體負載值來分配相應的數據分區數.

1) AHP

AHP由決策者對所有評價指標進行兩兩比較, 得到判斷矩陣U=(Aij)n×n. 本論文取CPU利用率、內存利用率和帶寬利用率作為負載的評價指標, 判斷矩陣如下:

其中,A1,A2,A3分別代表CPU利用率、內存利用率和帶寬利用率對節點整體負載影響的權重值. 對每列進行歸一化求取特征向量, 再對每行進行歸一操作求取特征向量, 最后得到各指標的權重配比, 同時對判斷矩陣A進行一致性檢驗, 證明判斷矩陣的合理性, 最終可得到CPU、內存和帶寬的主觀權重分別為WS1,WS2,WS3, 并且WS1+WS2+WS3=1.

2) 熵值法

熵值法通過判斷指標變化的離散度來反映該指標影響程度, 能夠通過指標變異度客觀地確定指標權重.具體步驟如下:

① 通過測試過程得到各指標負載來構建負載信息決策矩陣M

其中,n代表周期數,CUR、MUR和BUR分別代表CPU、內存和帶寬的利用率.

② 對決策矩陣M每列做歸一化處理得到矩陣R

③ 利用熵公式計算指標不確定度

用E表示某種指標的熵, 公式如下:

其中,Ej代表指標的熵值, 常數K=1/ln(n), 這樣能保證0≤E≤1, 即E最大為1. 當某個屬性下各值的貢獻度趨于一致時,E趨于1, 可看出屬性列值差異性大小可影響權系數大小, 因此可定義Dj為某個指標的貢獻度,Dj= 1-Ej.

④ 計算每種指標的客觀權重值, 公式如下:

WO1,WO2,WO3代表內存、CPU和帶寬對于節點負載影響的客觀權重值, 并且WO1+WO2+WO3=1. 先通過輸入每種指標不同周期負載值矩陣, 再計算每種指標客觀權重值, 最后通過熵值法計算得到每種指標的客觀權重值.

3) 主客觀AHP和熵值法權重集成法

真實情況可能出現主、客觀指標權重設計的弊端問題, 為了減少弊端影響性. 因此本發明設計主客觀集成的方法來解決此類問題, 平衡兩者的權重偏差. 集成權重公式如下:

其中,β為主客觀權重調整系數,wi為最終節點負載的權重, 其中i=1,2,3, 并且w1+w2+w3=1. 輸入每種指標的主客觀權重值, 再通過主客觀權重集成法得到每種指標的集成權重值.

4) 節點的數據分布

首先, 由前面模塊得到了內存、CPU、帶寬3種指標在負載中所占的主客觀集成權重大小后, 分別為w1,w2,w3.

然后, 通過每種指標權重計算得到每個節點的處理能力, 公式如下:

其中,CAUi,MAUi,BAUi分別代表指標預測后的CPU、內存、帶寬利用率,i代表第i節點.

最后, 得出每個節點要分配的數據量的占比, 公式如下:

其中,DPi代表第i節點應分配的數據量占比, 有m個節點.

通過以上步驟后可知給集群中每個節點分配的數據量, 即相應的分區數.

2.2.2 數據遷移策略

通過設置高低負載閾值來作為觸發數據遷移的條件, 構造出源機和目標機的選擇隊列. 在數據預分區之后出現負載不均衡問題或者增刪節點的情況, 需要選擇源機和目標機來進行數據遷移, 源機作為待遷移數據的節點, 目標機作為接受遷移數據的節點, 并獲得應遷移的分區數.

(1)源機選擇

首先, 從負載緩存數組中讀取內存利用率、CPU利用率和帶寬利用率負載信息采用二次平滑法進行預測, 預測T個周期后的每種指標平均負載值.

然后, 將每種指標的負載利用率預測值與主客觀權重集成方法得到每種指標權重值相結合, 進而得到每個節點的整體負載值Loadi. 負載值公式如下:

其中,CURi,MURi,BURi和w1,w2,w3分別為預測后的CPU利用率、內存利用率、帶寬的利用率和權重值.

接著, 比較每個節點的負載值Loadi和設置的閾值Hth, 如果某個節點的負載值超過閾值Hth, 則將該節點加入到高負載節點隊列中.

然后, 按照Loadi值由大到小構成源機選擇隊列S源={s1,s2, …,sm}.

最后, 從S源隊列中選取源機. 對S源隊列中的Load值按降序排列, 按Loadi值從大到小的順序進行源機的選擇.

(2)目標機選擇

首先, 從負載緩存數組中讀取內存利用率、CPU利用率和帶寬利用率負載信息進行預測, 分別預測每種指標T個周期后的平均負載值.

然后, 將每種指標的負載利用率預測值與主客觀權重集成方法得到每種指標的負載權重值結合, 代入主客觀集成法計算, 進而得到每個節點的整體負載值Loadi.

接著, 將每個節點的負載值Loadi與設置的閾值Lth進行比較, 如果某個節點的負載值低于閾值Lth, 則將該節點加入到低負載節點隊列中.

然后, 按照Loadi值構建由小到大目標機選擇隊列D目={d1,d2, …,dm}.

最后, 從D目隊列中選取目標機. 對D目隊列中的Load值按升序進行排列, 按Loadi從小到大的順序進行目標機的選擇.

(3)遷移的分區數

1)如果高低負載隊列節點數相同, 即S源=D目. 則分別將高低負載節點隊列的數據按照順序進行匹配并行遷移, 遷移的分區數公式如下:

其中,N遷,N源,N目分別代表遷移的分區數, 源機中的分區數, 目標機中的分區數.

2)如果高負載隊列節點數大于低負載節點數目,即S源＞D目. 則適當調整低負載閾值, 使低負載節點隊列節點數目等于或近大于高負載節點隊列節點數目,接著按照上述遷移公式設定遷移的分區數.

3)如果高負載隊列節點數目遠小于低負載節點數目, 即S源＜D目. 則適當調整高負載閾值, 使高負載節點隊列節點數目等于或近小于低負載節點隊列節點數目,接著按照上述遷移公式設定遷移的分區數.

4)得到匹配的源機和目標機隊列, 并知道了每組中源機應遷移的分區數, 采用并行進行遷移, 減少遷移開銷.

通過以上步驟, 系統可實現負載均衡. 對于增刪節點的突發情況, 同樣可以采用此種遷移策略.

3 實驗與分析

本文針對Spark-Elasticsearch集成框架的應用場景, 在局域網下部署Spark-Elasticsearch集成集群環境,集群中每個節點都是虛擬機, 本部分實驗4個節點, 相關配置參數如表1所示, 設定的總分區數為32個分區,利用某制造企業中的數據集, 驗證基于負載預測和AHP、熵值集成權重法結合的數據動態分區策略的有效性.

表1 Spark-MemSql集成框架機器參數

3.1 實驗環境

3.2 實驗數據

實驗采用某制造業表product作為測試數據集, 如圖5所示, 大約有5000萬行數據. 每條數據主要包括產品長度、產品拉伸長度、產品重量等. 其中weight和length兩列作為關聯分析應用測試集, weight、drawlength、length三列可作為K-means應用測試集,不同的應用利用不同的數據集做測試.

圖5 分區策略性能對比測試數據集

3.3 基于節點負載的動態分區策略實驗分析

(1)對不同預分區策略進行性能對比測試. 本實驗對weight和length兩列做關聯分析, 分析產品長度和重量之間的關聯性； 對weight、drawlength、length三列做K-means聚類分析, 通過聚類分析分類. 通過比較默認預分區策略、負載預測+AHP權重法、負載預測+AHP與熵值集成權重法的3種不同預分區策略, 然后分別統計執行相同應用的時間, 驗證方案的有效性.

(2)在Spark-Elasticsearch框架中如果出現集群負載不均衡現象, 結合遷移策略對源機和目標機的數據分區塊進行遷移, 重復運行應用程序, 對遷移前后做性能對比, 驗證方案的有效性.

3.3.1 預分區策略對比測試

通過不同的預分區策略進行分區, 實驗重復運行應用程序, 第1組實驗進行關聯分析的應用； 第2組實驗進行K-means聚類分析的應用. 對執行時間進行對比, 驗證不同分區方案的有效性.

(1)不同應用中不同指標平滑系數α

采用二次平滑預測算法最終獲得不同應用場景下的不同指標的平滑系數α, 如表2和表3所示.

表2 關聯分析應用中不同指標的平滑系數α

表3 K-means聚類分析應用中不同指標的平滑系數α

(2)利用AHP得出每種指標的權重

首先, 輸入指標決策矩陣A:

評判采用列與行進行兩兩比較, 其中A1,A2,A3分別代表CPU、內存、帶寬； 然后, 計算隨機一致性比率C.R.=C.I./R.I.=0.001＜0.1, 說明決策矩陣設計合理；接著, 利用AHP獲得每種指標的權重值； 最后通過多次實驗調整設置權重系數β為0.7, 得到集成權重值,不同的應用場景結果分別如表4和表5所示.

表4 關聯分析應用中不同負載指標權重值對應表(%)

表5 K-means聚類分析應用中不同負載指標權重值對應表(%)

(3)根據應用中預測的每種指標負載值和不同權重方法, 獲得不同分區策略下每個節點的處理能力, 得出每個節點分區數的分區數, 如表6所示.

表6 不同分區策略推薦的每個節點的分區數

通過圖6、圖7所示, 分別執行關聯分析和K-means聚類應用. 從整體上看默認分區策略效果最差, 本文設計的預測+AHP與熵值權重集成法分區策略最好, 并且隨著數據量的增加, 效果越顯著. AHP權重法是主觀權重法, 沒有根據實際應用場景進行權重配比, 有失客觀性； Spark-Elasticsearch框架的數據計算是在內存中進行的, 因此內存使用較穩定, 而帶寬使用變化程度較大,但利用率很低, 如果只采用客觀法會導致內存權重小、帶寬權重較大的錯誤結果. 因此集成主客觀權重會帶來更好的結果. 執行不同的應用取得了同樣的效果, 說明本文研究的預分區策略在處理相對獨立任務的應用上具有推廣性.

圖6 關聯分析應用預分區策略性能對比圖

圖7 K-means聚類分析應用預分區策略性能對比圖

如圖8、圖9所示, 針對不同預分區策略執行相同的應用, 計算整個應用過程中每個節點平均負載利用率. 從整體上看默認分區策略出現嚴重的負載不均衡現象, 預測+AHP、預測+AHP+熵值權重集成法結合的預分區策略都能較好地解決集群負載問題, 實現集群負載的均衡性.

圖8 關聯分析應用不同預分區策略節點負載利用率對比圖

圖9 K-means聚類分析應用的不同預分區策略節點負載利用率對比圖

3.3.2 數據遷移對比測試

在Spark-Elasticsearch框架中遇到負載不均衡現象, 通過數據遷移策略, 對遷移前后的執行時間進行對比, 并考慮遷移時間開銷, 驗證方案有效性.

利用遷移策略構造高低負載隊列, 獲得不同節點應發送或接收的分區塊數, 執行遷移操作后, 每個節點的分區數如表7所示.

表7 遷移前后的節點分區數對應表

通過圖10、圖11所示, 表明了遷移策略的有效性, 可以改善集群的負載均衡性, 一定程度上提高了應用的響應速度. 數據量較少時, 關聯分析數據量小于3000萬時和K-means分析數據量小于2000萬時負載沒到設定的閾值, 不觸發遷移, 但是當數據量相對較大時, 即關聯分析數據量達到3000萬和K-means分析數據量達到2000萬時負載超過閾值, 觸發遷移. 雖然改善了集群的負載均衡, 但是遷移需要消耗時間, 導致總時間較長, 當數據量擴大時, 負載不均衡性加劇, 導致遷移成本相對較小, 提升了應用的響應速度.

圖10 關聯分析遷移策略性能對比圖

圖11 K-means聚類分析遷移策略性能對比圖

通過圖12、圖13所示, 對不同應用進行遷移, 比較遷移前后整個應用過程中每個節點平均負載利用率,結果展示通過遷移能改善集群負載均衡性.

圖12 關聯分析數據遷移前后節點負載利用率平均值對比圖

圖13 K-means聚類分析數據遷移前后節點負載利用率平均值對比圖

4 總結

本文雖然改善了集群負載均衡性, 提高了數據分析應用的響應速度, 但是依然存在一些不足之處. 日后的工作應該圍繞以下幾個方面進行研究:

(1)指標權重的獲得

針對不同的應用難以找到最佳指標權重值, 本文采用主客觀權重集成法, 能較好地避免主客觀引起的偏差, 但不能得到指標權重配比最優解, 指標權重需做進一步研究及大量實驗驗證.

(2)數據遷移開銷的理論研究

本文雖然通過數據遷移策略改善了集群負載均衡性, 但沒從理論上考慮數據遷移過程中成本問題, 只是實驗中包括了遷移時間.