Doug Patti on State Machine Replication, and Why You Should Care

Doug Patti — distributed-systems engineer at Jane Street — walks host Ron Minsky through the architecture of Concord, Jane Street’s replicated state machine platform for bilateral trading, and the lessons that shaped its successor system, Aria.

Key ideas

1. A replicated state machine is the foundation of reliable distributed software. A state machine here is not the diagram of boxes and arrows from a CS textbook; it is any module that holds some state and processes messages one at a time — deterministically, with no network calls or blocking I/O mid-message. Feed the same sequence of messages to the same code on ten different machines and you get ten identical copies of the same state. That reproducibility is what makes crash recovery, auditing, and fault tolerance tractable.
2. A single sequencer provides total ordering cheaply and surprisingly scalably. Rather than a consensus algorithm like Paxos or Raft, Concord routes all messages through one sequencer process that stamps each packet with a sequence number and re-broadcasts it via UDP multicast — a protocol where one packet is copied to all recipients by the network switches, not by software. Round-trip latency through the sequencer sits at eight to twelve microseconds; throughput reaches hundreds of gigabytes and over 100,000 messages per second across a trading day.
3. Inversion of control forces all state to be visible and makes testing exact. Applications in Concord and Aria do not push messages out; they wait to be asked what they want to send next. This inverted style — borrowed from the Unix select model of event-driven programming — means every piece of state that affects future behaviour must live in an inspectable data structure. Race conditions that are nearly impossible to reproduce in a threaded system can be simulated exactly by replaying a controlled message sequence.
4. Versioning and performance are the hardest operational costs of the design. Because every process must read every message from the beginning of the session to recover, changing the message format forces a coordinated, all-at-once rollout; rolling back a change mid-day means processes can no longer parse messages already written to the transaction log. And although each process discards most messages quickly on type alone, falling even slightly behind the stream causes a process to queue up a debt of unprocessed packets it may never clear.
5. Aria generalises Concord by decoupling the core infrastructure from individual applications. Where standing up a new Concord instance requires a dedicated cabinet of hardware, a sequencer, re-transmitters, and full system configuration, Aria provides that shared infrastructure centrally. Applications connect via a proxy layer that filters the stream to only the topics they subscribe to, lowering the barrier from weeks of set-up to reading the docs and sequencing a first message.

Content

The business context: bilateral trading and why reliability changes shape

Patti joined Concord roughly four years into its life. The system was built to support bilateral trading relationships — arrangements where Jane Street acts as a liquidity provider and also runs the exchange-like infrastructure through which clients connect. That dual role brings obligations that on-exchange activity does not: guaranteed uptime, fast turnaround on incoming orders, and a durable audit trail for regulatory purposes.

The concrete reliability requirement is straightforward but demanding. A client sends an order; something crashes; the client reconnects. They need to know whether they traded or not. ‘That’s an awkward conversation to have with a client,’ Minsky notes. The system must be able to resynchronise any client from any crash point, which means the server-side state cannot live solely in the memory of a single process.

Scalability adds a second pressure. On a normal trading day Concord handles over 100,000 messages per second; on a busy day that rate can be several times higher. The system also ingests the full market data feed from all public exchanges — a large, continuously arriving stream — alongside client orders, which means some message paths must be processed far faster than others.

The state machine abstraction

Concord’s architectural answer is the replicated state machine. Patti is careful to distinguish the term from its textbook cousin: this is not a finite automaton with a fixed set of named states. It is an encapsulated module with three properties — it processes messages one at a time, it is synchronous (no blocking calls inside message handling), and it is deterministic. Given the same input sequence, it always produces the same state.

Determinism is the load-bearing property. It means that if you record the stream of messages and replay it into the same code on a different machine, you recover the same state exactly. Crash recovery in Concord works on precisely this principle: when a process restarts, it reads the day’s transaction log from the beginning and arrives at an exact copy of its pre-crash state.

The synchronous constraint — no outbound network calls, no disk reads, mid-message — is what makes the determinism cheap. There is no hidden timing variation from waiting on external systems, and the single-threaded processing model means there is no need for locks or mutexes.

The sequencer and UDP multicast

The transaction log is produced by a single process: the sequencer. Every process in the system sends proposed messages to a multicast group (a network address that the switches copy to all subscribers simultaneously). The sequencer listens on that group, stamps each packet with a sequence number and a timestamp, and re-emits it on a separate multicast group that all applications listen to. The total ordering falls out of the fact that everything passes through one counter.

UDP multicast is efficient — the copying is done in hardware by the switches, not in software — but it is lossy: packets can be dropped. Concord recovers reliability the same way TCP does, with sequence numbers, but persistently rather than just for the duration of a connection. If a process receives packets 45 and 47 and notices the gap, it contacts a re-transmitter service. Re-transmitters are ordinary processes that listen to the sequencer and record everything; if a re-transmitter has also missed the packet it can escalate to the sequencer directly.

Round-trip latency through the sequencer is eight to twelve microseconds, which Minsky notes is within an order of magnitude of the theoretical minimum for a software solution on standard PCI express hardware. Peak throughput on the Concord transaction log has exceeded 400 gigabytes across a single trading day.

Inversion of control and the testability dividend

In most programs, when your code wants to send a message, it just sends it. Concord’s application framework forbids that. An application does not push messages; it exposes a function that answers the question ‘what is the next message you want to send?’ — and it only gets asked that question by the framework, not at a time of its own choosing. When the application sees its proposed message arrive on the stream, it updates its state and changes its answer. Until then, it keeps proposing the same message.

Minsky draws the lineage back to the Unix select call of the mid-1970s: rather than threads that do one thing after another, you write event handlers that respond to whatever the system delivers. The advantage is that all relevant state must live in explicitly inspectable data structures. There is nowhere to hide it in a thread’s call stack or in a mutex-guarded shared variable.

The testability gain is substantial. To reproduce a race condition in a threaded program you have to arrange for threads to interleave in exactly the right way, which may happen once in a million runs. In Concord you replay a message sequence and the race condition is there every time. You can also pause the system at any point and ask every process what it wants to send next, which makes integration tests for distributed scenarios tractable in a way they rarely are elsewhere.

Composability: shared state machines instead of inter-process calls

State machines in Concord compose by inclusion rather than by communication. If process A needs to know what process B knows, A simply embeds the same sub-state-machine that B runs and feeds it the same messages. Because both are deterministic and see the same stream, they arrive at the same conclusions without ever exchanging a direct message. The architecture forbids direct inter-process calls outside the transaction log precisely to preserve this guarantee.

This also gives Concord a natural decomposition operator. A process doing too much work can be split into two smaller processes that share state machines for the data they both need; two processes with overlapping data needs can be merged for performance. The unit of reuse is the sub-state-machine library rather than a network API.

Costs: performance discipline and versioning brittleness

Every process must read every message on the stream, even if it discards most of them immediately. The critical path is the discard: a process that cannot determine quickly from a message’s type field that the message is irrelevant will fall behind the stream, accumulating debt it may not clear before the next burst. Concord applications are therefore written in allocate-free OCaml — minimising garbage collection pauses — and are profiled for efficient message triage.

The versioning story is strict. Concord has a single top-level message type that encompasses the entire protocol. Changing it requires updating every process simultaneously; rolling back mid-day means any messages already written to the log under the new type become unreadable by the old code. The first message of the day carries a digest of the full message type; a process that does not recognise it refuses to start. Patti notes this is not purely an implementation detail — the persistent transaction log imposes a forward-compatibility requirement that any broadcast architecture will feel, because there is no per-connection negotiation phase.

Aria: generalising the pattern

The overhead of running Concord — dedicated hardware, per-instance configuration, bespoke sequencer and re-transmitter setup — makes it impractical for small or experimental applications. Aria is Concord’s generalisation: a shared, centrally administered sequencer that any team can connect to.

Applications communicate with Aria’s core through a proxy layer rather than directly. The proxy filters the stream to the topics — hierarchical name-space paths — that each application subscribes to, so an application ingesting high-frequency market data does not impose that load on a toy application subscribing to a handful of administrative messages. The core itself treats payloads as opaque bytes; it does not parse them, so the bottleneck is raw byte throughput rather than message semantics.

The total ordering across all topics is preserved. This distinguishes Aria from systems like Kafka, where ordering is guaranteed only within a single shard. Patti and Minsky work through why this matters: a state machine that joins two Kafka topics can produce different results depending on which topic’s messages arrive first during a replay, because inter-topic ordering is not guaranteed. In Aria, any combination of topics can be composed into a reproducible state machine because every message, regardless of topic, has a position in the global sequence.

Write permissions in Aria are administered per sub-tree of the topic hierarchy. Read permissions are a work in progress: UDP multicast is difficult to gate at the application layer, so the current model is write-permissioned, read-open. The team is adding a best-effort read check at the library level.

Patti describes two missing features that Aria still needs before a broad rollout: rate limiting (a misbehaving client can flood the stream and consume disk and sequencer capacity at the expense of others) and snapshots. Snapshots would allow a process starting mid-session to load a compact summary of current state rather than replaying every message since the session began — critical as Aria moves toward week-long sessions rather than daily resets. The snapshot design is deliberately user-extensible: each application or team publishes a snapshot server suited to its own state machines, which may embed snapshot components published by upstream data providers.

Evangelising a different way of thinking

Aria requires programmers to relearn a core habit: you do not send messages; you propose them. The commonest class of bug in new Aria code is the infinite loop: an application that proposes message A, but fails to update its state when A is sequenced, and so keeps proposing A forever — what Minsky calls ‘the hypochondriac who thinks there’s always a problem.’ The cure is both cultural and mechanical. The team is building documentation and bootcamp exercises around the standard application patterns (the injector that reads external data onto the stream; the aggregator that joins multiple topics; the replicated service). They are also building abstractions — a pipe library that lets you push items in at one end and have them sequenced one at a time — that make the correct pattern the path of least resistance.

Related

• Doug Patti — speaker
• Ron Minsky — host
• Stephen Dolan on Memory Management, Garbage Collection, and OCaml — Signals and Threads; adjacent episode on OCaml’s runtime internals, the language in which Concord and Aria are written
• Will Wilson on Why Testing is Hard and How to Fix it — Signals and Threads; the testability argument Patti makes for inverted control connects directly to Wilson’s analysis of what makes distributed systems hard to test
• The Future of Software Engineering — theme; Concord and Aria represent a distinctive, production-proven answer to how large-scale concurrent software should be structured