海量流程實(shí)例的存儲、索引與檢索研究

1、海量流程實(shí)例的存儲、索引與檢索研究郭芬，聞立杰，王建民1目錄2目錄3研究背景4信息系統(tǒng)、互聯(lián)網(wǎng)、傳感器等信息系統(tǒng)、互聯(lián)網(wǎng)、傳感器等是大數(shù)據(jù)的主要來源是大數(shù)據(jù)的主要來源- 事件日志事件日志大數(shù)據(jù)大數(shù)據(jù)挑戰(zhàn)挑戰(zhàn)機(jī)遇機(jī)遇發(fā)現(xiàn)、檢測和改善發(fā)現(xiàn)、檢測和改善業(yè)務(wù)過程業(yè)務(wù)過程- 過程挖掘過程挖掘提取有效信息提取有效信息快速的日志轉(zhuǎn)換快速的日志轉(zhuǎn)換有效的事件日志管理有效的事件日志管理- 事件日志的采集、索事件日志的采集、索引和檢索引和檢索大數(shù)據(jù)環(huán)境下的機(jī)遇和挑戰(zhàn)大數(shù)據(jù)環(huán)境下的機(jī)遇和挑戰(zhàn)目錄5通用的流程實(shí)例管理框架6數(shù)據(jù)庫日志純文本日志EXCEL日志日志轉(zhuǎn)換流程實(shí)例庫索引管理器索引創(chuàng)建/使用檢索器流程實(shí)例結(jié)果集

2、XES事件日志本文研究范圍目錄7海量流程實(shí)例的存儲和索引流程實(shí)例流程實(shí)例caseidcaseidchannelchannel時(shí)間時(shí)間useriduseridbrowserbrowsercase1news2013/3/23 14:20 fenyochromecase1video2013/3/23 14:21fenyochromecase1page2013/3/23 14:21fenyochromecase1page2013/3/23 14:23fenyochromecase1weather2013/3/23 14:25 fenyochrome案例ID活動任務(wù)時(shí)間戳屬性1屬性n8海量流程實(shí)例的存儲

3、和索引流程實(shí)例的特點(diǎn)流程實(shí)例的特點(diǎn) 流程實(shí)例數(shù)量龐大 某小用戶量的搜索引擎每天2G的點(diǎn)擊日志 三一重工的裝備每天產(chǎn)生約2億條工況數(shù)據(jù) 案例ID，活動任務(wù)，時(shí)間戳必須存在 屬性可以不存在，不同流程實(shí)例所擁有的屬性可以相差很大9海量流程實(shí)例的存儲和索引流程實(shí)例存儲結(jié)構(gòu)流程實(shí)例存儲結(jié)構(gòu)caseidRowKey:taskid_caseidstartingtimeendingtimeactivitysequencecasecontent通過taskid_caseid唯一確定一個(gè)流程實(shí)例taskid確定同一批事件日志中不同流程實(shí)例區(qū)分不同事件日志轉(zhuǎn)換任務(wù)(建立二級索引)流程實(shí)例開始時(shí)間流程實(shí)例結(jié)束時(shí)間流程

4、實(shí)例活動序列（如A-B-C-D）流程實(shí)例的JSON表述10海量流程實(shí)例的存儲和索引列名列名內(nèi)容內(nèi)容caseidcase1 startingtime2013/3/23 14:20 endingtime2013/3/23 14:25taskide1activitysequencenews-video-page-page-weather casecontentcaseid:case1,taskid:e1,activityarray:time:2013/3/23 14:20,activity:news,attributes:browser:chrome,userid:fenyo,time:2013/3

5、/23 14:21,activity:video,attributes:browser:chrome,userid:fenyo,time:2013/3/23 14:23,activity:page,attributes:browser:chrome,userid:fenyo,time:2013/3/23 14:23,activity:page,attributes:browser:chrome,userid:fenyo,time:2013/3/23 14:25,activity:weather,attributes:browser:chrome,userid:fenyo流程實(shí)例的存儲流程實(shí)例的

6、存儲11海量流程實(shí)例的存儲和索引流程實(shí)例的索引流程實(shí)例的索引案例案例IDID流程實(shí)例流程實(shí)例case1case1news-page-page-weathernews-page-page-weathercase2case2news-video-imagenews-video-imagecase3case3page-news-musicpage-news-musiccase4case4page-weather-musicpage-weather-music活動活動流程實(shí)例流程實(shí)例pagepagee1_case1,e1_case2,e1_case3,ee1_case1,e1_case2,e1_cas

7、e3,e1_case41_case4newse1_case1,e1_case2,e1_case3e1_case1,e1_case2,e1_case3videovideoe1_case2e1_case2weatherweathere1_case1,e1_case4e1_case1,e1_case4imageimagee1_case2e1_case2musicmusice1_case3,e1_case4e1_case3,e1_case4活動索引Rowkey:pagee1_case1 e1_case2e1_case4e1_case3Rowkey:newse1_case1e1_case2e1_case

8、3Rowkey:musice1_case3e1_case412海量流程實(shí)例的存儲和索引13統(tǒng)一的索引接口統(tǒng)一的索引接口索引接口索引接口說明說明等于檢索等于檢索類似于關(guān)系數(shù)據(jù)庫查詢中的類似于關(guān)系數(shù)據(jù)庫查詢中的“=”“=”操作符操作符區(qū)間檢索區(qū)間檢索類似于關(guān)系型數(shù)據(jù)庫中的類似于關(guān)系型數(shù)據(jù)庫中的“b“betweenetween”操作符操作符包含檢索包含檢索類似于關(guān)系型數(shù)據(jù)庫中的類似于關(guān)系型數(shù)據(jù)庫中的“in”“in”操作符操作符相似檢索相似檢索類似于類似于“l(fā)ike”“l(fā)ike”操作符操作符是否等于某個(gè)檢索條件是否等于某個(gè)檢索條件判斷判斷流程流程實(shí)例的某個(gè)屬性是否滿足希望的某個(gè)檢索條件實(shí)例的某個(gè)屬性是

9、否滿足希望的某個(gè)檢索條件是否屬于某個(gè)區(qū)間是否屬于某個(gè)區(qū)間判斷流程實(shí)例的某個(gè)屬性是否介于某個(gè)區(qū)間，與區(qū)間檢判斷流程實(shí)例的某個(gè)屬性是否介于某個(gè)區(qū)間，與區(qū)間檢索是相對應(yīng)的索是相對應(yīng)的是否包含于某個(gè)列表是否包含于某個(gè)列表判斷流程實(shí)例的某個(gè)屬性是否在某個(gè)列表中，與包含檢判斷流程實(shí)例的某個(gè)屬性是否在某個(gè)列表中，與包含檢索是相對應(yīng)的索是相對應(yīng)的是否相似于某個(gè)字符串是否相似于某個(gè)字符串判斷判斷流程流程實(shí)例的某個(gè)屬性是否類似于某個(gè)字符串實(shí)例的某個(gè)屬性是否類似于某個(gè)字符串，與相與相似檢索是相對應(yīng)的似檢索是相對應(yīng)的添加流程實(shí)例添加流程實(shí)例為流程實(shí)例添加索引數(shù)據(jù)為流程實(shí)例添加索引數(shù)據(jù)刪除流程實(shí)例刪除流程實(shí)例刪除流程實(shí)

10、例索引數(shù)據(jù)刪除流程實(shí)例索引數(shù)據(jù)索引是否啟用索引是否啟用判斷索引是否已被啟用判斷索引是否已被啟用13海量流程實(shí)例的存儲和索引14索引管理器輸入taskid索引1索引3索引2索引4索引n啟用的索引Cassandra數(shù)據(jù)庫索引構(gòu)建索引構(gòu)建存儲中間件14海量流程實(shí)例的存儲和索引默認(rèn)的索引存儲方式默認(rèn)的索引存儲方式流程實(shí)例活動索引活動長度索引活動序列索引news:e1_case1video:e1_case1page:e1_case1weather:e1_case15:e1_case1news-video:e1_case1video-page:e1_case1page-page:e1_case1page-

11、weather:e1_caseCassandra數(shù)據(jù)庫流程實(shí)例索引項(xiàng)索引存儲中間件15海量流程實(shí)例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實(shí)例流程實(shí)例( (萬萬) )1841843683684834835895897867861046104612111211138413841627162720572057寫數(shù)據(jù)庫（萬）寫數(shù)據(jù)庫（萬）38.238.266.666.6114.3114.3150.150.8 8184.6184.666466470370386286297297212391239讀數(shù)據(jù)庫（萬）讀數(shù)據(jù)庫（萬）1.841.843.683.6

12、84.834.835.895.895.865.8610.4610.4612.1112.1113.8413.8416.2716.2720.5720.57活動索引（萬）活動索引（萬）3823826666661143114315081508184618462193219325362536298529853542354242924292活動序列索引（活動序列索引（萬）萬）27327375175189489410361036124712471134113412231223140214021873187325812581屬性索引（萬）屬性索引（萬）11461146199819983429342945124

13、5125538553865796579760876088955895510626106261287612876活動長度（萬）活動長度（萬）1841843683684834835895895865861046104612111211138413841627162720572057耗時(shí)（分鐘）耗時(shí)（分鐘）19.5424248.348.376.376.3159159201.7201.7343343484484587587使用內(nèi)存（使用內(nèi)存（G G）1.71.7CPUCP

14、U占用率占用率1 15%5%1.5%1.5%1.4%1.4%1.5%1.5%1.5%1.5%2%2%1.7%1.7%1.7%1.7%1.6%1.6%2%2%索引構(gòu)建效率索引構(gòu)建效率16海量流程實(shí)例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實(shí)例流程實(shí)例( (萬萬) )1841843683684834835895897867861046104612111211138413841627162720572057寫數(shù)據(jù)庫（萬）寫數(shù)據(jù)庫（萬）38.238.266.666.6114.3114.3150.150.8 8184.6184.6664664703703

15、86286297297212391239讀數(shù)據(jù)庫（萬）讀數(shù)據(jù)庫（萬）1.841.843.683.684.834.835.895.895.865.8610.4610.4612.1112.1113.8413.8416.2716.2720.5720.57活動索引（萬）活動索引（萬）3823826666661143114315081508184618462193219325362536298529853542354242924292活動序列索引（活動序列索引（萬）萬）27327375175189489410361036124712471134113412231223140214021873187325

16、812581屬性索引（萬）屬性索引（萬）114611461998199834293429451245125538553865796579760876088955895510626106261287612876活動長度（萬）活動長度（萬）1841843683684834835895895865861046104612111211138413841627162720572057耗時(shí)（分鐘）耗時(shí)（分鐘）19.5424248.348.376.376.3159159201.7201.7343343484484587587使用內(nèi)存（使用內(nèi)存（G G）1.61.71

17、.1.71.7CPUCPU占用率占用率1 15%5%1.5%1.5%1.4%1.4%1.5%1.5%1.5%1.5%2%2%1.7%1.7%1.7%1.7%1.6%1.6%2%2%索引構(gòu)建效率索引構(gòu)建效率CPU占用率低，索引項(xiàng)的生成并不是索引構(gòu)建的瓶頸17海量流程實(shí)例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實(shí)例流程實(shí)例( (萬萬) )1841843683684834835895897867861046104612111211138413841627162720572057

18、寫數(shù)據(jù)庫（萬）寫數(shù)據(jù)庫（萬）38.238.266.666.6114.3114.3150.150.8 8184.6184.666466470370386286297297212391239讀數(shù)據(jù)庫（萬）讀數(shù)據(jù)庫（萬）1.841.843.683.684.834.835.895.895.865.8610.4610.4612.1112.1113.8413.8416.2716.2720.5720.57活動索引（萬）活動索引（萬）3823826666661143114315081508184618462193219325362536298529853542354242924292活動序列索引（活動序列索引

19、（萬）萬）27327375175189489410361036124712471134113412231223140214021873187325812581屬性索引（萬）屬性索引（萬）114611461998199834293429451245125538553865796579760876088955895510626106261287612876活動長度（萬）活動長度（萬）1841843683684834835895895865861046104612111211138413841627162720572057耗時(shí)（分鐘）耗時(shí)（分鐘）19.5424248.348.

20、376.376.3159159201.7201.7343343484484587587使用內(nèi)存（使用內(nèi)存（G G）1.71.7CPUCPU占用率占用率1 15%5%1.5%1.5%1.4%1.4%1.5%1.5%1.5%1.5%2%2%1.7%1.7%1.7%1.7%1.6%1.6%2%2%索引構(gòu)建效率索引構(gòu)建效率數(shù)據(jù)庫讀寫數(shù)量太多，數(shù)據(jù)庫服務(wù)器性能及對應(yīng)網(wǎng)絡(luò)速度才是索引構(gòu)建性能瓶頸18海量流程實(shí)例的存儲和索引索引構(gòu)建效率索引構(gòu)建效率索引構(gòu)建耗時(shí)隨著過程實(shí)例數(shù)目的增加而增加，總體上呈現(xiàn)一

21、種正相關(guān)的關(guān)系19目錄20過程實(shí)例的檢索框架過程實(shí)例的檢索框架21檢索類型檢索類型參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)參數(shù)類型參數(shù)類型等于檢索等于檢索1String區(qū)間檢索區(qū)間檢索2String包含檢索包含檢索1ArrayList相似檢索相似檢索1String統(tǒng)一的輸入接口統(tǒng)一的輸入接口2223檢索優(yōu)化器檢索優(yōu)化器輸入輸入默認(rèn)檢索方案估計(jì)每個(gè)檢索條件對應(yīng)結(jié)果集大小調(diào)整默認(rèn)檢索順序調(diào)整檢索種類優(yōu)化過程優(yōu)化過程輸出輸出較優(yōu)檢索方案活動序列長度4和6之間活動包含page或document活動序列長度包含4、5、6活動等于page活動序列長度包含4、5、6(700)活動等于page(30)活動等于page(30)活動序列

22、長度包含4、5、6(700)23檢索執(zhí)行引擎檢索執(zhí)行引擎較優(yōu)檢索方案執(zhí)行檢索合并結(jié)果集確定最終結(jié)果集分頁返回結(jié)果集依次執(zhí)行各個(gè)檢索條件并合并結(jié)果集直至當(dāng)前結(jié)果集足夠小（如|A|page”54.1萬條屬性等于屬性等于“browser: Nokia5000/1.0 (06.32) Profile/MIDP-2.1 Configuration/CLDC-1.1”149條最終結(jié)果集最終結(jié)果集72條所用內(nèi)存所用內(nèi)存843MB讀數(shù)據(jù)庫讀數(shù)據(jù)庫3次（耗時(shí)0.001s）比較次數(shù)比較次數(shù)0次耗時(shí)耗時(shí)10秒直接讀取數(shù)據(jù)庫判斷直接讀取數(shù)據(jù)庫判斷12分鐘比直接讀取數(shù)據(jù)庫判斷效率更高比直接讀取數(shù)據(jù)庫判斷效率更高25檢索條件和性能指標(biāo)檢索條件和性能指標(biāo)數(shù)據(jù)數(shù)據(jù)活動序列為活動序列為31.7萬條包含活動包含活動“image”2.3萬條類似屬性類似屬性“srcip:10.10.%”1544萬條最終結(jié)果集最終結(jié)果集1700條所用內(nèi)存所用內(nèi)存965MB讀數(shù)據(jù)庫讀數(shù)據(jù)庫83次（耗時(shí)0.01s）比較次數(shù)比較次數(shù)1550萬次耗時(shí)耗時(shí)1分鐘直接讀取數(shù)據(jù)庫判斷直接讀取數(shù)據(jù)庫判斷35分鐘過程實(shí)例檢索效率過程實(shí)例檢索效率26檢索條件和性能指標(biāo)檢索條件和性能指標(biāo)數(shù)據(jù)數(shù)據(jù)活動序列等于活動序列等于“page-page”54.1萬條屬性等于屬性等于“b