16Protocols II: Binary Exchange Protocols

A futures exchange sends every packet of its market data twice, over two separate networks, as binary messages at fixed offsets that a program reads without parsing. CME Group’s documentation tells its clients to “process both the Incremental Feed A and Incremental Feed B due to the unreliable nature of UDP transport”, to keep each sequence number from whichever line brings it first, and to treat a sequence number that neither brought as a loss on both lines, which calls for recovery. The feed handler’s first job is therefore not to understand the market but to keep the first copy of everything and forget the second. This chapter reads the binary protocols of the exchange simulator of One Quant Book 10, which follow the public Nasdaq specifications: order-by-order messages at fixed offsets, packets that carry sequence numbers over multicast, snapshot and retransmission channels for recovery, and order entry over a sequenced session. It generates the codecs from a schema instead of writing them by hand, arbitrates two lossy lines, and measures what decoding costs.

16.1 Order-by-order feeds and their messages

A venue’s direct feed (One Quant Book 1, chapter 9) publishes every event of its book: an order added, executed, reduced, deleted, replaced, a trade against hidden liquidity, an auction’s cross. This is the market-by-order view of One Quant Book 1, chapter 19, from which a subscriber rebuilds the book to any depth. Nasdaq’s TotalView-ITCH is the model the simulator follows: each message starts with a one-byte type, then fields at fixed offsets, with “all integer fields … big endian (network byte order)”. An Add Order is 36 bytes: the type at offset 0, a two-byte stock locate code at 1 (a small integer “employed with the intent of serving as an array index”), a tracking number at 3, a six-byte timestamp in nanoseconds since midnight at 5, the order reference at 11, the side at 19, the shares at 20, the symbol at 24 and the price at 32, an integer in ten-thousandths (Figure 16.1). Nothing needs to be searched: the price of an Add Order is always the four bytes at offset 32.

The build generates one flyweight per message from Book 10’s machine-readable schema, a reader and a writer, and a dispatcher that calls a visitor with the right type for a message’s first byte (Listing 16.1). Book 1’s decoder of chapter 28 did the opposite: it copied every message into a common structure and called a std::function for it. Both are correct; Figure 16.3 measures the difference.

// feed A: 36 bytes
struct FeedA {
    static constexpr char kType = 'A';
    static constexpr std::size_t kLength = 36;
    const std::uint8_t* p;
    std::uint16_t locate() const { return static_cast<std::uint16_t>(be16(p + 1)); }
    std::uint16_t tracking() const { return static_cast<std::uint16_t>(be16(p + 3)); }
    std::uint64_t ts() const { return be(p + 5, 6); }
    std::uint64_t ref() const { return be64(p + 11); }
    char side() const { return static_cast<char>(p[19]); }
    std::uint32_t shares() const { return static_cast<std::uint32_t>(be32(p + 20)); }
    std::string_view stock() const { return {reinterpret_cast<const char*>(p + 24), 8}; }
    std::uint32_t price() const { return static_cast<std::uint32_t>(be32(p + 32)); }

16.2 Packets, sequence numbers and multicast

Market data is published over UDP multicast because one packet then reaches every subscriber at the same time, whatever their number: MoldUDP64, the packet protocol of the simulator’s feed, is described by its specification as a “lightweight protocol layer built on top of UDP” in which “each outbound packet is transmitted only once regardless of the number of listeners”. UDP delivers without acknowledgement, retransmission or ordering, so the protocol above it carries what the receiver needs to notice a loss: each packet’s header gives the sequence number of its first message and the number of messages it carries (Figure 16.1). A packet whose first number is above the next expected one reveals a gap of the difference. When there is no data, the publisher sends heartbeats, packets with a count of zero carrying the next sequence number, “typically … once per second”, so that a loss is noticed even in a quiet market; a count of 65 535 marks the end of the session. The sequence numbers are those of One Quant Book 1, chapter 28, on a wire.

16.3 Incremental and snapshot channels, retransmission and recovery

A gap leaves the receiver two ways back. Retransmission asks a server for the missing sequence numbers: MoldUDP64 has a request packet for this, the simulator answers up to 1 000 messages per request from a window of its last 100 000, and a small gap is closed in a round trip. A gap beyond the window, or a receiver starting in the middle of the day, needs the snapshot channel: the simulator publishes, for each instrument, a begin marker with the incremental sequence number the snapshot reflects, the trading state, every displayed order in priority order, and an end marker with a checksum. The receiver keeps buffering incremental messages, waits for the next snapshot, loads it, discards the buffered messages the snapshot already reflects and applies the rest (the snapshot-and-delta pattern of One Quant Book 3, chapter 26, and the snapshot recovery of One Quant Book 10, chapter 26). CME’s snapshot messages carry the same synchronisation field, LastMsgSeqNumProcessed, “used to synchronize the snapshot loop with the real-time feed”. The recovery time is set by the snapshot interval, and Proposition 16.5 says how often it is needed.

16.4 Arbitration of redundant lines

    std::uint64_t on_packet(const std::uint8_t* p, std::uint64_t& first) {
        const firm::wire::MoldHeader h{p};
        const std::uint64_t seq = h.seq();
        const std::uint64_t count = h.count() == 0xFFFF ? 0 : h.count();
        if (count != 0 && seq + count <= next_) {
            ++c.duplicates;
            return 0;
        }
        if (seq > next_) {
            ++c.gaps;
            c.missing += seq - next_;
        }
        first = seq > next_ ? seq : next_;
        const std::uint64_t fresh = seq + count - first;
        c.messages += fresh;
        ++c.packets;
        if (seq + count > next_) next_ = seq + count;
        return fresh;
    }

Redundancy multiplies probabilities only when the lines fail independently, which is the point of sending them over separate networks, and the reason the simulator draws each line’s losses from its own random stream.

Burstiness does not change a line’s average loss rate, but it does change what a receiver sees: losses arrive in runs, several packets at once, too many for a quick retransmission at the worst moment. And a common cause, however rare, dominates: at $p = 10^{-4}$, independent losses on both lines cost $10^{-8}$ per packet, and a shared failure of $10^{-6}$ is a hundred times more.

Figure 16.2 runs the arithmetic on the simulator. Sixty seconds of a busy instrument, about 32 000 packets, with each line losing 0.1% of packets independently plus Gilbert–Elliott bursts, and a 60-millisecond outage on each line, the two overlapping by 25 milliseconds. Line A shows 56 gaps and 160 missing messages, line B 65 gaps and 186; the arbitrated stream shows two: the 17 messages published while both lines were out, and one packet lost on line B while line A was down.

Arbitration costs little: the build’s arbiter handles a packet in about $1.3\,\mathrm{n}\mathrm{s}$, a comparison of two sequence numbers. What costs is the design around it: two network interfaces, two paths through two sets of switches, and a feed handler that reads both without letting one line’s delay hold up the other (chapter 18).

16.5 Binary order entry and simple binary encoding

Order entry is binary too at most venues where speed matters. The simulator’s order-entry protocol (One Quant Book 10, chapter 26) runs over SoupBinTCP, which Nasdaq’s specification calls “a lightweight point-to-point protocol, built on top of TCP/IP sockets” that delivers the server’s sequenced messages in order “even across underlying TCP/IP socket connection failures”: its sequenced messages carry no explicit number, both sides count them, and a client that logs in again asks for the next number it wants. It plays the part of the FIX session of chapter 15 at a fraction of the cost: a new order is a 38-byte message with its fields at fixed offsets.

SBE is the FIX Trading Community’s answer to the same needs, standardised in 2016: its specification states a “preference for fixed positions and fixed length fields, supporting direct access to data”. The build derives an SBE-style schema for the simulator’s feed messages from the same JSON schema, little-endian, with the eight-byte message header and natural field sizes (the six-byte timestamp widened to eight), and generates a second set of flyweights from that XML alone.

  <sbe:message name="FeedA" id="65" blockLength="37">
    <field name="locate" id="1" type="uint16" offset="0" />
    <field name="tracking" id="2" type="uint16" offset="2" />
    <field name="ts" id="3" type="uint64" offset="4" />
    <field name="ref" id="4" type="uint64" offset="12" />
    <field name="side" id="5" type="char" offset="20" />
    <field name="shares" id="6" type="uint32" offset="21" />
    <field name="stock" id="7" type="alpha8" offset="25" />
    <field name="price" id="8" type="uint32" offset="33" />
  </sbe:message>

Figure 16.3 compares the decoders on 60 seconds of line A. Book 1’s decoder, which copies each message and calls a std::function, takes about $11\,\mathrm{n}\mathrm{s}$ per message; the generated flyweights about $5\,\mathrm{n}\mathrm{s}$, whichever the byte order: a byte swap is one instruction and costs nothing measurable here, while the copy and the indirect call cost half. Framing whole packets and dispatching every message costs about $7\,\mathrm{n}\mathrm{s}$ per message in C++ and $8\,\mathrm{n}\mathrm{s}$ in Rust. At a million messages a second, decoding is under 1% of a core: the protocol was designed for that.

16.6 Tutorial: generated codecs and two lossy lines

16.7 Build: the wire codecs

16.8 Exercises

16.9 Problem: Two Copies of Everything

16.10 Interview questions