Hacker News Reader

Comment by winstonprivacy | Hacker News Reader

State machines are a good solution when you have a typical transactional business process (order fulfillment, inventory management, etc). But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states.

For instance, let's say that are trying to execute a complex spread in the market. You might be partially filled on one leg (the timing of which is completely out of your control, if it happens at all). Then this needs to spawn an offsetting trade (or two), both of which may or may not be completely filled over multiple tickets. Super messy.

A naive state machine simply doesn't work for this, as the overall unit of work (a "trade") can have multiple sub-states all operating more or less independently of one another.

Are there well-known patterns to handle such situations?

View on HN

> But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states.

That's what State Charts were designed for: https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res...

It's used as the basis for a number of state machine / state chart libraries, for instance XState: https://xstate.js.org/docs/

Not that I know of (so I'd like to see if someone can suggest anything).

In practice, what I have always done is to decompose the "object" into a set of components. Each of these components can be in a number of states, and there are rules to set the header state depending on what the substates are.

Practical example:

------------

Business order #2849 State: PSH (Partially shipped)

Item 2849.01 State ONO (Ordered, not confirmed)

Item 2849.02 State STR (Received, stored)

Item 2849.03 State SSH (Shipped by supplier)

Item 2849.04 State STR (Received, stored)

-------------

Where the "business rules" are something like:

* "If all items are SSH or better, status=SSH"

* "If at leat one item is ONO, status=POR" (on order, not fully confirmed)

... Etc.

That is precisely what I'm doing now and it's the best solution I've found so far. However it is brittle and it takes quite a long time to iron out the edge cases where things can happen that you didn't anticipate.

I have one system that has been more or less stable for two months and once a week, it fails inexplicably (dumping no logs either). Whenever this happens, I find myself writing a ton of debug code hoping to catch it.

I worked on a highly complex, high-volume automated procurement sourcing system many years ago. Each Purchase Requisition (PR) -> RFQ -> Bid Response -> Purchase Order could have many-to-many relationships, splitting & bundling at each line item (even the arrows above don't give the right idea, as things could go to re-bid, long-term contract with task orders, etc.).

We tried for nearly two years to get the status/state of each PR line item to update in real-time as events occurred during follow-on steps, but it was extremely brittle.

We finally added an intermediary queue and centralized all the logic in batch. Anytime something happened that might trigger a state (not verified), we tossed it in the queue. Then, we processed the queue every five minutes through a rules engine that was a classic factory pattern (a favorite anti-pattern). Every time the PR # ran through the rules engine, it would have a deterministic result. Sometimes it would pass through 10-20 times with no state change, but at least it was predictable.

We thought it would be too inefficient, potentially processing the same PRs 100s of times without any actual change to the state. However, the servers handled it fine, and it was real-time "enough" the users didn't notice a lag. We went from fixing issues several times a week to no changes for the remaining two years I was on the project.

Not sure about the specifics but yes, in cases like the one I described in my oriignal post, the "header" state will not change immediately but some kind of service thread would periodically revisit the active headers (i.e. anything that had not reached the final stable state) and check all the items in order to update the header state.

That worked fine for us. Also, I have recently (< six months ago) used a SM to build a module in the application I am working on and I am quite happy how it allowed us to quickly adapt to the corner cases that inevitably started cropping up after deploying the module.

I am fairly convinced that a different approach would have make been much more difficult to adapt, and that testing for subtle interactions of different states would have been much more complicated.

I agree on the fact that you may have edge cases cropping up in production... still, in my experience this approach makes adjusting (either by introducing new States, or by altering the logic that guides a State Transition) much easier because you can reason about the problem in terms of a specific item and a specific State Transition at the time, even if this happens to 10k records at the same time, and there are another 10M records of different type and in different states.

I used a SM no more than six months ago to process vouchers and voucher redemption from a third party service and while we had no less than 10 changes after deploying in prod... each one was easy to analyze and the actual fix was like 2-3 lines of code.

These is analogous to kubernetes conditions in the old-debate between explicit state machines with phases/transitions and events/conditions for k8s resources.

https://maelvls.dev/kubernetes-conditions/

Interesting, thanks!

I have zero experience (or knowledge) of Kubernetes, but I feel this somehow strengthens my idea that SM can be a very powerful tool indeed when dealing with some specific problem.

Are those really all the states?

If you have a rigid state machine, you better know all the edge cases and states.

Architecturally state machines seem simple but they area computational power beneath stack machines and of course Turing machines.

So next thing you want is a simple rules engine. Well next comes the rete processing rabbit hole, etc.

We want to think computation is just state transition graphs but real computation even just business logic goes off the rails real fast.

Sorry, seen this only now. Yep, I do consider these states, and yes, I am aware that trying to scale up to a "simple" rule engine is a huge effort.

Personally I always worked with relatively simple state machines and always wrote actual code to handle new cases or edge conditions that were not in the original design.

As a tool (and at the tactical level), these work fine. Making these an overarching paradigm for your whole system, and especially adding a rule engine is something I never did and I would be wary to try, personally.

> Are there well-known patterns to handle such situations?

I'm not familiar with algorithmic trading so may be way off, but if I understand your problem correctly, it sounds like you need what is called parallel states: state machine where a "state" is in itself a state machine. The trick here is that transition of one "leg" can be transition trigger for another leg. In your example you would have 4 states: "Executing trade leg A/B" and "Executing balancing trade". Suppose trade A fills first (a complex machine in itself), it triggers leg B to terminate and transition to balancing trade state while leg A would transition to completion state.

I think the problem with parallel states is the combinatorial explosion of the number of transitions - instead of having O(n) transitions, now you have O(n_1*n_2*...*n_k) transitions between all possible k-tuples of parallel states.

Um... No? Parallel (though hierarchical/recursive would be more fitting term) states are literally designed to fight combinatorial explosion of transitions. Qt docs provide nice, concise summary: https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-...

Instead of transitioning on multiple parameters you decompose states into respective nested state machines to avoid this explosion

Can you share what your current solution looks like for something like that?

> But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states.

Your comment resonated with me relative to regulated financial services where a relationship with a customer has many states can can be independent or intertwined depending on regulatory environment and subject matter i.e. status and renewal of terms of a contract/agreement, billing/payment, different pricing revisions, etc.

Basically, lots of if...else statements combined with coroutines. Refactoring out as many big blocks of code helps a bit, but there's always yet another exception lurking in the shadows, waiting to show up at the least opportune time (such as when the system is under stress).

Just take the product of the two independent states. If you had 5 + 5 states, now you have 25 superstates each representing a potentially unique situation. As long as the sub-states are enumerable, the superstates will be enumerable too. One could argue this is exactly where state machines shine, because they allow you to methodically consider every condition.

In terms of specific implementation I'm not sure, but it may be possible to use a formal modeling tool like TLA+ to prove a particular approach only results in outcomes you consider correct. So you could try to model the trade and all the sub states you mention in a naive state machine way, then check if that super messy tangle works as intended or if it has incorrect behavior.

I know I’m missing the point, but many exchanges have support for defining and executing spread strategies atomically.

Look up HSMs.

I've looked into HSMs and I don't think they are intended to handle this scenario due to the needed to be in multiple states at once.

For instance, you partially fill one trade. This spawns a process which must then enter an offsetting trade for that partial amount.

While this is going on, you may partially fill more of your initial trade, which then must spawn an offsetting trade for that amount (and so on).

This quickly escalates out of control when you consider all of the possibilities which can happen at each state along the way (partial fills, cancels, connection issues, circuit breakers).

Reply on news.ycombinator.com