Fast Bounded-Concurrency Hash Tables

Session information has not yet been published for this event.

*
Performance and Scalability
Microconference Session

One Line Summary

This talk introduces a general technique for achieving single-writer non-blocking hash tables at low to negligible cost.

Abstract

Non-blocking data structures and their benefits often come at the cost of increased latency because they require additional complexity in the common case. There are plenty of exceptions to this if the requirements of the data structure are relaxed, such as supporting only a bounded level of write or read concurrency.

For this reason, well-designed specialized non-blocking data structures guarantee improved resiliency, throughput and latency in all cases compared to alternatives relying on traditional blocking synchronization primitives such as read-write locks. Specialized concurrent structures are common place in the Linux kernel and other performance critical systems.

This talk introduces a general technique for achieving single-writer non-blocking hash tables at low to negligible cost. The resulting hash table requires no barriers (fences) or locked instructions on architectures such as x86/x86-64. Read operations are lock-free and write operations are fast and bounded. Insertion and deletion are wait-free. Probe sequence mutation is linearized for the common case, bounded and fast. Architectures with relaxed memory models still require barriers.

Back to list of proposals

Speaker

  • Samy Bahra

    Backtrace I/O

    Biography

    Prior to Backtrace, Samy was a principal engineer at AppNexus, where he played a lead role in the architecture and development of many mission-critical components of the ecosystem. His work at AppNexus was instrumental in scaling the system to 18 billion impressions with orders of magnitude in efficiency improvements. Prior to AppNexus, Samy was behind major performance improvements to the core technology at Message Systems. At the George Washington University High Performance Computing Laboratory, Samy worked on the UPC programming language, heterogeneous computing and multicore synchronization. Samy is also the founder of the Concurrency Kit project, which several leading technology companies rely on for scalability and performance. Samy serves on the ACM Practitioners Board.