In an effort to help encourage those thinking of learning more
about the internals of rule engines. I have made a document on
implementating left and right unlinking. I describe the initial
paper in terms relevant to Drools users, and then how that can be
implemented in Drools and a series of enhancements over the
original paper. The task is actually surprisingly simple and you
only need to learn a very small part of the Drools implementation
to do it, as such it's a great getting started task. For really
large stateful systems of hundreds or even thousands of rules and
hundreds of thousands of facts it should save significant amounts
of memory.
http://blog.athico.com/2010/08/left-and-right-unlinking-community.html
Any takers?
Mark
Introduction
The following paper describes Left and Right unlinking
enhancements for Rete based networks:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.6246
A rete based rule engine consists of two parts of the network, the
alpha nodes and the beta nodes. When an object is first inserted
into the engine it is discriminated against by the object type
Node, this is a one input and one output node. From there it may
be further discriminated against by alpha nodes that constrain on
literal values before reaching the right input of a join node in
the beta part of the network. Join nodes have two inputs, left and
right. The right input receives propagations consisting of a
single object from the alpha part of the network. The left input
receives propagations consisting of 1 or more objects, from the
parent beta node. We refer to these propagating objects as
LeftTuple and RightTuple, other engines also use the terms tokens
or partial matches. When a tuple propagation reaches a left or
right input it's stored in that inputs memory and it attempts to
join with all possible tuples on the opposite side. If there are
no tuples on the opposite side then no join can happen and the
tuple just waits in the node's memory until a propagation from the
opposite side attempts to join with it. If a given. It would be
better if the engine could avoid populating that node's memory
until both sides have tuples. Left and right unlinking are
solutions to this problem.
The paper proposes that a node can either be left unlinked or
right unlinked, but not both, as then the rule would be completely
disconnected from the network. Unlinking an input means that it
will not receive any propagations and that the node's memory for
that input is not populated, saving memory space. When the
opposite side, which is still linked, receives a propagation the
unlinked side is linked back in and receives all the none
propagated tuples. As both sides cannot be unlinked, the paper
describes a simple heuristic for choosing which side to unlink.
Which ever side becomes empty first, then unlink the other. It
says that on start up just arbitrarily chose to unlink one side as
default. The initial hit from choosing the wrong side will be
negligible, as the heuristic corrects this after the first set of
propagations.
If the left input becomes empty the right input is unlink, thus
clearing the right input's memory too. The moment the left input
receives a propagation it re-attaches the right input fully
populating it's memory. The node can then attempt joins as normal.
Vice-versa if the right input becomes empty it unlinks the left
input. The moment the right input receives a propagation it
re-attaches the left input fully populating it's memory so that
the node can attempt to join as normal.
Implementing
Left and Right Unlinking for shared Knowledge Bases
The description of unlinking in the paper won't work for Drools or
for other rule engines that share the knowledge base between
multiple sessions. In Drools the session data is decoupled from
the main knowledge base and multiple sessions can share the same
knowledge base. The paper above describes systems where the
session data is tightly coupled to the knowledge base and the
knowledge base has only a single session. In shared systems a node
input that is empty for one session might not be empty for
another. Instead of physically unlinking the nodes, as described
in the paper, an integer value can be used on the session's node
memory that indicates if the node is unlinked for left, right or
both inputs. When the propagating node attempts to propagate
instead of just creating a left or right tuple and pushing it into
the node. It'll first retrieve the node's memory and only create
the tuple and propagate if it's linked.
This is great as it also avoids creating tuple objects that would
just be discarded afterwards as there would be nothing to join
with, making things lighter on the GC. However it means the engine
looks up the node memory twice, once before propagating to the
node and also inside of the node as it attempt to do joins.
Instead the node memory should be looked up once, prior to
propagating and then passed as an argument, avoiding the double
lookup.
Traditional Rete has memory per alpha node, for each literal
constraint, in the network. Drools does not have alpha memory,
instead facts are pulled from the object type node. This means
that facts may needlessly evaluate in the alpha part of the
network, only to be refused addition to the node memory
afterwards. Rete supports something called “node sharing”, where
multiple rules with similar constructs use the same nodes in the
network. For this reason shared nodes cannot easily be unlinked.
As a compromise when the alpha node is no longer shared, the
network can do a node memory lookup, prior to doing the evaluation
and check if that section of the network is unlinked and avoid
attempting the evaluation if it is. This allows for left and right
unlinking to be used in a engine such as Drools.
Using Left and
Right Unlinking at the Same Time
The original paper describes an implantation in which a node
cannot have both the left and right inputs unlinked for the same
node. Building on the extension above to allow unlinking to work
with a shared knowledge base the initial linking status value can
be set to both left and right being unlinked. However in this
initial state, where both sides are unlinked, the leaf node's
right input isn't just waiting for a left propagation so the right
can re-link itself (which it can't as the left is unlinked too).
It's also waiting to receive it's first propagation, when it does
it will link the left input back in. This will then tell it's
parent node's right input to also do the same, i.e. wait for it's
first right input propagation and link in the left when it
happens. If it already has a right propagation it'll just link in
the left anyway. This will trickle up until the root is finally
linked in and propagations can happen as normally, and the rule's
nodes return to the above heuristics for when to link and unlink
the nodes.
Avoid
Unnecessary Eager Propagations
A rule always eagerly propagates all joins, regardless of whether
the child node can undertake joins too, for instance of there is
no propagates for the leaf node then no rules can fire, and the
eager propagations are wasted work. Unlinking can be extended to
try to prevent some level of eager propagations. Should the leaf
node become right unlinked and that right input also become empty
it will unlink the left too (so both sides are unlinked) and go
back to waiting for the first right propagation, at which point
it'll re-link the left. If the parent node also has it's right
input unlinked at the point that it's child node unlinks the left
it will do this too. It will repeat this up the chain until it
reaches a node that has both left and right linked in. This stops
any further eager matching from occurring that we know can't
result in an activation until the leaf node has at least one right
input.
Heuristics
to Avoid Churn from Excessive and Unnecessary Unlinking
The only case where left and right linking would be a bad idea is
in situations that would cause a "churn”. Churn is when a node
with have a large amount of right input memory is continually
caused to be linked in and linked out, forcing those nodes to be
repeatedly populated which causes a slow down. However heuristics
can be used here too, to avoid unnecessary unlinking. The first
time an input becomes empty unlink the opposite and store a time
stamp (integer counter for fact handles from the WM). Then have a
minimum delta number, say 100. The next time it attempts to
unlink, calculate the delta of the current time stamp (integer
counter on fact handle) and the time stamp of the node which last
unlinked (which was recorded at the point of unlinking) if it's
less than 100 then do nothing and don't unlink until it's 100 or
more. If it's 100 or more then unlink and as well as storing the
unlink time stamp, then take the delta of 100 or more and apply a
multiple (2, 3, 4 etc depending on how steep you want it to rise,
3 is a good starting number) and store it. Such as if the delta is
100 then store 300. The next time the node links and attempts to
unlink it must be a delta of 300 or more, the time after that 900
the time after that 2700.