The Event Bus and K-Way Merge: Why Every Backtest Is Bit-Identical

Run a backtest on Monday. Run it again on Tuesday, with the same data and the same configuration. If even one fill differs, you cannot trust either result. A backtest that disagrees with itself is not an experiment at all, it is a random number generator with extra steps.

• Same inputs, same outputs
• Always

Kestrel has two demands that seem to pull against each other. The engine must be perfectly repeatable. Yet a browser GUI must be able to watch the state of a running backtest, live, without slowing the engine down. Locks give you safety, but they also give you timing, and timing is the enemy of repeatability.

• Repeatable engine
• Observable from a GUI
• Without locking

In the previous episode we saw how the history store keeps bar files from ever corrupting. Today we use those bars. We will cover the single owner rule, the EventBus, the k way merge that decides which bar comes next, snapshots for the GUI, and finally an argument for why every run is bit identical. What happens inside a single bar belongs to the next episode.

• Owner, bus, merge
• Snapshots, determinism

The Engine object owns a lot. An InstrumentRegistry, the MarketState, a DerivedBarGenerator, a StateStore and the EventBus. It owns the order gateway, which in turn owns the order manager, positions, risk and a venue through the ExecutionCore. And it owns the data sources and one AlphaHost per alpha.

• Engine owns everything
• Gateway owns OMS, risk, venue

Here is the rule that makes the rest possible. Engine run, on the main thread, is the only thread that touches market state, the order manager, positions, risk, the venue and the alphas. Because exactly one thread ever reads or writes them, none of them needs a lock. There is nothing to contend with, so there is nothing to race.

• Engine::run is the sole owner
• No locks on engine state

But other threads exist. An HTTP thread serving the GUI, for example. They follow two permitted moves only. They may post an event onto the bus, or they may read a snapshot. They never reach into the engine's objects directly.

• Post events
• Read snapshots
• Nothing else

This design prevents a whole family of bugs. There are no data races on positions, because only one thread has positions. There are no lock ordering deadlocks between the order manager and risk, because there are no locks between them. And most importantly for us, there is no thread scheduling that can change the order in which things happen.

• No data races
• No lock-order deadlocks
• No scheduler dependence

Now the glue between components: the EventBus. Internally it is simple. A mutex, a condition variable and a deque of events. Handlers are registered per EventKind, stored in a plain array indexed by the kind. Posting is the only operation that other threads may use.

• mutex + condvar + deque
• Handlers per EventKind

The interesting method is drain. It takes the lock, and under that lock it swaps the entire queue into a local batch. Then it releases the lock, and only afterwards does it dispatch the events in that batch to handlers. Swapping a deque is constant time, so the lock is held for almost no time at all.

• Swap under the lock
• Dispatch outside the lock

Here is the real excerpt. First it exchanges the dispatching flag, and if it was already set, it throws a logic error, because drain must never be re entered. A guard resets the flag on exit. Then an outer loop. Inside a small block we take the lock, clear the woken flag, break if the queue is empty, and otherwise swap it into the batch. The block closes, the lock is gone, and only then the inner loop pops each event and dispatches it.

• Re-entry throws
• Lock scope is the inner block

Why does the lock scope end before dispatch? Imagine the opposite. A handler receives a bar and decides to post a new event. Posting needs the same mutex, which this thread already holds. Deadlock, on the very first reaction. By dispatching outside the lock, handlers may post new events freely, and those events simply land in the shared queue.

• Handler posts need the mutex
• Lock held means deadlock

Because handlers can post, one pass is not enough. The outer loop keeps going. Each round swaps in whatever was posted during the last round, dispatches it, and tries again, until the queue is empty. The effect is that after drain returns, every consequence of the original event has been fully processed, in order.

• Handlers may post
• Loop until queue is empty

Two more safety rules. Handler exceptions are caught, so one misbehaving handler cannot tear down the whole run. And subscribing after the first drain is a logic error. Handler lists never change while events are flowing, which means dispatch can read them without any locking at all.

• Handler exceptions caught
• Subscribe after first drain: error

Before any bar flows, initialize builds the world. It adds instruments, and resolves underlyings for options and futures. It builds the gateway. It opens the data sources. It then builds the AlphaEnvironment and one AlphaHost per alpha, where the strategy id is simply the alpha's index plus one. Finally it publishes an initial snapshot, so a GUI has something to show immediately.

• Instruments, gateway, sources
• AlphaHost id = index + 1
• Initial snapshot

One check in initialize deserves attention. If the configured venue reports that it places real orders, then in a backtest that is a ConfigError. A research run must be physically unable to touch a real broker. We will see the full set of live safety layers much later in the series, but this is the first one you meet.

• Real-order venue rejected
• ConfigError in backtest

Engine run has a contract: it never throws. Anything that goes wrong inside is caught and stored as runError, a value the caller can inspect afterwards. For a service that may run thousands of backtest jobs, that matters. A failure in one job becomes data, not a crashed process.

• run() never throws
• Errors become runError_

Now the heart of the backtest. We usually have several bar sources, say one per instrument. Each source is already sorted by time. But the engine needs a single global timeline, so that a bar ending at nine sixteen in one source is processed before a bar ending at nine seventeen in another. This is a classic k way merge.

• Each source sorted
• Need one global order

The trick is to keep only the front bar of each source in a priority queue. Pop the smallest, process it, then refill the heap from the source that bar came from. The heap never holds more than one entry per source, so memory stays small and each step costs only a logarithm of the number of sources.

• One entry per source
• Pop minimum, refill same source

The comparator is called HeapLater. It compares bar end time first. If those are equal, it compares the source index. If those are equal too, it compares a sequence number. Every comparison uses greater than. That is deliberate: std priority queue is a max heap, so asking whether something is greater makes it behave as a min heap, with the earliest entry on top.

• Order by end, source, seq
• Greater-than flips max to min-heap

Let's use real numbers. Source zero has two bars, ending at nine sixteen and nine seventeen. Source one also has two bars, ending at nine sixteen and nine eighteen. The heap starts with the front of each: source zero at nine sixteen, and source one at nine sixteen. A tie on end time.

• Source 0: 09:16, 09:17
• Source 1: 09:16, 09:18

Both candidates end at nine sixteen, so end time cannot decide. The comparator moves to the second key, the source index. Zero is smaller than one, so source zero wins. Notice the tie break is by a number, not by anything arbitrary like memory address or arrival time. That is the whole point.

• End time ties
• Lower source index wins

Step by step. Pop source zero at nine sixteen, and refill with its next bar, nine seventeen. Now the heap holds source one at nine sixteen and source zero at nine seventeen. Source one pops next. Refill with nine eighteen. Then zero at nine seventeen, and finally one at nine eighteen. The order is zero at nine sixteen, one at nine sixteen, zero at nine seventeen, one at nine eighteen.

• 0@09:16, 1@09:16
• 0@09:17, 1@09:18

Now the loop itself, simplified. Take the top of the heap, then pop it. Post a BarEvent carrying that bar onto the bus. Drain the bus completely. Refill the heap from the same source. And maybe publish a snapshot. That is the entire shape of a backtest: one bar in, the whole cascade resolved, then the next bar.

• post, drain, refill
• One bar fully resolved at a time

Why drain completely before pulling the next bar? Because everything caused by a bar, fills, order updates, new alpha decisions, must be finished before time moves on. If the next bar were allowed in while reactions were pending, the order of cause and effect would depend on queue mechanics. Draining fully makes each bar an atomic step of the simulation. What actually happens inside that step is the subject of episode six.

• Each bar is atomic
• Cascade ends before next bar

Two practical details. If a source throws while refilling, the error is logged and that source is dropped, and the run continues with the rest. And a setting called replay speed controls pacing. Zero means full speed. A positive value makes the loop sleep in chunks of one hundred milliseconds, so a person watching in the GUI can follow along.

• Throwing source is dropped
• replaySpeed 0 = full speed

The merge assumes sources are sorted, but data can be imperfect. So MarketState defends itself. It rejects any bar whose start is not strictly after the last accepted start for that instrument. A duplicate bar, or one that arrives out of order, is refused instead of silently corrupting prices and indicators.

• Start strictly after last
• Duplicates rejected
• Out-of-order rejected

Now back to the second requirement. A GUI wants to display positions, prices and orders while the engine runs. But we said no other thread may touch engine state. And we do not want the engine to wait on a reader. So we do not share the state at all. We share a photograph of it.

• Do not share state
• Share a photograph of it

Every snapshot interval, measured in wall clock milliseconds, the engine builds an immutable Snapshot. It publishes it to the StateStore, which is just a mutex protected shared pointer to a const Snapshot. Publishing replaces the pointer. Readers on HTTP threads copy the pointer and then read from it freely, because a const snapshot can never change underneath them.

• shared_ptr<const Snapshot>
• Lock only to swap or copy pointer

You may have noticed something. Snapshot timing uses wall clock time, which is non deterministic. Is that a problem? No, because snapshots are only an output channel. They are read by humans and never feed back into the simulation. The engine publishes them, but nothing in the trading logic ever reads them. The photograph cannot change the scene.

• Wall clock only for publishing
• Output never feeds back

Let's put the argument together. A deterministic program is one where every decision is a function of the inputs and nothing else. We now need to list every place where order or time could sneak in, and show each one is pinned down. There are seven.

• Inputs only
• Seven pinned-down choices

One: a single thread runs everything, so there is no scheduler interleaving. Two: the merge order is the triple of end time, source index and sequence number, a total order with no ties left. Three: where the store breaks ties, it does so by instrument id, a stable number, instead of hash order or pointer order.

• Single thread
• Total order: end, source, seq
• Store ties by instrument id

Four: the venue iterates its working orders by ascending order id, not in hash table order. Five: execution reports are delivered in the order they were produced. Six: risk checks use event time, the time carried by the bars, never the wall clock. Seven: derived bars are generated synchronously in the same thread, and there is no randomness anywhere.

• Venue: ascending order id
• Reports in production order
• Risk uses event time
• Derived bars synchronous, no randomness

An argument is good, but a test is better. Kestrel pins this behaviour with golden tests, which compare a full run against a stored expected result. We will look at how those work in episode sixteen. For scale, this single threaded design processes about one point six million bars per second, so determinism did not cost us speed.

• Golden tests pin the output
• About 1.6 million bars per second

Now the common mistakes. The first is calling handlers while holding the queue lock. It looks harmless, until a handler posts a new event and the thread waits on a mutex it already owns. The fix is the pattern you saw: swap under the lock, dispatch outside it, and loop until empty.

• Never dispatch under the lock
• Swap, release, then dispatch

The second mistake is using wall time anywhere in the simulation. A timeout, a rate limit, a cooldown measured with the system clock will behave differently on a fast machine than on a slow one, and differently at replay speed than at full speed. In backtests, time is whatever the bars say it is. Nothing else.

• Wall clock varies by machine
• Use event time from bars

To recap. One thread owns all engine state, so nothing locks. The EventBus swaps its queue under a lock and dispatches outside it, looping until empty. The merge pops bars by end time, then source index, then sequence number, draining the bus fully after each bar. Snapshots let the GUI look without touching. And together, these choices make every run bit identical.

• Single owner, no locks
• Drain outside the lock
• Merge by end, source, seq
• Snapshots for readers

We said handleBar would wait. In the next episode we open it up: the exact per-bar pipeline, derived bars and expiry, and why its order prevents lookahead. This series is educational only, it is not financial advice, and the numbers shown are illustrative.

• Next: the per-bar pipeline
• Subscribe for episode 6