ETL工作流活動優先級的確定及并行實現

摘 要:ETL流程是一個以數據為中心的工作流，對ETL工作流的執行過程進行論述，提出了一個算法，計算ETL工作流中各個活動的執行優先級，在工作流執行中為優先級相同且相互之間沒有依賴關系的活動集創建多個線程，通過并行執行這些活動，提高了ETL工作流的執行效率。實驗結果表明，所提出的并行算法與串行算法比較，在數據量足夠大的情況下，加速比可接近理想值，加速比隨著數據量增大而提高。

關鍵詞:數據倉庫; 抽取、轉換和加載工作流; 執行優先級; 并行執行

中圖分類號:TP311

文獻標志碼:A

文章編號:1001-3695(2010)02-0548-04

doi:10.3969/j.issn.1001-3695.2010.02.040

Determine priority of ETL workflow activities and their parallel execution

HUANG Jue-ming， XI Jian-qing

(College of Computer Science Engineering， South China University of Technology， Guangzhou 510006， China)

Abstract:The process of ETL could be treated as a data-centric workflow. This paper discussed the execution of the ETL workflow and proposed an algorithm to determine the priority of the activities in the ETL workflow， threads were created for the activities that share the same priority and were not dependent on each other. The activities were put in the parallel execution environment， which could improve the execution efficiency of the ETL workflow. The result of the experiment shows that the acceleration ratio of the parallel algorithm and the serial algorithm could be approaching the ideal value， as long as the data records involving is large enough. The acceleration ratio rises as the number of the involved data records increases.

Key words:data warehouse; ETL(extraction， transformation， loading) workflow; execution priority; parallel execution

0 引言

建立數據倉庫的操作過程通常可以看做是一個工作流，這個工作流以數據為中心，包括了數據抽取、數據轉換、清洗以及數據加載。ETL工具即是負責處理這一類流程的數據集成工具。其主要功能特性包括:a)找出數據源的相關元數據，包括數據表的模式、文件的結構等;b)依據a)中的元數據從數據源中抽取原始數據;c)將被抽取出來的異構數據進行轉換，以形成統一格式的數據集;d)根據用戶的業務規則，將上一階段的數據集進行清洗;e)將統一的、清潔的數據加載到目標數據倉庫中。ETL工具中包含有若干種組件，這些組件可以完成ETL流程中的某個功能特性，可以根據業務需求將這些組件進行組裝，形成一個工作流。

ETL工作流設計的合理性以及流程的運行效率對于一個數據倉庫項目建設的成功與否起著至關重要的作用。根據文獻[1]顯示，在數據倉庫的建設過程中，用于ETL工具購買或者開發的費用以及ETL流程的設計與維護的開銷往往占整個項目總開銷的30%以上，有一些甚至占60%。

ETL工作流的設計質量往往取決于能否對業務需求和數據倉庫環境進行形式化建模。ETL工作流模型包括ETL概念模型和ETL邏輯模型兩部分。文獻[2]中定義了ETL概念模型中的基本元素，并提供了概念模型中常見的轉換。文獻[3]中闡述了建立一個ETL概念模型的方法以及步驟。文獻[4]提出在ETL概念建模的過程中使用UML方法。文獻[5]定義了ETL邏輯模型的基本元素，并介紹了使用形式化的方法建立一個ETL邏輯模型的過程;文獻[6]提出將一個ETL流程建模為一個有向圖，使用圖論中的研究成果來研究ETL工作流;文獻[7]介紹了一種將ETL概念模型轉換為ETL邏輯模型的方法，這是一個半自動的過程，可以提高ETL流程的設計質量。

以上的文獻大多是提出建立ETL工作流模型的方法，而對于工作流的執行卻都沒有涉及，現有的ETL工具一般采用串行執行ETL工作流中的每一個活動的方法。本文首先簡單介紹了ETL概念模型與邏輯模型，接著提出一種算法，對ETL工作流進行分析，計算確定工作流中每個活動的執行優先級，并通過創建多個線程，并行執行相互之間沒有依賴關系的活動，有效提高了ETL工作流的執行效率。

本文介紹了ETL概念模型和ETL邏輯模型，并說明如何對ETL流程建模的方法，然后提出了一個算法，用于確定ETL工作流中各個活動的執行優先級，并通過為相互之間沒有依賴關系的活動創建多個線程，并行執行這些活動，提高了整個ETL工作流的執行效率，實驗分別使用了串行方法與并行方法執行ETL工作流中的活動，通過比較這兩種方法的時間效率，證明所提出算法的有效性。

1 ETL工作流模型

在ETL流程設計中，首先應該根據業務需求和相關數據源的結構建立概念模型，確定源數據庫與目標數據庫之間的映射關系，然后根據概念模型建立邏輯模型。

1.1 ETL概念模型

概念建模是整個ETL流程設計的最初階段，在這個階段，ETL流程設計者的主要任務是搜集用戶的需求，然后分析相關數據源的結構及其內容[2]，確定抽取操作所使用的數據源。ETL概念模型主要是建立數據源與數據倉庫的模式或者屬性之間的映射關系，以及在映射過程所需要的轉換和清洗操作。

下面給出在本文中使用的幾個ETL概念模型基本元素的定義:

轉換(transform) 是從數據源到目標數據倉庫屬性映射過程中對數據進行必要的轉換、清洗操作。它包括了數據清洗/過濾操作與模式轉換操作。

約束(ETL constrain) 對數據集合中的數據必須滿足的某些條件進行建模的結果。

數據供應關系(provider relationship) 定義從數據源到目標數據倉庫的屬性之間的映射關系，以及中間可選的相關轉換。

下面以一個例子來說明ETL流程的概念建模。一家電子商務跨國企業，需要從中國和美國兩個分公司的數據庫抽取注冊用戶的信息到集中的數據倉庫中進行分析，假設數據源和數據倉庫中的模式如下:

S1.customer(customerID，name，cityID，email，date)

S1.city(cityID，cityName，countryName)

S2.customer(name，countryName，cityName，email，date)

DW.customer(customerID，name，countryName，cityName，email，date)

對于這個ETL場景，可以建立如圖1所示的概念模型。其中:S1和S2表示數據源中的表，DSA表示中間數據庫，DW表示目標數據倉庫。

在上面這個例子中，為了保證目標數據倉庫中數據的完整性，需要從S1和S2兩個數據源抽取數據，對它們執行并(union)操作。為了與數據倉庫中事實表的模式一致，必須對S1中的customer表和city表執行外連接，而且還要將S2中date屬性的數據從北美的日期格式(mm/dd/yyyy)轉換成中國的日期格式(yyyy/mm/dd)，還需要根據S2的其他屬性組合(name、email)為S2表計算生成一個主鍵。其中，并運算、外連接運算以及日期轉換屬于概念模型中的轉換(transform)，其他的操作如PK、SK則屬于約束(ETL constrain)。

1.2 ETL邏輯模型

ETL概念模型并不是一個完整的工作流模型[7]，它定義了數據源與目標數據倉庫屬性之間的映射關系以及中間必要的轉換，但并不關注轉換的語義以及執行順序。

ETL流程的邏輯模型是一個以數據為中心的工作流模型，在邏輯建模階段，ETL流程的設計者需要明確定義數據流所經過的各個活動的操作語義，并確定整個流程中各個活動的執行順序。

活動(activity)是ETL工作流的基本執行單元，是ETL邏輯模型中一個重要元素。它定義了輸入數據模式、輸出數據模式、活動的操作語義以及活動的執行優先級。活動的操作語義定義了活動對輸入數據所執行的操作，以及輸入數據模式到輸出數據模式之間的映射關系，可以使用SQL語言或者其他的形式化語言對語義進行描述，也可以使用ETL工具箱中的操作組件和相應的運行時參數進行表示。在一個ETL流程中，必須明確規定每一個活動的執行優先級，ETL流程中的任意兩個活動，如果存在依賴關系，即一個活動的輸入模式依賴于另一個活動的輸出模式(不一定是相鄰活動)，那么，這兩個活動構成嚴格偏序關系，可以確定其執行的先后順序。一般情況下，在一個ETL流程中，抽取操作(extract)總是最先執行，加載操作(load)最后執行。

ETL邏輯模型中的活動對應于ETL概念模型中的轉換或約束，但它提供了更詳細的運行時信息。每一個活動都必須定義明確的操作語義，還必須規定每一個活動的執行優先級。本文的第3章將給出一個算法，闡述如何在一個ETL工作流中計算每個活動的執行優先級。

對于1.1節所舉的例子，圖2是它所對應的邏輯模型圖，圖中主要表示了活動的語義以及執行優先級，對于比較明顯的語義沒有標出。

2 ETL活動優先級的確定及并行執行

在ETL邏輯模型中，必須確定每一個活動的執行優先級，以確定整個ETL工作流的執行順序。在確定了執行的優先級之后，可對相互之間沒有依賴關系的活動并行執行，以提高整個ETL工作流的執行效率。

2.1 確定ETL工作流活動優先級

下面首先闡述確定活動執行優先級的算法思想，然后使用偽碼對算法進行形式化描述:

在ETL邏輯模型中，可能會存在多個數據供應關系，每一個數據供應關系都是以抽取操作開始，以加載操作結束的。在確定活動優先級的時候，把每一個抽取操作(即起始操作)的優先級定義為1(假定ETL工作流的優先級從數值1開始，依次遞增，數值越小優先級越高)，然后分析其他的非起始活動。對于每一個尚未確定其優先級的活動，如果它的所有前驅活動都已經確定了優先級，那么可以通過計算它的所有前驅活動優先級的最大值，再加1取得。通過遍歷活動集中的所有活動，就可以確定ETL工作流中所有活動的優先級。

算法1 確定ETL工作流活動優先級

輸入:圖G(V，E)表示ETL工作流，V表示工作流中的活動集，E表示活動之間的拓撲關系;

輸出:活動節點集V，包含了ETL工作流中各個活動的執行優先級信息。

L1 unvisited = V;

L2 for each act in V{

L3

if(act ∈ startActivity){

L4

act.order = 1;

L5

visited = visited ∪ {act};

L6

unvisited = unvisited – {act};} }

L7 while(unvisited is not empty){

L8for each act in unvisited{

L9

if((a ， act) ∈ E anda ∈ visited ) {

L10

act.order = max{a.order} + 1;

L11

visited = visited ∪ {act};

L12

unvisited = unvisited – {act};} } }

在上面的算法描述中，L1將活動節點集的所有活動都放在unvisited數組中，表示所有活動都是未訪問的;L2~L6遍歷整個節點集并判斷活動act是否是起始操作，如果是則將其優先級設置為1，將其加入visited數組，并從unvisited數組中將其移除;L7~L12不斷遍歷unvisited數組直到其為空，L9表示如果一個活動act的所有前驅活動的優先級都已經確定，則act的優先級也可以確定，L10計算act所有前驅活動優先級的最大值，再加1作為act的優先級，同時將act加入visited數組，并從unvisited數組中將其移除。

2.2 并行執行ETL工作流中的活動

確定了ETL邏輯模型中每一個活動的優先級之后，ETL工作流引擎會按照優先級從高到低依次執行工作流中的每一個活動。

在使用串行方法執行的工作流引擎中，每次從活動集中獲取優先級最高的一個活動并執行，執行完一個活動之后再選擇另一個當前優先級最高的活動執行，不斷重復這樣的過程直到ETL工作流中的所有活動執行完畢。

如果存在多個活動的優先級相同，在上述的串行方法中需要依次順序執行這些活動，但是這些活動是可以并行執行的。把這些活動放進一個執行階段，每一個執行階段都是一個容器，存放多個優先級相同的活動。同一執行階段的活動不存在依賴關系，根據前面的討論，存在依賴關系的活動構成嚴格偏序關系，其優先級不可能相等。并行執行優先級相同的多個活動能夠獲得更高的時間效率。

在同一執行階段中的各個活動，在執行順序上不存在依賴關系，但ETL工作流是以數據為中心的，各個活動處理的對象是數據庫中的數據表或者操作系統中的文件，有可能存在同一執行階段的兩個或者多個活動對同一對象(數據表或者文件)進行操作的情況。如果操作對象是數據庫中的數據表，大多數數據庫管理系統都有比較完善的并發執行控制機制，所以ETL工作流引擎把并發讀寫一個數據表所需要處理的工作(如對數據表加鎖等)交給相應的數據庫管理系統進行處理;如果在同一執行階段存在多個活動對同一個文件進行操作，則必須把這些活動分配到不同的執行階段中執行，每次只允許相互爭奪資源(即文件)的一個活動對文件進行讀寫，這樣可以保證ETL工作流中每一個活動所處理的數據滿足一致性的要求。

在并行計算環境中，可以創建多個線程分別執行同一個執行階段中可以并行執行的活動。下面的算法描述工作流引擎識別并執行這些活動的過程。

算法2 ETL工作流引擎識別與執行活動算法描述

輸入:活動節點集V，包含了ETL工作流中各個活動的執行優先級信息。

輸出:ETL工作流的執行結果

L1 unfinishedActs = V;

L2 while( unfinishedActs is not empty ) {

L3runActs = getHighestPriorityActs();

L4runActs = handleConflictAct(runActs);

L5for each act in runActs {

L6

createThread( act );

L7

unfinishedActs = unfinishedAct – {act};} }

在上面的算法描述中，L1把所有的活動都放在unfinished數組中，表示這些活動是未執行的;L2不斷遍歷活動集直到其為空，L3函數getHighestPriorityActs遍歷所有尚未執行的活動，識別出優先級最高的活動集合，將其放到一個容器中，等待執行;L4函數handleConflictAct處理一個執行階段中存在多個活動對同一個文件進行操作的情況，實現的功能是只保留互相爭奪資源的一個活動在容器中，將其他活動從runActs中移出，放在后續的執行階段執行，這樣可以確保對于任意一個文件，每個執行階段只有一個活動對其進行操作。L5~L7工作流引擎為可以并行執行的每一個活動act各創建一個線程，并將活動act從unfinishedActs數組中移除。

通過并行執行多個活動，可以明顯提高ETL工作流的執行效率，在更短的時間之內完成目標數據倉庫數據的加載與更新，使數據倉庫的用戶可以及時使用最新的數據進行分析，從而作出更加正確的決策。

3 實驗結果分析

本文對上述的算法進行實現，采用C++語言，并使用boost thread函數庫為每個可以并行執行的活動創建線程，使用標準模板庫(STL)中的vector容器存放優先級相同的活動。

下面對以上提出的算法作一個性能分析，在主流的數據庫環境下，對算法中所提出的為優先級相同且相互之間沒有依賴關系的多個活動創建線程，并行執行這些活動，與每次只選取ETL工作流中優先級最高的一個活動串行執行的方法進行時間性能的比較。

實驗環境為:Intel Core T2300 1.6 GHz×2，內存為DDR2 2 GB，磁盤為80 GB，操作系統為MS Windows XP Professional SP2，開發環境為MS Visual Studio.NET 2003。數據庫環境包括Oracle 10.2g、MS SQL Server 2005、MySQL 5.1。

實驗場景是模擬1.2節所舉例子的數據，從兩個源數據庫中分別抽取注冊用戶信息到一個中間工作數據庫進行處理。實驗的方法分別是將兩個數據抽取操作并行執行(這兩個抽取操作不存在依賴關系)，以及將這兩個數據抽取操作串行執行，即一個操作結束后才啟動另一個操作(以下的分析中將這兩種方法簡稱為并行方法與串行方法)。每一組實驗數據都是三次實驗數據取平均值的結果。

實驗場景一 數據源S1位于SQL Server數據庫中，數據源S2位于Oracle數據庫中，工作數據庫位于SQL Server數據庫中。表1是實驗數據。

表1 場景一實驗數據

數據元組數并行方法/ms串行方法/ms加速比

1 0003 6775 5681.51

5 0007 896134111.70

10 00012 31322 2241.80

20 00021 94341 8331.91

50 00053 765104 7711.95

100000107 365211 7861.97

實驗場景二 數據源S1位于SQL Server數據庫中，數據源S2位于MySQL數據庫中，工作數據庫位于SQL Server數據庫中。表2是實驗數據。

表2 場景二實驗數據

數據元組數并行方法/ms串行方法/ms加速比

1 0003 8435 4161.41

5 0007 80213 4531.72

10 00012 56312 5631.83

20 00023 39642 8941.83

50 00055 302103 0591.86

100 000112 328209 8441.87

由上面的實驗數據可以看出，本文所提出的算法可以有效提高ETL工作流的執行效率。本實驗中，并行執行的活動數為2，理想情況下加速比為2，實驗結果顯示實際加速比在1.4~2.0，當數據量增大時，加速比也隨著增大。這是因為當一個活動所處理的數據量比較小時，遷移數據本身所需要的時間也比較少，而創建線程需要一定的時間開銷，此時占用的比例較大;而當處理的數據量比較大時，創建線程所需要的時間占總時間的比例下降，達到了比較好的加速比。ETL工具所處理的數據量通常情況下都比較大，本文所提出的這個算法所帶來時間效率的提高是比較明顯的，具有很強的實用性。

4 結束語

本文首先介紹了ETL的概念模型和邏輯模型，ETL概念模型主要是建立數據源與數據倉庫之間的映射關系，而ETL邏輯模型則主要是確定流程中各個活動的執行優先級及其語義。本文通過一個電子商務的例子闡述了建立ETL概念模型和邏輯模型的過程，提出了一個算法，分析ETL工作流并計算工作流中各個活動的執行優先級，將優先級相同并且相互之間沒有依賴關系的活動放在同一個執行階段，通過創建多個線程并行執行這些活動，提高了ETL工作流的執行效率。實驗數據表明，該算法與現有的串行算法比較在時間效率方面具有較大優勢，并且隨著數據量增大，加速比提高，當參與計算的數據量比較大時，加速比可以趨近于理想值。數據倉庫環境中的ETL工具經常需要處理海量數據，這個算法對于ETL工具性能的提高具有較強的實用性。

參考文獻:

[1]STRANGE K. ETL was the key to this data warehouse’s success， Technical Report CS-15-3143[R]. 2002.

[2]VASSILIADIS P， SIMITSIS A， SKIADOPOULOS S. Conceptual mode-ling for ETL processes[C]//Proc of the 5th ACM International Worshop on Data Warehousing and OLAP. 2002:14-21.

[3]SIMITSIS A， VASSILIADIS P. A methodology for the conceptual modeling of ETL processes[C]//Proc of the Decision Systems Engineering. 2003:305-316

[4]TRUJILLO J， LUJAN-MORA S. A UML based approach for modeling ETL processes in data warehouse[C]//Proc of LNCS， vol 2813. 2003:307-320.

[5]VASSILIADIS P， SIMITSIS A， GEORGANTAS P， et al. A generic and customizable framework for the design of ETL scenarios[J]. Information Support Systems， 2005，30(7):492-525.

[6]VASSILIADIS P， SIMITSIS A， SKIADOPOULOS S. Modeling ETL activities as graphs[C]//Proc of the 4th International Workshop on Decision and Management of Data Warehouses. 2002:52-61.

[7]SIMITSIS A， VASSILIADIS P. A method for the mapping of conceptual designs to logical blueprints for ETL processes[J]. Decision Support Systems， 2008，45(1):22-40.

[8]張忠平，趙瑞珍.基于結構圖的ETL過程建模方法[J]. 計算機應用研究，2008， 25(11):3354-3356.

[9]張旭峰，孫未未，汪衛，等.增量ETL過程自動化產生方法的研究[J]. 計算機研究與發展，2006，43(6):1097-1103.