Design Considerations for P99-optimized Hash Tables

Hash tables are a classic data structure but struggle in P99-optimized applications, especially with variable-length records. Open addressing works well for fixed-length data, while chaining (as used in Redis) adds latency and pointer overhead. This talk presents an alternative: organizing hash tables as blocks that pack variable-length records together, reducing random memory accesses and cache inefficiencies. We’ll explore how block-based design with robin-hood hashing can deliver lower, more predictable latency.
Who is this presentation for?
Low-latency engineers
Prerequisite knowledge:
A general knowledge of hash tables
What you'll learn?
How a novel data structure for hash tables can reduce latency and a variance in latency.

Steve Heller has been a programmer since the late Neolithic in computer history terms, having written his first program in 1965 in FORTRAN II. He has been a programmer ever since with a few side forays, e.g., textbook writing and top-level technical support at Microsoft. Efficient variable-length data storage on block devices has been a passion of his for the last 50 years.