Skip to content

ADR 0002: Flat Hash Table for Connection Tracking

Status

Approved

Context

Worker threads must track active TCP/UDP connections using a 5-tuple key. Standard std::unordered_map uses node-based chaining which dynamically allocates memory on insertion. Pointer chasing across heap memory invalidates CPU caches, degrading lookup performance under millions of active flows.

Decision

We will implement a flat, open-addressed hash map with linear probing or flat indexing (collision chaining via array offsets) that is pre-allocated at startup.

Design Constraints:

  • Zero Runtime Heap Allocation: All memory nodes must be allocated inside a flat contiguous array at startup.
  • Hash Collisions: Handled via open addressing (e.g. probing to adjacent cells) or index chaining inside the pre-allocated array.
  • Data Locality: Keys and values must be stored contiguously in memory to utilize L1/L2 prefetching.

Options Considered

  1. std::unordered_map: Standard, easy to use, but causes massive heap allocation fragmentation and pointer-chasing cache misses.
  2. Standard Chained Hash Map with Custom Pool Allocator: Solves allocation overhead, but still suffers from cache misses due to pointer links.
  3. Flat Hash Table (Open Addressing): Excellent cache locality, zero allocation on insert. Performance degrades if load factor exceeds 70-80%.

Consequences

  • Positive: Fast connection tracking lookups (<50ns), zero heap allocations on new flow creation, high cache efficiency.
  • Negative: Fixed capacity. Requires sizing the table larger than the peak expected flow count (load factor ≤ 70%).