Designing a cache-friendly, SIMD-accelerated key-value store

One of the first questions I had to answer while building the matching engine was where the order book actually lives. What data structure holds a price level?

The requirements weren't really up for debate:

• fast O(1) lookup, insert, and delete
• no runtime allocation
• low jitter, the same cost on every call, which is what a matching engine can't do without
• good cache locality

So it had to be a key-value store, and it had to behave predictably, not just fast on average but fast every time.

Why not a price-indexed array

The fastest option was the obvious one: index directly by price. Allocate an array wide enough to cover the range and use the price itself as the index. No hashing, no probing, nothing to get wrong.

The problem is the range. It's cheap only when the range of possible prices is small and mostly full. The moment the range gets wide with just a handful of active levels, most of that array sits empty, allocated and taking up cache lines nobody touches. I wanted something that stayed flexible about how sparse or wide the price range could get, so I moved to a hash map.

Open addressing, and where it breaks

A flat hash map is a normal hash map's cheaper cousin. Instead of every bucket pointing to a linked list of collided entries, the hash points straight to an index in one contiguous array, and collisions get resolved by taking the next free slot instead of chasing a pointer.

The catch is that the next free slot can end up very far from the slot a key actually hashed to, especially once a few keys have piled up nearby, and every operation after that pays for the walk.

Robin Hood displacement

The well-known fix is Robin Hood hashing. Every slot tracks a "dib", how many slots away its occupant currently sits from its own home slot. On insert, the rule is: if the resident's dib is lower than the dib the incoming key has already built up, they swap. Whoever has traveled less gives up the seat to whoever has traveled more.

Tags[cur_idx] is the resident's dib at the slot currently being probed, and cur_dib is how far the incoming key has already traveled:

if (Tags[cur_idx] < cur_dib)
{
    PaddingSafeSwap(cur_idx, cur_dib, key, &val);
}

That one rule keeps every original slot's displaced entries bunched together in one contiguous run, instead of scattered wherever they happened to find room, because a resident with a high dib will always give way to an even higher one rather than let a newcomer skip past into empty space further out. It also means a drop in dib while scanning forward tells you the key isn't in the table at all: Robin Hood's invariant guarantees that if it were further along, it would already have displaced whatever lower-dib entry you just found. So a miss doesn't need to scan to the end of the table, it just stops the moment the pattern breaks.

Why not tombstones

Deletion is harder. Lookup depends on every slot in a cluster being physically present and contiguous, so clearing a deleted slot and calling it empty breaks things: a later lookup scanning past it would stop early and wrongly decide the key it's after doesn't exist.

The usual fix is a tombstone: mark the slot deleted but not empty, so lookups keep scanning through it. It's cheap to implement, but tombstones accumulate.

There are mitigation strategies, periodic compaction, opportunistic cleanup on insert, but none of them reliably keep the count down under sustained delete traffic, so the table gets slower to search the longer it runs, which is the jitter this whole design was trying to avoid.

Backward-shift deletion

The other option is backward-shift deletion. After removing a key, every following slot that's still displaced from its own home shifts back one and has its dib decremented, as if it had been placed one step closer to home from the start. That's not necessarily limited to the deleted key's own cluster, either: Robin Hood displacement means a key from a completely different home slot can end up sitting right after it in the same contiguous run, and the shift pulls that one back too.

cur_idx starts at the slot that was just emptied. Each loop iteration looks one slot forward (next_idx, wrapping around the table with the & (total_size - 1) mask) and reads that slot's dib (next_tag). The loop doesn't care which key's cluster a slot belongs to, only whether it's still displaced: hitting EMPTY_MARKER, or a dib of 0 (a key already sitting at its own home), is what stops it:

while (true)
{
    size_t next_idx = (cur_idx + 1) & (total_size - 1);
    uint8_t next_tag = Tags[next_idx];

    if (next_tag == EMPTY_MARKER || next_tag == 0)
    {
        break;
    }

    PaddingSafeWrite(cur_idx, next_tag - 1, Keys[next_idx], Data[next_idx]);
    cur_idx = next_idx;
}

PaddingSafeWrite copies that next entry back into cur_idx, with its dib written as next_tag - 1, one slot closer to home than it was.

It's a slower delete, real writes instead of flipping one flag, but it leaves no tombstones behind. Price levels get deleted far less often than they get looked up, so paying on delete to keep every lookup short is the right side of the trade.

Comparing sixteen slots in one instruction

Robin Hood displacement and shift-deletion cover correctness and keep the average case fast. What's left is making the common case, a lookup on a price level that already exists, as cheap as the hardware will let it be.

Every operation starts by finding the right slot. Instead of checking one slot's dib and moving on, SSE compares sixteen slots against the dib pattern the key's run should have in one instruction, and against the target key's footprint in another.

base_seq is just the sequence 0 through 15. Adding the key's current cur_dib to it gives the dib each of the sixteen lanes ought to have if it belongs to the same cluster the key is walking through. actual_tags and actual_footprints are what's really stored in those sixteen slots, sixteen bytes each, already pulled from memory:

__m128i expected_dibs = _mm_add_epi8(base_seq, _mm_set1_epi8(cur_dib));
__m128i dib_mask = _mm_cmpeq_epi8(actual_tags, expected_dibs);
__m128i footprint_mask = _mm_cmpeq_epi8(actual_footprints, _mm_set1_epi8(footprint));
__m128i match_mask = _mm_and_si128(dib_mask, footprint_mask);

dib_mask marks every lane whose dib is what it should be, and footprint_mask every lane whose footprint (one byte of the hash, separate from the bits that pick the bucket) matches the target key's. ANDing them gives the candidate slots. The same load also finds where to stop: a lane that's empty, or whose dib is lower than expected, is where the key's run would have ended, so a _mm_cmplt_epi8 against the same expected dibs gives the stop mask. Most lanes get ruled out on the footprint alone, and the full key, the expensive comparison, only gets checked for a candidate that comes before the first stop.

Comparing sixteen hash bytes in one SSE2 instruction is the idea behind Abseil's Swiss tables, and the footprint plays the role of their 7-bit hash fragment. The difference is the dib comparison next to it. Swiss tables don't keep slots in Robin Hood order and fall back to tombstones on delete, so a lookup keeps probing until it reaches a group with an empty slot. Here the dibs keep both the ordering and backward-shift deletion, and a lookup stops as soon as the key's run would have ended.

Hashing to a group of sixteen

The hash doesn't pick a slot, it picks a group of sixteen slots, and the key's home is the first slot of that group:

size_t cur_idx = (h & (Size - 1)) << 4;

So every probe starts on a 16-byte boundary of the tag array, and the first load covers the whole group with _mm_load_si128, the aligned form, which never straddles two cache lines. Later loads step by sixteen and stay aligned too. It also spreads keys out: there are sixteen slots of room after each home before one group's run starts spilling into the next group's.

A few more optimizations

Two smaller ones worth mentioning:

• Fibonacci hashing. The hash function multiplies the key by an odd constant derived from the golden ratio, instead of a heavier general-purpose hash. Order book keys are prices, which cluster tightly and increment in small steps, and a single multiply spreads them well, as long as the group comes from the right bits of the product (more on that in what measuring found).
• Power-of-two sizing. The table is a ring: probing past the last slot wraps back to the first, and that wrap happens on every probe step. The size is required to be a power of two, enforced at compile time by a PowerOfTwo concept on the template, so turning a hash or a probe position into a slot index is & (Size - 1), a single AND. With any other size it would be a modulo, which the compiler can at best turn into a multiply-and-shift sequence, and on a path this hot those few extra cycles are paid on every lookup.

Measuring it

I benchmarked the map against absl::flat_hash_map, std::unordered_map and std::map on the laptop the project page numbers come from (Ryzen 5 4600H), with the order book's own table size: 16,384 slots for up to 8,192 price levels. A single lookup takes a few nanoseconds, which is below what a fenced rdtsc can resolve on this CPU, so each sample is 32 lookups in a row where each key depends on the previous result, which stops them overlapping in the pipeline. Prices are drawn from a band around the mid price, and every figure is the median of three runs. The cache is warm, so these are best cases for every map.

With the book full, a lookup at P50 takes 15 ns for this map, 14 ns for absl, 21 ns for std::unordered_map and 80 ns for std::map. Absl ranks among the fastest maps for integer lookups in Martin Ankerl's 2022 benchmark, and this map stays within 10% of it. Inserts are close too (18.5 ns against 16 ns), but erases take 29 ns against absl's 12.5 ns. That's backward-shift deletion doing its real writes in a full table, the cost accepted above in exchange for having no tombstones.

The SIMD probe isn't free. On the same table, a plain loop that checks one slot at a time is faster while the book is small: 5.3 ns against 9.7 ns at 64 levels, and 10 ns against 14 ns at 1,024. Most keys then sit in their home slot, and one compare beats loading and comparing a whole group. SIMD takes over as the book fills and runs get longer: 15 ns against 20 ns at 8,192 levels, where the loop's exit becomes hard to predict and a mispredicted branch costs more than the group compare.

std::map didn't show the tail I expected. Its insert P99 is only about 1.2 times its P50. It did have a P99.9 around 400 ns, but on lookups as well, which never rebalance. The kernel here ticks every millisecond, and a batch of 32 std::map lookups lasts long enough to catch a tick about 0.2% of the time, against 0.04% for the hash maps, so that tail is the timer interrupt. What actually costs std::map is its median, five times this map's.

What measuring found

Checking that the map still held exactly the right keys after half a million inserts and erases at a full book turned up two bugs.

The first is in the insert path for keys more than 16 slots from home, the part that steps through the table one group of sixteen at a time. When the slot a key should take is the first one of a group, the code skips the whole group instead of swapping into it (else if (first_available) is false for lane 0). The key lands further along, past an entry closer to its own home, and a later lookup stops at that entry, exactly as the Robin Hood rule says it should, so the key can't be found even though it's in the table. Skipped groups also push keys further out, and the dib is stored in one byte where 0x80 means empty, so a key 128 or more slots from home is lost outright. The map stayed correct up to 5,120 live levels, lost keys from about 6,144, and at 8,192, the book's maximum, every key was unreachable after the churn. Taking out that condition brings the longest probe at 8,192 levels from 134 slots down to 18.

The second is the hash. The group comes from h & (Size - 1), the low bits of the product, and the low bits of a product depend only on the low bits of the key. Prices on a tick of 16 only ever reach one group in sixteen. At a tick of 32 or 64, keys were still lost with the first bug fixed and the table twice as large, because the few groups in use overflow past the one-byte limit. Taking the group from the top bits of the product instead, which is what Fibonacci hashing means, kept the longest probe at 17 slots or less for every tick I tried (1, 2, 16, 64 and 100).

A bigger table isn't a fix for either. It hides the first bug while probes stay short, doesn't help with the second, and costs lookups: with both fixes in, a full-book lookup takes 12.8 ns with today's table, 15.3 ns with twice the slots and 19.4 ns with four times, because today's 295 KB fits in this CPU's 512 KB L2 and the larger ones don't. Both fixes are written and pass the benchmark's checks; they aren't in the repository yet.

What this data structure still cannot do

None of this answers a question that matters just as much as "does price P have a level": what's the best price right now, and what's next after it. A hash map has no order. Getting that without giving up anything built here takes a second structure next to this one (one order book, two data structures).