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

海量流程实例的存储、索引与检索研究郭芬，闻立杰，王建民1目录研究背景通用的流程实例管理框架海量流程实例的存储和索引流程实例的检索工作总结2目录研究背景通用的流程实例管理框架海量流程实例的存储和索引流程实例的检索工作总结3研究背景4信息系统、互联网、传感器等是大数据的主要来源-事件日志大数据挑战机遇发现、检测和改善业务过程-过程挖掘•提取有效信息•快速的日志转换•有效的事件日志管理-事件日志的采集、索引和检索大数据环境下的机遇和挑战目录研究背景通用的流程实例管理框架海量流程实例的存储和索引流程实例的检索工作总结5通用的流程实例管理框架6数据库日志纯文本日志EXCEL日志日志转换流程实例库索引管理器索引创建/使用检索器流程实例结果集XES事件日志本文研究范围目录研究背景通用的流程实例管理框架海量流程实例的存储和索引流程实例的检索工作总结7海量流程实例的存储和索引流程实例caseidchannel时间userid∙∙∙browsercase1news2013/3/2314:20fenyo∙∙∙chromecase1video2013/3/2314:21fenyo∙∙∙chromecase1page2013/3/2314:21fenyo∙∙∙chromecase1page2013/3/2314:23fenyo∙∙∙∙chromecase1weather2013/3/2314:25fenyo∙∙∙chrome案例ID活动任务时间戳属性1属性n8海量流程实例的存储和索引流程实例的特点流程实例数量庞大某小用户量的搜索引擎每天2G的点击日志三一重工的装备每天产生约2亿条工况数据案例ID，活动任务，时间戳必须存在属性可以不存在，不同流程实例所拥有的属性可以相差很大9海量流程实例的存储和索引流程实例存储结构caseidRowKey:taskid_caseidstartingtimeendingtimeactivitysequencecasecontent通过taskid_caseid唯一确定一个流程实例taskid确定同一批事件日志中不同流程实例区分不同事件日志转换任务(建立二级索引)流程实例开始时间流程实例结束时间流程实例活动序列（如A-B-C-D）流程实例的JSON表述10海量流程实例的存储和索引列名内容caseidcase1startingtime2013/3/2314:20endingtime2013/3/2314:25taskide1activitysequencenews-video-page-page-weathercasecontent{caseid:case1,taskid:e1,activityarray:[{time:2013/3/2314:20,activity:news,attributes:[{browser:chrome,userid:fenyo}]},{time:2013/3/2314:21,activity:video,attributes:[{browser:chrome,userid:fenyo}]},{time:2013/3/2314:23,activity:page,attributes:[{browser:chrome,userid:fenyo}]},{time:2013/3/2314:23,activity:page,attributes:[{browser:chrome,userid:fenyo}]},{time:2013/3/2314:25,activity:weather,attributes:[{browser:chrome,userid:fenyo}]}]}流程实例的存储11海量流程实例的存储和索引流程实例的索引案例ID流程实例case1news-page-page-weathercase2news-video-imagecase3page-news-musiccase4page-weather-music活动流程实例pagee1_case1,e1_case2,e1_case3,e1_case4newse1_case1,e1_case2,e1_case3videoe1_case2weathere1_case1,e1_case4imagee1_case2musice1_case3,e1_case4活动索引Rowkey:pagee1_case1e1_case2e1_case4e1_case3Rowkey:newse1_case1e1_case2e1_case3Rowkey:musice1_case3e1_case4∙∙∙∙12海量流程实例的存储和索引13统一的索引接口索引接口说明等于检索类似于关系数据库查询中的“=”操作符区间检索类似于关系型数据库中的“between”操作符包含检索类似于关系型数据库中的“in”操作符相似检索类似于“like”操作符是否等于某个检索条件判断流程实例的某个属性是否满足希望的某个检索条件是否属于某个区间判断流程实例的某个属性是否介于某个区间，与区间检索是相对应的是否包含于某个列表判断流程实例的某个属性是否在某个列表中，与包含检索是相对应的是否相似于某个字符串判断流程实例的某个属性是否类似于某个字符串，与相似检索是相对应的添加流程实例为流程实例添加索引数据删除流程实例删除流程实例索引数据索引是否启用判断索引是否已被启用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-weather:e1_caseCassandra数据库流程实例索引项索引存储中间件15海量流程实例的存储和索引测试集12345678910流程实例(万)18436848358978610461211138416272057写数据库（万）38.266.6114.3150.8184.66647038629721239读数据库（万）1.843.684.835.895.8610.4612.1113.8416.2720.57活动索引（万）38266611431508184621932536298535424292活动序列索引（万）2737518941036124711341223140218732581属性索引（万）114619983429451255386579760889551062612876活动长度（万）18436848358958610461211138416272057耗时（分钟）10.219.54248.376.3159201.7343484587使用内存（G）1.71.61.71.71.61.71.71.81.71.7CPU占用率1．5%1.5%1.4%1.5%1.5%2%1.7%1.7%1.6%2%索引构建效率16海量流程实例的存储和索引测试集12345678910流程实例(万)18436848358978610461211138416272057写数据库（万）38.266.6114.3150.8184.66647038629721239读数据库（万）1.843.684.835.895.8610.4612.1113.8416.2720.57活动索引（万）38266611431508184621932536298535424292活动序列索引（万）2737518941036124711341223140218732581属性索引（万）114619983429451255386579760889551062612876活动长度（万）18436848358958610461211138416272057耗时（分钟）10.219.54248.376.3159201.7343484587使用内存（G）1.71.61.71.71.61.71.71.81.71.7CPU占用率1．5%1.5%1.4%1.5%1.5%2%1.7%1.7%1.6%2%索引构建效率CPU占用率低，索引项的生成并不是索引构建的瓶颈17海量流程实例的存储和索引测试集12345678910流程实例(万)18436848358978610461211138416272057写数据库（万）38.266.6114.3150.8184.66647038629721239读数据库（万）1.843.684.835.895.8610.4612.1113.8416.2720.57活动索引（万）38266611431508184621932536298535424292活动序列索引（万）2737518941036124711341223140218732581属性索引（万）114619983429451255386579760889551062612876活动长度（万）18436848358958610461211138416272057耗时（分钟）10.219.54248.376.3159201.7343484587使用内存（G）1.71.61.71.71.61.71.71.81.71.7CPU占用率1．5%1.5%1.4%1.5%1.5%2%1.7%1.7%1.6%2%索引构建效率数据库读写数量太多，数据库服务器性能及对应网络速度才是索引构建性能瓶颈18海量流程实例的存储和索引索引构建效率索引构建耗时随着过程实例数目的增加而增加，总体上呈现一种正相关的关系19目录研究背景通用的流程实例管理框架海量流程实例的存储和索引流程实例的检索工作总结20流程实例的检索过程实例的检索框架21流程实例的检索检索类型参数个数参数类型等于检索1String区间检索2String包含检索1ArrayList相似检索1String统一的输入接口22流程实例的检索23检索优化器输入默认检索方案估计每个检索条件对应结果集大小调整默认检索顺序调整检索种类优化过程输出较优检索方案活动序列长度4和6之间活动包含page或document活动序列长度包含4、5、6活动等于page活动序列长度包含4、5、6(700)活动等于page(30)活动等于page(30)活动序列长度包含4、5、6(700)23流程实例的检索检索执行引擎较优检索方案执行检索合并结果集确定最终结果集分页返回结果集依次执行各个检索条件并合并结果集直至当前结果集足够小（如|A|200）或所有检索条件都已检索完毕如果所有条件均检索完毕，则当前结果集即为最终结果集否则用当前结果集中流程实例判断是否满足剩余检索条件24流程实例的检索检索条件和性能指标数据活动序列为31.7万条包含活动“image”2.3万条类似属性“srcip:10.10.%”1544万条最终结果集1700条所用内存965MB读数据库83次（耗时0.01s）比较次数1550万次耗时1分钟直接读取数据库判断35分钟过程实例检索效率25检索条件和性能指标数据活动序列等于“page-page”54.1万条属性等于“browser:Nokia5000/1.0(06.32)Profile/MIDP-2.1Configuration/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）比较次