How does dashmap::DashMap achieve lock-free concurrent access compared to RwLock<HashMap>?
Concurrent map access in Rust typically requires synchronization, and the traditional approach uses RwLock<HashMap>. DashMap provides an alternative using sharded locking and atomic operations that achieves near lock-free behavior for many operations, dramatically improving performance under contention.
The RwLock Baseline
A standard concurrent map wraps a HashMap in an RwLock:
use std::collections::HashMap;
use std::sync::RwLock;
struct ConcurrentMap<K, V> {
map: RwLock<HashMap<K, V>>,
}
impl<K, V> ConcurrentMap<K, V>
where
K: Eq + std::hash::Hash + Clone,
V: Clone,
{
fn get(&self, key: &K) -> Option<V> {
let map = self.map.read().unwrap();
map.get(key).cloned()
}
fn insert(&self, key: K, value: V) -> Option<V> {
let mut map = self.map.write().unwrap();
map.insert(key, value)
}
fn remove(&self, key: &K) -> Option<V> {
let mut map = self.map.write().unwrap();
map.remove(key)
}
}The problem: every operation acquires a lock. A write lock blocks all readers and other writers, creating a serialization point.
DashMap's Sharding Strategy
DashMap divides the map into multiple independent shards:
use dashmap::DashMap;
let map: DashMap<String, i32> = DashMap::new();
// Operations only lock the relevant shard
map.insert("key_a".to_string(), 1); // Locks shard N
map.insert("key_b".to_string(), 2); // Locks shard M (different key may = different shard)
// Reads also lock one shard
if let Some(value) = map.get("key_a") {
println!("Value: {}", value);
}The number of shards defaults to the number of CPU cores, allowing concurrent access to different shards.
Hash-Based Shard Selection
Shard selection is deterministic based on the key's hash:
use dashmap::DashMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
fn which_shard<K: Hash>(key: &K, shard_count: usize) -> usize {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
let hash = hasher.finish();
// Use upper bits to determine shard
(hash >> 32) as usize % shard_count
}
// Keys hash to specific shards
// Operations on keys in different shards can proceed concurrentlyThis means two threads operating on keys that hash to different shards won't contend with each other.
What Lock-Free Actually Means Here
DashMap is not fully lock-free—it uses fine-grained locking at the shard level:
// Conceptual structure
struct DashMap<K, V> {
shards: Vec<RwLock<HashMap<K, V>>>,
// Each shard has its own RwLock
}
// An operation locks ONE shard, not the entire map
fn get(&self, key: &K) -> Option<V> {
let shard_idx = self.which_shard(key);
let shard = self.shards[shard_idx].read().unwrap();
shard.get(key).cloned()
}"Lock-free" in this context means:
- Operations on different shards don't block each other
- Read operations on the same shard can proceed concurrently
- Only write operations block other operations on the same shard
Read Operations: Concurrent Access
Multiple readers can access the same shard concurrently:
use dashmap::DashMap;
use std::sync::Arc;
use std::thread;
let map: Arc<DashMap<u32, String>> = Arc::new(DashMap::new());
// Populate
for i in 0..100 {
map.insert(i, format!("value_{}", i));
}
// Multiple threads reading concurrently
let handles: Vec<_> = (0..4)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
for i in 0..25 {
let key = tid * 25 + i;
if let Some(value) = map.get(&key) {
println!("Thread {} read: {}", tid, value);
}
}
})
})
.collect();
// All threads read concurrently
// Even if they hit the same shard, RwLock allows concurrent readsWrite Operations: Fine-Grained Locking
Write operations only lock one shard:
use dashmap::DashMap;
use std::sync::Arc;
use std::thread;
let map: Arc<DashMap<u32, u32>> = Arc::new(DashMap::new());
// Multiple threads writing to different keys
let handles: Vec<_> = (0..8)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
// Each thread writes to keys in a specific range
for i in 0..100 {
let key = tid * 1000 + i;
map.insert(key, tid);
}
})
})
.collect();
// If keys hash to different shards, writes proceed concurrently
// With RwLock<HashMap>, all 8 threads would serializeAtomic Operations for Entry Access
DashMap provides atomic entry operations that combine read-modify-write:
use dashmap::DashMap;
let map = DashMap::new();
// Atomic entry operations
map.entry("counter".to_string())
.and_modify(|v| *v += 1)
.or_insert(1);
// Atomic get-and-modify
map.entry("key".to_string())
.and_modify(|v| *v = v.to_uppercase());
// Compare and swap pattern
if let Some(mut entry) = map.get_mut(&"key".to_string()) {
*entry = "new_value".to_string();
}These operations hold the shard lock for the duration, ensuring atomicity without requiring external synchronization.
Entry API for Complex Operations
The entry API enables atomic complex operations:
use dashmap::DashMap;
let map: DashMap<String, Vec<i32>> = DashMap::new();
// Atomic insert-or-update
map.entry("numbers".to_string())
.or_insert_with(Vec::new)
.push(42);
// Atomic conditional insertion
map.entry("numbers".to_string())
.or_insert(vec![1, 2, 3]);
// This pattern is thread-safe without external locksComparing Contention Scenarios
High Contention on Same Keys
use dashmap::DashMap;
use std::sync::{Arc, RwLock};
use std::collections::HashMap;
use std::thread;
// RwLock<HashMap>: All operations serialize
let map: Arc<RwLock<HashMap<u32, u32>>> = Arc::new(RwLock::new(HashMap::new()));
let handles: Vec<_> = (0..10)
.map(|_| {
let map = Arc::clone(&map);
thread::spawn(move || {
for _ in 0..1000 {
// All threads hit the same key
let mut map = map.write().unwrap();
*map.entry(42).or_insert(0) += 1;
}
})
})
.collect();
// DashMap: Same issue - same key = same shard = same lock
let map: Arc<DashMap<u32, u32>> = Arc::new(DashMap::new());
let handles: Vec<_> = (0..10)
.map(|_| {
let map = Arc::clone(&map);
thread::spawn(move || {
for _ in 0..1000 {
// Still contended - same key hashes to same shard
*map.entry(42).or_insert(0) += 1;
}
})
})
.collect();When keys collide to the same shard, DashMap has no advantage over RwLock<HashMap>.
Low Contention on Different Keys
use dashmap::DashMap;
use std::sync::{Arc, RwLock};
use std::collections::HashMap;
use std::thread;
// RwLock<HashMap>: All operations still serialize
let map: Arc<RwLock<HashMap<u32, u32>>> = Arc::new(RwLock::new(HashMap::new()));
let handles: Vec<_> = (0..10)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
for i in 0..1000 {
// Different keys, but still single lock
let mut map = map.write().unwrap();
map.insert(tid * 10000 + i, i);
}
})
})
.collect();
// DashMap: Operations proceed concurrently on different shards
let map: Arc<DashMap<u32, u32>> = Arc::new(DashMap::new());
let handles: Vec<_> = (0..10)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
for i in 0..1000 {
// Different keys hash to different shards
// Operations proceed concurrently!
map.insert(tid * 10000 + i, i);
}
})
})
.collect();This is where DashMap excels: concurrent operations on different keys.
Iteration Behavior
Iteration in DashMap locks shards incrementally:
use dashmap::DashMap;
let map: DashMap<u32, String> = DashMap::new();
for i in 0..100 {
map.insert(i, format!("value_{}", i));
}
// Iteration locks one shard at a time
for entry in map.iter() {
println!("{}: {}", entry.key(), entry.value());
// Other operations on unlocked shards can proceed
}
// Compare to RwLock<HashMap>:
// let map = map.read().unwrap();
// for (k, v) in map.iter() { ... }
// The entire map is locked for the whole iterationMemory Ordering and Visibility
DashMap uses atomic operations for coordination:
// DashMap uses atomic operations for:
// 1. Determining which shard to use (pure computation)
// 2. Reference counting for iterators
// 3. Coordination between readers and writers
// The RwLock within each shard provides memory ordering guarantees:
// - All writes before releasing the lock are visible to next lock holder
// - Acquiring the lock establishes a happens-before relationshipConfiguring Shard Count
Shard count affects concurrency potential:
use dashmap::DashMap;
// Default: number of CPU cores
let map: DashMap<String, i32> = DashMap::new();
// Custom shard count (must be power of 2)
let map: DashMap<String, i32> = DashMap::with_shard_amount(64);
// More shards = more potential concurrency, more memory overhead
// Fewer shards = less overhead, more contention potentialWhen DashMap Is Not Lock-Free
Some operations require locking multiple shards:
use dashmap::DashMap;
let map: DashMap<u32, String> = DashMap::new();
// Operations that touch all shards
let len = map.len(); // Locks all shards briefly
map.clear(); // Locks all shards
map.shrink_to_fit(); // Locks all shards
// These are not concurrent with other operationsPractical Performance Comparison
use dashmap::DashMap;
use std::sync::{Arc, RwLock};
use std::collections::HashMap;
use std::thread;
use std::time::Instant;
fn benchmark_rwlock(threads: usize) -> u64 {
let map: Arc<RwLock<HashMap<u64, u64>>> = Arc::new(RwLock::new(HashMap::new()));
let start = Instant::now();
let handles: Vec<_> = (0..threads)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
for i in 0..10_000 {
let key = (tid as u64) * 100_000 + i;
let mut map = map.write().unwrap();
map.insert(key, i);
}
})
})
.collect();
for h in handles { h.join().unwrap(); }
start.elapsed().as_millis() as u64
}
fn benchmark_dashmap(threads: usize) -> u64 {
let map: Arc<DashMap<u64, u64>> = Arc::new(DashMap::new());
let start = Instant::now();
let handles: Vec<_> = (0..threads)
.map(|tid| {
let map = Arc::clone(&map);
thread::spawn(move || {
for i in 0..10_000 {
let key = (tid as u64) * 100_000 + i;
map.insert(key, i);
}
})
})
.collect();
for h in handles { h.join().unwrap(); }
start.elapsed().as_millis() as u64
}
// Typical results with different keys:
// threads=4: RwLock ~500ms, DashMap ~100ms
// threads=8: RwLock ~900ms, DashMap ~120ms
// threads=16: RwLock ~1500ms, DashMap ~150msMemory Overhead
DashMap trades memory for concurrency:
use dashmap::DashMap;
use std::collections::HashMap;
use std::mem::size_of;
// Each shard has:
// - Its own HashMap (buckets, entries)
// - Its own RwLock
// - Separate allocation overhead
// For 16 shards with a small map:
// 16 * (HashMap overhead + RwLock overhead + allocation padding)
// RwLock<HashMap> has:
// - One HashMap
// - One RwLock
// - Single allocation
// DashMap memory ≈ shards * per_shard_overhead + entries
// RwLock memory ≈ single HashMap + entriesSynthesis
DashMap achieves near lock-free concurrent access through sharding, not through lock-free algorithms. Each shard has its own lock, and hash-based shard selection ensures operations on different keys typically hit different shards. This provides:
-
Concurrent reads: Multiple threads can read from the same shard simultaneously (RwLock semantics per shard).
-
Concurrent writes to different shards: Threads writing to keys that hash to different shards don't contend.
-
Atomic entry operations: The entry API provides atomic read-modify-write without external synchronization.
The key insight is that DashMap reduces contention probability rather than eliminating locks entirely. When keys are well-distributed across shards, operations proceed concurrently. When keys collide on the same shard, operations still serialize—no better than RwLock<HashMap>.
For workloads with many concurrent operations on diverse keys, DashMap provides substantial throughput improvements. For workloads with hot keys or uniform access patterns, the benefit diminishes. The memory overhead of multiple shards is the price paid for reduced contention.