rete算法(drools 转)

Broadview 2014-03-26

rete算法简介  

        原文连接      

Rete算法是Charles Forgy在1979年的论文中首次提出的,针对基于规则知识表现的模式匹配算法。目前来说,大部分规则引擎还是基于rete算法作为核心,但都有所改 进,比如drool,jess等等,下面介绍rete算法的概念,一些术语,以及使用规则引擎需要注意的问题。

先来看看如下的表达式:

     (name-of-this-production
        LHS /* one or more conditions */
       -->
        RHS /* one or more actions */
       )

    name-of-this-production就是规则,LHS(left hand side)一系列条件,RHS(right hand side)这个是我们满足条件后应该执行的动作。

    

     

rete算法(drools  转)

     

   结合该图介绍几个概念:

    production memory(PM)是由所有的production形成。

    working memory(WM)由外界输入根据匹配算法形成的,反映了运行中的规则引擎的状态,记录各种数据, WM中每一个item称为working memory element(WME) ,由外界的输入产生。

     agenda负责匹配,冲突解决,执行动作。

   

    rete是网络的意思(拉丁语),它将所有的规则最终解释(或编译)生成一个识别网络,其中包括了alpha网络,beta网络。alpha网络是根据 LHS生成的网络,它根据外界的输入快速识别是否存在condition成立,并且跟其beta网络交互更新整个网络的状态,如下图:

rete算法(drools  转)

     

    最基本的alpha网络就如上图所示,类似于这样,所有的condition被parse到这样的网络,当外界输入wme时,该wme会进入这样一个网络 进行辨识,如果到达最底端,证明一个condition成立了,当然,如图这个网络算是最简单的实现了,实际规则引擎需要提供更快速的算法去辨识输入的 wme,比如将图中color的各种值存入hashtable,或者是jumptable,又或者是trie tree。整个alpha network是一个巨大的字符串匹配和过滤网络,需要将各种数据结构组合在一起去实现海量condition情况下的快速匹配。各种规则引擎的实现又是 不一致的,比如jess,如下图:

    (defrule done
       (TESTING)
       (number ?number)
       (TEST IS DONE)
      (INIT CREDIT 5)
      (CUSTOMER AGE ?age)
       (has ?type "PP"))
=>
      (assert (TEST COMPLETED)))

      rete算法(drools  转)


这 个production的解释后生成的网络,这里我们先注意红色的节点,这些节点就是alpha网络的节点,这个图只是描述了大致的过程,以第一列为例, 第一个红色node表示输入是否匹配TESTING这个字符串,第二个node匹配在TESTING后面的参数数量(slot)是否匹配0,如果我们 assert TESTING进入WM,那么这个fact是可以匹配到done这个rule的第一个condition的,其他可以依次类推,值得注意的是最后一个 condition,has是我们自定义的function,类似这样的function,jess没有单独生成一列,只是将它作为CUSTOMER AGE ?age这一列的最后一个node,这样的condition有个特点就是需要执行一段代码去判断某个事实是否成立(不仅仅只是做字符串的操作),这段代 码不仅仅是字符串的匹配,同时还具有实时性,类似这样的condition开发中需要注意,因为alpha network在运行期会不止一次去执行这个condition是否成立,这个是匹配算法的特性决定,所以,我们需要用cache或者规则语言的特性去避 免不必要的执行code以提高性能。

下面贴个比较复杂的例子:

   

rete算法(drools  转)   rete算法(drools  转)


   图太大,一个截不下来。。。。。。

   下面我们结合两个例子说说beta网络,当alpha网络过滤后condition成立,WME被传递到beta网络时,绿色的node就要发挥作用了, 这个node就是join node,它有两个input,一个join node ,一个alpha node(红色),join node是由多个WME组成的,对于初始的join node 我们称为left input adapter 如图中黄色的node,该node是空的,那么第一个把这个node作为left input的join node就只包含了一个WME,下一个join node则包含了两个WME,以此类推。图中天蓝色的node上方的join node 完全匹配了production执行需要的condition,所以这个rule就被激活等待执行了。

    假设我们需要编辑业务逻辑,那么最好的描述载体就是流程图,简单的流程图包含以下一些基本单元:起始节点,逻辑判断,执行动作,结束节点。这些节点可以完 成最简单的业务逻辑描述,那么我们把这些流程parse到规则的时候,我们会怎么去做,第一个逻辑判断单元返回true,于是我们执行某个动作,第二,三 个逻辑判断单元返回true我们执行某个动作,相当于会parse到两个规则,符合condition1,production1触发,符合 condition2,3,production2触发,有了beta网络,我们在触发production2时只需要判断condition2,3是否 成立,对于更复杂的情况,beta网络提高了速度,避免了重复匹配。

   

    开发中使用规则引擎也遇到些问题,总结如下:

    1)规则引擎中对于特殊condition的处理,由于condition会在部分production中重复出现,所以会造成condition的重复匹配问题,影响了程序的性能,这个要结合项目去优化rule脚本的parse或者使用cache去提升性能。

    2)内存消耗问题,rete算法是空间换时间,所以对于内存的消耗是比较大的,特别是加载rule的时候(生成网络),在运行期内存会缓慢增长,所以gc效率需要注意,同时单个服务器所能承受的压力(多个WM)也跟规则引擎息息相关。

    3)测试,对于使用规则去表达业务的系统,如何测试是必须解决的问题,对于这个问题,也只能保证基本的流程分支覆盖测试,对于复杂情况下的defect很 难发现,不过有些原则需要注意,如果要使用规则引擎,我们必须完全以规则引擎为核心,对于业务逻辑必须尽可能的抽取到规则引擎去实现,对于扩展实现的 function粒度必须小且简单,不要再代码中去实现业务逻辑。

    4)大部分的condition需要是不变的,也就是说基本信息需要保持稳定不变。比如某客户公司上属集团信用额度大于100w这样的condition,这个额度变化的频度不会很高,不需要去实时匹配。

    5),remove WME production是较复杂的操作,规则较复杂时,应该尽量少去做这样的操作。