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

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

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

關鍵詞：業務過程模型管理；Hadoop；檢索；存儲；效率

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

1引言

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

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

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

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

計算技術與自動化2015年12月

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

2相關研究

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

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

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

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

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

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

3.1模型庫管理平臺模型

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

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

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

3.2過程庫存儲機制

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

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

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

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

允許一個塊存放多個模型，一個塊對應多個模型；使用分布式內存Cache系統來緩存業務過程模型和塊的對應關系。

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

Master設計模型

由于模型和塊的關系數量巨大，已經不能全部放在內存中了。因此，簡單的存儲已經不能滿足需要，需要使用多臺數據存服務器來存儲模型和塊的關系。

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

3.3Hadoop平臺過程庫檢索機制

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

定義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實際上指向列表第一個存儲塊的位置。上述存儲結構如圖4所示。在目前大多采用的方法中，B+樹的根節點被存儲在內存中，而其它結點以及相應的倒排表都存儲在文件中，為了提高性能，目前針對B+樹的結點和倒排表使用了緩存機制。

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

Algorithm 1： Map

Function Map

輸入：查詢樣例模型

輸出：單個節點上的樣例模型

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；

模型被檢索之后對模型的讀取，應用程序調用HDFS 的Client API庫，讀模型的數據；Client API收到請求后，發出獲取文件Meta和塊信息請求給查詢Master；查詢Master向后臺數據管理系統查詢該模型相關的信息，查詢后返回給Client API；Client API得到Meta信息塊的信息后，向對應的塊服務器發出讀相關的塊數據指令；塊服務器根據指令讀取相應的塊數據返回給Client API；Client API 返回請求給應用程序，如圖5所示：

4實驗評估

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

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

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

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

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

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

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

5結束語

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

參考文獻

[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云平臺的海量數字圖像數據挖掘的研究[D] .上海：上海交通大學，2013.

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

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

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

[13]唐真. 基于Hadoop的推薦系統設計與實現[D].成都：電子科技大學，2013.

[14]葉偉. 互聯網時代的軟件革命--SaaS架構設計[M].北京：電子工業出版社， 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]金濤. 業務過程模型檢索與重構[D]. 北京：清華大學，2012.