Lock-Free Queues in Rust

Abstract

The Rust programming language offers strong compile-time safety guarantees and a modern approach to concurrency, positioning it as a promising candidate for developing concurrent data structures. Despite this, the ecosystem of lock-free data structures in Rust remains fragmented with significant variation in quality, performance and correctness. This thesis addresses these deficiencies by surveying the current state of lock-free concurrent queue implementations in Rust, identifying critical flaws in existing crates and benchmarking them alongside well-established C/C++ implementations. To enable consistent evaluation, we designed and developed a benchmarking framework to measure throughput, fairness, memory usage and ordering guarantees under various configurable workloads. Furthermore, we implemented several state-of-the-art lock-free queue designs in Rust and analysed their performance, highlighting challenges such as memory reclamation and limitations in Rust’s type system in low-level concurrency contexts. Our results expose serious issues in popular crates and demonstrate through our implementations that high-performance, safe, and verifiable lock-free queues are achievable in Rust. In doing so, this work takes a step toward addressing the fragmentation in Rust’s lock-free concurrency landscape.