The shared-state trap
Every storage engine starts with one lock around one map. It works, right up until a compaction thread and a flusher disagree about the same memtable and you spend an afternoon chasing a corruption that only reproduces under real write pressure.
The instinct is to add more locks. The better move is to have less shared state.
Partitioning by hash
The first change was to stop treating the table as one object. Hash the key, pick a shard, and let each shard own its own map and its own lock. Contention drops roughly linearly with shard count until you hit the point where cache lines start to matter.
pub struct ShardedStore {
shards: Vec<Mutex<Map<Key, Value>>>,
mask: usize,
}
impl ShardedStore {
fn read(&self, k: &Key) -> Option<Value> {
let i = k.hash() & self.mask;
self.shards[i].lock().unwrap().get(k).cloned()
}
}Single-writer invariants
Once each shard has exactly one writer, most of the hard concurrency questions disappear. Readers never observe a half-written page because writes land through an epoch counter that is bumped after the swap, not during it.
Durability you cannot explain is a bug you have not hit yet.
Benchmarks
| Design | p99 read | Throughput |
|---|---|---|
| Global mutex | 8.4ms | 41k ops/s |
| 64 shards | 0.9ms | 640k ops/s |
| 64 shards + epochs | 0.4ms | 1.2M ops/s |
The lesson is not that locks are bad. It is that the shape of your state decides how much locking you need.