drools:顺序的Rete算法

 

顺序的Rete算法 <o:p></o:p>

作者： Mark Proctor <o:p></o:p>

无状态和有状态Session

使用Rete，你有一个有状态的Session，在那里对象可以随时被设置或修改，规则也可以随时被增加和删除。现在我们假设一个无状态Session会发生什么样的情况呢？在完成了初始数据集后，没有更多的数据可以被设置或修改（没有规则的重新评估），并且没有规则可以在被增加或删除。这意味着我们可以认为引擎在这种情况下所处理的工作量是最小的。<o:p></o:p>

算法<o:p></o:p>

1. 使用salience和在规则集中的位置（只要仔规则终节点上设置一个sequence属性就可以）排序规则<o:p></o:p>
2. 建立一个数组，每一个可能的激活规则对应一个数组元素，元素的位置象征着激发的顺序<o:p></o:p>
3. 关掉除了右输入对象内存之外的所有节点内存<o:p></o:p>
4. 切断LeftInputAdapterNode的传播，并且在一个Command对象中有这个对象（LeftInputAdapterNode）和节点的索引，Command对象被加入WorkingMemory的列表中随后执行。<o:p></o:p>
5. 设置所有的对象，当完成断言后右输入节点内存检查Command列表并且按照顺序执行<o:p></o:p>
6. 所有激活结果应当被放置在数组中，按照规则的Sequence编号所决定的顺序。记录第一个和最后一个元素的位置，以减少遍历范围。<o:p></o:p>
7. 遍历激活规则的数组，按顺序执行元素<o:p></o:p>
8. 如果我们有一个允许执行规则的最大数，就能够尽早的退出网络评估而去激发数组中的规则<o:p></o:p>

LeftInputAdapterNode不再去建立组元，增加对象然后传播这个组元，代替的是一个Command对象被建立并且增加到Working Memory内的一个列表中。这个Command对象保存了一个指向LeftInputAdapterNode的引用和要传播的对象。这在设置时停止了任何左输入的传播，因此我们知道一个右输入传播不再需要尝试与左输入进行合作（因为删除了左输入内存）。所有的节点内存被关闭，包括左输入组元内存，除了右输入对象内存——也就是说能够记住断言传播路径的节点只有右输入对象内存。一旦所有的断言完成并且所有的右输入内存配置完毕，我们就能遍历LeftInputAdatperNode Command对象列表，并按顺序调用；它们将通过网络向下传播，并尝试与右输入对象合作；而不需要再保存在左输入中，因为我们知道没有对象会再被设置并传播到右输入内存。<o:p></o:p>

Agenda不再存在，不再用一个优先队列来组织这些组元，而是代替以一个规则数量长度的数组。RuleTerminalNode的sequence数值代表激活规则在数组中的位置。一旦所有Command对象准备完成，就可以遍历数组，依次检查每个元素并激发存在的规则。为了增加数组处理性能，我们记录最初和最后的单元位置。<o:p></o:p>

<o:p> </o:p>

构造的网络中，每一个RuleTerminalNode被赋予了一个sequence数值，基于salience数值与它被加入到网络中的顺序。

数据结构

<o:p></o:p>

右输入节点内存的典型结构是HashMap，为了更快的回收对象（我们知道事实上没有对象要回收），在对象的值没有索引时，我们可以使用列表。对于存在大量的对象情况，索引的HashMap提供性能的提升，如果我们已知对象只有很少的实例，那么对象列表的性能可能比HashMap索引要更好。<o:p></o:p>

上面所提到的内容在JBoss Drools4.0中实现，接下来的内容是对未来的一些想法，在目前它仍然是含糊不清的。<o:p></o:p>

如果存在海量的规则，那么一个被分页索引的直接地址表可以用来取代保存结果激活规则的数组。在这里我们建立数组的分页，对拥有常规指针的页面，我们建立更深层的索引指针指向页面。页面可以显示是否它其中的任一元素被填充或没有填充，允许我们忽略这些元素的遍历。<o:p></o:p>

压缩节点，代码产生和节点排序

<o:p></o:p>

有状态Rete可以新增或删除节点，为了最大化节点共享，我们趋向于每一个字符串约束有一个AlphaNode。无论怎样我们知道已经没有更多的规则加入时，我们可以压缩共享的节点到一个单独的评估中。如果我们有3个连续的AlphaNode：A,B和C。A和B是共享的，C不是。我们可以压缩A和B到一个单独的节点，并且产生代码来完成多个评估。节点排序可以让共享节点最大化。那里可能也会有一些beta node的级别可以进行压缩，但是我还没有更仔细的考虑它。<o:p></o:p>

使用多线程<o:p></o:p>

在通常的Rete中使用多线程是困难的，因为你不会知道是否一个组元将要进入左输入，或者一个对象将要进入右输入——也就是说读和写可以同时进行，为此而增加锁定控制的花费是昂贵的，并且过去的研究表明，这样的花费要超过使用不需要锁定的单线程方法。但是在顺序方法中，我们知道写必然与读在不同的时间发生。所有写操作在对象最初被传播到右输入节点期间发生。所有读操作当组元从LeftInputAdapterNode传播过来时发生。我们可以利用这点来为每一个阶段执行并发的线程，使用并发的集合结构。我们只能处理两个阶段的同步，也就是说知道何时所有对象传播完成以及何时组元传播完成。以同步的方式执行规则是有点困难的，因为我们不容易知道用户对规则顺序的排列意图。一个属性可以用来执行可以同步执行的规则组，这些规则和分组必须按照时间顺序排列。也就是说如果组A在组B之前激发，那么所有组A的规则必须一开始指定好。或者这些组的执行顺序可以单独指定，这样允许规则可以有更多的灵活性。<o:p></o:p>

评论: <o:p></o:p>

Mark Proctor 说... <o:p></o:p>

相比于我们标准的Rete算法，顺序Rete算法带来了30%-350%的性能提升，依赖于规则和数据的复杂度以及数量。节点压缩也能推进性能的提升。在某一个发布版本中我们会为引擎增加一个激发限制，用一个整数值指明允许执行规则的数量，这样我们可以更早的退出网络评估的时间——因此用户可以指定是否当前的规则集的结果是激发1，3或者10个规则。<o:p></o:p>

7/06/2007 2:42 PM   <o:p></o:p>

<o:p> </o:p>

Mark Proctor 说... <o:p></o:p>

此时我们发现最好的情况是对于有许多fact（如5万）的情况，这种情况下带来350%的效率提升。少量fact大量规则的情况下提升的效率比较少，但也比标准算法高30%以上。对于这种情况，可能节点压缩和更多的代码产生能够有所帮助。<o:p></o:p>

7/06/2007 5:17 PM   <o:p></o:p>

<o:p> </o:p>