Implementing a Concurrent Cache

You will build a thread-safe caching layer that handles concurrent reads and writes.

Implementing a Concurrent Cache

In this lesson, you will learn how to design a thread-safe caching layer that balances high-concurrency read access with safe, consistent writes.

When multiple threads need to access a shared cache, a standard Mutex<HashMap<K, V>> often becomes a bottleneck. Even if most operations are reads, the mutex forces threads to queue up, destroying throughput. To solve this, we use a strategy that separates the locking granularity and leverages internal synchronization primitives.

The Strategy: Sharding and Interior Mutability

To implement an efficient cache, we avoid a single global lock by using sharding. We partition our keyspace into $N$ independent buckets, each protected by its own lock. This allows thread A to read from shard 0 while thread B writes to shard 1 simultaneously.

Within each shard, we use RwLock instead of Mutex. This allows multiple concurrent readers to access the data without blocking one another, only requiring exclusive access when a write occurs.

use std::sync::{RwLock, Arc};
use std::collections::HashMap;

struct Shard<K, V> {
    data: RwLock<HashMap<K, V>>,
}

pub struct ConcurrentCache<K, V> {
    shards: Vec<Shard<K, V>>,
}

impl<K: std::hash::Hash + Eq, V> ConcurrentCache<K, V> {
    pub fn get(&self, key: &K) -> Option<V> where V: Clone {
        let shard = self.get_shard(key);
        let read_guard = shard.data.read().unwrap();
        read_guard.get(key).cloned()
    }
}

Handling Contention

When building this, consider the read-to-write ratio. If your cache is read-heavy, the RwLock pattern is highly effective. However, if your workload involves frequent updates (like invalidating entries), you might encounter Cache Line Padding issues where threads on different cores fight for ownership of the same memory line. In such cases, ensure your Shard structures are aligned to prevent false sharing, ensuring that the performance gains from sharding aren't negated by hardware-level contention.

By combining sharding with RwLock, you transform a serialized bottleneck into a highly parallel system that scales linearly with the number of available CPU cores.

Key Takeaway: To achieve high-throughput concurrency in a cache, use sharding to divide the lock contention and prefer RwLock to allow multiple simultaneous readers.