Triple-buffering client state without ever blocking a reader

One thread keeps updating a piece of state, another reads it constantly, and the reader can never be the one that waits, not even on a lock held for a handful of instructions.

In Naoto the reader is the risk check, which reads a client's balance on every order, on the order path. The writer is the gateway's states writer, which applies fills from the multicast stream of trade reports and the snapshots coming back from the account service.

Why not a mutex, a shared struct or a seqlock

A mutex makes the read correct, but an order that arrives while the writer holds it waits, and however short the hold is, it's unpredictable and it's on the order path. Dropping the lock and sharing one plain ClientState struct avoids the wait and lets the reader copy it halfway through an update instead, getting a new Confirmed next to an old Attempt, a pair that was never true at any moment.

The usual answer to exactly this is a seqlock: the writer bumps a counter before and after each update, and a reader that sees the counter change during its copy throws the copy away and tries again. It keeps a single copy of the state, but a read that overlaps a write has to retry, so the reader's worst case depends on the writer's timing. With three buffers the reader does one load and one copy, every time, and the price is paid in memory instead.

An index and three buffers

The actual structure is three full copies of a client's state, and one atomic index saying which of the three is the one readers should trust right now:

alignas(64) std::vector<ClientState> States1;
alignas(64) std::vector<ClientState> States2;
alignas(64) std::vector<ClientState> States3;
alignas(64) std::vector<std::atomic<uint8_t>> Complete;

Complete[clientFd] holds 0, 1, or 2, and a reader's whole job is to load it once and pick a buffer:

[[nodiscard]] ClientState
GetClientState(const uint32_t clientFd) const noexcept
{
    uint8_t complete =
        Complete[clientFd].load(std::memory_order_acquire);
    return complete == 0 ? States1[clientFd]
        : complete == 1  ? States2[clientFd]
                         : States3[clientFd];
}

That returns a copy, not a reference, which matters: once a reader has it, nothing happening in another thread can change the numbers it's holding. And the writer doesn't touch the buffer it copied from until it has flushed that client twice more.

The writer never touches what readers see

The writer never aims at States[complete]. It aims one buffer ahead, and even then it doesn't write the new value directly, it accumulates a delta:

void SetClientAssets(const uint32_t clientId, const int64_t confirmed,
                     const int64_t attempt, uint16_t assetId) noexcept
{
    uint8_t complete =
        Complete[clientId].load(std::memory_order_relaxed);

    ClientState &toChange = complete == 0
        ? States2[clientId]
        : (complete == 1 ? States3[clientId] : States1[clientId]);

    for (size_t i = 0; i < MaxPositions; ++i)
    {
        if (toChange.AssetId[i] == assetId)
        {
            Deltas[clientId][complete].Confirmed[i] += confirmed;
            Deltas[clientId][complete].Attempt[i] += attempt;
        }
    }
}

toChange is only read here, to find which asset slot matches. What actually changes is Deltas[clientId][complete]. Every generation, meaning the stretch between two flushes, gets its own delta slot, and an update only ever adds to the current generation's slot. It never touches States1, States2 or States3, so a reader can't catch one of them mid-write.

Flushing: fold, publish, prepare

FlushTripleBuffer is what turns accumulated deltas into an actual published state, and it's worth walking in three pieces. First, it folds this generation's deltas into the not-yet-published buffer:

ClientState *curState = complete == 0
    ? &States2[clientFd]
    : (complete == 1 ? &States3[clientFd] : &States1[clientFd]);

for (size_t i = 0; i < MaxPositions; ++i)
{
    curState->Confirmed[i] += curDelta[complete].Confirmed[i];
    curState->Attempt[i] += curDelta[complete].Attempt[i];
}

Then it publishes, with a single atomic store:

complete = complete == 2 ? 0 : complete + 1;
Complete[clientFd].store(complete, std::memory_order_release);

One instruction, and every reader that loads Complete after it sees the fully-updated buffer. Never a partial one, because the store only happens once curState is completely folded.

The last piece is the least obvious one. The buffer the writer stages into next isn't fresh: it's the one that was published two flushes ago, and it has missed every update since, which is two whole generations of them. Catching it up means adding both of those generations' deltas. So the flush first clears the slot the new generation is about to use, then folds all three slots into that buffer:

for (size_t i = 0; i < MaxPositions; ++i)
{
    curDelta[complete].Confirmed[i] = 0;
    curDelta[complete].Attempt[i] = 0;
    newState->Confirmed[i] += curDelta[0].Confirmed[i];
    newState->Confirmed[i] += curDelta[1].Confirmed[i];
    newState->Confirmed[i] += curDelta[2].Confirmed[i];
    newState->Attempt[i] += curDelta[0].Attempt[i];
    newState->Attempt[i] += curDelta[1].Attempt[i];
    newState->Attempt[i] += curDelta[2].Attempt[i];
}

With the new slot zeroed, "all three" is exactly the two generations that buffer missed. Each generation's delta lives for two flushes, until all three buffers have absorbed it, and gets cleared when its slot comes around again. The table follows one balance through three flushes: at flush 3 the +5 slot has just been cleared, so buffer 1, still at 105, gets +3 +4 and lands on 112 like the others.

Why three, not two

With two buffers, the only place left to stage into after a flush is the buffer that was published a moment ago, and a reader might still be in the middle of copying it. Writing into it then would hand that reader half old and half new values, the torn read from earlier, just moved somewhere else. A third buffer gives a full generation of slack: one is published, one may still be being copied, and the writer only ever touches the third. That holds as long as a reader finishes its copy before the writer has flushed that client twice, which usually happens but isn't guaranteed (when a read spans two flushes).

It costs memory, since every client's state exists three times over, and every flush is real write work rather than a pointer swap. Both of those happen on the writer's core, which is the side that can afford them.

Measured against a mutex and a seqlock

I put the triple buffer next to a mutex and a seqlock guarding the same ClientState, with the threads where the gateway pins them: the reader on CPU 4 and the writer on CPU 10, which sits on the other half of this laptop's Ryzen 5 4600H (each half of six hardware threads shares its own L3). Reads are spaced about 500 ns apart, like orders arriving, and each one gets a client's state and reads one asset, as the risk check does. Each write applies a fill the way the gateway's writer does: two assets, then a flush.

With the writer applying a million updates a second, 25 times the order rate the project page quotes, the read takes 60 ns at P50 and 150 ns at P99 with the triple buffer, 60 ns and 75 ns with the seqlock, and 70 ns and 950 ns with the mutex. With no writer at all the same read is an L1 hit, under 10 ns, so most of those 60 ns are the cache lines the writer just changed coming across from the other half of the CPU, which every one of these schemes pays. Copying the whole 320-byte state instead of the one slot the check needs adds only about 10 ns, because the core fetches its five lines in parallel.

At rates like these the seqlock does as well as the triple buffer, slightly better at P99. A seqlock write touches two values and a counter, while a flush here writes two whole buffers plus the deltas. The writer shows the gap directly: run back to back, it gets through 90 to 130 million seqlock updates a second against 17 to 20 million flushes.

What the triple buffer buys shows up when the writer runs flat out, starting each update as soon as the last one is done. The read stays at 120 ns P50 and 140 ns P99, the mutex goes to 780 ns and 1.5 µs, and the seqlock reader keeps finding the counter changed under it: 7.5 µs at P50 and 365 µs at P99. A burst of fills for one client is when that would happen, and the triple buffer's read cost doesn't depend on it.

When a read spans two flushes

Three buffers are safe as long as no read lasts across two flushes of the same client, and the risk thread doesn't control that. A read can be interrupted in the middle of its copy for several microseconds, and a writer that was descheduled for a while catches up by flushing back to back.

To test it, the writer moves one unit from one asset to another, with the two fields on different cache lines, so every published state has the same sum and a read with any other sum is torn. Real copies tore zero times in 80 million reads, with the writer at a million updates a second or running flat out. With a pause between reading the two fields, standing in for an interrupt mid-copy, it tears: a 1 µs pause tears 1.1% of reads with the writer at a million updates a second and 99.9% with the writer flat out, and a 5 µs pause tears nearly every read. Nothing tells the reader, and a torn balance could let an order through against funds the client never had at any moment.

The fix is to take the seqlock's check for this one case: a per-client count of flushes, read before and after the copy, with a retry if it moved by two or more. Two flushes almost never land inside one copy, so reads would almost never retry, and the bound above stays. It isn't in the repository yet.