An exchange that never loses a cent: the deterministic engine of a prediction market

Financial systems · Rust · Node.js · gRPC · MemoryDB · PostgreSQL

A prediction market is an exchange where predictions are traded. Each event (“who wins the match?”) has several possible outcomes, and for each outcome contracts are bought and sold: a YES contract pays 1 if the outcome occurs, a NO contract pays 1 if it does not. The price of a YES contract, between 0.01 and 0.99, is therefore the probability the market assigns to that outcome. The platform never bets against its own users: it matches those who believe in an outcome with those who believe in the opposite, and earns a fee on every contract traded.

From an engineering standpoint, it is an unforgiving problem. Traffic concentrates in the last minutes of each event and on the same outcomes, that is, on the same order book. Every order moves money, and a rounding error, an order applied twice or two servers that disagree on the state are not cosmetic defects, but money created or destroyed. And since this is a regulated product, user protection controls and the reconciliation of funds are part of the system from day one.

For this platform we designed and built the entire system: backend, trading engine, apps for iOS, Android and web, back office and infrastructure. This article covers the engine: a state machine in Rust that keeps all trading state in memory and changes it only by applying, one at a time, the commands of a durable log. The idea that holds up everything else is that in a system that moves money, correctness has to be built as a verifiable property: if the state is a deterministic function of an ordered log, duplicates, restarts and replicas become harmless by construction, instead of being cases to handle one by one.

A single book per outcome turns accounting into a conservation law

There are four operations: buying or selling YES, buying or selling NO. The most obvious model treats YES and NO as two separate securities, each with its own book. But then someone buying YES at 0.40 and someone buying NO at 0.60, who together form exactly one pair worth 1, would never meet: a counterparty would be needed in between, which is precisely the role the platform chose not to play.

We gave each outcome a single order book, in which every price is a YES price. Buying NO at 0.60 is equivalent to an order at 0.40 on the NO side; selling a YES you own exposes you to the market just like buying a NO. The four operations end up on just two sides, and the same match has different but consistent effects depending on who is on the other side:

The advantage is not just liquidity. From this model follows an invariant that is simple to state: for each outcome, the YES contracts in circulation are always as many as the NO contracts, and every pair is backed by one unit of deposited money. The money that came in, minus the money that went out, always equals the balances, plus the money locked by open orders, plus the fees collected, plus the value of the pairs in circulation. Accounting becomes a conservation law, and a conservation law can be checked after every command.

The market rules are designed to respect it in every combination. Every order reserves in advance the maximum fee it could incur, even with tiered fees and maker discounts, and the system rejects any configuration in which a match would pay out more than it collects. The opening auction executes crossing orders at the single price that maximizes volume, with a computation verified against a quadratic reference implementation on 20,000 random books.

The bottleneck is a contended book, not the number of servers

The burst of orders on the same outcome when an event closes cannot be solved by adding servers: a book’s orders must be applied in a precise order, and balances are shared across all the books a user trades on. The most common approach, a relational database with a lock per order, would turn the burst into a queue of conflicting transactions exactly when it matters most.

We separated the jobs. The Node.js backend handles authentication, the catalog, regulatory checks and everything that is “application”. The engine keeps books, balances, contracts, fees and spending limits in memory, and applies commands on a single thread. This is the choice made by LMAX, Coinbase and TigerBeetle: with state shared across books, one thread per book would require coordination between threads and would make the replicas non-deterministic.

We chose the language by measuring the same simplified engine, with a large state, on batches of 1,000 orders:

The figure that matters is the maximum: Node.js’s 658 ms are a garbage collector pause, and in the engine of an exchange a pause like that tends to land exactly when the book is most crowded, because that is where allocation peaks. With no garbage collector, Rust keeps tail latency close to the median.

Determinism is a discipline, not a property of the code

A single thread guarantees an order, not the same result on different machines. Divergence between replicas rarely comes from a matching bug: it comes from details that look harmless, such as the system time, the iteration order of a map or a rounding. That is why the engine’s core is a library with no access to the network, the disk or the clock, with a single function that receives a command and returns a response and events. The result is the property the whole system rests on: the same commands, in the same order, produce the same state, the same responses and the same events, on any machine and on every re-run.

Every rule of the discipline closes off a concrete path to divergence. Time comes from the timestamp the log assigns to the command, never from the clock, so two replicas cannot decide differently whether an order arrived before or after the close. Hash maps are used only for lookups, never for iteration. Money is an integer throughout the system, in millionths on 64-bit integers, and an amount that is not a whole number of cents is rejected, never rounded. Every operation checks everything before writing, so a rejected command leaves the state as it was. Overflow checks stay enabled in production: a balance that “wraps around” would be applied by every replica and exported as true, while a stopped engine is a much smaller problem.

Two tools make determinism verifiable, not merely declared. An audit recomputes every invariant from scratch, from the conservation of money to the parity between YES and NO, and the tests run it after every command. A digest computes a 64-bit fingerprint of the entire state over an explicit canonical encoding, destructuring every structure field by field: adding a field to the state without including it in the digest does not compile, so the check stays valid after the next change too. Two replicas at the same position in the log must have the same digest, and a reloaded snapshot with a different digest is rejected.

A log instead of consensus

If the state is a function of the commands, it is enough to make the commands durable. What remains is deciding who establishes their order. The classic answer is a consensus protocol such as Raft, in which a leader elected by a majority of the nodes receives the commands and replicates them. Aeron Cluster, which implements it, offers sub-millisecond commits, but brings along an extra gateway, nodes with a stable identity and orchestrated releases. Kafka and Kinesis would have required a whole cluster for a single stream or about 200 ms of read delay, and a queue like SQS FIFO cannot be re-read.

We chose to entrust the order to the log rather than to a leader, and not to write any consensus code. Every command is written to a Redis stream hosted on Amazon MemoryDB, which acknowledges a write only once it is recorded in its transaction log across multiple availability zones. Every engine replica accepts commands, appends them to the log, reads the whole log and computes the whole state. There is no leader to elect, and two replicas running side by side during a release do not diverge, because they apply the same commands in the same order.

Removing the leader shifts three problems elsewhere.

The first is throughput. One log write per command, in our measurements, saturates at around 40,000 orders per second, and batching at fixed intervals would add waiting time even at low traffic. Instead, each replica has a single writer with a single write in flight, and the commands that arrived in the meantime go out together in the next entry: this is Martin Thompson’s smart batching, the same principle as group commit in databases. An isolated command goes out immediately, under load entries grow with traffic, and the ceiling rises to about 80,000 orders per second.

The second is time: if the engine does not read the clock, something has to tell it that an event must close. When an opening or a close is due, every replica appends a “tick” command, like Aeron Cluster timers: the first one applied performs the close, the others find nothing to do. The close stays exact to the millisecond, because an order with a later timestamp finds the event already closed even before a tick arrives. The backend has no cron jobs to open or close markets.

The third is reads. A read may reach a replica that is slightly behind, and a user must not see the order they just placed disappear. Every write returns its own position in the log, the app sends it back with the next read, and the replica waits, if needed, until it has applied it, as with Cosmos DB session tokens.

Retrying must be safe, from the app to the engine

A response can be lost after the command has been executed, and for an order, or worse for a withdrawal, “retry” has to mean “apply at most once”. The most common solution is an idempotency table in the backend, but here the effect happens in the engine, and an external table always leaves a window between execution and recording the outcome. We moved the guarantee to where the effect happens: the backend derives the command id from the app’s idempotency key, and the engine does the deduplication.

For a window of time, the engine remembers every applied id, together with a fingerprint of the command and the response it gave, rejections included: the same command repeated receives the original response with no effect, while a different command with the same id receives an explicit error, as in Stripe’s idempotent APIs and the IETF draft on the Idempotency-Key header. On this basis the backend handles uncertainty instead of hiding it: it retries for a few seconds with randomized backoff, always with the same id and even on another replica, and when time runs out it answers explicitly “outcome unknown, retry”. A failed write, a lost response or a replica that goes down right after the write: the command is applied at most once.

One detail separates a system that is idempotent in theory from one that really is: every automatic retry, from the app to the jobs that move money, must finish well before the engine forgets the command. The backend checks these constraints at startup and, if the configuration violates them, refuses to start. It is an error that would otherwise surface only in production, on the day someone lengthens a timeout.

The same mechanism protects money coming in and going out: every money movement uses the id of the business request as its own, and the balance is credited only after the payment has been reconciled. Spending limits, too, sit where correctness is simplest to guarantee: the engine enforces them in the same step in which it reserves the order’s money, so there is no room for a race between check and write.

Every output has an identity, and a duplicate costs nothing

The platform also needs a queryable history and real-time notifications. This is where a replicated system usually gets complicated: who exports, who writes the snapshots, how duplicates are avoided. Determinism makes it possible to answer without coordination, because every event has a deterministic identity: the position of the entry in the log plus a sequence number within it, the same on every replica and on every re-run.

Durable events leave the engine off the critical path, and PostgreSQL uses their identity as a unique key, discarding duplicates. This is why a standard SQS queue, which guarantees at-least-once delivery but may deliver a message more than once or out of order, is enough: redeliveries are harmless, and the order lives in the positions, not in the queue. One replica exports at a time, thanks to a lease, but the lease is there for efficiency, not correctness, in the sense described by Martin Kleppmann: if for a moment two replicas export together, the database only receives duplicates. Neither fencing nor consensus is needed. If the queue stays unreachable for a long time, the engine suspends new commands in a controlled way instead of running out of memory, and when it recovers nothing has been lost.

Snapshots follow the same reasoning: any replica can write one, precisely because the state at a given position is deterministic. So do notifications: every backend process forwards a replica’s gRPC stream to its own clients, without a shared broker, because all replicas produce the same notifications. Prices go out every 100 ms as full state, not as a difference, so a lost update is repaired by the next one.

The core is much faster than what feeds it

We measured performance in a benchmark environment, with an open-loop load generator: latency is measured from the moment the request was scheduled, as Gil Tene recommends, so queues cannot hide.

Every order measured on the core pays for everything a real order pays for: validation, money reservation, spending limits, matching, settlement of both parties, events and deduplication. Throughput through the log does not depend on commit latency, thanks to write batching. The core applies orders much faster than the log and the backend can deliver them: the headroom is where it should be.

Tests that compare the system with a simple reference

Determinism makes it possible to compare every result with a simple reference. Property-based tests generate random sessions of hundreds of commands, with a fixed seed and therefore reproducible, and verify that the invariants hold after every command, that two engines fed the same inputs agree on responses, events and digest, that the events are enough to rebuild every balance, and that matching gives the same results as a deliberately naive implementation.

The same goes for replicas: clusters of 2, 3, 6 and 10 replicas, under random concurrent traffic with duplicate submissions, sudden crashes, releases and restarts, must produce the same results as a single engine reading the log in order. In the tests on failover of the log’s primary node, the longest pause between two responses during a planned failover was about 50 ms, and with a stuck primary, writes resume within a few seconds without losing any acknowledged command. In the backend, race conditions and responses lost after an executed order are reproduced deterministically against a real engine binary, so a concurrency defect makes the test fail on every run, not once in a hundred.

A release is also a correctness problem, because for its entire duration two versions of the engine apply the same entries. Entry and snapshot formats are versioned, readers are released before writers, and a replica that encounters an entry it cannot read stops before applying it instead of diverging. The engine is thus updated with an ordinary rolling release.

The value for the platform

For a prediction market, the trading engine is the product: it decides who bought what, at what price, and who gets paid in the end. What we built gives the client three guarantees that do not depend on luck: money is conserved, as an audit run after every command in the tests verifies; every operation is applied at most once, from the app all the way to the log; every replica reaches the same state, which can be verified by comparing a fingerprint. These are also the choices that make the system simple to operate: a single thread for the sensitive work, durability and replication entrusted to a managed service, outputs that tolerate duplicates and restarts. New access points are added around the core without rewriting it.

The method applies beyond this project. Diverging replicas, lost responses, duplicate messages and restarts halfway through are not solved by handling them one by one, but by making the system deterministic and every one of its outputs identifiable. At that point repeating an operation is harmless, and correctness stops being a hope and becomes something the tests verify.