Designing A Fast Concurrent Hash Table
I recently released papaya, a fast and feature-complete concurrent hash table for Rust. In this post I want to dive into the design and research that went into creating it, as well as why you might consider using it over existing solutions. If you're looking for an overview of papaya, you might find it more useful to consult the documentation.
Concurrent hash tables are a well explored topic, both in academic literature and open-source implementations. In some ways, they are the holy grail of concurrent data structures. On the other hand, a concurrent hash table is an inelegant blob of shared mutable data, often a marker of a poorly architectured program. Hash tables in general have many unfortunate properties, most of which are exacerbated in a concurrent context. However, despite their downsides, hash tables can be a necessary evil, especially for read-heavy use cases where alternative data structures are not competitive in terms of performance.
Concurrent hash tables fall into a large spectrum depending on which of the above properties are prioritized. papaya cares a lot more about readers than writers. Reads should be extremely low latency and never blocked by a slow writer. However, it also cares a lot about predictable latency in general. While write throughput may not be exceptional, neither readers nor writers should ever suffer from latency spikes.
