基于Hadoop的業(yè)務過程模型管理方法研究

盧廳劉建勛++文一憑+周棟++石敏++陳聰陽

摘要：目前現(xiàn)有業(yè)務過程模型研究的共同特點便是基于單機環(huán)境來構(gòu)建業(yè)務過程庫，并基于傳統(tǒng)關(guān)系數(shù)據(jù)庫來管理業(yè)務過程模型，完成相關(guān)的檢索、存儲等操作。為提高大規(guī)模業(yè)務過程模型檢索與存儲的效率，本文提出一種新的業(yè)務過程模型管理方法。該方法采用基于Hadoop大數(shù)據(jù)處理平臺對業(yè)務過程模型進行管理，并采用Map/Reduce編程框架和HDFS文件系統(tǒng)分別對業(yè)務過程模型進行檢索和存儲，提高了業(yè)務過程模型存儲效率，減少了模型檢索匹配的時間。通過原型系統(tǒng)進行試驗驗證評估，證明了所提方法在存儲和檢索效率方面高于單機環(huán)境。

關(guān)鍵詞：業(yè)務過程模型管理；Hadoop；檢索；存儲；效率

中圖分類號：TP311文獻標識碼：A

1引言

隨著計算機與網(wǎng)絡的不斷發(fā)展與成熟，以信息技術(shù)為主導的各種高新技術(shù)為企業(yè)的發(fā)展提供了極大的支持，其中敏捷制造、并行工程、企業(yè)業(yè)務過程重組、供應鏈管理等先進制造技術(shù)的應用與推廣成為當前企業(yè)贏得市場競爭采取的主要手段。以上技術(shù)都以企業(yè)業(yè)務過程為基礎施行的，從而要求企業(yè)管理的模式從傳統(tǒng)面向功能部門制的管理轉(zhuǎn)化為面向企業(yè)業(yè)務過程的管理，簡稱面向過程的管理。業(yè)務過程是指在人員和技術(shù)的協(xié)調(diào)下所進行的一組為實現(xiàn)共同業(yè)務目標而采取的活動。在20世紀90年代以前企業(yè)采用的基于功能部門制的管理方式是一種嚴格的遞階式關(guān)系管理，易造成組織之間交流上的障礙。而面向過程的管理方式，通過業(yè)務過程將企業(yè)中的活動連接起來，模糊了組織邊界，通過組織間的無障礙交流提高企業(yè)工作效率。

業(yè)務過程模型是一種通過定義組成活動及活動間邏輯關(guān)系，來描述工作過程的模型，是企業(yè)業(yè)務過程分析與重組的基礎，是記錄和保存企業(yè)經(jīng)營過程知識的一種有效途徑。由于業(yè)務過程模型描述了業(yè)務是如何一步步被處理的，也描述了在業(yè)務處理過程中數(shù)據(jù)是如何被處理的，人員是如何配置的，因此業(yè)務過程模型成為了組織部門很重要的資產(chǎn)。隨著業(yè)務過程管理系統(tǒng)越來越廣泛的應用，導致各行各業(yè)積累了越來越多的業(yè)務過程模型，有些企業(yè)已經(jīng)積累了上千的業(yè)務過程模型。這樣便產(chǎn)生了一系列新的問題，例如：如何存儲業(yè)務過程模型？如何進行業(yè)務過程模型的檢索？

國內(nèi)外已有相關(guān)學者對此展開研究，但現(xiàn)有研究的共同特點便是基于單機環(huán)境來構(gòu)建業(yè)務過程庫，并基于傳統(tǒng)關(guān)系數(shù)據(jù)庫來管理業(yè)務過程模型，完成相關(guān)的存儲、檢索等操作。但事實上，從信息處理的角度看，業(yè)務過程模型可視為一種特殊類型的數(shù)據(jù)，由于業(yè)務過程模型是由眾多企業(yè)組織機構(gòu)生成的，它具有數(shù)據(jù)源多樣性、分布性等特點，當業(yè)務過程模型的規(guī)模增長到一定規(guī)模時，傳統(tǒng)關(guān)系數(shù)據(jù)庫在處理這些這樣海量的數(shù)據(jù)時出現(xiàn)性能和可擴展性的瓶頸。更為重要的是，利用單臺主機來管理業(yè)務過程模型，盡管主機能達到很高的硬件配置，但其處理能力還是有限的。因此，采用分布式存儲和計算來管理大規(guī)模業(yè)務過程模型將是一種必然的發(fā)展趨勢。

目前，分布式存儲和計算領(lǐng)域，全球約有上百種不同的方案，而Hadoop是其中使用較為廣泛的一種。近年來，隨著大數(shù)據(jù)研究與應用興起，工業(yè)界已經(jīng)廣泛使用 Hadoop 作為其大數(shù)據(jù)處理平臺，且具有相對較為成熟的商業(yè)應用。Hadoop技術(shù)宗旨就是在于分布式處理數(shù)據(jù)，采用分布式計算和存儲技術(shù)，并且將簡化了分布式處理細節(jié)。Hadoop非常適合處理非結(jié)構(gòu)化的海量數(shù)據(jù)。因此，基于Hadoop來完成海量分布的業(yè)務過程模型管理可能是一種可行的解決方案，該研究不僅具有重要的理論意義，同時也具有十分重要的實際應用價值。

計算技術(shù)與自動化2015年12月

第34卷第4期盧廳等：基于Hadoop的業(yè)務過程模型管理方法研究

2相關(guān)研究

業(yè)務過程模型可以采用圖表示，因此可以基于圖檢索領(lǐng)域相關(guān)工作和業(yè)務過程模型檢索領(lǐng)域兩個方面分析業(yè)務過程領(lǐng)域相關(guān)工作。在基于圖檢索領(lǐng)域可以借鑒的工作的有基于圖結(jié)構(gòu)的精確檢索與基于圖結(jié)構(gòu)的相似性檢索。在文獻[1]中，作者Ke Y總結(jié)了圖檢索方面的工作。Shasha D 等人[2]基于圖路徑建索引，用戶設定被索引的最長路徑的長度；文獻[3]改進了FG-Index，對于經(jīng)常使用的查詢建立了索引。

在基于業(yè)務過程模型檢索領(lǐng)域也出現(xiàn)了很多相關(guān)工作。文獻[4-6]提出基于業(yè)務流程建模標注BPMN的模型檢索語言，采用了數(shù)據(jù)庫管理系統(tǒng)的檢索性能來加速BPMN模型檢索的機制；文獻[7，9]是業(yè)務過程模型相似檢索工作的綜述，文中涉及的所有工作由于無索引來提高檢索效率，因此采用逐個模型與檢索樣例模型比較相似度的方法，十分耗時。在文獻[9]中，作者提出了基于度量樹索引方法，該方法使用圖編輯距離計算模型相似度。在文獻[10]中，作者基于最大公共子圖和最小公共超圖的圖匹配方法，提出了JTangWFR流程推薦系統(tǒng)，該方法使用圖編輯距離計算模型相似度。作者曹斌[11]基于近距離最大子圖優(yōu)先方法，提出了流程推薦系統(tǒng)。文獻[12]基于Levenshtein距離計算最小深度優(yōu)先搜索編碼，提出了新的流程檢索。上述業(yè)務過程模型檢索各項的工作均沒有采用模型行為語義。

文獻[13]嘗試利用Hadoop云平臺來進行海量數(shù)字圖像的數(shù)據(jù)挖掘，解決日益增多的圖像進行有效的存儲和快速的數(shù)據(jù)挖掘的問題。因為單機不能夠滿足海量數(shù)據(jù)推薦計算的需要，文獻[14]提出了基于分布式計算開源軟件框架Hadoop的系統(tǒng)解決方案，解決推薦系統(tǒng)的可擴展性問題。文獻[15]中針對海量小文件小而多的特點提出了多Master分布式存儲與檢索，解決了海量小文件的分布式存儲與檢索問題。

BeeHiveZ是一個過程模型數(shù)據(jù)的應用開發(fā)框架，可在此之上進行過程模型相似性度量、過程模型檢索等應用開發(fā)。BeeHiveZ實現(xiàn)是一個開源的軟件（SourceForge.net）。它能夠?qū)崿F(xiàn)業(yè)務過程模型作為數(shù)據(jù)進行有效的管理、建立企業(yè)過程模型庫，并支持對過程模型的存儲、瀏覽、相似性度量、檢索等操作。

3基于Hadoop分布式業(yè)務過程模型庫管理方法

為了提高模型檢索的效率，結(jié)合Hadoop框架特點，將模型檢索分為過濾、驗證兩個階段。在Map階段使用過濾，得到能滿足用戶需要模型候選集，在Reduce階段僅針對少量候選集進行驗證。本文設計了基于Hadoop業(yè)務過程模型管理平臺，實現(xiàn)模型庫分布式管理，解決傳統(tǒng)單機環(huán)境下模型管理效率低的問題。結(jié)合業(yè)務過程模型特點對Hadoop文件存儲系統(tǒng)進行改進。

3.1模型庫管理平臺模型

本文提出了基于Hadoop業(yè)務過程庫管理平臺，設計了過程庫管理平臺模型。此模型根據(jù)業(yè)務過程模型小文件的特性對Hadoop進行相應改進。利用Hadoop分布式處理能力，采用Map/Reduce編程框架，Master/Slave原型，對模型庫進行分布式管理，其業(yè)務過程庫管理模型如下圖：

圖1所示為Hadoop業(yè)務過程庫管理平臺模型。如圖所示，NameNode為主節(jié)點Master，管理數(shù)據(jù)塊映射，處理客戶端發(fā)送的讀寫請求，配置副本策略，管理HDFS的名稱空間。SecondaryNameNode處理NameNode的部分工作量，例如某些比較消耗內(nèi)存的工作，是NameNode的冷備份，即NameNode失效后不會立即啟動，僅恢復部分數(shù)據(jù)，減低失效帶來的損失；合并Fsimage和edits然后再報送到NameNode。Fsimage為元數(shù)據(jù)鏡像文件（文件系統(tǒng)的目錄樹）。Edits為元數(shù)據(jù)的操作日志，針對文件系統(tǒng)做的修改操作記錄。DataNode為Slave從節(jié)點，負責將client發(fā)來的數(shù)據(jù)塊block存儲到具體相應位置，執(zhí)行數(shù)據(jù)塊的讀、寫操作。其中，JobTracker主要職責是負責監(jiān)控資源和調(diào)度作業(yè)。JobTracker會將任務執(zhí)行進度和資源使用情況反饋給調(diào)度器，調(diào)度器再根據(jù)反饋信息，進行資源再次分配，從而實現(xiàn)資源的動態(tài)調(diào)度。JobTracker將任務（Task）一一分發(fā)到各個相應TaskTracker上面執(zhí)行的過程稱之為Hadoop作業(yè)調(diào)度。TaskTracker周期性通過Heartbeat向JobTracker匯報資源使用情況以及任務進度。

模型在存儲之后且被檢索之前，在線下對模型集進行基于路徑的索引構(gòu)造。Map再很據(jù)路徑索引進行過濾，過濾后得到的模型交給Reduce，在Reduce階段進行精確檢索，在模型庫中檢索出包含樣例為子圖的模型。

3.2過程庫存儲機制

基于Petri網(wǎng)描述業(yè)務過程模型的時候，可以將Petri網(wǎng)視為特殊的有向圖，其庫所和變遷是圖節(jié)點，弧是圖的邊。文獻[16]詳細描述了Petri網(wǎng)在業(yè)務過程建模領(lǐng)域的應用和分析。

業(yè)務過程模型采用圖方式存儲，而模型圖檢索處理海量的數(shù)據(jù)時，傳統(tǒng)的單節(jié)點存儲難以滿足快速存儲的要求。本系統(tǒng)采用Hadoop文件存儲框架，采用Master/Slave結(jié)構(gòu)，其中NameNode為Master負責維護集群元數(shù)據(jù)，DataNode為Slave負責存儲數(shù)據(jù)。利用Hadoop分布式文件系統(tǒng)HDFS進行數(shù)據(jù)管理，結(jié)合業(yè)務過程模型小文件的特點將Hadoop文件存儲做相應改進。

如圖2所示HDFS客戶端將模型文件按64M分塊，再向NameNode發(fā)送寫請求。NameNode節(jié)點負責記錄塊（block）信息，并將可用的DataNode節(jié)點信息返回給client，Client向DataNode發(fā)送64k Package，將Package寫入塊中，DataNode向NameNode和Client發(fā)送本次Package“寫完”報文，Client再向NameNode發(fā)送“寫完”報文。Client又開始寫新的Package和block，如此循環(huán)，當Client把所有模型寫完，Client向NameNode發(fā)送“寫完”報文，模型存儲操作就完成了。

在GFS/Hadoop中，把所有的，模型與塊之間的關(guān)系放在內(nèi)存中，這樣不利于對海量小文件進行存儲。單個業(yè)務過程模型都是小文件（小于1M），模型通常是一次寫、多次讀，除某些特定情況外不會對模型進行頻繁的修改。針對海量模型，需要對HDFS進行修改設計模式來更加高效的支持。針對上述問題，將HDFS進行以下修改：

允許一個塊存放多個模型，一個塊對應多個模型；使用分布式內(nèi)存Cache系統(tǒng)來緩存業(yè)務過程模型和塊的對應關(guān)系。

設計模型存儲格式，對模型與塊的關(guān)系進行修改，增加塊內(nèi)偏移，即一個模型和塊的對應關(guān)系為：模型名<-->{塊ID+塊內(nèi)偏移}+{中間ID}+{塊ID+塊內(nèi)偏移+場內(nèi)長度}；其中{中間塊ID}代表0到N個塊間的ID；塊內(nèi)長度以頁為單位的（默認一頁16K），每一頁有一定長度的頁頭用來描述該頁信息，假設為20字節(jié)。模型和塊的對應關(guān)系如圖3所示：

Master設計模型

由于模型和塊的關(guān)系數(shù)量巨大，已經(jīng)不能全部放在內(nèi)存中了。因此，簡單的存儲已經(jīng)不能滿足需要，需要使用多臺數(shù)據(jù)存服務器來存儲模型和塊的關(guān)系。

Master負責映射關(guān)系數(shù)據(jù)和邏輯分配管理系統(tǒng)。整個Master系統(tǒng)具體負責有分配新的文件分配塊，文件副本的增加和減少，以及存儲文件和塊的映射函數(shù)。當系統(tǒng)應用程序希望讀取某個文件數(shù)據(jù)時，Master返回該文件及Meta信息和塊相關(guān)信息。

3.3Hadoop平臺過程庫檢索機制

定義1 （Petri網(wǎng)）： Petri網(wǎng)是一個三元組N=（P； T； F），其中P和T表示庫所和變遷的集合并且滿足P∩T=Φ，F(xiàn)（P×T）∪（T×P）是弧的集合，表示流關(guān)系。

定義2 （基于路徑定義索引）：一個R模型庫基于路徑索引InR，路徑長度為n，例如（Φi；Φi.list），其中Φi是長度為n的變遷路徑，Φi.list是所有包含Φi的模型集合。

為了使路徑索引的效率更高，不直接存儲（Φi，Φi.list），而是將（Φi，Φi.list.pointer）存儲到二叉樹中，使用倒排表存儲（Φi.list.pointer，Φi.list），其中Φi用作二叉樹鍵值，Φi.list.pointer指向倒排表中Φi.list的位置。為了提高I/O性能，這些列表被存儲在固定長度的存儲塊中。當一個列表需要多個塊時，第一個塊包含了一個指針信息指向第二個塊，需要更多塊時，依此類推。Φi.list.pointer實際上指向列表第一個存儲塊的位置。上述存儲結(jié)構(gòu)如圖4所示。在目前大多采用的方法中，B+樹的根節(jié)點被存儲在內(nèi)存中，而其它結(jié)點以及相應的倒排表都存儲在文件中，為了提高性能，目前針對B+樹的結(jié)點和倒排表使用了緩存機制。

Map函數(shù)模型檢索如算法1所示：第1行，Map函數(shù)接口將大文件數(shù)據(jù)分割成若干個數(shù)據(jù)塊；第2到5行所有路徑被順序處理；第3行，將過濾到的模型位置存放在list中；第4行，將目標模型存放在context當中；第5行，返回context作為Map函數(shù)的輸出。Reduce函數(shù)模型檢索如算法2所示：第1行，Map函數(shù)輸出作為本階段輸入；第2到第5行行順序執(zhí)行；第3行，將檢索到的模型位置存放在R中第5行，包含path路徑的模型作為輸出。

Algorithm 1： Map

Function Map

輸入：查詢樣例模型

輸出：單個節(jié)點上的樣例模型

1 Data_Block ← All Data；

2 for Data_Block do

3 list ← PathIndexQuery （path）；

4 add list to context；

5 return context；

Algorithm 2： Reduce

Function Reduce

輸入：context

輸出：目標模型R

1 get context；

2 for context do

3 list ←LengthOnePathIndex（Data_Block）；

4 add list to R；

5 return R；

模型被檢索之后對模型的讀取，應用程序調(diào)用HDFS 的Client API庫，讀模型的數(shù)據(jù)；Client API收到請求后，發(fā)出獲取文件Meta和塊信息請求給查詢Master；查詢Master向后臺數(shù)據(jù)管理系統(tǒng)查詢該模型相關(guān)的信息，查詢后返回給Client API；Client API得到Meta信息塊的信息后，向?qū)膲K服務器發(fā)出讀相關(guān)的塊數(shù)據(jù)指令；塊服務器根據(jù)指令讀取相應的塊數(shù)據(jù)返回給Client API；Client API 返回請求給應用程序，如圖5所示：

4實驗評估

為了驗證本文提出模型管理方法的有效性，在Hadoop平臺中實現(xiàn)了模型分布式檢索，并在模型集中驗證了方法的有效性和性能。平臺實驗環(huán)境為：Vmware 7，VMware ESX 4.1，Intel（R） Xeon（R） CPU E5620， CentOS 6.4，內(nèi)存4.0 GB；Hadoop-1.2.1，Eclipse，JDK1.7。

基于Hadoop業(yè)務過程管理平臺具體實現(xiàn)步驟：第一步，將BeeHiveZ源碼中模型檢索模塊中的某一個檢索算法[13]提取出來；第二步，在服務器安裝三臺linux虛擬機，搭建完全分布式Hadoop平臺，對Hadoop存儲進行調(diào)整以更好支持小文件存儲；第三步，利用BeeHiveZ自動生成業(yè)務過程模型，在Hadoop分布式文件系統(tǒng)HDFS進行存儲，存儲索引，為簡化索引生成將單機生成索引拷貝到HDFS中；第四步，將過濾、檢索與Map/Reduce編程模式相對應，Map階段，采用索引過濾，Reduce階段將第一步得到的算法進行檢索；第五步，運行調(diào)試Hadoop代碼進行檢索，記錄實驗時間，得出實驗結(jié)果。

方法有效性驗證：將產(chǎn)生的查詢實例模型F添加到模型庫中，產(chǎn)生一個查詢樣例模型集合F添加到模型庫中，之后將產(chǎn)生包含更多模型集合S添加到總模型庫中，針對每一個查詢實例模型f ∈F，在模型庫F∪S中進行檢索，驗證集合中是否包含實例模型f。通過實驗驗證，在單機平臺和Hadoop都能檢索出相應的模型。

圖6（a）顯示了無索引情況下即不采用模型檢索算法不同平臺檢索需要的時間，目標模型會與模型庫中模型一一比較，從而檢索出目標模型，可以看出Hadoop平臺檢索時間明顯少于單機平臺檢索時間；圖6（b）顯示了在采用索引情況下使用LengthOnePath檢索算法[16]不同平臺檢索需要時間，可以看出Hadoop平臺檢索仍然優(yōu)于單機平臺檢索。從圖6（a）（b）兩圖紅色三角形可以看出，Hadoop平臺能夠在采用檢索算法情況下有效提

升檢索效率，保證檢索的高效性。

圖6（c）單機下索引生成時間，為簡化索引生成將單機生成索引存儲到Hadoop平臺，索引在模型檢索之前，存儲之后在單機環(huán)境下增量更新，而模型每次增量更新時間很短。圖6（d）顯示了兩平臺存儲空間大小比較，HDFS為保證Hadoop平臺魯棒性采用備份機制，同等存儲內(nèi)容條件下，其存儲空間為單機條件下3倍。采用Hadoop平臺管理業(yè)務過程模型確實可以提高效率但也會帶來帶寬、存儲空間等資源消耗，其硬件要求也高于單機環(huán)境。

如圖6所示單機平臺與Hadoop平臺檢索性能綜合比較比較，在不同平臺中將業(yè)務過程模型庫增量更新，比較兩種平臺的效率。從實驗結(jié)果可以得出，在同等條件下，無論采用索引與否Hadoop平臺檢索效率明顯高于單機環(huán)境。

5結(jié)束語

針對單機環(huán)境下傳統(tǒng)關(guān)系型數(shù)據(jù)庫對大量業(yè)務過程模型檢索、存儲效率不高的問題，本文提出并實現(xiàn)了分布式環(huán)境下基于Hadoop的業(yè)務過程模型管理方法。本文采用Hadoop中Map/Reduce和HDFS作為過程庫的檢索和存儲框架，對Hadoop存儲進行了改進；設計了業(yè)務過程模型索引結(jié)構(gòu)，采用過濾、驗證模式快速檢索模型，本文實驗模型由BeehiveZ中模型生成器自動生成。Hadoop平臺整體資源開銷大于單機環(huán)境，存儲空間以及流量帶寬會是單機環(huán)境的3倍。通過這些開銷能夠換得理想的模型管理效率。結(jié)果表明：基于Hadoop的業(yè)務過程模型管理方法可以有效實現(xiàn)業(yè)務過程模型分布式管理，并且其管理效率比單機環(huán)境下要好。在已有成果基礎上，本課題組將圍繞分布式業(yè)務過程模型庫檢索算法的研究展開工作。

參考文獻

[1]Ke Yiping， Cheng James， Yu Jeffrey Xu. Querying Large Graph Databases[J]. Proceedings of DASFAA （2）， 2010. 487-488.

[2]Shasha Dennis， Wang Jason TL， Giugno Rosalba. Algorithmics andApplications of Tree andGraph Searching[C]// Proceeding of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. New York， N. Y. USA： ACM， 2002： 39-52.

[3]Cheng James， Ke Yiping， Ng Wilfred. Effcient Query Processing on Graph Databases[J].ACM Trans. Database Syst， 2009， 34（1）： 2.

[4]AWAD A，POLYVYANYY A，WESKE M. Semantic Querying of Business Process Models[J]. Proceedings of EDOC， 2008. 85-94.

[5]SARKR S，AWAD A. A Framework for Querying Graph-Based Business Process Models[J]. Proceedings of WWW， 2010. 1297-1300.

[6]AWAD A，SAKR S. Querying Graph-Based Repositories of Business Process Models[J]. Proceedings of DASFAA Workshops， 2010. 33-44.

[7]Dumas Marlon， GarciaBanuelos Luciano， Dijkman Remco. Similarity Search of Business Process Models[J].IEEE Data Eng. Bull.， 2009， 32（3）：23-28.

[8]Dijkman Remco， Dumas Marlon， Dongen Boudewijn， et al. Similarity of Business Process Models： Metrics and Evaluation[J]. Inf. Syst.， 2011， 36（2）：498-516.

[9]張良將. 基于Hadoop云平臺的海量數(shù)字圖像數(shù)據(jù)挖掘的研究[D] .上海：上海交通大學，2013.

[10]王東京， 鄧水光， 曹斌，等. JTangWFR一個高效可靠的流程推薦系統(tǒng)[J].計算機集成制造系統(tǒng)， 2013， 19（8）：1883-1990.

[11]曹斌， 尹建偉， 鄧水光，等. 一種基于近距離最大子圖優(yōu)先的業(yè)務流程推薦技術(shù)[J].計算機學報， 2013， 36（2）： 263-274.

[12]曹斌， 尹建偉， 陳慧蕊. 基于Levenshtein距離的流程檢索方法[J].計算機集成制造系統(tǒng)，2012， 18（8）：1766-1773.

[13]唐真. 基于Hadoop的推薦系統(tǒng)設計與實現(xiàn)[D].成都：電子科技大學，2013.

[14]葉偉. 互聯(lián)網(wǎng)時代的軟件革命--SaaS架構(gòu)設計[M].北京：電子工業(yè)出版社， 2009.

[15]VAN DER AALIST W M P. The application of Petri nets to workflow management [J].Journal of Circuits， Systems， and Computers， 1998， 8（1）： 21-66.

[16]金濤. 業(yè)務過程模型檢索與重構(gòu)[D]. 北京：清華大學，2012.