Saturday, May 12, 2007

Food for thought

Peter Lin is doing quite a few posts lately sharing his thoughts about temporal logic implementation in the last few days. Thank you Peter!

In this post, he makes a point in the AI x Business Rules scenarios and I agree with him. Although, the most fun is the AI side, the Business Rules side is the one that gets more practice and real use out there. Can we attend to both? :)

Anyway, he also talks about the retraction of facts from the network. The approach for doing it is not clear for me either, but I agree with him that the polling is complex and probably a waste of resources. I was thinking if it is possible to have a kind of registry, where facts registry themselves for removal at a specific time and this way we avoid the polling? Kind of what happens in simulation systems where the events are recorded in a time line in a way that the clock does not need to simulate every single instant in the time line... the clock can simply go from one event to other, since between events, there is no state change.

But that brings us to the most difficult design decision for me in the beginning of this research: how to model the clock?

Maybe Peter can blog about it? :)
Basically my thoughts and questions are:

* one can make the engine work with the either the real system clock or a pseudo clock implementation.

* using the real clock seems wrong to me, as the engine has no control over it. So if the engine is under a heavy load or must fire a lot of activations as a result of a given state, it may lose time windows and get inconsistent.

* using event's timestamps as the clock driver for temporal rules seems also no good for me because again, the engine has no control over arriving events (and it's clock). An example of problem with such approach is: what happens if events arrive out of order or from multiple, de-synchronized streams?

* so, the only option I feel it is feasible is to implement a pseudo clock over which the engine has full control. The user would still be able to constrain patterns of event's timestamps, since they are natural attributes of the facts, but the temporal behavior would be defined in relation to this pseudo clock. Question is: how does this pseudo clock gets "updated"? will the user explicitly call a "tick" method for each clock tick? will the engine somehow run the clock based on an external resource? I came to no conclusion so far and appreciate directions in case anyone already did something similar in the past.

Thinking out loud... ;)


1 comment:

woolfel said...

Here's some random thoughts, hopefully they make sense. I did think about having a registry like component which keeps the temporal facts in time order. The idea I had is that when an object is asserted, it is passed to the registry. Let's call it temporal registry for a lack of better name.

The simplest way I can think of is to have the temporal registry calculate the elapsed time between current time and the top fact in the registry. To keep performance acceptable I was thinking the granularity should be at the minute level. More granular than that, it could be rather expensive, especially in a real-time system where there's a constant stream of events. The registry could easily get overwhelmed.

I know firms like fidelity generate upwards of 5% of the trading volume on NYSE and their systems handle 2K transactions per second for 18hours a day. There's a four hour period where the transaction rate dips down, but there's always transactions happening. I believe the time corresponds to the gap between NYSE and the japanese stock market.

Anyway, back to the temporal registry. Using the real system clock probably isn't practical for a couple of reasons. The trading systems I know of use synchronized time, so it's not the system time.
The engine could use an internal timestamp, assuming the system time is already insync with GMT time.

The downside I see with a temporal registry is this. At best, it can only gaurantee the fact won't be retracted before the expiration time. It won't be able to gaurantee the fact will be removed exactly at expiration time. The rule engine can only promise that any matches after the expiration, will not fire a rule.

Johan Lindberg actually tried the polling approach in his python RETE engine and he saw the CPU usage go crazy :)

Chances are, the events will arrive out of order, especially trading systems. In the case of fidelity, they have offices in Boston, NY, Los Angeles, SF, Tokyo, London, and a half dozen other major cities. Those systems are literally going all the time, and the latency varies even in their own private network. For a trading system, I think the expiration time for the order should be set when the order is sent. That means the rule engine doesn't have control, and it also implies an absolute expiration time. As long as the rule engine can gaurantee the OMS ignores stale orders and remove them lazily, that's the best it can do.

A cheaper way of doing the temporal registry is to use a service rule as I mentioned. In an event driven system, the agenda should have at most 1 activation. This is because the activations are fired immediately and the rule have to be written properly. After the activation fires, the rule engine can run the service rule to remove expired facts. I would do it at the assert method. The pseudo logic might look like this.

// run the service rule(s)

When the executeServiceRule runs, it should retract all stale facts. This approach assumes activations are fired immediately, similar to JESS runUntilHalt. In jamocha, the rule would be declared (no-agenda true). I like explicitly declaring a rule by-passes the agenda, rather than runUntilHalt. Even in an event driven systems, there are times when I want a rule to not fire immediately. This gives users greater flexibility and mixed mode execution.

hope that makes some sense.