區域醫療數據采集方法優化

王正宏

（合肥工業大學計算機與信息學院 安徽省合肥市 230000）

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

1 問題描述

1.1 問題概述

區域醫療數據采集主要是將區域內各級醫療單位的異構醫療數據通過ETL工具集成到統一標準的區域中心數據倉庫。在淮南市健康信息平臺醫療數據采集過程中，我們發現ETL工具Kettle在集群模式下的數據采集效率相比單機環境得到明顯提升，但仍存在以下問題：

（1）不同任務要處理的業務數據重要程度不一，Kettle并未考慮任務本身的業務需求，導致一些急需執行的任務長時間處于等待序列。

（2）集群下Kettle在任務調度時默認使用輪詢算法，按照任務序列依次將任務分配給各個執行節點。該算法沒有考慮到任務本身的數據不平衡和各執行節點的資源占用情況，容易導致集群負載不均衡。

（3）任務執行時默認使用FCFS（First Come First Server）算法，這種靜態的執行順序不可調整的算法容易導致任務執行時間和等待時間不平衡問題。

1.2 ETL任務集群調度約束

圖1：示例ETL任務

圖2：拆分后的示例ETL任務

圖3：ETL任務調度工作流程圖

ETL指將一個或多個異構數據源的數據經過一系列加工處理再輸出到一個或多個目標數據存儲的流程。本文采用Kettle工具完成整個ETL流程。

Kettle中的ETL任務表現為Job和Transformation兩種形式。Kettle中將轉換作業作為一個任務調度單位，每個Kettle作業在同一時刻只能在集群中的一個執行節點上運行，不同的Kettle作業可以在集群中并行執行。一個Kettle作業中包含一個或多個具有指定先后順序的步驟（Step）。步驟是每個Kettle作業的最小單位，一般將一個步驟作為一個線程在執行節點上執行。

ETL任務調度的目標就是在任務約束和資源約束的前提下，通過適當的調度策略將不同的任務分配到最合適的執行節點上，并且在執行隊列中采用高效公平的執行策略，使集群環境下的資源得到高效的利用從而縮短ETL任務的執行時間。

2 改進的ETL任務調度策略

2.1 ETL任務相關定義

為了清晰表述文中任務調度的相關概念，這里引入數學模型的方法給出如下的一些定義。

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

定義8：Type(Stepi)表示任務負載類型。

2.2 ETL任務預處理策略

2.2.1 ETL任務緊迫度權值模型

基于淮南市健康信息平臺的實際業務需求，可以發現平臺對數據需求的緊迫程度基本符合二八定律，即只有20%的中心庫業務表數據是急需的。也就是說完成這部分數據的處理整個數據采集工作中最緊迫的。因此需要在任務調度之前根據實際業務需求為每個任務設定一個緊迫度，保證高緊迫度任務優先處理。

本文基于統一標準下的中心數據倉庫表結構，為每個業務表賦予一個緊迫度權值α，α值越大說明該業務表緊迫度越高。當調度器讀取ETL任務資源庫時，根據每個ETL任務目標表的α值中的最大值為該任務賦予緊迫度權值θ

ETL任務調度器根據θi對ETL任務排序，并按上述定義分為高緊迫度任務和低緊迫度任務。

2.2.2 ETL任務劃分策略

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

表1：集群配置信息

2.2.3 ETL任務負載模式分類

在實際環境中每個ETL任務都包含大量的數據處理步驟，例如：值映射、格式轉換、合并計算等。由于每個步驟要實現的功能不同，對處理資源的需求也存在很大的差異。比如有些步驟實現的功能需要進行大量的計算，那么就應該將該類型的任務放在CPU利用低的執行節點上執行。因此本文給出如下定義：

ETL任務調度器在任務分配時根據λi值的大小，將計算密集型任務分配到CPU使用率較低的執行節點上執行。

2.3 ETL任務調度分配策略

本文結合區域醫療數據ETL任務的本身特性和集群中各執行節點的資源使用情況提出一種基于貪心算法思想的任務調度分配策略?；谠摬呗栽O計的ETL任務調度工作流程圖如圖3所示。

貪心算法是一種求解近似最優解的方法，其核心思想就是從一個初始解出發不斷選擇當前的局部最優解，并最終通過這種貪心選擇策略得到一個近似的整體最優解。本文貪心調度分配算法具體步驟如下：

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

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

（3）根據每個ETL任務待處理源數據量大小分別對Q1和Q2從大到小排序。

（4）獲取集群各執行節點的CPU與內存資源使用情況。

（5）取Q1隊列中的首個任務放入當前CPU使用率最低的執行節點，若Q1隊列不為空,則繼續將隊首任務放入當前CPU利用率最低的執行節點，直至Q1隊列為空。

（6）取Q2隊列中的首個任務放入當前內存使用率最低的執行節點，若Q2隊列不為空,則繼續將當前隊首任務放入當前內存利用率最低的執行節點，直Q2隊列為空。

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

ETL任務通過貪心調度分配到執行節點后，存儲在執行器節點上的待執行隊列中。Kettle中默認先來先服務（FCFS）作為待執行隊列調度策略，FCFS是一種靜態不可調的調度策略。這種策略容易導致執行節點資源長期被某個作業占用，隊列中其它作業長時間處于等待狀態。高響應比優先（HRRN）算法能夠綜合考慮執行時間和等待時間，動態調整任務執行優先級，相對FCFS算法而言能夠較為公平的為每個任務分配線程資源。因此本文使用高響應比優先算法作為執行節點的執行策略。

表2：高緊迫度任務執行情況

圖4：ETL任務執行時間對比

圖5：集群節點CPU利用率

圖6：集群節點內存利用率

3 實驗結果與分析

3.1 實驗環境

為測試本文ETL任務調度策略的性能，本實驗在4臺虛擬機上搭建了包含一個主節點和三個執行節點的集群環境。具體配置如表1所示。本文選取淮南市區域健康信息平臺一個月的電子病歷數據作為實驗測試數據，該測試數據約包含一千萬條數據記錄。實驗中共創建29個ETL任務，其中十萬條記錄以下的8個，十萬至百萬條的17個，百萬條以上的4個。

3.2 結果與分析

實驗通過在相同的集群環境下分別應用Kettle原始調度策略和本文所提的改進策略，從任務總執行時間和集群資源利用率兩方面對所提ETL任務調度策略驗證分析。ETL任務數量為5、10、20、29個時，使用兩種調度策略消耗的時間如圖4所示。

由圖4可以看出在任務數不同的情況下，本文所提的ETL任務調度策略整體上優于Kettle的原始調度策略，并且隨著任務數的增加兩者調度執行時間差別不斷增大。由此可知本文所提任務調度策略非常適用于大規模的ETL任務調度環境。

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

由表2可以發現Kettle原始調度策略在執行高緊迫度任務時，由于其采用的輪詢調度策略導致高緊迫度任務長期處于等待狀態，非常不利于業務正常開展。本文提出的改進的任務調度策略在滿足業務需求方面相對原始調度策略有非常大的提高。在執行29個ETL任務的實驗中我們分別統計了兩種調度策略在三個執行節點上的CPU和內存平均利用率，具體情況如圖5和圖6所示。

由圖5和圖6所示的各執行節點CPU、內存利用率折線圖可知本文調度策略下CPU和內存使用率較Kettle原始調度策略而言分配比較均勻，據此判斷基于貪心算法的任務調度方案下集群負載較為均衡。綜上所述實驗分別從任務調度總耗時、業務需求以及集群負載均衡三個方面驗證了本文所提改進ETL任務調度策略的優勢。

4 結論

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