Parsing Market Data: Binary Protocols Without Copies
Decode a binary market-data feed into typed events with bounds-checked reads, explicit byte order and no struct casts, then rebuild the book and recover from gaps.
A feed is a stream of changes, not a picture
An exchange does not send its customers a copy of the order book every time something happens. It sends a market-data feed: a stream of small messages, each describing one change. "Order 42 was added: buy 25 lots at 10003 ticks." "Order 42 lost 10 lots to a trade." "Order 42 was cancelled." A consumer who starts from an empty book and applies every message, in order, ends up with the same book the exchange has. That is the whole contract, and it has two sides.
The first side is speed and size. A busy instrument can produce a very large number of these messages, so feeds are binary: integers are sent as raw bytes, not as decimal text, and each message is a few dozen bytes. Parsing them is the first thing a trading system does with every piece of information it receives, so the parser has to be fast. It also has to be correct on bytes it did not choose, because those bytes come from a network.
The second side is loss. Many feeds are sent over UDP multicast: one packet from the exchange reaches every subscriber, and nobody retransmits a packet that a subscriber missed. Every message therefore carries a sequence number, consecutive across the feed. A consumer that sees 7, 8, 11 knows that 9 and 10 are missing, and that its book is now wrong. A consumer that sees 5 twice knows to ignore the second copy. Feeds that work this way usually come with a separate snapshot service (the full book as of some sequence number) or a retransmission service (send me messages 9 to 10 again) so that a consumer can repair itself.
Terms from the order book lesson carry over: an order rests in the book at a price, measured in integer ticks (the smallest allowed price step; with the course's tick of 0.01, 10003 ticks is 100.03); an execution (or fill) is a trade against a resting order, which reduces its quantity. This lesson builds a parser for a small binary feed format, decodes it into typed events, rebuilds a book from those events, and handles gaps and duplicates. Everything is synthetic: the format is this course's own, and the data comes from a seeded generator.
Byte order and why a struct is not a message
A 32-bit integer occupies four bytes, and there are two common conventions for the order in which they are written. Big-endian puts the most significant byte first. It is called network byte order because many Internet protocol headers use it. Little-endian puts the least significant byte first, and it is how x86-64 and (in their usual configuration) ARM processors store integers in memory.
A protocol has to pick one, and different protocols pick differently. Nasdaq's TotalView-ITCH 5.0 specification states that all integer fields are big-endian. The FIX Trading Community's Simple Binary Encoding (SBE) lets each message schema declare its byte order and makes little-endian the default. Neither choice is wrong. What is wrong is not knowing which one you are reading.
The first program reads the same four bytes both ways, then compares the layout of a message on the wire with the layout of a C++ struct that has the same fields:
#include <bit>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <print>
static_assert(std::endian::native == std::endian::little ||
std::endian::native == std::endian::big, "mixed-endian machine");
// Read 4 bytes as a big-endian number: the first byte is the most significant.
std::uint32_t be_by_shifts(const unsigned char* p) {
return std::uint32_t(p[0]) << 24 | std::uint32_t(p[1]) << 16 |
std::uint32_t(p[2]) << 8 | std::uint32_t(p[3]);
}
// The same bytes read the other way round: the first byte is the least significant.
std::uint32_t le_by_shifts(const unsigned char* p) {
return std::uint32_t(p[3]) << 24 | std::uint32_t(p[2]) << 16 |
std::uint32_t(p[1]) << 8 | std::uint32_t(p[0]);
}
// The usual fast form: copy the bytes into a local, swap if the machine is little-endian.
std::uint32_t load_be32(const unsigned char* p) {
std::uint32_t v;
std::memcpy(&v, p, sizeof v); // any alignment, no aliasing question
if constexpr (std::endian::native == std::endian::little) v = std::byteswap(v);
return v;
}
// What the Add message would look like as a C++ struct.
struct AddAsStruct {
char type;
std::uint32_t seq;
std::uint64_t id;
char side;
std::uint32_t price;
std::uint32_t qty;
};
int main() {
const unsigned char wire[] = {0x00, 0x00, 0x30, 0x39};
std::println("bytes on the wire: 00 00 30 39");
std::println("read big-endian: {}", be_by_shifts(wire));
std::println("read little-endian: {}", le_by_shifts(wire));
std::println("load_be32: {}", load_be32(wire));
std::println("\nfield wire offset struct offset");
std::println("seq {:>11} {:>13}", 1, offsetof(AddAsStruct, seq));
std::println("id {:>11} {:>13}", 5, offsetof(AddAsStruct, id));
std::println("side {:>11} {:>13}", 13, offsetof(AddAsStruct, side));
std::println("price {:>11} {:>13}", 14, offsetof(AddAsStruct, price));
std::println("qty {:>11} {:>13}", 18, offsetof(AddAsStruct, qty));
std::println("size {:>11} {:>13}", 22, sizeof(AddAsStruct));
}Press Run to compile and run this example.
bytes on the wire: 00 00 30 39
read big-endian: 12345
read little-endian: 959447040
load_be32: 12345
field wire offset struct offset
seq 1 4
id 5 8
side 13 16
price 14 20
qty 18 24
size 22 32The bytes 00 00 30 39 mean 12345 to a big-endian reader and 959447040 to a little-endian one. Nothing in the bytes says which is meant; only the specification does. load_be32 is the form you will see in real parsers: std::memcpy the bytes into a local integer, then std::byteswap (C++23, in <bit>) if the machine is little-endian. std::endian::native (C++20) is a compile-time constant, so if constexpr removes the branch entirely. With optimization on, compilers can turn both this and the shift version into one load and one byte-reverse instruction. Apple Clang 21 at -O2 on AArch64, the compiler this lesson was checked with, does exactly that; look at your own compiler's assembly output before you rely on it.
The second half of the output is the reason you cannot simply cast a pointer to the received bytes to a struct pointer. The struct column shows offsets for the usual 64-bit ABIs (x86-64 and AArch64); the standard leaves padding to the implementation, which is part of the problem. The compiler inserts padding so that each field starts at a multiple of its alignment: 3 bytes after type, 3 after side, 4 at the end. The wire format has no padding, because every byte costs bandwidth. In TotalView-ITCH's Add Order message, for example, the 8-byte order reference number starts at offset 11.
The picture shows the same thing. Each cell is one byte; red cells are padding.
#include <cstddef>
#include <cstdint>
#include <print>
struct AddAsStruct { // the tempting struct from the first program
char type;
std::uint32_t seq;
std::uint64_t id;
char side;
std::uint32_t price;
std::uint32_t qty;
};
struct Field { const char* name; std::size_t wire_at, size, struct_at; };
constexpr double kCell = 18; // width of one byte in the picture
void row(double y, const char* label, std::size_t total) {
std::println(R"(<text x="2" y="{}" font-size="10">{}</text>)", y + 13, label);
for (std::size_t i = 0; i < total; ++i) // every byte starts as padding (red)
std::println(R"(<rect x="{}" y="{}" width="{}" height="18" fill="#dc2626" )"
R"(fill-opacity="0.25" stroke="#1f2937" stroke-width="0.5"/>)",
50 + i * kCell, y, kCell);
}
void field(double y, std::size_t at, const Field& f) {
std::println(R"(<rect x="{}" y="{}" width="{}" height="18" fill="#ffffff" )"
R"(stroke="#1f2937"/>)", 50 + at * kCell, y, f.size * kCell);
std::println(R"(<rect x="{}" y="{}" width="{}" height="18" fill="#2563eb" )"
R"(fill-opacity="0.2" stroke="#1f2937"/>)", 50 + at * kCell, y,
f.size * kCell);
std::println(R"(<text x="{}" y="{}" font-size="9" text-anchor="middle">{}</text>)",
50 + (at + f.size / 2.0) * kCell, y + 12, f.name);
}
int main() {
const Field fields[] = {
{"type", 0, 1, offsetof(AddAsStruct, type)},
{"seq", 1, 4, offsetof(AddAsStruct, seq)},
{"id", 5, 8, offsetof(AddAsStruct, id)},
{"side", 13, 1, offsetof(AddAsStruct, side)},
{"price", 14, 4, offsetof(AddAsStruct, price)},
{"qty", 18, 4, offsetof(AddAsStruct, qty)},
};
std::println(R"(<svg viewBox="0 0 640 100">)");
row(10, "wire", 22);
row(50, "struct", sizeof(AddAsStruct));
for (const Field& f : fields) {
field(10, f.wire_at, f);
field(50, f.struct_at, f);
}
for (std::size_t i = 0; i <= 32; i += 8) // byte offsets under the struct row
std::println(R"(<text x="{}" y="84" font-size="8">{}</text>)", 48 + i * kCell, i);
std::println("</svg>");
}Press Run to compile and run this example.
Even if the layouts matched (say, with a non-standard #pragma pack), a cast would still be wrong in three ways:
- Alignment. Reading a
std::uint64_tat an address that is not a multiple of its alignment is undefined behavior in C++. Some processors fault; others are slower; UBSan reports it. - Object lifetime and aliasing. There is no
AddAsStructobject in a receive buffer of bytes. Reading one through a cast pointer accesses storage through a type that does not live there, which the aliasing rules make undefined. The optimizer is allowed to assume you did not do it. - Byte order. A cast reads integers in the machine's order. On a little-endian machine every big-endian field comes out byte-reversed, as the 959447040 above shows.
std::memcpy from the buffer into a local variable avoids all three: it has no alignment requirement, it copies bytes into an object that really exists, and the swap fixes the order afterward. std::bit_cast (C++20) does the same for a value you already hold, such as a std::array of bytes: it requires both types to be trivially copyable and of equal size, and checks that at compile time. If you want a refresher on what undefined behavior permits the compiler to do, see Undefined Behavior.
A reader that cannot run off the end
Real decoding needs two small tools. A writer appends integers in big-endian order; we need it only to produce test feeds inside our programs. A reader walks through a std::span<const std::byte> (a pointer and a length, no ownership, no copy of the data) and hands out integers.
The reader's one rule is that it never touches a byte outside its span. When a read would go past the end, it returns zero and sets a sticky failure flag that stays set. Code that decodes a message can then perform all its reads and check ok() once, instead of checking after every field. If it forgets to check, it gets zeros, not a crash or a read of someone else's memory.
#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <print>
#include <span>
#include <vector>
// Appends each value in big-endian order.
template <std::unsigned_integral... T>
void put(std::vector<std::byte>& out, T... values) {
auto one = [&]<class U>(U v) {
if constexpr (std::endian::native == std::endian::little) v = std::byteswap(v);
auto raw = std::bit_cast<std::array<std::byte, sizeof(U)>>(v);
out.insert(out.end(), raw.begin(), raw.end());
};
(one(values), ...);
}
class Reader { // reads big-endian integers; never reads outside the span
public:
explicit Reader(std::span<const std::byte> buf) : buf_(buf) {}
std::span<const std::byte> take(std::size_t n) {
if (remaining() < n) { failed_ = true; pos_ = buf_.size(); return {}; }
pos_ += n;
return buf_.subspan(pos_ - n, n);
}
template <std::unsigned_integral T> T get() {
std::array<std::byte, sizeof(T)> raw{}; // zeros if the read fails
if (auto src = take(sizeof(T)); !src.empty())
std::memcpy(raw.data(), src.data(), sizeof(T));
T v = std::bit_cast<T>(raw);
if constexpr (std::endian::native == std::endian::little) v = std::byteswap(v);
return v;
}
std::size_t remaining() const { return buf_.size() - pos_; }
bool ok() const { return !failed_; } // sticky: false after any failed read
private:
std::span<const std::byte> buf_;
std::size_t pos_ = 0;
bool failed_ = false;
};
int main() {
using U8 = std::uint8_t;
using U16 = std::uint16_t;
using U32 = std::uint32_t;
using U64 = std::uint64_t;
// An add message: length 22, type 'A', seq 7, id 42, side 'B', price 10003, qty 25.
std::vector<std::byte> wire;
put(wire, U16{22}, U8{'A'}, U32{7}, U64{42}, U8{'B'}, U32{10003}, U32{25});
std::print("{} bytes:", wire.size());
for (std::byte b : wire) std::print(" {:02x}", std::to_integer<unsigned>(b));
std::println("");
Reader r(wire);
auto length = r.get<U16>();
auto type = r.get<U8>();
auto seq = r.get<U32>();
auto id = r.get<U64>();
auto side = r.get<U8>();
auto price = r.get<U32>();
auto qty = r.get<U32>();
std::println("length={} type={:c} seq={} id={} side={:c} price={} qty={}",
length, type, seq, id, side, price, qty);
std::println("ok={} remaining={}", r.ok(), r.remaining());
auto extra = r.get<U32>(); // one read too many
std::println("extra={} ok={} remaining={}", extra, r.ok(), r.remaining());
}Press Run to compile and run this example.
24 bytes: 00 16 41 00 00 00 07 00 00 00 00 00 00 00 2a 42 00 00 27 13 00 00 00 19
length=22 type=A seq=7 id=42 side=B price=10003 qty=25
ok=true remaining=0
extra=0 ok=false remaining=0The 24 bytes start with 00 16, the length 22 in big-endian. Then 41 is the character 'A', 00 00 00 07 is the sequence number, the 8-byte id ends in 2a (42), 42 is 'B', 00 00 27 13 is 10003, and 00 00 00 19 is 25. The last read asks for 4 more bytes when none are left: it returns 0, ok() becomes false, and nothing outside the buffer is read.
Note what is not happening. The reader never allocates and never copies the message to an intermediate buffer; take returns a sub-span that points into the original bytes. Each field is loaded straight from the receive buffer into a local integer. That is what "without copies" means for a parser: the only memory traffic is the bytes you actually need, once.
The course's feed format
The format used for the rest of this course is deliberately small. The message letters follow TotalView-ITCH's meanings for the same events (A add, D delete, E executed), but the layouts are our own and do not match ITCH's. Every message is a frame: a 2-byte big-endian length, followed by that many bytes of body.
frame: u16 length | body (length bytes)
body: u8 type | u32 seq | u64 id | ...
'A' add ... | u8 side ('B' or 'S') | u32 price (ticks) | u32 qty 22 bytes
'D' cancel ... (nothing more) 13 bytes
'E' execute ... | u32 qty (lots executed against resting order id) 17 bytes
all integers big-endian, unsignedThe length prefix is what makes the stream robust to message types the consumer does not know: it can skip a frame it does not understand, because it knows where the next one starts. MoldUDP64, the transport Nasdaq uses for ITCH over UDP, frames messages the same way (a 2-byte big-endian message length before each message). The price and quantity are 32-bit on the wire but become the course's 64-bit Price and Qty in memory. Wire types are chosen for size; in-memory types are chosen so that arithmetic on them does not overflow (lesson 6 has the details).
Real feeds also carry messages that do not change the visible book. TotalView-ITCH, for example, has a Trade message for executions of non-displayed orders, which its specification says can be ignored by a consumer that only builds the book. Our format leaves them out.
Decoding into typed events
The decoder turns a frame into one of three event types held in a std::variant, or into an error held in a std::expected (C++23). The order matters:
- Read the type byte. Unknown type: reject the message, but the frame boundary is still known, so the stream continues.
- Compare the body length with the size this type must have. Mismatch: reject. After this check, every field read is known to be in bounds; the per-read checks in the reader are a second line of defense, not the main one.
- Read the fields and validate their values: the side must be
BorS, quantities must be positive.
The test buffer below is written out byte by byte, as it might arrive from the network, and contains one of each problem.
#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <expected>
#include <print>
#include <span>
#include <variant>
#include <vector>
using Price = std::int64_t;
using Qty = std::int64_t;
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct AddOrder { std::uint32_t seq; Order order; };
struct CancelOrder { std::uint32_t seq; OrderId id; };
struct ExecuteOrder { std::uint32_t seq; OrderId id; Qty qty; };
using Event = std::variant<AddOrder, CancelOrder, ExecuteOrder>;
template <class... F> struct Overloaded : F... { using F::operator()...; };
class Reader { // reads big-endian integers; never reads outside the span
public:
explicit Reader(std::span<const std::byte> buf) : buf_(buf) {}
std::span<const std::byte> take(std::size_t n) {
if (remaining() < n) { failed_ = true; pos_ = buf_.size(); return {}; }
pos_ += n;
return buf_.subspan(pos_ - n, n);
}
template <std::unsigned_integral T> T get() {
std::array<std::byte, sizeof(T)> raw{}; // zeros if the read fails
if (auto src = take(sizeof(T)); !src.empty())
std::memcpy(raw.data(), src.data(), sizeof(T));
T v = std::bit_cast<T>(raw);
if constexpr (std::endian::native == std::endian::little) v = std::byteswap(v);
return v;
}
std::size_t remaining() const { return buf_.size() - pos_; }
bool ok() const { return !failed_; } // sticky: false after any failed read
private:
std::span<const std::byte> buf_;
std::size_t pos_ = 0;
bool failed_ = false;
};
// Each message is [u16 length][body]. Body: u8 type, u32 seq, u64 id, then
// 'A': u8 side ('B' or 'S'), u32 price, u32 qty 'D': nothing 'E': u32 qty
constexpr std::size_t body_size(std::uint8_t type) {
return type == 'A' ? 22 : type == 'D' ? 13 : type == 'E' ? 17 : 0;
}
enum class ParseError { Truncated, UnknownType, BadLength, BadSide, ZeroQty };
std::expected<std::span<const std::byte>, ParseError> next_frame(Reader& r) {
auto body = r.take(r.get<std::uint16_t>());
if (!r.ok()) return std::unexpected(ParseError::Truncated);
return body;
}
std::expected<Event, ParseError> decode(std::span<const std::byte> body) {
if (body.empty()) return std::unexpected(ParseError::Truncated);
Reader r(body);
auto type = r.get<std::uint8_t>();
if (body_size(type) == 0) return std::unexpected(ParseError::UnknownType);
if (body.size() != body_size(type)) return std::unexpected(ParseError::BadLength);
// Every read below is in bounds: the length was checked once, above.
auto seq = r.get<std::uint32_t>();
OrderId id = r.get<std::uint64_t>();
if (type == 'D') return CancelOrder{seq, id};
if (type == 'E') {
Qty qty = r.get<std::uint32_t>();
if (qty == 0) return std::unexpected(ParseError::ZeroQty);
return ExecuteOrder{seq, id, qty};
}
auto side = r.get<std::uint8_t>();
Price price = r.get<std::uint32_t>();
Qty qty = r.get<std::uint32_t>();
if (side != 'B' && side != 'S') return std::unexpected(ParseError::BadSide);
if (qty == 0) return std::unexpected(ParseError::ZeroQty);
return AddOrder{seq, {id, side == 'B' ? Side::Buy : Side::Sell, price, qty}};
}
void print_event(const Event& ev) {
std::visit(Overloaded{
[](const AddOrder& m) {
std::println("#{} add id={} {} {} @ {}", m.seq, m.order.id,
m.order.side == Side::Buy ? "buy" : "sell", m.order.qty,
m.order.price); },
[](const CancelOrder& m) { std::println("#{} cancel id={}", m.seq, m.id); },
[](const ExecuteOrder& m) {
std::println("#{} execute id={} qty={}", m.seq, m.id, m.qty); },
}, ev);
}
// Bytes as they might arrive from the network, one message per line.
constexpr unsigned char kFeed[] = {
0,22, 'A', 0,0,0,1, 0,0,0,0,0,0,0,42, 'B', 0,0,0x27,0x13, 0,0,0,25, // add
0,17, 'E', 0,0,0,2, 0,0,0,0,0,0,0,42, 0,0,0,10, // execute
0,3, 'Z', 0,0, // new type
0,22, 'A', 0,0,0,4, 0,0,0,0,0,0,0,43, 'Q', 0,0,0x27,0x13, 0,0,0,5, // side 'Q'
0,12, 'D', 0,0,0,5, 0,0,0,0,0,0,0, // 12, not 13
0,13, 'D', 0,0,0,6, 0,0,0,0,0,0,0,42, // cancel
0,13, 'D', 0,0,0,7, // cut off
};
int main() {
const char* error_name[] = {"truncated", "unknown type", "bad length", "bad side",
"zero quantity"};
Reader r(std::as_bytes(std::span(kFeed)));
while (r.remaining() > 0) {
auto frame = next_frame(r);
if (!frame) {
std::println("frame error: {}; stop reading", error_name[int(frame.error())]);
break;
}
if (auto ev = decode(*frame)) print_event(*ev);
else std::println("rejected: {}", error_name[int(ev.error())]);
}
}Press Run to compile and run this example.
#1 add id=42 buy 25 @ 10003
#2 execute id=42 qty=10
rejected: unknown type
rejected: bad side
rejected: bad length
#6 cancel id=42
frame error: truncated; stop readingTwo kinds of failure behave differently, and the difference is the most important design decision in a parser. A bad message (unknown type, wrong length, bad side) is contained: the frame told us where the message ends, so we report it and move on. A bad frame (the length says 13 bytes, but only 5 remain) is not: we no longer know where the next message starts, so the only safe action is to stop. In a live system that last case usually means the data arrived incomplete; the bytes may come in the next read from the socket, and a stream parser keeps the partial frame until they do.
std::expected<Event, ParseError> makes both outcomes explicit in the signature, so a caller cannot use an event without first checking that there is one. optional, variant and expected covers the three vocabulary types in more depth.
Rebuilding the book from the feed
Our feed is market by order: every message names an individual order. Many consumers want market by price instead: for each price, the total quantity resting there. A book builder keeps both. It needs the orders, because an execute message names only an order id and the consumer must remember that order's side and price. It publishes the price levels, because that is what strategies and screens read.
The program below is the test that matters for a book builder. A generator plays the exchange: it adds, cancels and executes orders at random (seeded), always against orders that exist, and records what its own book contains. The builder sees only the events. At the end, the two sets of price levels must be identical. Executions go to the oldest order at the best price, which is the price-time priority from lesson 1. A matching engine like the one in lesson 2 would publish one execute message per fill.
This program works on decoded events rather than bytes. Parsing and book building are separate layers, so each gets its own test; the round-trip test later in this lesson connects them.
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iterator>
#include <map>
#include <print>
#include <unordered_map>
#include <variant>
#include <vector>
using Price = std::int64_t;
using Qty = std::int64_t;
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct AddOrder { std::uint32_t seq; Order order; };
struct CancelOrder { std::uint32_t seq; OrderId id; };
struct ExecuteOrder { std::uint32_t seq; OrderId id; Qty qty; };
using Event = std::variant<AddOrder, CancelOrder, ExecuteOrder>;
template <class... F> struct Overloaded : F... { using F::operator()...; };
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { // inclusive
return lo + int(next() % std::uint32_t(hi - lo + 1));
}
};
// Price levels: total resting quantity at each price. Bids best (highest) first.
struct Levels {
std::map<Price, Qty, std::greater<>> bids;
std::map<Price, Qty> asks;
void change(const Order& o, Qty delta) {
auto bump = [&](auto& side) {
if ((side[o.price] += delta) == 0) side.erase(o.price);
};
if (o.side == Side::Buy) bump(bids); else bump(asks);
}
bool operator==(const Levels&) const = default;
};
// The consumer: turns order-by-order events into price levels.
class BookBuilder {
public:
void apply(const Event& ev) {
std::visit(Overloaded{
[&](const AddOrder& m) { orders_[m.order.id] = m.order;
levels.change(m.order, m.order.qty); },
[&](const CancelOrder& m) { reduce(m.id, -1); },
[&](const ExecuteOrder& m) { reduce(m.id, m.qty); },
}, ev);
}
Levels levels;
int errors = 0; // events that refer to orders we do not know: book is suspect
private:
void reduce(OrderId id, Qty qty) { // qty -1 means "all of it"
auto it = orders_.find(id);
if (it == orders_.end() || qty > it->second.qty) { ++errors; return; }
Qty taken = qty < 0 ? it->second.qty : qty;
levels.change(it->second, -taken);
if ((it->second.qty -= taken) == 0) orders_.erase(it);
}
std::unordered_map<OrderId, Order> orders_;
};
int main() {
// The exchange side: a random but consistent sequence of book events.
Lcg rng{2024};
std::map<OrderId, Order> live; // ordered by id, so oldest first
std::vector<Event> feed;
std::uint32_t seq = 0;
OrderId next_id = 1;
for (int step = 0; step < 3000; ++step) {
int roll = rng.range(0, 9);
if (live.size() < 4 || roll < 4) {
Side side = rng.range(0, 1) ? Side::Buy : Side::Sell;
Price price = side == Side::Buy ? rng.range(9990, 9999)
: rng.range(10001, 10010);
Order o{next_id++, side, price, rng.range(1, 50)};
live[o.id] = o;
feed.push_back(AddOrder{++seq, o});
} else if (roll < 7) {
auto it = std::next(live.begin(), rng.range(0, int(live.size()) - 1));
feed.push_back(CancelOrder{++seq, it->first});
live.erase(it);
} else { // execute against the oldest order at the best price of one side
Side side = rng.range(0, 1) ? Side::Buy : Side::Sell;
auto best = live.end();
for (auto it = live.begin(); it != live.end(); ++it) {
const Order& o = it->second;
if (o.side != side) continue;
if (best == live.end() || // test first: never dereference end()
(side == Side::Buy ? o.price > best->second.price
: o.price < best->second.price))
best = it;
}
if (best == live.end()) continue;
Qty qty = rng.range(1, int(best->second.qty));
feed.push_back(ExecuteOrder{++seq, best->first, qty});
if ((best->second.qty -= qty) == 0) live.erase(best);
}
}
Levels truth;
for (const auto& [id, o] : live) truth.change(o, o.qty);
BookBuilder book;
for (const Event& ev : feed) book.apply(ev);
std::println("events: {}, resting orders: {}, errors: {}", feed.size(), live.size(),
book.errors);
std::println("books equal: {}", book.levels == truth);
std::println("{:>8} {:>6} {:>8}", "bid qty", "price", "ask qty");
std::vector<std::pair<Price, Qty>> asks(book.levels.asks.begin(),
book.levels.asks.end());
for (int i = std::min(3, int(asks.size())) - 1; i >= 0; --i) // best ask lowest
std::println("{:>8} {:>6} {:>8}", "", asks[i].first, asks[i].second);
int shown = 0;
for (const auto& [price, qty] : book.levels.bids)
if (shown++ < 3) std::println("{:>8} {:>6} {:>8}", qty, price, "");
}Press Run to compile and run this example.
events: 3000, resting orders: 73, errors: 0
books equal: true
bid qty price ask qty
10004 12
10003 68
10002 26
22 9999
46 9998
16 9997Three thousand events, 73 orders left resting, no event that referred to an unknown order, and identical levels. The errors counter is worth having in production too: an execute or cancel for an order id the builder has never seen means its book has diverged from the exchange's, usually because of a missed message. The right reaction is the same as for a sequence gap.
BookBuilder keeps its orders in a std::unordered_map for constant-time lookup by id. It never iterates over that map, which is what keeps its behavior independent of hash ordering. The price levels live in ordered maps because the best bid and best ask are what consumers ask for most.
Sequence numbers, gaps and recovery
Every message has a sequence number one higher than the previous message's. That gives a consumer three cases for each message it receives:
seq == expected: apply it and incrementexpected.seqlower thanexpected: a duplicate (or a replay of something already applied). Ignore it.seqhigher thanexpected: a gap. Messages were lost. The book is now stale: it may be wrong, and nothing downstream should trade on it.
A gap needs a recovery policy. The common choices are a retransmission request for the missing range (MoldUDP64 defines a request packet for exactly this, answered by a re-request server) and waiting for a snapshot: the full book as of some sequence number S, published periodically or on request. Either way, messages that arrive during recovery must be buffered, because after the repair they are still needed.
The next program implements the snapshot policy. To keep it short, a message is a signed change to one order's quantity and the book is a map from order id to remaining quantity; the sequencing logic is the same for the full format. The simulated network loses messages 9 and 10 and delivers 5 twice. The exchange takes a snapshot after every 10th message, and each snapshot reaches the consumer three messages later.
#include <algorithm>
#include <cstdint>
#include <iterator>
#include <map>
#include <print>
#include <variant>
#include <vector>
using Qty = std::int64_t;
using OrderId = std::uint64_t;
// To keep the program short, a message is a signed change to one order's quantity
// and the book is a map from order id to remaining quantity.
struct Msg { std::uint32_t seq; OrderId id; Qty delta; };
using Book = std::map<OrderId, Qty>;
struct Snapshot { std::uint32_t seq; Book book; }; // the book after message `seq`
void apply_change(Book& book, const Msg& m) {
if ((book[m.id] += m.delta) == 0) book.erase(m.id);
}
class FeedHandler {
public:
void on_message(const Msg& m) {
if (recovering_) { buffered_.push_back(m); return; }
if (m.seq < expected_) {
std::println("#{}: duplicate, ignored", m.seq);
return;
}
if (m.seq > expected_) {
std::println("#{}: gap, #{}..#{} missing; book is stale, buffering",
m.seq, expected_, m.seq - 1);
recovering_ = true;
buffered_.push_back(m);
return;
}
apply_change(book, m);
++expected_;
}
void on_snapshot(const Snapshot& s) {
if (!recovering_) return; // live and in sequence: nothing to repair
if (!buffered_.empty() && s.seq + 1 < buffered_.front().seq) return; // too old
book = s.book;
expected_ = s.seq + 1;
recovering_ = false;
std::vector<Msg> pending;
pending.swap(buffered_);
auto newer = std::ranges::count_if(pending,
[&](const Msg& m) { return m.seq > s.seq; });
std::println("snapshot @{}: book replaced; {} buffered, {} newer to replay",
s.seq, pending.size(), newer);
for (const Msg& m : pending) // older ones are already inside the snapshot
if (m.seq > s.seq) on_message(m);
}
Book book;
private:
std::uint32_t expected_ = 1;
bool recovering_ = false;
std::vector<Msg> buffered_;
};
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { // inclusive
return lo + int(next() % std::uint32_t(hi - lo + 1));
}
};
int main() {
// The exchange: 30 messages, and a snapshot of its book after every 10th,
// which reaches the consumer three messages later.
Lcg rng{7};
Book exchange;
std::vector<std::variant<Msg, Snapshot>> wire; // what the consumer receives
std::vector<Snapshot> snapshots;
OrderId next_id = 1;
for (std::uint32_t seq = 1; seq <= 30; ++seq) {
Msg m{seq, next_id, rng.range(1, 9)}; // add a new order...
if (exchange.size() >= 3 && rng.range(0, 1)) { // ...or reduce an existing one
int pick = rng.range(0, int(exchange.size()) - 1);
auto it = std::next(exchange.begin(), pick);
m = {seq, it->first, -rng.range(1, int(it->second))};
} else {
++next_id;
}
apply_change(exchange, m);
if (seq != 9 && seq != 10) wire.push_back(m); // the network loses #9 and #10
if (seq == 6) wire.push_back(Msg{5, 0, 0}); // and delivers #5 a second time
if (seq % 10 == 0) snapshots.push_back({seq, exchange});
if (seq % 10 == 3 && seq > 10) wire.push_back(snapshots.back());
}
FeedHandler handler;
for (const auto& item : wire) {
if (auto* m = std::get_if<Msg>(&item)) handler.on_message(*m);
else handler.on_snapshot(std::get<Snapshot>(item));
}
std::println("final book matches the exchange: {}", handler.book == exchange);
std::println("orders resting: {}", handler.book.size());
}Press Run to compile and run this example.
#5: duplicate, ignored
#11: gap, #9..#10 missing; book is stale, buffering
snapshot @10: book replaced; 3 buffered, 3 newer to replay
final book matches the exchange: true
orders resting: 12Walk through it. Message 5 arrives a second time and is dropped. Message 11 arrives when 9 is expected: the handler marks its book stale and starts buffering. The snapshot taken after message 10 arrives after message 13, so 11, 12 and 13 are in the buffer. The handler replaces its book with the snapshot, sets expected to 11 and replays the buffer through the normal path; all three are newer than the snapshot, so all three are applied. The snapshot after message 20 arrives while the handler is live and in sequence, so it is ignored. The final book matches the exchange's.
Two details are easy to get wrong. A snapshot older than the first buffered message (here, one taken before message 10) cannot repair the gap, because the messages between the snapshot and the buffer are still missing; the handler waits for a newer one. And buffered messages are replayed through on_message, not applied directly, so that duplicates and a second gap inside the buffer are handled by the same code.