Design Considerations for P99-optimized Hash Tables by Steve Heller

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.

1. A ScyllaDB Community
Design Considerations for
P99-optimized Hash Tables
Steve Heller
President and Chief
Consultant
Chrysalis
Software Corp.

2. Steve Heller
Chief Consultant at Chrysalis Software Corp.
■I wrote a program to email out thousands of copies of my
resume to answer job ads. In 2001.
■The first 99% of the latency reduction takes the first 99%
of the time. The other 1% takes the other 99% of the time.
■I’ve been to Antarctica.
■Where is this mythical “away from work”? Chrysalis
Software
Corp.

3. Previous state of the art

4. A hash table with buckets and separate chaining
Hash_table_5_0_1_1_1_1_1_LL.svg,
created by JorgeStolfi, licensed under
https://creativecommons.org/licenses/by-sa/3.0/

5. A hash table with open addressing and linear probing
By Jorge Stolfi - Own work, CC BY-SA 3.0,
https://commons.wikimedia.org/w/index.php?curid=6400669

6. The variable-length-native hash table

7. Short records stored in the tranche data structure used by the
variable-length-native hash table

8. Short records and overflow records stored in the
variable-length-native hash table

9. Performance

10. Redis vs. VLNHT Average Get time
Horizontal axis unit: 100 million records

11. Redis vs. VLNHT: P99 Get time
Horizontal axis unit: 100 million records

12. Redis vs. VLNHT Memory usage
Horizontal axis unit: 100 million records

13. VLNHT get times up to 10 billion records, sync save
Horizontal axis unit: 100 million records

14. VLNHT get times up to 10 billion records, async save
Horizontal axis unit: 100 million records

15. Thank you! Let’s connect.
Steve Heller
[email protected]
ChrysalisSoftwareCorporation.com