海量流程实例的存储、索引与检索研究

1、海量流程实例的存储、索引与检索研究郭芬，闻立杰，王建民1目录2目录3研究背景4信息系统、互联网、传感器等信息系统、互联网、传感器等是大数据的主要来源是大数据的主要来源- 事件日志事件日志大数据大数据挑战挑战机遇机遇发现、检测和改善发现、检测和改善业务过程业务过程- 过程挖掘过程挖掘提取有效信息提取有效信息快速的日志转换快速的日志转换有效的事件日志管理有效的事件日志管理- 事件日志的采集、索事件日志的采集、索引和检索引和检索大数据环境下的机遇和挑战大数据环境下的机遇和挑战目录5通用的流程实例管理框架6数据库日志纯文本日志EXCEL日志日志转换流程实例库索引管理器索引创建/使用检索器流程实例结果集

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、和索引流程实例的特点流程实例的特点 流程实例数量庞大 某小用户量的搜索引擎每天2G的点击日志 三一重工的装备每天产生约2亿条工况数据 案例ID，活动任务，时间戳必须存在 属性可以不存在，不同流程实例所拥有的属性可以相差很大9海量流程实例的存储和索引流程实例存储结构流程实例存储结构caseidRowKey:taskid_caseidstartingtimeendingtimeactivitysequencecasecontent通过taskid_caseid唯一确定一个流程实例taskid确定同一批事件日志中不同流程实例区分不同事件日志转换任务(建立二级索引)流程实例开始时间流程实例结束时间流程

4、实例活动序列（如A-B-C-D）流程实例的JSON表述10海量流程实例的存储和索引列名列名内容内容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统一的索引接口统一的索引接口索引接口索引接口说明说明等于检索等于检索类似于关系数据库查询中的类似于关系数据库查询中的“=”“=”操作符操作符区间检索区间检索类似于关系型数据库中的类似于关系型数据库中的“b“betweenetween”操作符操作符包含检索包含检索类似于关系型数据库中的类似于关系型数据库中的“in”“in”操作符操作符相似检索相似检索类似于类似于“like”“like”操作符操作符是否等于某个检索条件是否等于某个检索条件判断判断流程流程实例的某个属性是否满足希望的某个检索条件实例的某个属性是

9、否满足希望的某个检索条件是否属于某个区间是否属于某个区间判断流程实例的某个属性是否介于某个区间，与区间检判断流程实例的某个属性是否介于某个区间，与区间检索是相对应的索是相对应的是否包含于某个列表是否包含于某个列表判断流程实例的某个属性是否在某个列表中，与包含检判断流程实例的某个属性是否在某个列表中，与包含检索是相对应的索是相对应的是否相似于某个字符串是否相似于某个字符串判断判断流程流程实例的某个属性是否类似于某个字符串实例的某个属性是否类似于某个字符串，与相与相似检索是相对应的似检索是相对应的添加流程实例添加流程实例为流程实例添加索引数据为流程实例添加索引数据删除流程实例删除流程实例删除流程实

10、例索引数据删除流程实例索引数据索引是否启用索引是否启用判断索引是否已被启用判断索引是否已被启用13海量流程实例的存储和索引14索引管理器输入taskid索引1索引3索引2索引4索引n启用的索引Cassandra数据库索引构建索引构建存储中间件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数据库流程实例索引项索引存储中间件15海量流程实例的存储和索引测试集测试集1 12 23 34 45 56 67 78 89 91010流程实例流程实例( (万万) )1841843683684834835895897867861046104612111211138413841627162720572057写数据库（万）写数据库（万）38.238.266.666.6114.3114.3150.150.8 8184.6184.666466470370386286297297212391239读数据库（万）读数据库（万）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使用内存（使用内存（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%索引构建效率索引构建效率16海量流程实例的存储和索引测试集测试集1 12 23 34 45 56 67 78 89 91010流程实例流程实例( (万万) )1841843683684834835895897867861046104612111211138413841627162720572057写数据库（万）写数据库（万）38.238.266.666.6114.3114.3150.150.8 8184.6184.6664664703703

15、86286297297212391239读数据库（万）读数据库（万）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使用内存（使用内存（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%索引构建效率索引构建效率CPU占用率低，索引项的生成并不是索引构建的瓶颈17海量流程实例的存储和索引测试集测试集1 12 23 34 45 56 67 78 89 91010流程实例流程实例( (万万) )1841843683684834835895897867861046104612111211138413841627162720572057

18、写数据库（万）写数据库（万）38.238.266.666.6114.3114.3150.150.8 8184.6184.666466470370386286297297212391239读数据库（万）读数据库（万）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使用内存（使用内存（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%索引构建效率索引构建效率数据库读写数量太多，数据库服务器性能及对应网络速度才是索引构建性能瓶颈18海量流程实例的存储和索引索引构建效率索引构建效率索引构建耗时随着过程实例数目的增加而增加，总体上呈现一

21、种正相关的关系19目录20过程实例的检索框架过程实例的检索框架21检索类型检索类型参数个数参数个数参数类型参数类型等于检索等于检索1String区间检索区间检索2String包含检索包含检索1ArrayList相似检索相似检索1String统一的输入接口统一的输入接口2223检索优化器检索优化器输入输入默认检索方案估计每个检索条件对应结果集大小调整默认检索顺序调整检索种类优化过程优化过程输出输出较优检索方案活动序列长度4和6之间活动包含page或document活动序列长度包含4、5、6活动等于page活动序列长度包含4、5、6(700)活动等于page(30)活动等于page(30)活动序列

22、长度包含4、5、6(700)23检索执行引擎检索执行引擎较优检索方案执行检索合并结果集确定最终结果集分页返回结果集依次执行各个检索条件并合并结果集直至当前结果集足够小（如|A|page”54.1万条属性等于属性等于“browser: Nokia5000/1.0 (06.32) Profile/MIDP-2.1 Configuration/CLDC-1.1”149条最终结果集最终结果集72条所用内存所用内存843MB读数据库读数据库3次（耗时0.001s）比较次数比较次数0次耗时耗时10秒直接读取数据库判断直接读取数据库判断12分钟比直接读取数据库判断效率更高比直接读取数据库判断效率更高25检索条件和性能指标检索条件和性能指标数据数据活动序列为活动序列为31.7万条包含活动包含活动“image”2.3万条类似属性类似属性“srcip:10.10.%”1544万条最终结果集最终结果集1700条所用内存所用内存965MB读数据库读数据库83次（耗时0.01s）比较次数比较次数1550万次耗时耗时1分钟直接读取数据库判断直接读取数据库判断35分钟过程实例检索效率过程实例检索效率26检索条件和性能指标检索条件和性能指标数据数据活动序列等于活动序列等于“page-page”54.1万条属性等于属性等于“b