deterministic state machines

I’ve been moving more of my code into deterministic state machines. I want to reproduce a component’s state changes from its initial state and the inputs it received. The difficulty is that a function’s arguments often aren’t all of its inputs. It might also read the clock, receive data from a socket, or fetch some state through an RPC.

Consider a request we want to retry after ten seconds if we’re still waiting for a reply. Whether it needs another attempt depends on the current time and whether a reply has already been processed. If the request code manages the socket and timer itself, reproducing that decision means controlling both operations. A reply that arrived after the timeout on one run might arrive before it on the next.

I separate the retry logic from those operations by having the caller supply the time and any replies. The request keeps its deadline and completion flag, so it can decide whether another attempt is due. If it needs to retry, it returns a Send action and the caller sends the request. The caller can use async to wait for the socket, while the request’s methods finish updating its fields before the next input is handled. This is the Sans I/O pattern used in protocol libraries.

State transitions

Assume request 7 was sent at time zero, with its first retry due at ten seconds. Its Request struct holds the ID, a done flag, a retry_at deadline, and a ten-second retry_interval. Time is a Duration measured from that origin.

impl Request {
    fn tick(&mut self, now: Duration) -> Option<Action> {
        if self.done || now < self.retry_at {
            return None;
        }

        self.retry_at = now + self.retry_interval;
        Some(Action::Send {
            request_id: self.id,
        })
    }

    fn on_reply(&mut self) -> Option<Action> {
        if self.done {
            return None;
        }

        self.done = true;
        Some(Action::Complete {
            request_id: self.id,
        })
    }
}

For a pending request, a call to tick at or after the deadline advances the deadline and returns Send. The caller sends the request and routes replies to on_reply, which returns Complete for the first reply and no action for later ones. The done flag stops this client from reporting completion twice. The server could still execute both attempts, so it needs to recognize a request ID it has already handled or use an operation whose effect is the same when repeated.

If a failed socket write should change the retry deadline, the caller would pass that error back through another method. The request could then update its deadline without making the write itself.

Event ordering

A test can deliver the reply before checking the deadline, or call tick at the deadline before delivering the reply. Both cases exercise the same implementation without opening a socket or waiting for a timeout.

Here, pending_request() constructs that initial state, with the first retry due at ten seconds.

#[test]
fn reply_before_timeout() {
    let mut request = pending_request();

    assert_eq!(request.on_reply(), Some(Action::Complete { request_id: 7 }));
    assert_eq!(request.tick(Duration::from_secs(10)), None);
}

#[test]
fn timeout_before_reply() {
    let mut request = pending_request();

    assert_eq!(
        request.tick(Duration::from_secs(10)),
        Some(Action::Send { request_id: 7 })
    );
    assert_eq!(request.on_reply(), Some(Action::Complete { request_id: 7 }));
}

If the reply is sitting unread in the socket buffer, tick can still trigger a retry at the deadline.

Replay

The tests above each deliver one reply. If we forgot the done check in on_reply, both would still pass. A timeout followed by two replies exposes the mistake: the request returns Complete twice.

#[test]
fn duplicate_reply_does_not_complete_twice() {
    let mut request = pending_request();

    request.tick(Duration::from_secs(10));
    request.on_reply();
    assert_eq!(request.on_reply(), None);
}

For this failure, the history is Tick(10s), Reply, Reply. Replaying it requires the initial state, input values, delivery order, and code version. For randomized retries, we can record the chosen delay so a replay doesn’t choose a different deadline. For an RPC, we need the result the component received, not just a record that the call happened.

Stepping through that history shows done becoming true on the first reply. A second Complete action would expose the bug even though done stays true. After changing the code, we can rerun the same calls and inspect their results without sending requests to the server.

Simulation testing

A simulation can try a reply after several retries, two replies in a row, or a run with no reply at all. After each input it checks whether the request has completed more than once and saves the sequence if it has. A ten-second timeout can be tested by passing that time to tick, without sleeping.

The complete example starts with a pending request and tries sequences of replies and time updates, up to six inputs, without moving the clock backwards. A request that never completes would pass the duplicate-completion check, so the ordering tests also require the first reply to return Complete.

These tests would still pass if the socket-reading code dropped every reply: they call on_reply directly. To test that path, we need to send a request through the socket and check that its reply reaches the state machine.

FoundationDB and TigerBeetle test database clusters with simulators that can delay messages, fail storage operations, and repeat the same sequence of faults.

If I ask an agent to fix the duplicate-reply bug, I can give it the three calls above and the failing assertion. It can change on_reply, rerun the sequence, and check whether the second reply still completes the request.