劉旋律 顧進(jìn)廣

(武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢430065)(智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室(武漢科技大學(xué)) 湖北 武漢430065)(武漢科技大學(xué)大數(shù)據(jù)科學(xué)與工程研究院 湖北 武漢430065)(國家新聞出版署富媒體數(shù)字出版內(nèi)容組織與知識(shí)服務(wù)重點(diǎn)實(shí)驗(yàn)室 北京 100038)

0 引 言

傳統(tǒng)的ETL是通過批處理的方式，利用晚上或者周末空閑的時(shí)間來完成提取、轉(zhuǎn)換和加載操作。然而，在如今競爭劇烈的商業(yè)環(huán)境下，面對著數(shù)據(jù)量大、數(shù)據(jù)需求多變、時(shí)間敏感等問題與挑戰(zhàn)[1]，傳統(tǒng)的ETL無法應(yīng)對。為了使數(shù)據(jù)能夠及時(shí)、連續(xù)地轉(zhuǎn)換到數(shù)據(jù)倉庫，以便用戶能夠快速做出決策，實(shí)時(shí)ETL被提出。在實(shí)時(shí)ETL系統(tǒng)中，高可用、低延遲和橫向可擴(kuò)展是三個(gè)關(guān)鍵特性[2]。文獻(xiàn)[3]通過分析ETL過程，并行化執(zhí)行同優(yōu)先級(jí)的ETL操作的方式來減少ETL過程的執(zhí)行時(shí)間，而文獻(xiàn)[4]通過將ETL過程運(yùn)行到Hadoop計(jì)算引擎上，提高運(yùn)行速度。文獻(xiàn)[5]使用面向服務(wù)的體系結(jié)構(gòu)，將ETL過程中每一個(gè)操作封裝為一個(gè)RESTful API的方式來解耦ETL操作，通過升級(jí)和快速迭代服務(wù)的方式來解決數(shù)據(jù)需求多變的問題，通過集群部署的方式來提高ETL操作速度。

上述解決方案都能在一定限度上解決實(shí)時(shí)ETL中存在的問題。但是，以上解決方案都沒有考慮到數(shù)據(jù)的動(dòng)態(tài)性。在很多實(shí)際場景中，數(shù)據(jù)源的數(shù)據(jù)生產(chǎn)速度隨著時(shí)間波動(dòng)且波動(dòng)區(qū)間較廣，例如，醫(yī)院藥房藥品數(shù)據(jù)、醫(yī)療傳感器實(shí)時(shí)數(shù)據(jù)、人群聽歌和購物的行為數(shù)據(jù)、物流倉庫中的物流數(shù)據(jù)。

在實(shí)時(shí)ETL系統(tǒng)中，每個(gè)ETL過程中的ETL操作都是常駐服務(wù)。在上述解決方案中，ETL過程初始化完成后各個(gè)操作的進(jìn)程數(shù)不會(huì)改變，如果需要更改某個(gè)操作并行的進(jìn)程數(shù)，需要重新初始化該ETL過程。對于數(shù)據(jù)生產(chǎn)速度波動(dòng)較大的場景，如果ETL過程以數(shù)據(jù)源的數(shù)據(jù)生產(chǎn)速度最大值初始化ETL過程，則在大多數(shù)時(shí)間，ETL過程的資源利用率都不能達(dá)到理想狀態(tài)；如果ETL過程以低于數(shù)據(jù)生產(chǎn)速度最大值初始化，則存在一段時(shí)間，新增數(shù)據(jù)阻塞在數(shù)據(jù)源中；如果在允許的容忍時(shí)間范圍內(nèi)，不能夠把新增數(shù)據(jù)及時(shí)轉(zhuǎn)換到數(shù)據(jù)倉庫中，則不利于用戶快速地做出商業(yè)分析。

針對現(xiàn)有方案未考慮在數(shù)據(jù)生產(chǎn)速度波動(dòng)較大的場景下，ETL過程不能夠合理分配資源的問題，本文提出了一種基于穩(wěn)定匹配的實(shí)時(shí)ETL彈性調(diào)度機(jī)制。

1 相關(guān)工作

1.1 實(shí)時(shí)ETL

為了達(dá)到實(shí)時(shí)ETL的要求，文獻(xiàn)[2]提出了高可用、低延遲和橫向可擴(kuò)展三個(gè)要求。Kim等[3]為了解決基于流的空間信息數(shù)據(jù)量過大的問題，采用分布式并行的方式設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)空間ETL處理引擎來降低延遲。Zhang等[4]為了實(shí)時(shí)處理醫(yī)療傳感器收集的流式數(shù)據(jù)，使用Hadoop來解決該問題。文獻(xiàn)[4]監(jiān)控了Map任務(wù)和Reduce任務(wù)的負(fù)載情況，如果某個(gè)MR任務(wù)節(jié)點(diǎn)負(fù)載高就分裂該任務(wù)。該方法具有一定的伸縮性，但未從數(shù)據(jù)源的角度和整體變化去考慮。另外，使用Map與Reduce組合的方式并不能靈活地表示ETL的各種復(fù)雜操作。Hsieh等[5]使用RESTful API提供數(shù)據(jù)遷移功能，該方法能夠花費(fèi)較少的時(shí)間來應(yīng)對數(shù)據(jù)格式不斷變更的問題，同時(shí)分布式的調(diào)度方式為該系統(tǒng)提供了可擴(kuò)展性。Chen等[6]提出了一種基于多代理系統(tǒng)的并行ETL執(zhí)行工作流框架，該系統(tǒng)通過初始化ETL過程時(shí)，將相同優(yōu)先級(jí)的ETL操作并行化的方式來降低延遲。Santos等[7]為了能夠應(yīng)對海量數(shù)據(jù)的數(shù)據(jù)分析，提出了一種基于Spark的ETL平臺(tái)。Diouf等[8]提出可以使用云上的技術(shù)來解決實(shí)時(shí)ETL帶來的問題，同時(shí)也指出當(dāng)前研究沒有考慮到數(shù)據(jù)的動(dòng)態(tài)性和資源使用不夠合理的問題。以上解決方案都通過并行度降低了延遲，通過分布式環(huán)境保證了橫向可擴(kuò)展，但是都沒有考慮從整體上考慮資源的利用問題，ETL操作的可擴(kuò)展性較低，導(dǎo)致在數(shù)據(jù)生產(chǎn)速度變動(dòng)較大的時(shí)候，資源利用不夠合理。

1.2 匹配問題

匹配問題一直是眾多研究者討論的熱點(diǎn)問題。在兩個(gè)匹配集中，沒有比當(dāng)前匹配關(guān)系更優(yōu)的匹配關(guān)系存在，則當(dāng)前匹配為穩(wěn)定匹配。穩(wěn)定匹配是沒有不穩(wěn)定對的完美匹配。為了達(dá)到穩(wěn)定匹配，多種匹配算法被提出。為了使云平臺(tái)節(jié)點(diǎn)負(fù)載更合理，Wang等[9]提出了針對虛擬機(jī)分配的匹配算法，該算法根據(jù)虛擬機(jī)和主機(jī)各自的偏好進(jìn)行匹配。Islam等[10]提出了一種基于延遲接受的資源分配算法，用于將用戶蜂窩資源分配給D2D設(shè)備。Hamidouche等[11]提出了一種新的基于博弈論的匹配算法，用于解決小型基站和服務(wù)提供商服務(wù)器之間的多對多匹配博弈問題。Viet等[12]提出了一種雙向局部搜索算法，用于搜索穩(wěn)定婚姻問題中的平等和性別平等穩(wěn)定匹配。Zhou等[13]提出了一種迭代匹配算法，該算法首先基于固定偏好產(chǎn)生一個(gè)穩(wěn)定的匹配，然后根據(jù)每次迭代的最新匹配結(jié)果動(dòng)態(tài)更新偏好。本文的重點(diǎn)是實(shí)現(xiàn)ETL上下游操作中服務(wù)的關(guān)系匹配，保證數(shù)據(jù)的消費(fèi)速度最大，同時(shí)網(wǎng)絡(luò)拓?fù)渚嚯x費(fèi)用最低。

2 系統(tǒng)模型

2.1 執(zhí)行流程

一個(gè)ETL過程(OP)表示從數(shù)據(jù)源(S)獲取數(shù)據(jù)，經(jīng)過多次ETL操作(O)后，加載到目標(biāo)數(shù)據(jù)倉庫(D)的過程。一個(gè)ETL過程包含多個(gè)ETL操作。每一個(gè)ETL操作在對應(yīng)的ETL過程中都至少存在一個(gè)ETL服務(wù)(OS)，多個(gè)相同的ETL服務(wù)構(gòu)成一個(gè)ETL操作。

在實(shí)時(shí)ETL系統(tǒng)中，一個(gè)ETL過程初始化完成后，所有的ETL服務(wù)會(huì)常駐在系統(tǒng)中。本文通過調(diào)整ETL服務(wù)的個(gè)數(shù)來動(dòng)態(tài)調(diào)整ETL過程的消費(fèi)數(shù)據(jù)速度(CV)。根據(jù)調(diào)整的方式不同，本文將彈性調(diào)度機(jī)制分為彈性增長和彈性收縮兩種。首先，根據(jù)預(yù)測的數(shù)據(jù)生產(chǎn)速度(PV)來計(jì)算出ETL過程的最小消費(fèi)數(shù)據(jù)速度(CVm)。然后，比較CVm與當(dāng)前ETL操作的消費(fèi)數(shù)據(jù)速度(CV)。如果CVm大于CV，則當(dāng)前ETL過程需要彈性增長；如果CVm小于CV，則需要彈性收縮。

彈性增長流程需要判斷當(dāng)前ETL過程中各個(gè)操作的消費(fèi)數(shù)據(jù)速度(OCV)是否不小于CVm。若當(dāng)前ETL操作不滿足條件，則計(jì)算當(dāng)前操作需要調(diào)整的服務(wù)數(shù)量(SN)，并添加相應(yīng)數(shù)量的服務(wù)到該ETL過程中。最后，對于存在新增服務(wù)的操作Oi，重新確定與上下游操作Oi-1、Oi+1中各服務(wù)的匹配關(guān)系，保證所有的操作都能滿足CVm。

彈性收縮流程則是需要移除服務(wù)節(jié)省資源。本文不會(huì)將所有ETL操作的CV降低到CVm大小，這樣需要移除的ETL服務(wù)將覆蓋所有的ETL操作，執(zhí)行代價(jià)太大。由于發(fā)生變更的ETL操作是少部分，因此本文只會(huì)移除新增的ETL服務(wù)。遍歷所有存在變更的ETL操作，根據(jù)計(jì)算的SN移除新增的服務(wù)。若SN不小于新增服務(wù)數(shù)量(IN)，則只移除IN個(gè)服務(wù)；否則，按照加入順序依次移除SN個(gè)。

計(jì)算完SN后，需要調(diào)整ETL服務(wù)的數(shù)量。在分布式場景下，每個(gè)物理機(jī)器節(jié)點(diǎn)的性能不同，負(fù)載也不同，一次性添加或移除SN個(gè)ETL服務(wù)都會(huì)影響節(jié)點(diǎn)的負(fù)載。因此，需要考慮平衡物理節(jié)點(diǎn)的負(fù)載。

在調(diào)整完成后，需要確定與上下游ETL操作匹配關(guān)系。在分布式場景中，為了保證各節(jié)點(diǎn)的負(fù)載均衡，同一個(gè)ETL操作的ETL服務(wù)可能會(huì)分配到不同節(jié)點(diǎn)上。在數(shù)據(jù)量較大的情況下，跨節(jié)點(diǎn)ETL服務(wù)之間數(shù)據(jù)的轉(zhuǎn)發(fā)將增加網(wǎng)絡(luò)開銷，影響ETL過程的消費(fèi)數(shù)據(jù)速度。因此，在調(diào)整ETL服務(wù)數(shù)量后，如何保證在新的匹配關(guān)系中，消費(fèi)數(shù)據(jù)速度最大且網(wǎng)絡(luò)拓?fù)渚嚯x費(fèi)用最小是需要考慮的另外一個(gè)問題。

ETL過程彈性調(diào)度流程如圖1所示。

圖1 彈性調(diào)度流程圖

本文將整個(gè)調(diào)度流程分為以下四個(gè)步驟：(1) 預(yù)測數(shù)據(jù)生產(chǎn)速度PV；(2) 計(jì)算ETL操作中需要調(diào)整的服務(wù)數(shù)量SN；(3) 調(diào)整服務(wù)數(shù)量；(4) 確定上下游ETL操作匹配關(guān)系。本文中出現(xiàn)的主要的符號(hào)見表1。

表1 符號(hào)表

續(xù)表1

2.2 預(yù)測數(shù)據(jù)生產(chǎn)速度

不管是彈性增長還是彈性收縮，只有預(yù)測出數(shù)據(jù)生產(chǎn)速度，才能執(zhí)行彈性調(diào)度的策略。在數(shù)據(jù)生產(chǎn)速度波動(dòng)較大的場景中，數(shù)據(jù)生產(chǎn)速度并不會(huì)一直增加，而是達(dá)到最大值后下降或者維持一段時(shí)間。所以，ETL過程的CV與PV不要求相等。當(dāng)生產(chǎn)數(shù)據(jù)速度增長時(shí)，系統(tǒng)可以容忍一段時(shí)間內(nèi)新增的數(shù)據(jù)不用立即處理而是緩存到數(shù)據(jù)源中。如果數(shù)據(jù)速度增長后長期保持不變，則CV不能繼續(xù)小于PV，而是需要繼續(xù)增長避免未被消耗的數(shù)據(jù)數(shù)量持續(xù)增長。

這里引入容忍時(shí)間(DTT)和容忍容量(DTC)兩個(gè)變量，ETL過程可以容忍一個(gè)DTT后，新增數(shù)據(jù)的容量不超過DTC的大小。令C為當(dāng)前未被消費(fèi)的數(shù)據(jù)總量。

當(dāng)C≤DTC時(shí)，此時(shí)可以容忍CV小于PV，即：

DTT×(PV-CV)≤DTC-C

(1)

當(dāng)C>DTC時(shí)，此時(shí)為了恢復(fù)到容忍容量以內(nèi)，所以CV應(yīng)大于PV，即：

DTT×(CV-PV)≥C-DTC

(2)

2.3 計(jì)算調(diào)整的服務(wù)數(shù)量

為了使得ETL過程滿足要求，只有計(jì)算出需要調(diào)整的服務(wù)數(shù)量才能夠向相應(yīng)的ETL過程中添加或移除服務(wù)。一個(gè)ETL過程包含多個(gè)ETL操作，每個(gè)ETL操作包含多個(gè)相同的ETL服務(wù)。在實(shí)時(shí)ETL中，數(shù)據(jù)是通過數(shù)據(jù)流的方式在操作之間流轉(zhuǎn)。因此，ETL過程的消費(fèi)數(shù)據(jù)速度取決于屬于該ETL過程i的所有操作中消費(fèi)數(shù)據(jù)速度最小的操作。即：

CVi=min{OCV0,OCV1,…}

(3)

式中：CVi為ETL過程i的消費(fèi)數(shù)據(jù)速度；OCV0為ETL操作0的消費(fèi)數(shù)據(jù)速度。

對于ETL操作j，其消費(fèi)數(shù)據(jù)速度OCVj為該操作中所有的服務(wù)消費(fèi)數(shù)據(jù)速度之和，即：

(4)

式中：OCVj為ETL操作j的消費(fèi)數(shù)據(jù)速度；OMVjk為ETL操作j的ETL服務(wù)k的最大消費(fèi)數(shù)據(jù)速度。

在分布式環(huán)境中，一個(gè)ETL操作的多個(gè)服務(wù)雖然邏輯相同，但是由于分布不同，其消費(fèi)數(shù)據(jù)的速度不是絕對的相等，而是會(huì)在某個(gè)固定范圍內(nèi)波動(dòng)。本文使用該ETL操作的所有服務(wù)的消費(fèi)數(shù)據(jù)速度的平均值作為添加的服務(wù)所使用的消費(fèi)數(shù)據(jù)速度，即：

(5)

式中：αj表示ETL操作j的ETL服務(wù)平均消費(fèi)數(shù)據(jù)速度；OCVj為ETL操作j的消費(fèi)數(shù)據(jù)速度；OMVjk為ETL操作j的ETL服務(wù)k的消費(fèi)數(shù)據(jù)速度。

2.4 調(diào)整ETL服務(wù)數(shù)量

調(diào)整SN個(gè)數(shù)量的ETL服務(wù)，會(huì)使得多個(gè)節(jié)點(diǎn)的負(fù)載不夠均衡。一個(gè)節(jié)點(diǎn)的負(fù)載由該節(jié)點(diǎn)上的服務(wù)個(gè)數(shù)和服務(wù)類型決定，即：

Wm=WS1×n1+WS2×n2+WS3×n3+…

(6)

式中：Wm表示節(jié)點(diǎn)m使用資源量；WS1表示ETL服務(wù)類型1的資源量；n1表示ETL服務(wù)類型1的在節(jié)點(diǎn)m上的數(shù)量。這里需要考慮如何調(diào)整SN保證各節(jié)點(diǎn)的負(fù)載能夠均衡。

2.5 ETL操作關(guān)系匹配

一個(gè)ETL過程的消費(fèi)數(shù)據(jù)速度不僅僅由ETL操作最大消費(fèi)數(shù)據(jù)速度決定，也與操作之間的關(guān)系匹配有關(guān)。以圖2和圖3兩種匹配為例：ETL操作j的最大消費(fèi)數(shù)據(jù)速度為：OMVj1+OMVj2+OMVj3=83；ETL操作j+1的最大消費(fèi)數(shù)據(jù)速度為：OMVj+1,1+OMVj+1,2=95。

圖2 不合理匹配 圖3 合理匹配

如果按圖2匹配，則當(dāng)前ETL過程的最大消費(fèi)數(shù)據(jù)速度為OMVj+1,1+OMVj3=78；

如果按圖3匹配，則當(dāng)前ETL過程的最大消費(fèi)數(shù)據(jù)速度為OMVj1+OMVj2+OMVj3=83。

另外，為了保證各節(jié)點(diǎn)的負(fù)載，同一個(gè)ETL操作的ETL服務(wù)可能分布在不同的節(jié)點(diǎn)上。因此，在數(shù)據(jù)量大的情況下，節(jié)點(diǎn)之間數(shù)據(jù)傳輸?shù)膸捪牟蝗莺鲆暋Ｒ虼?，如何確定匹配關(guān)系保證網(wǎng)絡(luò)拓?fù)渚嚯x費(fèi)用最小也是需要考慮的問題。本文節(jié)點(diǎn)間網(wǎng)絡(luò)距離的計(jì)算參照Hadoop中網(wǎng)絡(luò)拓?fù)渚嚯x計(jì)算定義的方法，即：

(7)

3 流程實(shí)現(xiàn)

步驟一預(yù)測數(shù)據(jù)生產(chǎn)速度。數(shù)據(jù)源的數(shù)據(jù)生產(chǎn)速度的變化與其應(yīng)用實(shí)際場景有關(guān)，可以將數(shù)據(jù)生產(chǎn)速度預(yù)測問題轉(zhuǎn)為一個(gè)網(wǎng)絡(luò)流量預(yù)測問題，通過構(gòu)建時(shí)序預(yù)測模型來解決。Local Regression Robust(LRR)算法是文獻(xiàn)[8]提出的用來預(yù)測虛擬機(jī)關(guān)鍵主機(jī)用量的算法。該算法是一種自適應(yīng)預(yù)測檢測算法，它通過趨勢多項(xiàng)式擬合當(dāng)前的最后k個(gè)觀測值的方式來預(yù)測下一個(gè)觀測值。由文獻(xiàn)[8]中給出的結(jié)果可以看出，該算法優(yōu)于其他算法。因此，本文使用LRR算法來預(yù)測數(shù)據(jù)源生產(chǎn)數(shù)據(jù)速度。

步驟二計(jì)算調(diào)整服務(wù)數(shù)量。

根據(jù)式(1)，可以推導(dǎo)出：

(8)

根據(jù)式(2)，可以推導(dǎo)出：

(9)

因此，對于預(yù)測數(shù)據(jù)生產(chǎn)速度PV，要求的最小ETL過程消費(fèi)數(shù)據(jù)速度為：

(10)

彈性增長流程中，若對于ETL過程i，存在ETL操作j的消費(fèi)數(shù)據(jù)速度OCVj

(11)

彈性收縮流程中，此時(shí)CV>CVm，對于存在變更操作j，存在ETL服務(wù)n個(gè)，新增的服務(wù)數(shù)量為INj，該操作理應(yīng)移除的服務(wù)數(shù)量Uj為：

(12)

本文只是對存在變更的ETL操作進(jìn)行移除，且移除數(shù)不會(huì)超過新增的服務(wù)數(shù)量，因此ETL操作j應(yīng)該移除的服務(wù)數(shù)量為：

(13)

步驟三調(diào)整ETL服務(wù)數(shù)量。為了保證在調(diào)整ETL服務(wù)數(shù)量的時(shí)候，各個(gè)物理節(jié)點(diǎn)的負(fù)載均衡，本文提出了基于資源的貪婪負(fù)載均衡(Greedy Load Balance，GLB)算法。在彈性增長流程中，GLB算法選擇資源使用最小的節(jié)點(diǎn)分配。另外，GLB算法不會(huì)將SN個(gè)數(shù)量一次都分配到每個(gè)節(jié)點(diǎn)，而是采用依次分配的方式保證負(fù)載的均衡。在彈性收縮流程中，GLB算法選擇存在該ETL服務(wù)的最大資源使用節(jié)點(diǎn)移除。算法過程如算法1所示。

算法1GLB

輸入：ETL操作的當(dāng)前消費(fèi)數(shù)據(jù)速度v；ETL操作目標(biāo)速度t；當(dāng)前ETL操作數(shù)量n；ETL操作的平均速度a；每個(gè)節(jié)點(diǎn)的資源利用集合U。

輸出：被選擇節(jié)點(diǎn)的索引。

1.begin

2.ifv

3.sn←calculated adjusted number(v,t,n,a)

4.fork←0tosndo

5.i←find minimum resource usage node(U);

6.endfor

7.else

8.sn←calculated adjusted number(v,t,n,a)

9.fork←0tosndo

10.a←resource usage array sorted by maximum(U);

11.forl←0tolength(a)do

12.ifexist ETL service in lthen

13.i←l

14.break

15.endif

16.endfor

17.endfor

18.endif

19.returni;

20.end

步驟四ETL操作關(guān)系匹配。對于ETL操作，其各個(gè)ETL服務(wù)處理完數(shù)據(jù)后可以隨機(jī)轉(zhuǎn)發(fā)給下游的任意服務(wù)。因此，一定存在一種匹配關(guān)系使得操作j與操作j+1的整體消費(fèi)數(shù)據(jù)速度為min{OCVj,OCVj+1}。當(dāng)ETL操作j中添加了服務(wù)，需要確定Oj與Oj-1、Oj與Oj+1的匹配關(guān)系。通過步驟二已經(jīng)保證各個(gè)操作的消費(fèi)數(shù)據(jù)速度都滿足條件。因此，只需要確定匹配關(guān)系使得{Oj-1,Oj}和{Oj,Oj+1}這兩組的消費(fèi)數(shù)據(jù)速度CV分別為min{OCVj-1,OCVj}和min{OCVj,OCVj+1}即可滿足條件。

從可行流開始增廣時(shí)，最終的增廣量是一定的。所以為了滿足最小費(fèi)用，只需要每次找最小費(fèi)用的增廣路即可。本文提出基于Dicnic算法的改進(jìn)(Dicnic Improved,DI)算法來解決該問題。傳統(tǒng)的Dicnic算法通過先廣度優(yōu)先搜索(BFS)分層，后深度優(yōu)先搜索(DFS)的方式來找尋增廣路。本文求解的流量網(wǎng)絡(luò)是一個(gè)由Oj、Oj+1兩個(gè)操作的所有服務(wù)組成的網(wǎng)絡(luò)，其具有二分圖的性質(zhì)，每個(gè)操作即可為一層。因此，DI算法不需要通過BFS分層。由于操作已經(jīng)分層，因此，可以直接使用層次遍歷的方式來找尋最小費(fèi)用增廣路。算法的步驟如算法2所示。

算法2DI算法

輸入：上層服務(wù)流量集合S；基礎(chǔ)服務(wù)層流量集合T；

輸出：匹配關(guān)系矩陣G；匹配成本C；最大消費(fèi)數(shù)據(jù)速度V。

1.begin

2.s←calculate total service traffic(S),

t←calculate total service traffic(T),

needTranspose←false

3.ifs>tthen

4.M←S,S←T,T←S,needTranspose←true

5.endif

6.i←0,C←0,V←0,G←[length(S)][length(T)]

7.whiletruedo

8.whilei

9.i++

10.endwhile

11.ifi

12.I←MAX,J←MAX,minCost←MAX

13.fork←itolength(S)do

14.ifS[i] has trafficthen

15.forj←0tolength(T)do

16.ifT[j] has trafficthen

17.cost←calculatecost(i,j)

18.ifminCost>costthen

19.minCost←cost,I←i,J←j

20.endif

21.endif

22.endfor

23.endif

24.endfor

25.C←C+minCost,

26.minStream←min(S[i],T[j])

27.S[i]←S[i]-minStream,T[j]←T[j]-minStream,

G[I][J]←minStream,V←V+minStream

28.else

29. break

30.endif

31.endwhile

32.ifneedTransposethen

33. transpose(G)

34.endif

35.returnG,C,V;

36.end

4 實(shí) 驗(yàn)

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

本文基于容器調(diào)度平臺(tái)kubernetes構(gòu)建了一個(gè)分布式調(diào)度平臺(tái)。每個(gè)ETL服務(wù)都被封裝成為一個(gè)RESTful API的服務(wù)并轉(zhuǎn)化為一個(gè)docker鏡像保存到鏡像倉庫中。當(dāng)需要調(diào)整ETL服務(wù)數(shù)量的時(shí)候，通過kubernetes來進(jìn)行調(diào)整。該平臺(tái)配置如表2所示。

表2 平臺(tái)配置

在實(shí)時(shí)ETL系統(tǒng)中，ETL服務(wù)常駐在ETL系統(tǒng)中，數(shù)據(jù)以數(shù)據(jù)流的方式在ETL服務(wù)之間流轉(zhuǎn)。通過隨機(jī)構(gòu)造了100個(gè)正態(tài)分布函數(shù)用來模擬數(shù)據(jù)生產(chǎn)速度隨時(shí)間發(fā)生波動(dòng)較大變化的場景，并以此變化的數(shù)據(jù)生產(chǎn)速度不斷地向初始化后的ETL過程提供實(shí)時(shí)數(shù)據(jù)。在彈性調(diào)度方面，與傳統(tǒng)的調(diào)度方案在資源利用方面進(jìn)行了比較。在匹配問題方面，與貪婪(greedy)匹配算法和輪詢(poll)匹配算法在消費(fèi)數(shù)據(jù)速度和網(wǎng)絡(luò)距離費(fèi)用方面進(jìn)行了比較。

4.2 評測方法

為了驗(yàn)證實(shí)時(shí)ETL平臺(tái)彈性調(diào)度比傳統(tǒng)的調(diào)度在數(shù)據(jù)波動(dòng)較大的場景下，資源的利用具有優(yōu)越性，本文構(gòu)建速度浪費(fèi)μ和堆積浪費(fèi)ε兩個(gè)變量。

如果當(dāng)前的PV>CV，則ETL過程以最大消費(fèi)數(shù)據(jù)速度運(yùn)行，因此速度浪費(fèi)μ=0，但是會(huì)造成堆積浪費(fèi)，其值為：

(14)

如果當(dāng)前的PV

(15)

式中：Δt為單位時(shí)間；W為ETL過程投入的內(nèi)存大小。本文使用速度浪費(fèi)和堆積浪費(fèi)之和作為資源代價(jià)的衡量指標(biāo)。結(jié)果越大，代表浪費(fèi)越多，資源利用率越低。

本文匹配算法的提出是為了確定ETL操作匹配關(guān)系使得在消費(fèi)數(shù)據(jù)速度最大的同時(shí)網(wǎng)絡(luò)距離費(fèi)用最小。如果消費(fèi)數(shù)據(jù)速度越大，或者網(wǎng)絡(luò)距離費(fèi)用越小，則該匹配越穩(wěn)定。因此，本文構(gòu)建了穩(wěn)定度θ來表示匹配是否達(dá)到穩(wěn)定。其值為：

(16)

式中：COST表示的是匹配后網(wǎng)絡(luò)距離費(fèi)用。θ越大表示匹配關(guān)系越穩(wěn)定。

4.3 結(jié)果分析

圖4給出了傳統(tǒng)的實(shí)時(shí)ETL調(diào)度機(jī)制中，以消費(fèi)數(shù)據(jù)速度最大值調(diào)度(max)、以消費(fèi)數(shù)據(jù)速度的平均值進(jìn)行調(diào)度的代價(jià)變化(avg)及本文彈性調(diào)度機(jī)制的代價(jià)變化(paper)曲線圖。圖5給出了三種調(diào)度方式隨著時(shí)間增加消費(fèi)的數(shù)據(jù)總量變化圖。從圖4中可以看出，在生產(chǎn)數(shù)據(jù)速度發(fā)生波動(dòng)的時(shí)候，彈性調(diào)度機(jī)制的代價(jià)一直都是低于傳統(tǒng)的調(diào)度方式的代價(jià)。從圖5中可以看出，彈性調(diào)度的方式并不會(huì)影響數(shù)據(jù)消費(fèi)的速度，其消費(fèi)數(shù)據(jù)的總量和最大消費(fèi)數(shù)據(jù)速度配置的ETL過程差不多。因此，本文的彈性調(diào)度機(jī)制與傳統(tǒng)的調(diào)度機(jī)制相比，在數(shù)據(jù)生產(chǎn)速度波動(dòng)較大的場景下，其消費(fèi)數(shù)據(jù)速度與最大消費(fèi)數(shù)據(jù)配置的ETL過程相差不多，但資源代價(jià)更小。

圖4 不同的調(diào)度機(jī)制資源代價(jià)變化曲線

圖5 不同的調(diào)度機(jī)制消費(fèi)數(shù)據(jù)總量變化圖

圖6給出了相同的ETL過程增長相同的服務(wù)個(gè)數(shù)后，使用不同算法確定匹配關(guān)系的消費(fèi)數(shù)據(jù)速度變化圖。圖7給出了不同算法匹配后網(wǎng)絡(luò)拓?fù)渚嚯x費(fèi)用變化圖。圖8給出了不同算法匹配后匹配度的變化圖?？梢钥闯?，本文提出的匹配算法能夠保證消費(fèi)數(shù)據(jù)速度最高的同時(shí)費(fèi)用最小，匹配的穩(wěn)定度最高，匹配更穩(wěn)定。

圖6 不同匹配算法消費(fèi)數(shù)據(jù)速度變化圖

圖7 不同匹配算法網(wǎng)絡(luò)距離費(fèi)用變化圖

圖8 不同匹配算法的穩(wěn)定度變化圖

圖9給出了實(shí)驗(yàn)環(huán)境中三個(gè)工作節(jié)點(diǎn)在數(shù)據(jù)波動(dòng)過程中資源消耗情況。由圖9可以看出，使用GLB算法來調(diào)度服務(wù)的個(gè)數(shù)，能夠保證節(jié)點(diǎn)的負(fù)載均衡。

圖9 GLB算法節(jié)點(diǎn)資源消耗變化曲線圖

5 結(jié) 語

本文提出了一種基于穩(wěn)定匹配的實(shí)時(shí)ETL彈性調(diào)度機(jī)制，用于處理在數(shù)據(jù)波動(dòng)較大的情況下，傳統(tǒng)實(shí)時(shí)ETL方案資源配置不合理的問題。該機(jī)制通過預(yù)測生產(chǎn)數(shù)據(jù)速度來計(jì)算需要調(diào)整的ETL服務(wù)個(gè)數(shù)。然后使用GLB算法和DI算法來分別完成服務(wù)的調(diào)度問題及服務(wù)的匹配問題。通過實(shí)驗(yàn)驗(yàn)證了方案的有效性，也為ETL過程調(diào)度提供了參考。針對實(shí)時(shí)ETL平臺(tái)中多個(gè)ETL過程的資源彈性調(diào)度是下一步工作的重點(diǎn)。