Workflows as state machines

Orders, payments and bookings move through steps. The interviewer asks: "What stages can an order have? How do you stop a cancelled order from being shipped?"

A weak answer keeps a status text that any code can change. A strong answer lists the stages (called states) and a table of allowed changes, and checks every change against it. At SDE-1 level, list the states. At SDE-2 level, enforce the table. At SDE-3 level, handle repeated and late messages.

A parcel can be delivered only after it is packed. It cannot go from "delivered" back to "packed".

A state is the stage a thing is in now, such as PLACED. A move (also called a transition) changes the state, such as PLACED to ACCEPTED. A legal move is a move the rules allow. A final state has no legal move out, such as DELIVERED or CANCELLED. A state machine is the list of states plus the table of legal moves. At any time the thing has exactly one state.

Examples:

• Order: PLACED, ACCEPTED, PREPARING, READY, PICKED_UP, DELIVERED, and CANCELLED.
• Payment: CREATED to PENDING, then SUCCEEDED or FAILED. SUCCEEDED can move to REFUNDED.
• Booking: HELD, then CONFIRMED or EXPIRED. CONFIRMED can move to CANCELLED.

Three rules make it work:

1. One table, one place. The table lists each legal move and who may make it (the customer, the restaurant, the system). All code asks the table.
2. The check and the change are one statement. Use a conditional update (lesson 22), which changes the row only if it still has the old state: UPDATE orders SET status = 'ACCEPTED' WHERE id = 7 AND status = 'PLACED'. The database reports 1 row changed, or 0 rows. Two requests at the same time cannot both pass.
3. When 0 rows change, read the state. If the order is already in the state you wanted, this is a repeat. Return the current state as a success, so the move is idempotent (lesson 9). If not, the move is illegal. Return 409 Conflict (lesson 9).

Save each change as a row of history: old state, new state, time and who.

A food app. Assumptions (made up to teach with): 50,000 orders per day, and 0.2% of messages arrive late or twice.

The table has 9 legal moves:

The last row is 4 moves, so the table has 5 + 4 = 9 legal moves. With 7 states there are 7 x 6 = 42 pairs of different states. The other 42 - 9 = 33 pairs are illegal, and the table rejects all of them.

The late cancel. The order is DELIVERED, which is a final state. No row in the table starts at DELIVERED, so the cancel is illegal. The cancel update only matches orders in PLACED, ACCEPTED, PREPARING or READY, so it changes 0 rows. The order is not CANCELLED, so the system returns 409. This answers the predict box: no.

The size of the problem. 0.2% x 50,000 = 100 messages per day. Without the table, a late "delivered" message would mark a cancelled order as delivered, after its Rs 400 refund. If all 100 were like this, 100 x Rs 400 = Rs 40,000 would be refunded on delivered orders.

A repeat. The restaurant taps "accept" twice. The second update changes 0 rows. The state is already ACCEPTED, so the system returns success.

It solves wrong and repeated moves, and keeps the rules in one place. It costs a table that must change when the business changes. I would split the machine when states multiply. One status for payment (3 states) and delivery (4 states) needs 3 x 4 = 12 states. Two machines need 3 + 4 = 7. The cost of two machines is a rule that links them, such as "do not ship before payment".

"The status is a text field, so any code can set it." Then one bug can set DELIVERED on a cancelled order. Only the table should decide.

"A repeated message must return an error." The sender may have lost our answer. Return the current state as success. Reject only a move that is not legal.

1. What is a final state? Name two final states of a booking that is HELD, CONFIRMED, EXPIRED or CANCELLED.
2. A booking machine has 4 states and 3 legal moves. How many pairs of different states are there, and how many are illegal? If 20,000 bookings arrive in a day and 0.5% of messages are late, how many late messages arrive?
3. A customer taps "Cancel" twice. The first cancel worked. What should the second tap return, and why?