24Resilience

On 1 October 2020, a memory module failed in one of the two devices of a shared disk system inside the Tokyo Stock Exchange’s trading system. Operations “were supposed to switch automatically” to the second device, but the automatic switch did not work for that kind of failure unless a setting had been changed, and it had not. Engineers switched over by hand at 9:26, less than half an hour after the market should have opened, and every function returned to normal. Trading nevertheless stayed halted for the whole day. Orders received before the exchange cut its network had been matched, and their executions had accumulated inside the system without being sent to the participants; only a limited number of participants could have resent their orders, and there were no agreed, tested rules for restarting. The hardware recovered in minutes; the state did not. This chapter is about the second problem: how a trading system keeps one agreed history of what it received and what it sent, so that when a machine fails another can take over in milliseconds without losing an order or sending one twice.

24.1 Failure modes of a trading system

Components fail in a few ways, and each needs a different answer. A process crashes, or its machine does: it stops, and the question is who takes over and from what state. A process hangs or slows down: it has not stopped, so it may come back and act after someone else has taken over, which is worse than a crash. A network link fails: each side may believe the other is dead while both are alive. A venue session drops: the orders at the venue carry on, may fill or may be cancelled by the venue (chapter 21), and the firm does not know which until it reconnects. And the failover machinery itself fails, as in Tokyo, because it runs only when something else has already gone wrong and is therefore the least exercised code in the system. The operational risk of One Quant Book 6 (chapter 28) is, for a trading system, mostly this list.

The design goal follows: every input the system acts on, and every order it sends, must be recorded before it matters, in one order that everyone agrees on, so that any machine can rebuild the state by replaying the record, and any order can be recognised if it is sent again.

24.2 Sequencer architectures

The sequencer turns many unordered sources into one ordered history. It is the input journal of chapter 23 lifted from one process to the system: the market data from the feed handler, the reports from the order gateway, the parameter changes from the control plane all become numbered entries of one journal. The strategy engine’s replay of chapter 23 becomes the normal way of running: a component is a function of the journal, and two components that read the same journal compute the same thing. The cost is one more hop on the path of every input (a microsecond in the build’s simulation, more when the journal is replicated before it is acknowledged), and a component whose own failure must be handled; the retail exchange whose architecture Fowler described (chapter 20) kept its business logic on one thread fed by exactly such a journal, from which its state could be rebuilt.

24.3 Replicated state machines and failover

The state machine approach is old and general (Schneider’s tutorial of 1990), and the hard part of it, agreeing on the next entry of the log when machines fail, is what consensus algorithms such as Raft (Ongaro and Ousterhout, 2014) solve. A trading system usually needs less: one sequencer writing the journal, replicated synchronously to a second machine, and a rule for deciding who is primary. The build’s replicas are the strategy state of the book in miniature: firm.sequencer’s replica trades a hundred shares against every price move with an immediate-or-cancel order, within a position limit, and keeps its orders by an identifier derived from the journal entry that created them. The Python, C++ and Rust replicas replay the fixture’s journal (a failover, with a second epoch, resends and a duplicate in it) to the same states, hash included.

Split brain is prevented by fencing. The journal carries an epoch, a number that only grows; each primary writes under the epoch in which it became primary, and a backup that takes over first raises the journal’s epoch. From then on, the journal refuses any append under an older epoch (Listing 24.1): a primary that was only slow, and wakes up still believing itself in charge, can compute what it likes but can no longer record anything, and nothing it has not recorded is sent. The gateway enforces the same rule on outputs, since the venue does not know about epochs.

    // The sequence number of the new entry; throws if the writer's epoch has been fenced off.
    std::int64_t append(Entry e) {
        if (e.epoch < epoch_) throw std::runtime_error("fenced: an older epoch cannot append");
        e.seq = static_cast<std::int64_t>(entries_.size()) + 1;
        entries_.push_back(e);
        return e.seq;
    }
    void fence(std::int64_t epoch) {
        if (epoch <= epoch_) throw std::runtime_error("a new epoch must be larger");
        epoch_ = epoch;
    }

Failure is detected by heartbeats: the primary sends one every millisecond, and the backup declares it dead after three missed. Detection is therefore the largest part of the build’s recovery time: 2.8 to $3.1\,\mathrm{m}\mathrm{s}$ from the failure to a backup that is primary, reconnected and reconciled, of which the reconnection and the replay of the missed reports take tens of microseconds. A shorter timeout recovers faster and declares more slow primaries dead, which is exactly when fencing matters. The backup in the build is hot: it applies every journal entry as it is written, so there is nothing to catch up. A cold backup must replay the journal first; the C++ replica applies it at about $37\,\mathrm{n}\mathrm{s}$ an entry, so a day’s journal of 37 million entries (chapter 23) takes about a second and a half, acceptable for a restart and not for a failover.

24.4 Exchange disconnects and recovery

The dangerous moment of a failover is the orders in the gap: those the old primary sent whose reports were never journaled. The new primary knows they exist, since it computed them from the journal, but not whether they left: the old primary may have died before sending, while the order was on the wire, or after the venue executed it and before the report came back. It has three ways to proceed (Listing 24.2). It can resend them at once under fresh identifiers, the habit of gateways that never reuse an identifier. It can first log in again, ask the venue for the reports it missed (the sequenced replay of chapter 21), reconcile, and resend only what is still unaccounted for. Or it can resend at once under the orders’ original identifiers, derived from the journal, and let the venue reject any copy of an order it already has.

    def takeover(t):
        state["leader"], state["took_over"] = "backup", t
        state["epoch"] += 1
        journal.fence(state["epoch"])
        pending = backup.unacknowledged()
        if procedure == "fresh ids, reconciled":
            push(t + 2 * WIRE_NS, "login")                # replay first; resend after it (see "login")
            return
        for i, (key, cl) in enumerate(pending):
            resend(t, key, cl, i)
        push(t + 2 * WIRE_NS, "login")

    def resend(t, key, cl, i):
        o = backup.open[cl]
        out.resent += 1
        if procedure == "idempotency keys":
            send(t, cl, o.side, o.qty, o.price)
        else:
            new = 10**9 * state["epoch"] + i + 1
            journal_append(t, "A", key[0], key[1], new)
            key_of_cl[new] = key
            send(t, new, o.side, o.qty, o.price)

Table 24.1 kills the primary at every stage of every one of the scenario’s 46 orders, against Book 10’s matching engine. With fresh identifiers and no reconciliation, a failure while an order is on the wire or at the venue but not yet reported sends it twice: 54 of the 184 cut points end with a duplicate, one for each of the 27 orders that filled, in each of the two stages, and the worst push the position past its limit, to 1 100 shares against 1 000. Reconciling first removes them all in this model, because every order is reported within $40\,\text{µ}\mathrm{s}$ and the venue replays its reports. Idempotent identifiers remove them regardless of the order of operations, which matters when the venue is slow to report or the session cannot be replayed: the participants of the Tokyo exchange in 2020 were in exactly that position. In every case the new primary’s state equals a fresh replay of the journal and the position the venue holds.

The same reasoning applies to a simple disconnect, without any failover: the gateway loses its session, logs in again asking for the reports it has not seen, applies them (the venue’s cancel on disconnect may have cancelled resting orders meanwhile), reconciles against the drop copy, and only then lets the strategy trade. Book 10’s simulator provides each piece: sequenced replay on login, cancel on disconnect, and the rejection of a duplicate client order identifier.

24.5 Testing failover

Failover code runs when something else has already failed, so it is the least tested code in a system unless it is tested on purpose, and the Tokyo incident is the standard example of a switch that worked for the failures it was tested against and not for the one that happened. The build’s test is the table: the primary is killed at every stage of every order of a scenario, and each run is checked against properties that must hold whatever the failure point (the new primary’s state equals a replay of the journal; its position equals the venue’s; no order is executed twice when idempotency keys are used). The properties matter more than the scenario; exhaustive cut points turn a rare event into a routine test. In production, the same idea is practised by failing over deliberately, on a schedule, so that the procedure is exercised when nothing else is wrong.

24.6 Tutorial: kill the primary everywhere

24.7 Build: the sequencer

24.8 Exercises

24.9 Problem: The Failover That Doubled the Orders

24.10 Interview questions