區(qū)域醫(yī)療數(shù)據(jù)采集方法優(yōu)化

王正宏

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 安徽省合肥市 230000）

ETL（Extraction,Transformation and Loading）技術(shù)被廣泛應(yīng)用于醫(yī)療數(shù)據(jù)采集領(lǐng)域，是構(gòu)建區(qū)域健康信息平臺(tái)[1]的核心技術(shù)。在過(guò)去的研究中ETL任務(wù)分配和調(diào)度問(wèn)題已經(jīng)被證明是一個(gè)NP完全問(wèn)題[2]。對(duì)此問(wèn)題前人已經(jīng)做了大量的研究，并提出了許多有針對(duì)性的方案。其中部分研究基于DAG（Directed acyclic graph）模型模擬任務(wù)調(diào)度場(chǎng)景，分別從權(quán)重、優(yōu)先級(jí)和任務(wù)排序幾方面考慮尋求關(guān)鍵路徑[3~5]（即ETL任務(wù)的最短執(zhí)行時(shí)間）。不過(guò)大部分基于DAG模型的研究在集群環(huán)境下的應(yīng)用效果都不很理想，因?yàn)檫@類(lèi)研究主要依據(jù)確定的執(zhí)行時(shí)間，而在集群環(huán)境下精確預(yù)測(cè)不同任務(wù)的執(zhí)行時(shí)間非常困難。文獻(xiàn)[7]結(jié)合并行元啟發(fā)式方法與貪婪方案，提出了一種新的最優(yōu)調(diào)度元啟發(fā)式方法。文獻(xiàn)[8]利用遺傳算法對(duì)任務(wù)調(diào)度時(shí)間片中的應(yīng)用負(fù)載特征采樣，并將復(fù)雜的迭代過(guò)程分配到后續(xù)的多個(gè)調(diào)度采樣周期中，以此為依據(jù)為任務(wù)分配符合計(jì)算特性的核心。在集群負(fù)載均衡方面文獻(xiàn)[9~10]提出在云計(jì)算環(huán)境下的動(dòng)態(tài)加權(quán)和改進(jìn)的粒子群優(yōu)化算法，Kokilavani[11]等提出了用于靜態(tài)MetaTask調(diào)度的負(fù)載均衡Min-Min算法。業(yè)務(wù)數(shù)據(jù)加載、更新及時(shí)性高的業(yè)務(wù)需求方面，文獻(xiàn)[12~14]做了任務(wù)實(shí)時(shí)調(diào)度方面的研究。為提升ETL任務(wù)調(diào)度效率本文提出了一種改進(jìn)的任務(wù)調(diào)度策略。該策略綜合考慮任務(wù)緊迫度、負(fù)載模式、數(shù)據(jù)規(guī)模以及集群資源占用情況，結(jié)合貪心算法思想將每個(gè)ETL任務(wù)分配到最合適的節(jié)點(diǎn)上執(zhí)行。實(shí)驗(yàn)表明該策略能夠在滿(mǎn)足業(yè)務(wù)需求的情況下，有效提高ETL任務(wù)調(diào)度效率，縮短整體執(zhí)行時(shí)間。

1 問(wèn)題描述

1.1 問(wèn)題概述

區(qū)域醫(yī)療數(shù)據(jù)采集主要是將區(qū)域內(nèi)各級(jí)醫(yī)療單位的異構(gòu)醫(yī)療數(shù)據(jù)通過(guò)ETL工具集成到統(tǒng)一標(biāo)準(zhǔn)的區(qū)域中心數(shù)據(jù)倉(cāng)庫(kù)。在淮南市健康信息平臺(tái)醫(yī)療數(shù)據(jù)采集過(guò)程中，我們發(fā)現(xiàn)ETL工具Kettle在集群模式下的數(shù)據(jù)采集效率相比單機(jī)環(huán)境得到明顯提升，但仍存在以下問(wèn)題：

（1）不同任務(wù)要處理的業(yè)務(wù)數(shù)據(jù)重要程度不一，Kettle并未考慮任務(wù)本身的業(yè)務(wù)需求，導(dǎo)致一些急需執(zhí)行的任務(wù)長(zhǎng)時(shí)間處于等待序列。

（2）集群下Kettle在任務(wù)調(diào)度時(shí)默認(rèn)使用輪詢(xún)算法，按照任務(wù)序列依次將任務(wù)分配給各個(gè)執(zhí)行節(jié)點(diǎn)。該算法沒(méi)有考慮到任務(wù)本身的數(shù)據(jù)不平衡和各執(zhí)行節(jié)點(diǎn)的資源占用情況，容易導(dǎo)致集群負(fù)載不均衡。

（3）任務(wù)執(zhí)行時(shí)默認(rèn)使用FCFS（First Come First Server）算法，這種靜態(tài)的執(zhí)行順序不可調(diào)整的算法容易導(dǎo)致任務(wù)執(zhí)行時(shí)間和等待時(shí)間不平衡問(wèn)題。

1.2 ETL任務(wù)集群調(diào)度約束

圖1：示例ETL任務(wù)

圖2：拆分后的示例ETL任務(wù)

圖3：ETL任務(wù)調(diào)度工作流程圖

ETL指將一個(gè)或多個(gè)異構(gòu)數(shù)據(jù)源的數(shù)據(jù)經(jīng)過(guò)一系列加工處理再輸出到一個(gè)或多個(gè)目標(biāo)數(shù)據(jù)存儲(chǔ)的流程。本文采用Kettle工具完成整個(gè)ETL流程。

Kettle中的ETL任務(wù)表現(xiàn)為Job和Transformation兩種形式。Kettle中將轉(zhuǎn)換作業(yè)作為一個(gè)任務(wù)調(diào)度單位，每個(gè)Kettle作業(yè)在同一時(shí)刻只能在集群中的一個(gè)執(zhí)行節(jié)點(diǎn)上運(yùn)行，不同的Kettle作業(yè)可以在集群中并行執(zhí)行。一個(gè)Kettle作業(yè)中包含一個(gè)或多個(gè)具有指定先后順序的步驟（Step）。步驟是每個(gè)Kettle作業(yè)的最小單位，一般將一個(gè)步驟作為一個(gè)線(xiàn)程在執(zhí)行節(jié)點(diǎn)上執(zhí)行。

ETL任務(wù)調(diào)度的目標(biāo)就是在任務(wù)約束和資源約束的前提下，通過(guò)適當(dāng)?shù)恼{(diào)度策略將不同的任務(wù)分配到最合適的執(zhí)行節(jié)點(diǎn)上，并且在執(zhí)行隊(duì)列中采用高效公平的執(zhí)行策略，使集群環(huán)境下的資源得到高效的利用從而縮短ETL任務(wù)的執(zhí)行時(shí)間。

2 改進(jìn)的ETL任務(wù)調(diào)度策略

2.1 ETL任務(wù)相關(guān)定義

為了清晰表述文中任務(wù)調(diào)度的相關(guān)概念，這里引入數(shù)學(xué)模型的方法給出如下的一些定義。

定義5：E表示各步驟之間的先后關(guān)系。Pre(Stepj, Stepk)表示Stepj是Stepk的前驅(qū)步驟。

定義8：Type(Stepi)表示任務(wù)負(fù)載類(lèi)型。

2.2 ETL任務(wù)預(yù)處理策略

2.2.1 ETL任務(wù)緊迫度權(quán)值模型

基于淮南市健康信息平臺(tái)的實(shí)際業(yè)務(wù)需求，可以發(fā)現(xiàn)平臺(tái)對(duì)數(shù)據(jù)需求的緊迫程度基本符合二八定律，即只有20%的中心庫(kù)業(yè)務(wù)表數(shù)據(jù)是急需的。也就是說(shuō)完成這部分?jǐn)?shù)據(jù)的處理整個(gè)數(shù)據(jù)采集工作中最緊迫的。因此需要在任務(wù)調(diào)度之前根據(jù)實(shí)際業(yè)務(wù)需求為每個(gè)任務(wù)設(shè)定一個(gè)緊迫度，保證高緊迫度任務(wù)優(yōu)先處理。

本文基于統(tǒng)一標(biāo)準(zhǔn)下的中心數(shù)據(jù)倉(cāng)庫(kù)表結(jié)構(gòu)，為每個(gè)業(yè)務(wù)表賦予一個(gè)緊迫度權(quán)值α，α值越大說(shuō)明該業(yè)務(wù)表緊迫度越高。當(dāng)調(diào)度器讀取ETL任務(wù)資源庫(kù)時(shí)，根據(jù)每個(gè)ETL任務(wù)目標(biāo)表的α值中的最大值為該任務(wù)賦予緊迫度權(quán)值θ

ETL任務(wù)調(diào)度器根據(jù)θi對(duì)ETL任務(wù)排序，并按上述定義分為高緊迫度任務(wù)和低緊迫度任務(wù)。

2.2.2 ETL任務(wù)劃分策略

為了保證高緊迫度任務(wù)的高效執(zhí)行，本文對(duì)此類(lèi)任務(wù)進(jìn)行了任務(wù)劃分處理，從而提高任務(wù)并行度，縮短任務(wù)執(zhí)行時(shí)間。根據(jù)ETL任務(wù)的定義可知每個(gè)ETL任務(wù)中包含多個(gè)具有先后順序的處理步驟，正常調(diào)度情況下會(huì)將一個(gè)任務(wù)作為一個(gè)主體分配到一個(gè)執(zhí)行節(jié)點(diǎn)進(jìn)行處理。事實(shí)上每個(gè)任務(wù)中的這些處理步驟我們可以看作一個(gè)將每個(gè)步驟作為一個(gè)結(jié)點(diǎn)，步驟與步驟之間的先后關(guān)系作為邊的DAG。本文采用深度遍歷思想將一個(gè)復(fù)雜的ETL任務(wù)劃分成多個(gè)線(xiàn)性順序執(zhí)行的簡(jiǎn)單ETL任務(wù)。圖1所示是一個(gè)用DAG圖表示的ETL任務(wù)，通過(guò)任務(wù)拆分可以得到圖2所示的三個(gè)可以并行執(zhí)行的ETL任務(wù)。將任務(wù)劃分后得到的ETL任務(wù)重新賦予緊迫度權(quán)值，并根據(jù)緊迫度權(quán)值大小插入已排序的ETL任務(wù)列表。

表1：集群配置信息

2.2.3 ETL任務(wù)負(fù)載模式分類(lèi)

在實(shí)際環(huán)境中每個(gè)ETL任務(wù)都包含大量的數(shù)據(jù)處理步驟，例如：值映射、格式轉(zhuǎn)換、合并計(jì)算等。由于每個(gè)步驟要實(shí)現(xiàn)的功能不同，對(duì)處理資源的需求也存在很大的差異。比如有些步驟實(shí)現(xiàn)的功能需要進(jìn)行大量的計(jì)算，那么就應(yīng)該將該類(lèi)型的任務(wù)放在CPU利用低的執(zhí)行節(jié)點(diǎn)上執(zhí)行。因此本文給出如下定義：

ETL任務(wù)調(diào)度器在任務(wù)分配時(shí)根據(jù)λi值的大小，將計(jì)算密集型任務(wù)分配到CPU使用率較低的執(zhí)行節(jié)點(diǎn)上執(zhí)行。

2.3 ETL任務(wù)調(diào)度分配策略

本文結(jié)合區(qū)域醫(yī)療數(shù)據(jù)ETL任務(wù)的本身特性和集群中各執(zhí)行節(jié)點(diǎn)的資源使用情況提出一種基于貪心算法思想的任務(wù)調(diào)度分配策略?；谠摬呗栽O(shè)計(jì)的ETL任務(wù)調(diào)度工作流程圖如圖3所示。

貪心算法是一種求解近似最優(yōu)解的方法，其核心思想就是從一個(gè)初始解出發(fā)不斷選擇當(dāng)前的局部最優(yōu)解，并最終通過(guò)這種貪心選擇策略得到一個(gè)近似的整體最優(yōu)解。本文貪心調(diào)度分配算法具體步驟如下：

（1）從待處理ETL任務(wù)集合T中取出高緊迫度任務(wù)并放入子任務(wù)集T1。

（2）將子任務(wù)集T1中的ETL任務(wù)依據(jù)λi值分別存入計(jì)算密集型任務(wù)隊(duì)列Q1和內(nèi)存資源消耗型任務(wù)隊(duì)列Q2。

（3）根據(jù)每個(gè)ETL任務(wù)待處理源數(shù)據(jù)量大小分別對(duì)Q1和Q2從大到小排序。

（4）獲取集群各執(zhí)行節(jié)點(diǎn)的CPU與內(nèi)存資源使用情況。

（5）取Q1隊(duì)列中的首個(gè)任務(wù)放入當(dāng)前CPU使用率最低的執(zhí)行節(jié)點(diǎn)，若Q1隊(duì)列不為空,則繼續(xù)將隊(duì)首任務(wù)放入當(dāng)前CPU利用率最低的執(zhí)行節(jié)點(diǎn)，直至Q1隊(duì)列為空。

（6）取Q2隊(duì)列中的首個(gè)任務(wù)放入當(dāng)前內(nèi)存使用率最低的執(zhí)行節(jié)點(diǎn)，若Q2隊(duì)列不為空,則繼續(xù)將當(dāng)前隊(duì)首任務(wù)放入當(dāng)前內(nèi)存利用率最低的執(zhí)行節(jié)點(diǎn)，直Q2隊(duì)列為空。

（7）從待處理ETL任務(wù)集合T中取出剩余任務(wù)并放入子任務(wù)集T1，重復(fù)步驟2-6直至待處理ETL任務(wù)集合T為空時(shí)，算法結(jié)束。

ETL任務(wù)通過(guò)貪心調(diào)度分配到執(zhí)行節(jié)點(diǎn)后，存儲(chǔ)在執(zhí)行器節(jié)點(diǎn)上的待執(zhí)行隊(duì)列中。Kettle中默認(rèn)先來(lái)先服務(wù)（FCFS）作為待執(zhí)行隊(duì)列調(diào)度策略，F(xiàn)CFS是一種靜態(tài)不可調(diào)的調(diào)度策略。這種策略容易導(dǎo)致執(zhí)行節(jié)點(diǎn)資源長(zhǎng)期被某個(gè)作業(yè)占用，隊(duì)列中其它作業(yè)長(zhǎng)時(shí)間處于等待狀態(tài)。高響應(yīng)比優(yōu)先（HRRN）算法能夠綜合考慮執(zhí)行時(shí)間和等待時(shí)間，動(dòng)態(tài)調(diào)整任務(wù)執(zhí)行優(yōu)先級(jí)，相對(duì)FCFS算法而言能夠較為公平的為每個(gè)任務(wù)分配線(xiàn)程資源。因此本文使用高響應(yīng)比優(yōu)先算法作為執(zhí)行節(jié)點(diǎn)的執(zhí)行策略。

表2：高緊迫度任務(wù)執(zhí)行情況

圖4：ETL任務(wù)執(zhí)行時(shí)間對(duì)比

圖5：集群節(jié)點(diǎn)CPU利用率

圖6：集群節(jié)點(diǎn)內(nèi)存利用率

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

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

為測(cè)試本文ETL任務(wù)調(diào)度策略的性能，本實(shí)驗(yàn)在4臺(tái)虛擬機(jī)上搭建了包含一個(gè)主節(jié)點(diǎn)和三個(gè)執(zhí)行節(jié)點(diǎn)的集群環(huán)境。具體配置如表1所示。本文選取淮南市區(qū)域健康信息平臺(tái)一個(gè)月的電子病歷數(shù)據(jù)作為實(shí)驗(yàn)測(cè)試數(shù)據(jù)，該測(cè)試數(shù)據(jù)約包含一千萬(wàn)條數(shù)據(jù)記錄。實(shí)驗(yàn)中共創(chuàng)建29個(gè)ETL任務(wù)，其中十萬(wàn)條記錄以下的8個(gè)，十萬(wàn)至百萬(wàn)條的17個(gè)，百萬(wàn)條以上的4個(gè)。

3.2 結(jié)果與分析

實(shí)驗(yàn)通過(guò)在相同的集群環(huán)境下分別應(yīng)用Kettle原始調(diào)度策略和本文所提的改進(jìn)策略，從任務(wù)總執(zhí)行時(shí)間和集群資源利用率兩方面對(duì)所提ETL任務(wù)調(diào)度策略驗(yàn)證分析。ETL任務(wù)數(shù)量為5、10、20、29個(gè)時(shí)，使用兩種調(diào)度策略消耗的時(shí)間如圖4所示。

由圖4可以看出在任務(wù)數(shù)不同的情況下，本文所提的ETL任務(wù)調(diào)度策略整體上優(yōu)于Kettle的原始調(diào)度策略，并且隨著任務(wù)數(shù)的增加兩者調(diào)度執(zhí)行時(shí)間差別不斷增大。由此可知本文所提任務(wù)調(diào)度策略非常適用于大規(guī)模的ETL任務(wù)調(diào)度環(huán)境。

根據(jù)電子病歷業(yè)務(wù)需求和上文所述的高緊迫度任務(wù)判定策略，可知本文測(cè)試的29個(gè)ETL任務(wù)中共有5個(gè)屬于高緊迫度任務(wù)。在執(zhí)行所有的測(cè)試任務(wù)情況下，5個(gè)高緊迫度任務(wù)具體執(zhí)行情況如表2所示。（其中基于本文所提策略的任務(wù)調(diào)度開(kāi)始于2020.1.19-9:14:00,基于Kettle原始策略的任務(wù)調(diào)度開(kāi)始于2020.1.19-10:00:00）。

由表2可以發(fā)現(xiàn)Kettle原始調(diào)度策略在執(zhí)行高緊迫度任務(wù)時(shí)，由于其采用的輪詢(xún)調(diào)度策略導(dǎo)致高緊迫度任務(wù)長(zhǎng)期處于等待狀態(tài)，非常不利于業(yè)務(wù)正常開(kāi)展。本文提出的改進(jìn)的任務(wù)調(diào)度策略在滿(mǎn)足業(yè)務(wù)需求方面相對(duì)原始調(diào)度策略有非常大的提高。在執(zhí)行29個(gè)ETL任務(wù)的實(shí)驗(yàn)中我們分別統(tǒng)計(jì)了兩種調(diào)度策略在三個(gè)執(zhí)行節(jié)點(diǎn)上的CPU和內(nèi)存平均利用率，具體情況如圖5和圖6所示。

由圖5和圖6所示的各執(zhí)行節(jié)點(diǎn)CPU、內(nèi)存利用率折線(xiàn)圖可知本文調(diào)度策略下CPU和內(nèi)存使用率較Kettle原始調(diào)度策略而言分配比較均勻，據(jù)此判斷基于貪心算法的任務(wù)調(diào)度方案下集群負(fù)載較為均衡。綜上所述實(shí)驗(yàn)分別從任務(wù)調(diào)度總耗時(shí)、業(yè)務(wù)需求以及集群負(fù)載均衡三個(gè)方面驗(yàn)證了本文所提改進(jìn)ETL任務(wù)調(diào)度策略的優(yōu)勢(shì)。

4 結(jié)論

本文從淮南市健康信息平臺(tái)數(shù)據(jù)采集中的實(shí)際問(wèn)題出發(fā)，基于貪心算法思想提出了一種改進(jìn)的ETL任務(wù)調(diào)度優(yōu)化策略。該調(diào)度策略著重考慮了平臺(tái)實(shí)際業(yè)務(wù)需求和集群負(fù)載均衡問(wèn)題。實(shí)驗(yàn)證明，高緊迫度任務(wù)執(zhí)行時(shí)間大幅縮減，同時(shí)ETL任務(wù)隊(duì)列的整體執(zhí)行時(shí)間也有所降低，基本達(dá)到了預(yù)期目標(biāo)，并已在淮南市健康信息平臺(tái)數(shù)據(jù)采集工作中試用。