基于Storm非合作博弈調(diào)度的ETL研究

馬海旭，馮欣，王貴磊，孫開蔚

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

新技術(shù)的廣泛使用產(chǎn)生了大量數(shù)據(jù)。例如，Twitter［1］上的微博數(shù)量每一分鐘超過10萬條。數(shù)據(jù)價(jià)值隨著時(shí)間的流逝而減少并具有實(shí)時(shí)性、易失性等特點(diǎn)。目前發(fā)展較為成熟的Ma‐pReduce框架，本質(zhì)上是批數(shù)據(jù)處理，而純流式數(shù)據(jù)處理框架Storm能夠有效地解決實(shí)時(shí)流處理問題。利用Storm構(gòu)建ETL（Extract-Translation-Load）處理系統(tǒng)，本文針對ETL流程提取和轉(zhuǎn)換階段存在的問題展開研究。

變更數(shù)據(jù)捕獲作為ETL流程實(shí)時(shí)處理的關(guān)鍵。文獻(xiàn)［2］提出一種新的細(xì)粒度并行化/分發(fā)方法，對源數(shù)據(jù)進(jìn)行分區(qū)并行處理，通過快照對比捕獲變更數(shù)據(jù)。文獻(xiàn)［3］提出了一種能夠?qū)崟r(shí)地為應(yīng)用程序提供信息的ETL框架，該框架無需創(chuàng)建數(shù)據(jù)倉庫便可對現(xiàn)有存儲庫進(jìn)行分析。針對特定環(huán)境需求，文獻(xiàn)［4］對ETL體系結(jié)構(gòu)進(jìn)行了優(yōu)化，以滿足實(shí)時(shí)感知并捕獲數(shù)據(jù)。實(shí)時(shí)ETL關(guān)鍵在于提升數(shù)據(jù)捕獲性能，針對變更數(shù)據(jù)捕獲延遲問題，在快照對比捕獲變更算法基礎(chǔ)上，提出了變更數(shù)據(jù)標(biāo)記捕獲算法，該算法對源端變更數(shù)據(jù)置標(biāo)志位，實(shí)驗(yàn)結(jié)果表明，降低了ETL系統(tǒng)捕獲變更數(shù)據(jù)時(shí)間開銷。

數(shù)據(jù)中間處理作為ETL流程的重要步驟，采用Storm作為ETL過程數(shù)據(jù)處理框架，但Storm默認(rèn)采用輪詢調(diào)度策略，存在通信開銷大和負(fù)載失衡等問題，降低了系統(tǒng)數(shù)據(jù)處理性能。調(diào)度的關(guān)鍵任務(wù)是尋找最優(yōu)解，文獻(xiàn)［5］在生產(chǎn)調(diào)度中利用遺傳算法提出了優(yōu)化策略。Storm系統(tǒng)調(diào)度的目的是降低網(wǎng)絡(luò)通信開銷、系統(tǒng)處理延遲以及負(fù)載均衡。文獻(xiàn)［6］提出了在Storm環(huán)境下離線和在線的兩種自適應(yīng)調(diào)度算法，在線調(diào)度算法根據(jù)實(shí)時(shí)監(jiān)測節(jié)點(diǎn)負(fù)載及集群通信負(fù)載制定調(diào)度策略，彌補(bǔ)了離線調(diào)度的不足，對于復(fù)雜的拓?fù)淙菀紫萑刖植孔顑?yōu)。熊安萍等人［7］引入拓?fù)錈徇叺母拍?，該算法是將高頻熱邊關(guān)聯(lián)的任務(wù)對遷移到同一工作節(jié)點(diǎn)，但該算法只考慮優(yōu)化拓?fù)鋬?nèi)部高頻熱邊通信的任務(wù)。魯亮等人［8］提出了基于權(quán)重的任務(wù)調(diào)度算法，設(shè)計(jì)了邊權(quán)增益模型，將任務(wù)移動到邊權(quán)增益值較大的節(jié)點(diǎn)上。但存在一個工作節(jié)點(diǎn)負(fù)載過度低于其余節(jié)點(diǎn)的問題。劉粟等人［9］提出了基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略，將拓?fù)渲卸茸畲蟮慕M件對應(yīng)的線程優(yōu)先移動到CPU資源充足的節(jié)點(diǎn)上，但將任務(wù)盡可能移動到某個節(jié)點(diǎn)的同時(shí)必定影響集群負(fù)載均衡。文獻(xiàn)［10］提出并實(shí)現(xiàn)了一種自適應(yīng)在線調(diào)度方案，解決了在不發(fā)生擁塞的情況下處理波動負(fù)載，利用Cgroup實(shí)現(xiàn)了資源隔離，減輕了資源爭用帶來的性能干擾。王林等人［11］利用蟻群算法在NP-hard問題上的優(yōu)勢結(jié)合Storm本身拓?fù)涮攸c(diǎn)，提出改進(jìn)蟻群算法優(yōu)化Storm任務(wù)調(diào)度，但算法易出現(xiàn)局部最優(yōu)解。針對Storm默認(rèn)調(diào)度算法以及相關(guān)研究不足，本文提出了非合作博弈Storm調(diào)度算法，構(gòu)造博弈函數(shù)，充分考慮任務(wù)負(fù)載以及通信開銷，將任務(wù)調(diào)度到合適的工作節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，相對于Storm默認(rèn)調(diào)度算法以及文獻(xiàn)［6］的在線調(diào)度算法，提出的算法在通信開銷、負(fù)載均衡以及系統(tǒng)延遲方面均有所改進(jìn)。

1 ETL數(shù)據(jù)捕獲

ETL作為構(gòu)建數(shù)據(jù)倉庫的核心部件，捕獲數(shù)據(jù)又作為ETL的關(guān)鍵一步，企業(yè)組織要求零延遲捕獲數(shù)據(jù)以支持決策系統(tǒng)。變更數(shù)據(jù)捕獲（CDC）是ETL流程中數(shù)據(jù)捕獲（E）步驟的關(guān)鍵。當(dāng)變更數(shù)據(jù)捕獲流程發(fā)現(xiàn)源數(shù)據(jù)庫端有數(shù)據(jù)發(fā)生變化時(shí)，數(shù)據(jù)捕獲系統(tǒng)將提取并處理這些數(shù)據(jù)以刷新數(shù)據(jù)倉庫（DW）。其余數(shù)據(jù)（不受更改影響）將被拒絕，因?yàn)樗驯患虞d到DW中。

1.1 標(biāo)記變更捕獲

關(guān)于ETL的功能流程，在文獻(xiàn)［2］中作者詳細(xì)闡述了基于快照對比的變更數(shù)據(jù)捕獲（CDC）。針對快照對比無法低延遲捕獲變更數(shù)據(jù)的要求，本文提出了變更數(shù)據(jù)標(biāo)記捕獲算法。

提出的新方法需要由特殊的源數(shù)據(jù)庫端（標(biāo)記變更數(shù)據(jù)）和捕獲變更數(shù)據(jù)階段共同完成。首先需要為源表設(shè)置標(biāo)記位F，數(shù)據(jù)庫插入、更新、刪除操作標(biāo)記位F分別對應(yīng)1、2、3。表1為表2的快照。表2中標(biāo)記位F=1、2、3的元組分別各有2個，表示源表插入2個元組，更新2個元組，刪除2個元組，只是刪除操作并沒有立即執(zhí)行，便于捕獲階段提前發(fā)現(xiàn)刪除數(shù)據(jù)。待操作結(jié)束，需清零所有標(biāo)記位。捕獲變更數(shù)據(jù)和源數(shù)據(jù)庫操作可同時(shí)執(zhí)行，CDC階段無需逐條元組對比來捕獲變更數(shù)據(jù)，只是增加了源數(shù)據(jù)庫端的負(fù)擔(dān)。

表1 前一時(shí)刻表STpv

表2 當(dāng)前表ST

1.2 標(biāo)記捕獲算法

為了降低ETL流程再次發(fā)現(xiàn)并捕獲變更數(shù)據(jù)帶來的系統(tǒng)時(shí)間開銷，采取在源端標(biāo)記變更的數(shù)據(jù)元組，從而減輕提取變更數(shù)據(jù)的壓力。具體變更數(shù)據(jù)標(biāo)記捕獲算法如下：

算法1描述了改進(jìn)后的CDC功能。第一行表示在數(shù)據(jù)源端對變更的數(shù)據(jù)做標(biāo)記，對插入、更新、刪除對應(yīng)記錄的標(biāo)記位分別置1、2、3。依次讀取tuple，如果tuple.F=1，則表示插入操作；如果tuple.F=2，則表示更新操作；如果tuple.F=3，則表示刪除操作。

1.3 快照捕獲思想

設(shè)tuple1和tuple2分別是存儲在源數(shù)據(jù)庫表ST和該表對應(yīng)的快照表STpv中的兩個元組。如果tuple1和tuple2滿足式（1）和式（2），這意味著它們無變化（CRC，循環(huán)冗余校驗(yàn)）。tuple1應(yīng)該被CDC進(jìn)程拒絕，因?yàn)闆]有發(fā)生任何更改。如果僅滿足式（1），表示tuple1已受到更改的影響，由CDC進(jìn)程提取為UPDATE。如果滿足式（3），則這表示tuple1為新插入元組，由CDC進(jìn)程提取為INSERT。如果滿足式（4），表示tuple2為已刪除元組，由CDC進(jìn)程提取為DELETE。

1.4 捕獲實(shí)驗(yàn)分析

實(shí)驗(yàn)機(jī)器配有intel-Core i7-9700K CPU@3.6 GHZ x8處理器，8 GB RAM，40GB可用硬盤空間。機(jī)器安裝CentOS-7.0 64系統(tǒng)，使用Mysql-7.6.10數(shù)據(jù)庫和IDEA2018.2編輯器。采用高級語言Java編程語言，運(yùn)行環(huán)境采用JDK 64位。

針對快照對比捕獲變更數(shù)據(jù)算法與變更數(shù)據(jù)標(biāo)記捕獲算法對于發(fā)現(xiàn)并提取變更記錄的性能優(yōu)劣問題，本文利用單機(jī)模式及小規(guī)模數(shù)據(jù)，研究這兩種算法捕獲變更數(shù)據(jù)差異。采用簡單的字母序列，來分析兩種算法捕獲數(shù)據(jù)表中變化的數(shù)據(jù)記錄。

對比兩種方法在不同記錄數(shù)下捕獲變更數(shù)據(jù)耗時(shí)，分別向Mysql數(shù)據(jù)庫中加載不同數(shù)量的消息記錄（每條消息記錄包含20個字母型字段），執(zhí)行插入更新刪除數(shù)據(jù)庫變更操作，記錄被捕獲到的變更消息記錄。實(shí)驗(yàn)結(jié)果如圖1所示，變更數(shù)據(jù)標(biāo)記捕獲方法捕獲到變更數(shù)據(jù)消耗的時(shí)間相比快照對比方法捕獲到變更數(shù)據(jù)消耗的時(shí)間降低了22.6%。

圖1 記錄數(shù)對變更捕獲的影響

對比兩種方法在不同字段數(shù)下捕獲變更數(shù)據(jù)。分別向Mysql數(shù)據(jù)庫中載入不同字段數(shù)（字母型）的消息記錄（每種字段數(shù)均有2 000條記錄），執(zhí)行三種數(shù)據(jù)變更操作，記錄被捕獲到的變更消息記錄。實(shí)驗(yàn)結(jié)果如圖2所示，變更數(shù)據(jù)標(biāo)記捕獲方法捕獲變更數(shù)據(jù)消耗的時(shí)間相比快照對比方法降低了23.1%。

圖2 字段數(shù)對變更捕獲的影響

實(shí)驗(yàn)表明，在單機(jī)模式下，面對小數(shù)據(jù)量，變更數(shù)據(jù)標(biāo)記捕獲方法在捕獲變更數(shù)據(jù)方面要優(yōu)于通過快照對比捕獲變更數(shù)據(jù)的方法。

2 Storm博弈調(diào)度

2.1 Storm調(diào)度分析

Storm調(diào)度算法默認(rèn)采用輪詢算法，對空閑slot按端口號升序排序，將運(yùn)行任務(wù)的executor輪詢部署到已排序的slot上，集群最后一個節(jié)點(diǎn)負(fù)載明顯低于其余各節(jié)點(diǎn)。默認(rèn)輪詢的調(diào)度算法存在負(fù)載失衡的問題。默認(rèn)調(diào)度只是簡單的將實(shí)例化的executor輪詢分發(fā)到各節(jié)點(diǎn)，集群上各工作節(jié)點(diǎn)間存在大量的網(wǎng)絡(luò)通信開銷。如圖3所示，拓?fù)溆山M件Spout，Bolt_1和Bolt_2實(shí)例的任務(wù)組成。

圖3 拓?fù)浣Y(jié)構(gòu)圖

如圖4所示，顯而易見，部署到集群中的拓?fù)?，任?wù)之間均為網(wǎng)絡(luò)通信。數(shù)據(jù)通過網(wǎng)絡(luò)傳輸消耗的時(shí)間遠(yuǎn)大于計(jì)算機(jī)內(nèi)部進(jìn)程間或進(jìn)程內(nèi)部的數(shù)據(jù)傳輸延遲，因此，降低拓?fù)渚W(wǎng)絡(luò)間數(shù)據(jù)通信開銷，提高節(jié)點(diǎn)內(nèi)部數(shù)據(jù)通信量，可有效提升Storm數(shù)據(jù)處理性能。

圖4 拓?fù)洳渴饒D

2.2 調(diào)度思想

調(diào)度優(yōu)化思想闡述。本文假定的拓?fù)浜喕Ｐ腿鐖D5所示，集群配置了3個節(jié)點(diǎn)，每個節(jié)點(diǎn)僅配置一個slot。任務(wù)分配情況如圖5所示，拓?fù)淠Ｐ椭腥蝿?wù)t1和t2與任務(wù)t5傳輸?shù)臄?shù)據(jù)量遠(yuǎn)大于任務(wù)t4與任務(wù)t5之間的傳輸量，任務(wù)t6在節(jié)點(diǎn)2上無通信傳輸而與t8有通信往來，將任務(wù)t5從節(jié)點(diǎn)2轉(zhuǎn)移到節(jié)點(diǎn)1上，任務(wù)t6從節(jié)點(diǎn)2轉(zhuǎn)移到節(jié)點(diǎn)3上，可有效降低節(jié)點(diǎn)間通信開銷，提升集群的負(fù)載均衡性，如圖6所示。

圖5 未優(yōu)化拓?fù)?/p>

圖6 已優(yōu)化拓?fù)?/p>

2.3 相關(guān)定義

在Storm調(diào)度中，應(yīng)考慮節(jié)點(diǎn)內(nèi)部通信量最大（由數(shù)據(jù)傳輸總量固定，則節(jié)點(diǎn)間通信量最小）的同時(shí)兼顧集群負(fù)載均衡性，引入收益函數(shù)（博弈函數(shù)）求解系統(tǒng)調(diào)度的最優(yōu)解。為了降低網(wǎng)絡(luò)通信，一個節(jié)點(diǎn)部署一個slot［8］。針對上述模型，作出如下定義：

定義F為節(jié)點(diǎn)內(nèi)部數(shù)據(jù)傳輸總量，如下：

其中，S為集群slot集合（一個節(jié)點(diǎn)部署一個slot）；Tk為第k個slot內(nèi)部任務(wù)集合；rij為任務(wù)i到任務(wù)j的數(shù)據(jù)流；Skrij為第k個 slot內(nèi)部數(shù)據(jù)流rij。

其中，N為節(jié)點(diǎn)集合；nk為節(jié)點(diǎn)Wnk為節(jié)點(diǎn)的CPU負(fù)載；Mnk為節(jié)點(diǎn)的內(nèi)存負(fù)載。

定義θ和η分別為工作節(jié)點(diǎn)的CPU和內(nèi)存負(fù)載標(biāo)準(zhǔn)差，如式（9）、式（10）所示：

定義g為集群的CPU和內(nèi)存負(fù)載標(biāo)準(zhǔn)差加權(quán)之和，如下：

其中，λ為θ的權(quán)重；γ為η的權(quán)重；通常λ≥γ，主要考慮CPU負(fù)載對系統(tǒng)的影響。

調(diào)度優(yōu)化問題可以轉(zhuǎn)化為滿足式（12）、式（13）、式（14）的條件下收益函數(shù)u的最大值問題。

2.4 博弈建模

構(gòu)建Storm拓?fù)淇刂频姆呛献鞑┺哪Ｐ?，其中博弈模型的博弈局中人或稱博弈參與者為調(diào)度系統(tǒng)中的任務(wù)；參與者的策略為當(dāng)其他參與者策略保持不變時(shí)改變自己的調(diào)度策略來最大化自身以及系統(tǒng)整體效用，將博弈參與者的所有可用策略構(gòu)成一個策略集合，如下：

被稱為一個調(diào)度策略向量；當(dāng)博弈參與者使用上述策略時(shí)對應(yīng)得到非合作博弈函數(shù)如下：

根據(jù)納什均衡點(diǎn)的定義，當(dāng)構(gòu)造的Storm任務(wù)調(diào)度控制模型經(jīng)過博弈達(dá)到納什均衡時(shí)，即可認(rèn)為系統(tǒng)收益已達(dá)到穩(wěn)態(tài)，沒有任一任務(wù)可以通過僅改變自身調(diào)度策略來提高自身以及系統(tǒng)的整體效用。

定義 策略集合 σt=[σt,1,σt,2,σt,3,...,σt,n]是提出的多任務(wù)資源分配博弈模型的納什均衡點(diǎn)的充分必要條件，滿足式（17）：

接下來首先根據(jù)文獻(xiàn)［12］中Boyd S提出的納什均衡存在性定理Ⅱ證明所提出模型納什均衡點(diǎn)的存在性。

定理 構(gòu)造的任務(wù)調(diào)度控制非合作博弈模型存在納什均衡點(diǎn)。

證明 由于Storm任務(wù)調(diào)度優(yōu)化過程中集群節(jié)點(diǎn)內(nèi)部通信量逐漸增加并趨于平穩(wěn)，故邊界條件（13）是歐式空間上的一個非空有界閉凸集，然而只需證明邊界條件（14）滿足納什均衡存在性定理Ⅱ中規(guī)定的條件：

假設(shè)所有任務(wù)都分配給一個slot，那么必存在一個常量μ，使(m ax) Wnk< μ，根據(jù)式（9），θ≤(m ax) Wnk(1 ≤k≤n)，同理根據(jù)式（10），η ≤(m ax) Mnk(1 ≤k≤n)，而g=λθ+γη，又由于調(diào)度的不斷優(yōu)化，負(fù)載標(biāo)準(zhǔn)差逐漸減小并趨于平穩(wěn)，故g是歐式空間上的一個非空有界閉凹集。綜上所述，收益函數(shù)u為有界閉凸集。拓?fù)淙蝿?wù)調(diào)度的收益函數(shù)u存在最大值，因此構(gòu)建的Storm集群拓?fù)湔{(diào)度博弈模型中存在納什均衡點(diǎn)。

2.5 算法設(shè)計(jì)

本算法執(zhí)行的前提是監(jiān)控集群的運(yùn)行狀態(tài)，其中包括拓?fù)渲腥蝿?wù)間的數(shù)據(jù)流量和集群中各節(jié)點(diǎn)的CPU消耗量以及內(nèi)存的使用量。在獲取節(jié)點(diǎn)內(nèi)部任務(wù)間最大通信量的同時(shí)考慮負(fù)載均衡。因此在非合作博弈算法的設(shè)計(jì)過程中，當(dāng)用戶提交拓?fù)浜笙到y(tǒng)會先執(zhí)行默認(rèn)調(diào)度算法，并當(dāng)集群上各工作節(jié)點(diǎn)中的拓?fù)淙蝿?wù)運(yùn)行穩(wěn)定后，采集并存儲節(jié)點(diǎn)內(nèi)任務(wù)間數(shù)據(jù)流以及節(jié)點(diǎn)的CPU負(fù)載和內(nèi)存負(fù)載。結(jié)束后，則執(zhí)行博弈算法對任務(wù)進(jìn)行重新調(diào)度。在Storm拓?fù)溥\(yùn)行中，若出現(xiàn)集群上各節(jié)點(diǎn)CPU負(fù)載持續(xù)不均，即在指定持續(xù)時(shí)間間隔內(nèi)，集群中各個工作節(jié)點(diǎn)的CPU負(fù)載最大值與最小值之差大于設(shè)定閾值，則再次觸發(fā)博弈調(diào)度算法，具體算法如下，具體參數(shù)如下所示。

上述算法基于采集默認(rèn)調(diào)度信息，然后判斷是否觸發(fā)博弈調(diào)度。若初始調(diào)度集群節(jié)點(diǎn)任務(wù)數(shù)失衡，則重復(fù)初始化。隨后遍歷每個節(jié)點(diǎn)中的所有任務(wù)，分別移動到不同的節(jié)點(diǎn)，記錄最優(yōu)的收益值。迭代M次，若最優(yōu)值沒有改變，即為最優(yōu)值。此調(diào)度算法的關(guān)鍵在于，未獨(dú)立開來考慮減少集群上的網(wǎng)絡(luò)間的通信開銷與節(jié)點(diǎn)間的負(fù)載均衡，而是將節(jié)點(diǎn)內(nèi)的數(shù)據(jù)通信與集群資源的負(fù)載均衡有機(jī)結(jié)合到一起，從自適應(yīng)的角度出發(fā)，通過迭代的方法，使集群收益最大化，從而得出最優(yōu)的調(diào)度策略。

3 ETL流程優(yōu)化

改進(jìn)后的ETL流程如圖7所示，源數(shù)據(jù)庫在變更數(shù)據(jù)時(shí)標(biāo)記相關(guān)數(shù)據(jù)，便于ETL系統(tǒng)捕獲變更，這樣捕獲變更可以有效節(jié)省后期因遍歷數(shù)據(jù)帶來的時(shí)間開銷?；诜呛献鞑┺恼{(diào)度的Storm系統(tǒng)負(fù)責(zé)提取、處理，并加載數(shù)據(jù)到數(shù)據(jù)倉庫。本文提出的改進(jìn)算法構(gòu)建了實(shí)時(shí)GS-M-ETL數(shù)據(jù)處理流程。

圖7 ETL數(shù)據(jù)處理優(yōu)化圖

ETL流程中數(shù)據(jù)提取和處理轉(zhuǎn)換是影響系統(tǒng)性能的重要因素，其中數(shù)據(jù)提取是關(guān)鍵部分。數(shù)據(jù)捕獲采用變更標(biāo)記捕獲算法（CDMC），根據(jù)源數(shù)據(jù)庫端變更的數(shù)據(jù)記錄，提取相關(guān)的變更數(shù)據(jù)。數(shù)據(jù)處理采用基于非合作博弈調(diào)度的Storm（Game-Sorm）分布式流處理系統(tǒng)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

測試環(huán)境是由13臺PC搭建的Storm-1.2.2集群。每臺機(jī)器都配有intel-Core i7-9700K CPU@3.6 GHZ x8處理器，8 GB RAM，40 GB可用硬盤空間。機(jī)器均安裝CentOS-7.0 64系統(tǒng)，并通過LAN中的交換式以太網(wǎng)1 Gbit進(jìn)行互連。其中3個節(jié)點(diǎn)共同運(yùn)行Zookeeper-3.4.10集群和kafka-2.2.0集群，Nimbus、進(jìn)程UI和數(shù)據(jù)庫Mysql-7.6.10運(yùn)行在其中1個節(jié)點(diǎn)上。其余10個節(jié)點(diǎn)運(yùn)行Su‐pervisor守護(hù)進(jìn)程。

4.2 實(shí)驗(yàn)方案

實(shí)驗(yàn)使用Storm框架提供的可插拔的自定義任務(wù)調(diào)度器Pluggable Scheduler，該調(diào)度器是專為開發(fā)人員設(shè)計(jì)的。利用自行實(shí)現(xiàn)的負(fù)載監(jiān)控器Lead Monitor來采集拓?fù)溥\(yùn)行時(shí)對應(yīng)executor的一些關(guān)鍵數(shù)據(jù)，包括executor負(fù)載、worker node負(fù)載、executor間通信量等，并且Load Monitor以dae‐mon進(jìn)程方式在后臺運(yùn)行。此外，本實(shí)驗(yàn)選擇Ganglia［13］作為 Storm 集群監(jiān)控工具，利用 Ganglia提供的數(shù)據(jù)來輔助實(shí)驗(yàn)結(jié)果的分析。為驗(yàn)證非合作博弈調(diào)度算法Game-Storm的有效性，本文同時(shí)部署了Storm框架默認(rèn)調(diào)度算法（Default Scheduler）和Storm框架自適應(yīng)在線調(diào)度算法（Online Scheduler）［6］，算 法 Online-Storm 在 每 個節(jié)點(diǎn)配置2個slot，相關(guān)參數(shù)參照如表3所示。

表3列出了Game-Storm調(diào)度算法的各項(xiàng)參數(shù)配置。實(shí)驗(yàn)參數(shù)是通過若干次實(shí)驗(yàn)并經(jīng)過微調(diào)后確定的理想值，具體參數(shù)需要根據(jù)實(shí)際運(yùn)行情況進(jìn)行人為調(diào)整。實(shí)驗(yàn)設(shè)置10個工作節(jié)點(diǎn)和10個工作進(jìn)程，即每個工作節(jié)點(diǎn)上僅部署一個工作進(jìn)程，這樣可有效降低工作節(jié)點(diǎn)內(nèi)部進(jìn)程間通信開銷，與本文非合作博弈調(diào)度算法描述相符。

表3 Game-Storm參數(shù)配置

本文提出的算法調(diào)度必須在運(yùn)行時(shí)執(zhí)行，以便使分配適應(yīng)集群中負(fù)載的變化。圖8展示了需在Storm體系結(jié)構(gòu)中集成在線調(diào)度模塊。圖中描述的負(fù)載監(jiān)控器運(yùn)行在每臺機(jī)器上，負(fù)責(zé)采集工作節(jié)點(diǎn)的各項(xiàng)性能參數(shù)（如節(jié)點(diǎn)間通信量，CPU和內(nèi)存消耗量），并將負(fù)載數(shù)據(jù)存入數(shù)據(jù)庫中。調(diào)度生成器模塊從數(shù)據(jù)庫中讀取負(fù)載信息，生成調(diào)度策略。可以定期檢查監(jiān)控?cái)?shù)據(jù)，并運(yùn)行自定義調(diào)度程序，判斷是否可以部署新的更有效的調(diào)度策略。

圖8 改進(jìn)的Storm系統(tǒng)框圖

圖8展示了Storm集群負(fù)載監(jiān)視模塊，該監(jiān)控模塊負(fù)責(zé)在拓?fù)溥\(yùn)行一定的時(shí)間窗口內(nèi)，采集并計(jì)算拓?fù)淙蝿?wù)占用工作節(jié)點(diǎn)CPU負(fù)載信息，以及拓?fù)淙蝿?wù)之間的通信量大小，具體系統(tǒng)監(jiān)控及數(shù)據(jù)采集方案如下：

由于Storm系統(tǒng)中的一個拓?fù)淙蝿?wù)運(yùn)行于工作進(jìn)程的一個工作線程中，因此為了獲取拓?fù)淙蝿?wù)在執(zhí)行過程中對工作節(jié)點(diǎn)CPU、內(nèi)存資源的占用量，還有各對拓?fù)淙蝿?wù)在單位時(shí)間內(nèi)傳輸?shù)男畔⒘?，需?shí)時(shí)追蹤拓?fù)淙蝿?wù)對應(yīng)的工作線程ID及其相關(guān)聯(lián)的所有工作線程。利用線程所在工作節(jié)點(diǎn)的CPU主頻與該線程占用的CPU時(shí)間的乘積來表示線程占用的CPU資源大小。ThreadMXBean類的 getThreadCpuTime（long id）方法可以獲取線程id占用的CPU時(shí)間。

各對線程間通信速率以及線程占用的內(nèi)存大小，需要統(tǒng)計(jì)各線程收發(fā)總的元組數(shù)以及元組的傳輸時(shí)間，線程間的通信速率由線程收發(fā)數(shù)據(jù)差與對應(yīng)時(shí)間窗容量的商求得，線程執(zhí)行期間占用的內(nèi)存量由單位時(shí)間內(nèi)接受的元組數(shù)與發(fā)送的元組數(shù)之差決定。具體實(shí)現(xiàn)：在每個Spout/Bolt源中添加任務(wù)監(jiān)控器。在具體的每個任務(wù)中必須通知其線程ID以在特定Java進(jìn)程中運(yùn)行。對于每一個Spout/Bolt，添加一個全局變量：

為了評估本文提出的Game-Storm-ETL平臺，本文提供了一個ETL過程示例。開發(fā)了一個數(shù)據(jù)生成器程序來生成源數(shù)據(jù)，產(chǎn)生了1×109個元組，每個元組包含20個字母型字段。ETL過程為按如下方式處理數(shù)據(jù)。數(shù)據(jù)集載入Kafka（top‐ic=3，partitions=12）消息序列數(shù)據(jù)庫，數(shù)據(jù)載入過程存在更新與刪除操作。數(shù)據(jù)儲存在消息中間件Kafka中，Storm從Kafka中讀取數(shù)據(jù)，經(jīng)處理后加載到Mysql數(shù)據(jù)庫中。

4.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)對比優(yōu)化前后（Default調(diào)度算法、On‐line-Storm調(diào)度算法和改進(jìn)后的Game-Storm調(diào)度算法）的Storm系統(tǒng)在節(jié)點(diǎn)間網(wǎng)絡(luò)通信量和集群負(fù)載均衡兩個方面的性能，以及對比了改進(jìn)后的ETL系統(tǒng)數(shù)據(jù)處理延遲與原ETL系統(tǒng)數(shù)據(jù)處理延遲。實(shí)驗(yàn)結(jié)果如下：

如圖9所示，實(shí)驗(yàn)開始任務(wù)分配遵循Storm系統(tǒng)默認(rèn)的調(diào)度算法，首先執(zhí)行默認(rèn)調(diào)度算法，待Storm系統(tǒng)運(yùn)行趨于穩(wěn)定后，集群上節(jié)點(diǎn)間通信的數(shù)據(jù)流大小平均值約為119 372 tuple/s。由于在第85 s時(shí)系統(tǒng)出現(xiàn)持續(xù)70 s的觀測周期內(nèi)集群上工作節(jié)點(diǎn)的CPU負(fù)載的最大值與最小值之差大于20%，因此，再次觸發(fā)了調(diào)度，在第115 s處重調(diào)度已結(jié)束，節(jié)點(diǎn)間通信量持續(xù)增長。隨著時(shí)間的推移節(jié)點(diǎn)間通信量趨于平穩(wěn)。

圖9 三種節(jié)點(diǎn)間通信算法的比較

Game-Storm調(diào)度算法和Online-Storm調(diào)度算法在節(jié)點(diǎn)間數(shù)據(jù)流大小平均值分別為80 337 tuple/s和90 961 tuple/s，相比Storm默認(rèn)調(diào)度算法分別降低了32.5%和23.2%。

圖10顯示的是三種調(diào)度算法下集群CPU負(fù)載情況。默認(rèn)的調(diào)度算法CPU最大負(fù)載超過了60%，且最大最小CPU負(fù)載差也大于20%，所以在線算法與本文提出的算法都會被觸發(fā)。默認(rèn)調(diào)度CPU負(fù)載標(biāo)準(zhǔn)差高達(dá)9.57，重調(diào)度后，在線調(diào)度算法和Game-Storm調(diào)度算法的負(fù)載標(biāo)準(zhǔn)差分別為3.51和3.25。

圖10 三種CPU負(fù)載平衡算法的比較

如圖11所示，變更數(shù)據(jù)標(biāo)記捕獲算法與Game-Storm調(diào)度算法構(gòu)建的系統(tǒng)（GS-M-ETL）使得ETL性能得到了提升。待Game-Storm調(diào)度結(jié)束，且系統(tǒng)運(yùn)行趨于平穩(wěn)，ETL過程時(shí)延相比于未改進(jìn)的變更數(shù)據(jù)捕獲方法與默認(rèn)調(diào)度算法下的ETL系統(tǒng)，系統(tǒng)時(shí)延降低了29.5%左右。提出的基于非合作博弈的調(diào)度算法使Storm系統(tǒng)在降低網(wǎng)絡(luò)通信量以及負(fù)載均衡方面的性能得到了提升。同時(shí)，與提出的變更數(shù)據(jù)標(biāo)記捕獲方法結(jié)合，降低了ETL過程數(shù)據(jù)處理延遲，提升了ETL系統(tǒng)性能。

圖11 ETL系統(tǒng)處理延遲對比

利用Ganglia對集群負(fù)載進(jìn)行監(jiān)控。從Ganglia監(jiān)控改進(jìn)后的調(diào)度系統(tǒng)得到的數(shù)據(jù)來看，Storm集群各工作節(jié)點(diǎn)CPU、內(nèi)存等使用率都較為均衡，沒有節(jié)點(diǎn)負(fù)載過重，集群整體負(fù)載較為均衡。

5 結(jié)論

本文提出了變更數(shù)據(jù)標(biāo)記捕獲算法，相對于傳統(tǒng)基于快照對比捕獲算法，在變更數(shù)據(jù)捕獲方面性能得到了提升。Storm作為實(shí)時(shí)ETL流處理框架，默認(rèn)采用輪詢調(diào)度算法，節(jié)點(diǎn)網(wǎng)絡(luò)通信開銷和集群負(fù)載均衡存在優(yōu)化空間。本文提出了非合作博弈的Storm調(diào)度，實(shí)驗(yàn)證明集群網(wǎng)絡(luò)通信開銷和負(fù)載均衡得到了優(yōu)化。二者的改進(jìn)，使得ETL流程的整體性能得到了提升。Storm調(diào)度尚未考慮網(wǎng)絡(luò)帶寬問題以及未曾考慮I/O傳輸接口等硬件資源的影響，希望未來這些問題可以得到解決。