Project 6: Lock-Free Concurrent Queue (Atomics Without Fear)

A high-performance lock-free MPMC (multi-producer multi-consumer) queue that multiple threads can push/pop from simultaneously without any mutexes—using only atomic operations.

Quick Reference

Attribute Value
Primary Language Rust
Alternative Languages C++, C
Difficulty Level 4: Expert
Time Estimate 3-4 weeks
Knowledge Area Lock-Free Programming / Atomics / Memory Ordering
Tooling std::sync::atomic, crossbeam
Prerequisites Projects 1-3 completed, strong understanding of threads

What You Will Build

A high-performance lock-free MPMC (multi-producer multi-consumer) queue that multiple threads can push/pop from simultaneously without any mutexes—using only atomic operations.

Why It Matters

This project builds core skills that appear repeatedly in real-world systems and tooling.

Core Challenges

  • Understanding memory ordering (SeqCst, Release, Acquire) → maps to CPU memory models and visibility
  • Implementing compare-and-swap loops → maps to atomic operations
  • Preventing ABA problems → maps to hazard pointers or epoch-based reclamation
  • Ensuring your queue is actually correct → maps to formal reasoning about concurrency

Key Concepts

  • Memory ordering: “Rust Atomics and Locks” Chapter 3 - Mara Bos
  • Compare-and-swap: “Rust Atomics and Locks” Chapter 4 - Mara Bos
  • Lock-free data structures: “The Art of Multiprocessor Programming” - Herlihy & Shavit
  • Epoch-based reclamation: crossbeam-epoch documentation

Real-World Outcome

$ cargo run --release -- benchmark
🔥 Lock-Free Queue Benchmark
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Configuration: 8 producers, 8 consumers, 10M operations each

Mutex-based Queue:
  Throughput: 2.3 million ops/sec
  Latency p99: 4.2 μs

Your Lock-Free Queue:
  Throughput: 18.7 million ops/sec  (8.1x faster!)
  Latency p99: 0.3 μs               (14x lower!)

Correctness verification:
  ✅ All 80M items accounted for
  ✅ No duplicates
  ✅ No data corruption
  ✅ Stress test passed (1 hour, no hangs)

Implementation Guide

  1. Reproduce the simplest happy-path scenario.
  2. Build the smallest working version of the core feature.
  3. Add input validation and error handling.
  4. Add instrumentation/logging to confirm behavior.
  5. Refactor into clean modules with tests.

Milestones

  • Milestone 1: Minimal working program that runs end-to-end.
  • Milestone 2: Correct outputs for typical inputs.
  • Milestone 3: Robust handling of edge cases.
  • Milestone 4: Clean structure and documented usage.

Validation Checklist

  • Output matches the real-world outcome example
  • Handles invalid inputs safely
  • Provides clear errors and exit codes
  • Repeatable results across runs

References

  • Main guide: LEARN_RUST_DEEP_DIVE.md
  • “Rust Atomics and Locks” by Mara Bos