y implement state transition by static methods#OMS

(This discussion is relevant to any high-concurrency finite state machine or FSM, but I will use an order management system as example.)

Suppose my FSM implements state transitions in the form of instance methods defined on the Order object, myOrder->A_to_B(Event). Inside such a method, we verify this->currentState == A, validate other Conditions, and take the appropriate Action to process the Event, before updating this->currentState = B.

(The Transition/Event/Condition/Action/Validation concepts are fundamental to FSM in general. See http://www.thetibcoblog.com/2007/06/26/differences-between-a-bre-and-a-rule-driven-cep-engine-part-1)

I once proposed that A_to_B could convert to a static (java/c#/c++) or (c++) global, free-standing function A_to_B(Event, Order). I once said that this “might” be a bit easier to multi-thread. Now I feel in most cases such a simple change (from non-static to static) won’t improve concurrency. Such a change may have bigger benefits (to be elaborated) but concurrency is rarely one of them. However, here’s one possible “rare” context.

Following Functional Programming principle (as seen in FMD), each and every object is immutable, so is Order. Therefore the global function will return a new Order instance but representing the same real world order. Immutability removes the need to synchronize, completely.

Q: But what if 2 threads need to access a given Order?
A: If one of them is a reader, then immutability will probably help.
A: If both are writers, then my counter question is why this scenario is allowed to exist —

I feel in low latency OMS each order should ideally be updated by the same physical thread throughout. Multi-queue — each security/cusip belongs exclusively to a single thread, never hopping from thread X to thread Y — Rule 1.

I feel Rule 1 is an extremely practical rule but in some contexts it is over-restrictive and needs to be relaxed, but still at any moment an order is only updated on a single thread, never concurrently on 2 threads — Rule 1b.

However, I feel all good software rules have exceptions (as explained elsewhere in my blog) so sometimes it’s legitimate to break Rule 1b, though I won’t condone such reckless practice. Well I’m not boss…:)

In such a system, I take the liberty to assume every writer thread must put the updated Order into a shared cache. 2 writers using the instance method A_to_B()….must synchronize on the cache (usually a hash map). The FP design could use CAS. Since the chance of concurrent write is low, CAS retry is is unlikely, so CAS will be faster. Uncontended synchronization is always slower than uncontended CAS — see Brian Goetz article on http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html.

However, immutability entails more object creation instead of updating mutable fields. Trade-off to be measured.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s