基于MapReduce的分布式规则匹配系统的研究与实现

发布时间：2020-04-05 22:34

【摘要】：随着基于规则的系统的广泛使用,规则匹配的效率问题越来越受到人们的重视。自上世纪七、八十年代以来,人们一直为提高规则匹配的效率而努力。本文通过对优秀规则推理引擎系统进行学习和研究,同时在对分布式计算框架研究和学习的基础上,提出和实现了一个基于MapReduce的分布式规则匹配架构,利用MapReduce的思想,将匹配任务分解到一个集群中,并经过适当的归并,快速得到规则匹配的结果。在大规模的规则和数据的环境下能够显著提高规则的匹配效率,并且使系统具有更好的可扩展性和灵活性。本文首先从总体需求、接口及系统效率和可靠性需求等几个方面对系统需求进行了分析,并在此基础上提出了系统的总体架构。和MapReduce架构一致,系统采用了Master/Worker模式,将Worker分为Map Worker和Reduce Worker,分别进行分布式规则的匹配和结果汇总的工作。Master负责完成任务的分解和分配,并对所有Worker进行管理和监控。然后对分布式规则匹配系统的任务分配策略进行了介绍。在将规则分解成子规则的基础上,提出了一种子规则的分配策略,根据服务器负载信息和已分配的子规则信息,实现将子规则及规则匹配的任务能够均衡地分配到分布式环境中。在对事实进行分配时,基于子规则的分配情况,提出了事实的分配策略,将事实分配到存在相应子规则的Map Worker上。并给出了处理子规则与事实匹配的具体Map过程。接着详细介绍了分布式规则在完成匹配后的触发和执行方式。给出了在归并中间结果时所采用的具体Reduce过程。在处理规则触发时,提出了对关联规则进行触发的方法,并给出了控制规则触发过程的方式。在处理冲突时,介绍了几种比较常用的冲突解决策略。文章最后给出了原型系统的实现类图并对系统的性能进行了测试。在系统实现部分,以实现类图的方式介绍了对Master Map Worker、Reduce Worker及系统交互IO等主要模块的设计。通过对不同问题规模和服务器规模的情况进行测试,比较了系统匹配效率,测试结果基本上达到了预期效果。
【图文】：

结构图,推理引擎,议程,事实

3.推理引擎 (InferenceEngine):完成推理的过程，找出当前周期中哪条规则需要被激活。它们的结构图1.1所示:议议程程次次峻盘蜜幽幽工工作区区规规则库库幼幼‘一介、旋、、 ._...图1.1基于规则的专家系统构成其中，推理引擎通过匹配事实和规则完成推理的具体过程，其主要包括三个部分:模式匹配器 (pattemMateher)、议程(Agenda)和执行引擎(ExeeutionEngine)。推理引擎通过判断规则库中哪些规则满足工作区中的哪些事实或目标，来完成推理过程;满足事实或目标的规则被加入议程，，议程管理模式匹配器挑选出来的规则的执行次序;执行引擎负责规则的执行及其他动作。推理引擎的工作过程可以用三个阶段来进行描述:匹配，选择，执行12113]。推理引擎通过模式匹配器来完成规则库中规则和工作区中事实的匹配过程，以决定哪些规则被激活;通过议程完成规则的冲突处理和执行规则及其次序的选择;通过执行引擎完成规则的执行过程。我们可以用如下所示的步骤来描述推理引擎工作过程的三个阶段[4J:1.将事实输入到 workingMemory中。2.使用 PattemMatcher比较规则库中的规则(Rule)和工作区中的事实，判断能够和事实匹配的规则，即激活规则。3.如果执行规则存在冲突

过程图,推理引擎,过程,议程

5.使用执行引擎执行Agenda中的规则。重复步骤2至5，直到执行完毕所有Agenda中的规则。图1.2展示了推理引擎的工作过程:哥哥一一图1.2推理引擎的「作过程如图1.2所示，当推理引擎的规则执行时，会根据冲突解决后议程中的规则执行队列的顺序逐条执行规则执行实例。由于规则的执行可能会使工作区的事实发生改变，从而会使议程中的某些规则执行实例因为作用的事实的改变而失效，从而必须从议程中撤销，也可能会激活原来没有成功匹配的规则，生成新的规则执行实例进入议程。于是就产生了一种“动态”的规则执行链，形成规则的推理机制。近10年来，随着计算机技术和人工智能技术的飞速发展，尤其是网络技术的进步，基于规则的专家系统也有了新的重大发展，出现了以Java为核心的规则推理引擎系统如Drools、nog和Jess等，并在一些领域得到了广泛的应用。在商业应用领域
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP338.8

【参考文献】