Our Data Model

We had a relational data model which was quite complex but below is a minimal core data structure which we had to read from and write to.

struct Data {
    index: u32,
    metrics: Metrics, // mutable
    // other mutable/immutable fields
}
type Store = HashMap<u32, Arc<Data>>; 
type Block = Vec<Arc<Data>>; // Arc<Data> is a ref of data in `Store`

Store holds Data for IDs and each Block contains references to a subset of them.

Our service was read heavy. Every read request traverses all elements in a Block and does some computation over them. These reads happen concurrently.

We had a single writer thread which continuously updates data in Store.

Mutating Data

For each write, we had to replace the entire Metrics value. We considered two approaches for this: wrapping it in an RwLock, or replacing the value atomically.

RwLock

With multiple readers and a single writer, a read-write lock is generally the first thing we reach for:

use parking_lot::RwLock;
struct Data {
    index: u32,
    metrics: RwLock<Metrics>,
}
fn read(block: &Block) -> u32 {
    let mut max_count = 0;
    for data in block {
        max_count = max_count.max(data.metrics.read().count);
    }
    max_count
}
fn write(store: &Store, index: u32, metrics: Metrics) {
    *store[&index].metrics.write() = metrics;
}

There are other RwLock implementations as well in std and Tokio, but we chose parking_lot. std::sync::RwLock leaves reader/writer priority order to the OS, and tokio::sync::RwLock is asynchronous and acquiring it can yield. Our traversal was a synchronous computation and we didn't want to yield while acquiring every item, so parking_lot was a better fit.

Crossbeam Atomic

The alternative is to store an immutable Metrics value behind an atomic pointer. Readers load the current pointer, and the writer replaces it with a newly allocated value.

use crossbeam_epoch::{Atomic, Owned};
use std::sync::atomic::Ordering;
struct Data {
    index: u32,
    metrics: Atomic<Metrics>,
}
fn read(block: &Block) -> u32 {
    let guard = crossbeam_epoch::pin();
    let mut max_count = 0;
    for data in block {
        let metrics = data.metrics.load(Ordering::Acquire, &guard);
        // SAFETY: The epoch guard ensures the pointer remains valid
        if let Some(metrics) = unsafe { metrics.as_ref() } {
            max_count = max_count.max(metrics.count);
        }
    }
    max_count
}
fn write(store: &Store, index: u32, metrics: Metrics) {
    let guard = crossbeam_epoch::pin();
    let data = &store[&index];
    
    let old = data.metrics.swap(
        Owned::new(metrics),
        Ordering::AcqRel,
        &guard,
    );
    if !old.is_null() {
        // SAFETY: `old` is no longer stored in the atomic and is protected by the epoch guard
        unsafe {
            guard.defer_destroy(old);
        }
    }
}

When a reader loads Metrics, the epoch guard keeps that value alive until the reader is finished.

When the writer swaps metrics with a new value, the old value will not be freed immediately. defer_destroy marks that old value to be dropped later, when all active readers accessing it have finished.

Benchmark

The full benchmark code for this simplified example is on Git.

Setup

• Readers : 50 concurrent Tokio tasks
• Writers : 1 writer with 500 writes/sec
• Block Size : 16,384
• CPU Warmup : 2s
• Measurement : 10s, averaged over 5 runs
• Machine : MacBook Air with Apple Silicon

Each reader task calls read() in a loop with yield_now() after every call. The writer task calls write() at a fixed rate for 500 writes/sec.

Results

The lock-free version had significantly higher read throughput and much lower read latency across p50, p95 and p99 compared to RwLock.

At the first glance, it might seem like the lower throughput for RwLock is due to read-write contention. But when we turn off the writer, the read throughput barely changes.

Read Lock Acquisition

parking_lot internally uses AtomicUsize to track the number of active readers. When a read lock is acquired, it increments the active readers count via an atomic compare-and-exchange operation. And when the read lock is dropped, the readers count is decremented via an atomic subtraction.

So for one entry in Block, a simplified read is:

        reader
          |
          | read lock: readers_count + 1
          v
        read Metrics.count
          |
          | read unlock: readers_count - 1
          v
        continue

One logical block read, repeats the above 16,384 times:

read one Block
  |
  +-- Block[0]      lock -> read -> unlock
  +-- Block[1]      lock -> read -> unlock
  +-- Block[2]      lock -> read -> unlock
  |
  |   ...
  |
  +-- Block[16_383] lock -> read -> unlock

Here we have 16,384 read lock acquisitions and 16,384 lock releases for a single traversal. So, at ~16k traversals per second, around 524 million updates per second are performed by RwLock internally.

While CPUs are capable of performing billions of operations per second, atomic operations like compare-and-exchange and atomic subtraction are generally more expensive compared to ordinary reads and writes. These atomic operations must accurately track the active readers count under concurrent updates, which adds an overhead even when there is no contention.

Why Crossbeam Atomic Reads Were Cheaper

Crossbeam's pin() function pins the current thread to an epoch once for the entire Block traversal. This tells Crossbeam that the current thread could be accessing shared data, so any values which the thread could be using should not be reclaimed.

Each element in the Block now only requires an atomic pointer load instead of atomically incrementing/decrementing active reader count for every item.

pin epoch once
  |
  +-- Block[0]      atomic pointer load
  +-- Block[1]      atomic pointer load
  +-- Block[2]      atomic pointer load
  |
  |   ...
  |
  +-- Block[16_383] atomic pointer load
  |
drop epoch guard

Though epoch pinning and reclamation have their own bookkeeping overhead, replacing 16,384 RwLock read guards with one Crossbeam epoch guard and atomic pointer loads made a significant difference.

Other Alternatives

ArcSwap: ArcSwap is another option for read-heavy workloads. For this read pattern, using ArcSwap::load() for each item in the Block still adds some per-item overhead, while with Crossbeam we pin once for the whole Block.

left-right: left-right can provide much higher read throughput by keeping duplicate state and shifting more work to the writer. For our service, the production dataset was around 4GB in memory, so duplicating that state would have increased memory usage significantly. With Crossbeam, we were already meeting our throughput and latency requirements, so we didn't need that tradeoff.

Mutable Block

While our Metrics changed frequently, new entries were added to the Block only once or twice per second. For this, a simple RwLock around the Vec was sufficient.

use parking_lot::RwLock;
type Block = RwLock<Vec<Arc<Data>>>;

Here, the individual Metrics values in Data still use Crossbeam Atomic pointers. Since the insertions were infrequent, we didn't see a need to make the Block itself lock-free.

Conclusion

These results are specific to our workload and they don't necessarily mean lock-free is always faster.

Going lock-free helped us avoid the overhead of acquiring and releasing thousands of read locks. But we also saw that a simple RwLock worked well when placed around the Block.

In the end, it's not just about choosing between locked and lock-free. Where and how often synchronization happens matters just as much.