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

1、海量流程實例的存儲、索引與檢索研究郭芬，聞立杰，王建民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)機遇機遇發(fā)現(xiàn)、檢測和改善發(fā)現(xiàn)、檢測和改善業(yè)務過程業(yè)務過程- 過程挖掘過程挖掘提取有效信息提取有效信息快速的日志轉(zhuǎn)換快速的日志轉(zhuǎn)換有效的事件日志管理有效的事件日志管理- 事件日志的采集、索事件日志的采集、索引和檢索引和檢索大數(shù)據(jù)環(huán)境下的機遇和挑戰(zhàn)大數(shù)據(jù)環(huán)境下的機遇和挑戰(zhàn)目錄5通用的流程實例管理框架6數(shù)據(jù)庫日志純文本日志EXCEL日志日志轉(zhuǎn)換流程實例庫索引管理器索引創(chuàng)建/使用檢索器流程實例結(jié)果集

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

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

4、實例活動序列（如A-B-C-D）流程實例的JSON表述10海量流程實例的存儲和索引列名列名內(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流程實例的存儲流程實例的

6、存儲11海量流程實例的存儲和索引流程實例的索引流程實例的索引案例案例IDID流程實例流程實例case1case1news-page-page-weathernews-page-page-weathercase2case2news-video-imagenews-video-imagecase3case3page-news-musicpage-news-musiccase4case4page-weather-musicpage-weather-music活動活動流程實例流程實例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海量流程實例的存儲和索引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”操作符操作符是否等于某個檢索條件是否等于某個檢索條件判斷判斷流程流程實例的某個屬性是否滿足希望的某個檢索條件實例的某個屬性是

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

10、例索引數(shù)據(jù)刪除流程實例索引數(shù)據(jù)索引是否啟用索引是否啟用判斷索引是否已被啟用判斷索引是否已被啟用13海量流程實例的存儲和索引14索引管理器輸入taskid索引1索引3索引2索引4索引n啟用的索引Cassandra數(shù)據(jù)庫索引構(gòu)建索引構(gòu)建存儲中間件14海量流程實例的存儲和索引默認的索引存儲方式默認的索引存儲方式流程實例活動索引活動長度索引活動序列索引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ù)庫流程實例索引項索引存儲中間件15海量流程實例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實例流程實例( (萬萬) )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耗時（分鐘）耗時（分鐘）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海量流程實例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實例流程實例( (萬萬) )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耗時（分鐘）耗時（分鐘）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占用率低，索引項的生成并不是索引構(gòu)建的瓶頸17海量流程實例的存儲和索引測試集測試集1 12 23 34 45 56 67 78 89 91010流程實例流程實例( (萬萬) )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耗時（分鐘）耗時（分鐘）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ǎng)絡速度才是索引構(gòu)建性能瓶頸18海量流程實例的存儲和索引索引構(gòu)建效率索引構(gòu)建效率索引構(gòu)建耗時隨著過程實例數(shù)目的增加而增加，總體上呈現(xiàn)一

21、種正相關(guān)的關(guān)系19目錄20過程實例的檢索框架過程實例的檢索框架21檢索類型檢索類型參數(shù)個數(shù)參數(shù)個數(shù)參數(shù)類型參數(shù)類型等于檢索等于檢索1String區(qū)間檢索區(qū)間檢索2String包含檢索包含檢索1ArrayList相似檢索相似檢索1String統(tǒng)一的輸入接口統(tǒng)一的輸入接口2223檢索優(yōu)化器檢索優(yōu)化器輸入輸入默認檢索方案估計每個檢索條件對應結(jié)果集大小調(diào)整默認檢索順序調(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í)行各個檢索條件并合并結(jié)果集直至當前結(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次（耗時0.001s）比較次數(shù)比較次數(shù)0次耗時耗時10秒直接讀取數(shù)據(jù)庫判斷直接讀取數(shù)據(jù)庫判斷12分鐘比直接讀取數(shù)據(jù)庫判斷效率更高比直接讀取數(shù)據(jù)庫判斷效率更高25檢索條件和性能指標檢索條件和性能指標數(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次（耗時0.01s）比較次數(shù)比較次數(shù)1550萬次耗時耗時1分鐘直接讀取數(shù)據(jù)庫判斷直接讀取數(shù)據(jù)庫判斷35分鐘過程實例檢索效率過程實例檢索效率26檢索條件和性能指標檢索條件和性能指標數(shù)據(jù)數(shù)據(jù)活動序列等于活動序列等于“page-page”54.1萬條屬性等于屬性等于“b