汪文豪，史雪榮

（1.南京工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，南京 211816；2.鹽城師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，江蘇 鹽城 224002）

0 概述

近年來，云計算、大數(shù)據(jù)、物聯(lián)網(wǎng)、人工智能等新一代信息技術(shù)快速發(fā)展，信息產(chǎn)業(yè)的數(shù)據(jù)量急劇增長。截止到2020 年底，我國的數(shù)據(jù)總量預(yù)計到達8 060 EB［1］。隨著信息數(shù)據(jù)量劇增，數(shù)據(jù)處理技術(shù)也在發(fā)生著巨大變化，涌現(xiàn)出Apache Hadoop、Apache Spark、Apache Storm、Heron、Flink 等［2］一大批數(shù)據(jù)計算系統(tǒng)。在數(shù)據(jù)處理的硬件方面，各種機構(gòu)和設(shè)備的更新?lián)Q代和新興技術(shù)的引入，使得各個數(shù)據(jù)計算系統(tǒng)在實際生產(chǎn)環(huán)境中變得越來越異構(gòu)［3-4］。這種異構(gòu)集群特征直觀表現(xiàn)在其節(jié)點的CPU、內(nèi)存等各方面存在差異致使集群運行時的處理能力不盡相同，從而使得集群在調(diào)度節(jié)點執(zhí)行任務(wù)時，集群效率明顯下降［5］。

目前，國內(nèi)外眾多學(xué)者對資源彈性管理問題和分布式框架下的任務(wù)及節(jié)點調(diào)度問題展開研究。在資源彈性管理方面：文獻［6］提出使用排隊理論進行建模，通過部署主動彈性控制器和反應(yīng)彈性控制器相結(jié)合的模型來估計集群節(jié)點的未來負(fù)載；文獻［7］認(rèn)為云計算存在資源傾斜的問題，提出動態(tài)實時云框架，使集群可以自動適應(yīng)不同的工作負(fù)載，并根據(jù)需求重新分配資源；文獻［8］基于云計算通用工作負(fù)載預(yù)測器，設(shè)計一種可以為不同工作負(fù)載提供高精度預(yù)測的長期記憶模型，解決了通用預(yù)測器精度不夠的問題，進一步優(yōu)化了集群資源彈性管理。在批處理框架方面：文獻［9］認(rèn)為Hadoop 框架在默認(rèn)調(diào)度時未考慮Map 與Reduce 之間存在差異性，據(jù)此提出一種基于Hadoop 框架的截止時間約束的擴展MapReduce 任務(wù)調(diào)度算法；文獻［10］認(rèn)為在Hadoop默認(rèn)調(diào)度方式下缺乏對整體集群異構(gòu)性的考慮，提出基于資源感知與資源異構(gòu)的云計算環(huán)境任務(wù)調(diào)度算法；文獻［11］基于Hadoop 框架的節(jié)點計算能力，設(shè)計能夠按計算能力分配數(shù)據(jù)塊的數(shù)據(jù)局部性調(diào)度器；文獻［12］認(rèn)為在異構(gòu)Hadoop 集群中會出現(xiàn)節(jié)點隨任務(wù)動態(tài)分配而產(chǎn)生性能差異的問題，提出基于動態(tài)工作負(fù)載調(diào)整的任務(wù)調(diào)度策略；文獻［13］在YARN 資源調(diào)度器的基礎(chǔ)上，結(jié)合閉環(huán)反饋控制方法，使Hadoop 集群在運行時可以動態(tài)對MapReduce作業(yè)數(shù)進行控制，避免出現(xiàn)主觀性的問題；文獻［14］基于異構(gòu)Spark 集群，提出通過監(jiān)測節(jié)點資源的自適應(yīng)動態(tài)節(jié)點任務(wù)調(diào)度策略，但是該策略依賴于人工設(shè)定的閾值，無法體現(xiàn)客觀性；文獻［15］在文獻［14］的基礎(chǔ)上，提出基于異構(gòu)節(jié)點優(yōu)先級的Spark 動態(tài)自適應(yīng)調(diào)度算法，該算法能夠根據(jù)實時節(jié)點優(yōu)先級完成調(diào)度，但是忽略了任務(wù)種類和集群整體工作環(huán)境，沒有徹底解決主觀性問題。在流處理框架方面：文獻［16］提出在流處理框架Storm on YARN 上構(gòu)建一種雙層調(diào)度模型，通過對流數(shù)據(jù)處理的實時監(jiān)測，做出合理的資源分配預(yù)測，解決框架需要人工干預(yù)調(diào)整的問題；文獻［17］針對流處理框架的數(shù)據(jù)拓?fù)渲腥蝿?wù)間通信開銷較大的問題，提出Flink 框架下的拓?fù)潢P(guān)鍵路徑模型，該模型能夠確保關(guān)鍵路徑上節(jié)點負(fù)載差異較小的同時最小化任務(wù)的節(jié)點間通信開銷。

但是現(xiàn)階段國內(nèi)外的相關(guān)研究主要存在兩方面的問題。一方面，大部分的分布式調(diào)度研究主要關(guān)注于批處理，將Hadoop 框架與Spark 框架作為主要的實驗環(huán)境，而對于流處理，尤其是以Flink 框架作為實驗環(huán)境的研究相對較少。另一方面，在實際作業(yè)環(huán)境中，很難避免整體集群出現(xiàn)異構(gòu)的情況，針對結(jié)合實際作業(yè)環(huán)境的異構(gòu)Flink 環(huán)境的研究也相對較少。本文通過研究分布式節(jié)點的實時性能和集群的工作環(huán)境預(yù)測機制，充分考慮現(xiàn)實生產(chǎn)環(huán)境的異構(gòu)分布問題，從而對Flink 底層默認(rèn)調(diào)度策略進行優(yōu)化，以提高Flink 系統(tǒng)的工作效率。

1 相關(guān)技術(shù)

Apache Flink 是一個面向數(shù)據(jù)流的有狀態(tài)計算框架，核心是一個流數(shù)據(jù)的處理引擎。在計算過程中，F(xiàn)link 將所有任務(wù)當(dāng)作流來處理，批處理任務(wù)被看作具備有限邊界的特殊數(shù)據(jù)流。相對于目前的大部分流處理框架，F(xiàn)link 框架在數(shù)據(jù)處理方面有低延遲、高吞吐的優(yōu)勢，在集群功能方面則提供了消息傳遞、狀態(tài)管理、容錯恢復(fù)等一系列服務(wù)［18-19］。

Flink 集群主要由兩個重要進程JobManager 和TaskManager 組成，如圖1 所示，其中虛線表示任務(wù)的流轉(zhuǎn)。JobManager 又稱為Master，主要協(xié)調(diào)整體架構(gòu)的數(shù)據(jù)流圖的運算和執(zhí)行，其中的調(diào)度器模塊和Checkpoint 協(xié)調(diào)器模塊還負(fù)責(zé)調(diào)度任務(wù)、協(xié)調(diào)檢查和故障恢復(fù)。TaskManager又稱為Worker，主要執(zhí)行由JobManager分配的任務(wù)。同時，每一個TaskManager都具有緩存數(shù)據(jù)和節(jié)點間通信的功能。在Flink 中，一個TaskManager 即為一個JVM 進程，JVM 進程允許并行地執(zhí)行子任務(wù)，并能夠指定若干slot。每一個slot 可以執(zhí)行若干子任務(wù)，即運行若干線程［18］。

圖1 Flink 集群架構(gòu)Fig.1 Flink cluster architecture

Flink 在調(diào)度任務(wù)分配slot 時，遵循2 個原則：1）同一Job 中的同一分組的不同task 可以共享同一slot；2）任務(wù)調(diào)度按照拓?fù)漤樞驈腟ource 調(diào)度到Sink。以圖2（a）的Flink 拓?fù)淠Ｐ蜑槔黜旤cν表示Flink 中的Operator 算子，νa表示Source 算子組件，νb、νc和νd表示并行度為3 的Transformation 算子組件，νe和νf表示并行度為2 的Sink 算子組件。首先由Source 組件將讀取的數(shù)據(jù)發(fā)送至Transformation 組件；然后Transformation 組件負(fù)責(zé)處理上游發(fā)送的數(shù)據(jù)；最后由Sink 組件接收上游處理結(jié)果并持久化至數(shù)據(jù)庫［20］。以有2 個TaskManager 的Flink 分布式集群為例，每一個TaskManager 配置有2 個slot。Flink在默認(rèn)調(diào)度下對于該任務(wù)拓?fù)涞膕lot 分配模型如圖2（b）所示。首先調(diào)度默認(rèn)從拓?fù)涞腟ource 任務(wù)開始，將νa隨機調(diào)度給任一slot，如圖2（b）中νa調(diào)度至slot11 所示；然后將νb、νc和νd調(diào)度至任意的slot，但νb、νc和νd同屬于一種Operator 算子，不能共享同一slot，因此將νb、νc和νd分別調(diào)度至slot11、slot12 和slot21；最后將νe和νf也分別調(diào)度至slot11 和slot12。

圖2 任務(wù)拓?fù)浞峙淠Ｐ虵ig.2 Task topology assignment model

2 基于節(jié)點優(yōu)先級的Flink 動態(tài)調(diào)度策略

2.1 節(jié)點優(yōu)先級定義及調(diào)整方法描述

2.1.1 相關(guān)定義

定義1（節(jié)點優(yōu)先級）Flink 集群的節(jié)點優(yōu)先級集合為P=｛P1，P2，…｝。Pix表示第i個節(jié)點的偏x相關(guān)性能優(yōu)先級指數(shù)，當(dāng)x=c時表示節(jié)點偏CPU 相關(guān)性能優(yōu)先級指數(shù)，當(dāng)x=m時表示節(jié)點偏內(nèi)存相關(guān)性能優(yōu)先級指數(shù)。

定義2（節(jié)點性能指數(shù)計算權(quán)值）在節(jié)點性能指數(shù)計算時，引入的各動靜態(tài)性能因素權(quán)值表示為向量與向量，當(dāng)x=c時當(dāng)前權(quán)值側(cè)重計算CPU相關(guān)優(yōu)先性能指數(shù)，當(dāng)x=m時當(dāng)前權(quán)值側(cè)重計算內(nèi)存相關(guān)優(yōu)先性能指數(shù)。對于任意的，有；對于任意的。

定義3（節(jié)點資源因素指數(shù)［15］）動態(tài)性能指數(shù)D=｛D1，D2，…｝表示節(jié)點在執(zhí)行任務(wù)時的實時性能變化。對于動態(tài)性能指數(shù)有3 個資源約束，分別是CPU 剩余率（CSR）、內(nèi)存剩余率（MSR）和磁盤剩余率（DSR）。靜態(tài)性能指數(shù)S=｛S1，S2，…｝表示節(jié)點的不對稱性能因素。對于靜態(tài)性能指數(shù)有4 個資源約束，分別為CPU 速度（CS）、CPU 核數(shù)（CQ）、內(nèi)存容量（MC）和磁盤容量（DC）。

對于每個動態(tài)指數(shù)Di∈D，對應(yīng)資源約束向量di=(CCSRi，MMSRi，DDSRi)；對于每個靜態(tài)指數(shù)Si∈S，對應(yīng)資源約束向量si=(CCSi，CCQi，MMCi，DDCi)。引入定義2中權(quán)值的計算后，得到Dix表示第i個節(jié)點的動態(tài)偏x性能指數(shù)，Six表示第i個節(jié)點的靜態(tài)偏x性能指數(shù)。

2.1.2 調(diào)整方法描述

本文所設(shè)計的節(jié)點優(yōu)先級調(diào)整方法是即時反饋方法，節(jié)點優(yōu)先級計算公式如下：

其中：α、β為節(jié)點整體動靜態(tài)因素指數(shù)權(quán)值，α+β=1；和表示節(jié)點動靜態(tài)偏x性能指數(shù)。和計算公式如下：

以4 個節(jié)點組成的Flink 異構(gòu)集群為例，給出節(jié)點優(yōu)先級調(diào)整架構(gòu)如圖3 所示。

圖3 節(jié)點優(yōu)先級調(diào)整架構(gòu)Fig.3 Node priority adjustment architecture

監(jiān)控器運行在集群Master 節(jié)點中，負(fù)責(zé)周期性收集節(jié)點的資源使用情況和任務(wù)隊列長度。獲取的資源信息將傳入到控制器中，由控制器完成具體節(jié)點優(yōu)先級計算。監(jiān)控器采用Ganglia［21］進行實現(xiàn)，Ganglia 是一個可擴展分布式集群資源監(jiān)控系統(tǒng)，能夠?qū)崿F(xiàn)對集群信息的監(jiān)控。

控制器負(fù)責(zé)根據(jù)監(jiān)控器監(jiān)測到的信息計算出各節(jié)點的優(yōu)先級。本文節(jié)點優(yōu)先級調(diào)整方法引入作業(yè)環(huán)境預(yù)測機制，在一個周期內(nèi)判定當(dāng)前集群作業(yè)環(huán)境的參數(shù)x由式（4）確定。如果集群節(jié)點的I/O 操作平均時間T（I/O）超過了整體操作時間T（all）的65%，則判定當(dāng)前集群作業(yè)環(huán)境為I/O 密集型，否則判定為CPU 密集型。

當(dāng)監(jiān)控器判定為I/O 密集型環(huán)境時，控制器將節(jié)點動靜態(tài)因素指數(shù)計算的權(quán)值重置為和，節(jié)點的偏內(nèi)存性能優(yōu)先級指數(shù)的計算公式如下：

當(dāng)監(jiān)控器判定為CPU 密集型環(huán)境時，控制器將節(jié)點動靜態(tài)因素指數(shù)計算的權(quán)值重置為和，節(jié)點的偏CPU 性能優(yōu)先級指數(shù)的計算公式如下：

2.2 節(jié)點優(yōu)先級調(diào)整算法

算法1節(jié)點優(yōu)先級調(diào)整算法EP-NPAA

2.3 基于節(jié)點優(yōu)先級的Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度策略

在實際運行環(huán)境中，異構(gòu)分布式集群的節(jié)點往往會出現(xiàn)資源不平衡和負(fù)載不均衡的情況。為保證任務(wù)的高效完成，需要準(zhǔn)確衡量各節(jié)點的性能以及整體集群的負(fù)載程度，選擇合適的節(jié)點分配任務(wù)［22］。本文提出一種基于節(jié)點優(yōu)先級的Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度算法。

2.3.1 基于節(jié)點優(yōu)先級的調(diào)度方法描述

基于節(jié)點優(yōu)先級的Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度方法建立在集群異構(gòu)的情況下，該方法的主要構(gòu)成如下：1）Master 節(jié)點監(jiān)控器定期監(jiān)控每個Worker 節(jié)點自身資源情況及負(fù)載變化情況，并反饋控制器定期動態(tài)計算各Worker 節(jié)點的優(yōu)先級指數(shù)；2）在Master 節(jié)點進行任務(wù)調(diào)度時，讀取各節(jié)點優(yōu)先級指數(shù)，選擇指數(shù)較大的節(jié)點分配任務(wù)。Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度架構(gòu)如圖4 所示。

圖4 Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度架構(gòu)Fig.4 Dynamic adaptive Flink node scheduling architecture

2.3.2 Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度算法

Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度算法運行在Master節(jié)點上，具體步驟為：1）啟動集群，Master 節(jié)點檢測節(jié)點是否出現(xiàn)變化，根據(jù)變化狀態(tài)調(diào)用EP-NPAA 算法重新計算節(jié)點的靜態(tài)因素指數(shù)Si；2）Master 節(jié)點內(nèi)控制器調(diào)用EP-NPAA 算法，依次計算每個Worker 節(jié)點的優(yōu)先級得到P=｛P1，P2，…｝，并對節(jié)點集合NodeSets 進行排序；3）控制器從節(jié)點集合NodeSets中按優(yōu)先級指數(shù)高低依次調(diào)用每個節(jié)點，檢測當(dāng)前調(diào)用節(jié)點是否有當(dāng)前task 可用的slot，若有可用的slot，則分配任務(wù)給該節(jié)點；若無可用slot，則繼續(xù)調(diào)用下一節(jié)點。

算法2Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度算法F-DASA

3 實驗與結(jié)果分析

3.1 實驗環(huán)境配置

為驗證本文自適應(yīng)調(diào)度策略對Flink 異構(gòu)集群的節(jié)點調(diào)度性能更佳，構(gòu)建Flink 異構(gòu)集群數(shù)據(jù)實驗平臺。該平臺由5 臺服務(wù)器組成，其中，1 臺為主服務(wù)器Master，4 臺為從服務(wù)器Worker。集群節(jié)點硬件與軟件配置如表1、表2 所示。

表1 集群節(jié)點硬件配置Table 1 Hardware configuration of cluster nodes

表2 集群節(jié)點軟件配置Table 2 Software configuration of cluster nodes

在實驗中進行節(jié)點優(yōu)先級計算時，規(guī)定動靜態(tài)因素權(quán)值α和β分別取值為0.65 和0.35；在內(nèi)存密集型作業(yè)環(huán)境下，各動態(tài)因素權(quán)值取值為（0.3，0.6，0.1），各靜態(tài)因素權(quán)值取值為（0.05，0.30，0.55，0.10）。在CPU 密集型作業(yè)環(huán)境下，各動態(tài)因素權(quán)值取值為（0.5，0.4，0.1），各靜態(tài)因素權(quán)值取值為（0.10，0.50，0.35，0.05）。

3.2 實驗數(shù)據(jù)設(shè)置

為有效驗證F-DASA 算法對Flink 異構(gòu)集群的影響，實驗將本文策略與Flink 默認(rèn)調(diào)度策略以及TSS-Flink 策略［17］進行大數(shù)據(jù)基準(zhǔn)測試WorldCount和TeraSort 對比。WorldCount 是詞頻統(tǒng)計基準(zhǔn)測試，特點是CPU 資源占用率較高、內(nèi)存占用率較低，數(shù)據(jù)集采用9 個表生成模擬5 種事務(wù)處理的TPC-C 數(shù)據(jù)集［23］。TeraSort 是分布式排序基準(zhǔn)測試，在執(zhí)行過程中會大量占用內(nèi)存資源，數(shù)據(jù)集為待排序的數(shù)值型數(shù)據(jù)集。

3.3 結(jié)果分析

3.3.1 運行時間對比

實驗通過對比使用Flink 默認(rèn)調(diào)度策略、TSSFlink 策略和本文策略后的作業(yè)運行時間，驗證F-DASA 算法對Flink 異構(gòu)集群的影響。在實驗過程中，基準(zhǔn)測試WorldCount 的數(shù)據(jù)集規(guī)模分別為2 GB、4 GB 和6 GB，且設(shè)置不同的作業(yè)并行度，運行時間如圖5 所示。

圖5 作業(yè)運行時間對比Fig.5 Comparison of job runtime

從圖5 的實驗結(jié)果可以看出，在并行度為8 和16 的情況下，使用TSS-Flink 策略和本文策略后，基準(zhǔn)測試WorldCount 的運行時間都有所減少。在使用本文策略之后，比使用Flink 默認(rèn)調(diào)度策略約平均減少了6%。這是因為在默認(rèn)調(diào)度策略下，調(diào)度器使異構(gòu)集群中資源較少的節(jié)點完成和其他節(jié)點同等的任務(wù)，拖慢了整體作業(yè)運行時間。在本文策略下，調(diào)度器使任務(wù)得到均勻分配，資源多的節(jié)點可以完成盡可能多的任務(wù)，縮短了整體運行時間。相較于TSS-Flink 策略，本文策略的運行時間更少，這是因為TSS-Flink 策略缺少對于異構(gòu)環(huán)境下節(jié)點資源不均衡問題的考慮，從而導(dǎo)致性能有所差異。

3.3.2 系統(tǒng)延遲對比

實驗通過對比Flink 默認(rèn)調(diào)度策略與本文策略之間的延遲關(guān)系，驗證F-DASA 算法對Flink 異構(gòu)集群的影響。在實驗過程中，在設(shè)置作業(yè)并行度為8的情況下，對比基準(zhǔn)測試WorldCount 和TeraSort 下不同數(shù)據(jù)吞吐量的系統(tǒng)延遲，實驗結(jié)果如圖6所示。

圖6 2 種策略的系統(tǒng)延遲對比Fig.6 Comparison of system delay of two strategies

由圖6（a）可以看出，基準(zhǔn)測試WorldCount 在使用默認(rèn)調(diào)度策略時，隨著吞吐量的增加，系統(tǒng)延遲在100 ms 至150 ms 內(nèi)緩慢上升。使用本文策略后，在吞吐量為1～6 萬組/s 時，系統(tǒng)延遲在100 ms 至150 ms 內(nèi)緩慢上升，與Flink 默認(rèn)調(diào)度策略的系統(tǒng)延遲相近；在吞吐量達到6 萬組/s 以上時，系統(tǒng)延遲上升幅度略微增大，屬于可接受范圍。由圖6（b）可以看出，基準(zhǔn)測試TeraSort 在使用默認(rèn)調(diào)度策略時，隨著吞吐量的增加，系統(tǒng)延遲始終在150 ms 上下浮動。在使用本文策略后，系統(tǒng)延遲在吞吐量為1～6 萬組/s時，在145 ms 上下浮動，略微優(yōu)于Flink 默認(rèn)調(diào)度策略；在吞吐量達到6 萬組/s 以上時，系統(tǒng)延遲上升幅度略微增大，屬于可接受范圍。綜上所述，在異構(gòu)Flink 集群中使用本文策略后，依然能夠保持較為穩(wěn)定的延遲率，達到集群原有的響應(yīng)速度。

4 結(jié)束語

針對異構(gòu)Flink 集群默認(rèn)策略在節(jié)點調(diào)度過程中存在部分節(jié)點負(fù)載不均衡的問題，本文提出一種基于節(jié)點優(yōu)先級的Flink 節(jié)點動態(tài)自適應(yīng)調(diào)度策略。該策略能夠監(jiān)控集群中任務(wù)與節(jié)點的各項數(shù)據(jù)，并在任務(wù)執(zhí)行過程中根據(jù)實時的作業(yè)環(huán)境更新各個節(jié)點的優(yōu)先級指數(shù)，為系統(tǒng)任務(wù)找到最佳的執(zhí)行節(jié)點。實驗結(jié)果表明，該策略可在保持集群低延遲的基礎(chǔ)上，提高異構(gòu)Flink 集群對于節(jié)點資源的利用率。下一步將針對節(jié)點的CPU、內(nèi)存和帶寬性能設(shè)置合理的閾值，確保集群不會出現(xiàn)滿負(fù)載狀態(tài)，同時設(shè)計集群任務(wù)選擇算法，并將其與F-DASA 算法相結(jié)合進一步提升異構(gòu)Flink 集群整體性能。