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 (a red-black tree's rebalancing can cause a huge P99 spike, exactly what a matching engine can't afford)
• 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.

A flat hash map, the hard way

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.

That's the whole idea, and it's also where it falls apart if you stop there. 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. That's the failure mode a flat hash map has to be designed around.

Robin Hood: swap the rich for the poor

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.

Tombstones, the easy way that stops being easy

Deletion is where this gets interesting. 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 obvious fix is a tombstone, mark the slot deleted but not empty, so lookups keep scanning through it. Cheap to implement. It's also a trap, because 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, and the table gets slower to search the longer it runs. That's exactly the kind of behavior a matching engine can't tolerate.

Shifting instead

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 zero tombstones behind. In a matching engine, price levels get deleted far less often than they get read, so that cost barely matters. Reads dominate deletes for an order book pretty much always, which makes shifting the clear choice here.

Sixteen slots at once, in parallel

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.

The obvious lever is SIMD. Every operation starts by finding the right slot, and instead of checking one slot's dib against the expected value and moving on, SIMD compares a whole batch of slots against the expected dib pattern 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 matches what's expected, footprint_mask marks every lane whose footprint (one byte of the hash, separate from the bits used to pick the bucket) matches the target key's, and ANDing them together finds the matching slot and the stop slot, where the cluster's dib pattern breaks, in the same pass. Most of the sixteen lanes get ruled out on the footprint alone, and the real key only gets compared, which is the expensive part, once a slot has already cleared both checks.

Alignment is not an accident

Slots are allocated sixteen to a cluster, aligned to that boundary, whether sixteen keys ever actually land there or not.

That buys two things. There's more physical room before one original slot's cluster starts bumping into the next one's, so clusters stay shorter in practice. And every SIMD load lands on a 16-byte boundary, so it never straddles two cache lines, which is what actually makes a load slow on modern x86, and it can use the aligned forms that older SSE instructions require for memory operands. Tying the cluster size to the SIMD width means alignment doesn't depend on the allocator getting lucky, it's guaranteed by how the table is laid out.

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 and keeps the high bits, instead of a heavier general-purpose hash. Order book keys are prices, which cluster tightly and increment in small steps, so a cheap multiply-and-shift is enough to spread them into well-distributed buckets.
• 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.

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 took a second structure living alongside this one, which is what the dual-view order book post is about.