Sharded Maps in Go for Heavy Concurrent Write Workloads

A map behind one mutex is the right answer until it isn't. When dozens of goroutines write to it all the time, they queue on the lock, and adding cores makes the queue longer rather than the program faster. The classic remedy is to shard: split the map into N independent maps, each with its own lock, and send each key to one of them. Two goroutines working on different keys then usually take different locks and do not wait for each other.

This article builds that data structure with generics, tests it, and benchmarks it against the alternatives under three read/write mixes, because the honest result is that sharding is a clear win in the write-heavy mix and loses to sync.Map in the read-heavy one. It belongs to the concurrency patterns cluster, follows safe concurrent slices and maps, and is the map-sized version of the sharded counter in safe counters. Everything ran on Go 1.25.6 on an Apple M1 Max.

The type

The design has three parts: a hash function to pick a shard, a slice of shards each holding a lock and a map, and operations that lock only the shard they need. Go 1.24 added maphash.Comparable, which hashes any comparable value with a per-process seed, so the map can be generic over its key without a hash function argument:

package main

import (
	"hash/maphash"
	"sync"
)

type shard[K comparable, V any] struct {
	mu sync.RWMutex
	m  map[K]V
}

// ShardedMap spreads its keys over independently locked maps.
type ShardedMap[K comparable, V any] struct {
	seed   maphash.Seed
	shards []*shard[K, V]
}

// NewSharded returns a map with n shards. A power of two keeps the intent clear;
// the modulo works for any n.
func NewSharded[K comparable, V any](n int) *ShardedMap[K, V] {
	s := &ShardedMap[K, V]{seed: maphash.MakeSeed(), shards: make([]*shard[K, V], n)}
	for i := range s.shards {
		s.shards[i] = &shard[K, V]{m: make(map[K]V)}
	}
	return s
}

func (s *ShardedMap[K, V]) shardFor(key K) *shard[K, V] {
	return s.shards[maphash.Comparable(s.seed, key)%uint64(len(s.shards))]
}

func (s *ShardedMap[K, V]) Load(key K) (V, bool) {
	sh := s.shardFor(key)
	sh.mu.RLock()
	defer sh.mu.RUnlock()
	v, ok := sh.m[key]
	return v, ok
}

func (s *ShardedMap[K, V]) Store(key K, val V) {
	sh := s.shardFor(key)
	sh.mu.Lock()
	sh.m[key] = val
	sh.mu.Unlock()
}

func (s *ShardedMap[K, V]) Delete(key K) {
	sh := s.shardFor(key)
	sh.mu.Lock()
	delete(sh.m, key)
	sh.mu.Unlock()
}

// Update applies fn to the current value (or the zero value) under the shard's lock,
// so a read-modify-write is one atomic step.
func (s *ShardedMap[K, V]) Update(key K, fn func(old V, exists bool) V) {
	sh := s.shardFor(key)
	sh.mu.Lock()
	old, ok := sh.m[key]
	sh.m[key] = fn(old, ok)
	sh.mu.Unlock()
}

// Len adds up the shards one at a time. Under concurrent writes it is approximate.
func (s *ShardedMap[K, V]) Len() int {
	n := 0
	for _, sh := range s.shards {
		sh.mu.RLock()
		n += len(sh.m)
		sh.mu.RUnlock()
	}
	return n
}

The seed matters. maphash.MakeSeed returns a random seed per map, which means the key-to-shard assignment differs between runs and between maps, and an attacker who controls keys cannot craft input that lands everything in one shard, which is the hash-flooding attack that built-in maps defend against the same way. The same key always hashes to the same shard within one map, which is the one property the design needs.

Update deserves attention. A counter map (m[word]++) needs the read and the write under one lock; calling Load then Store would let two goroutines both read 5 and both write 6. The callback form runs the whole step while holding the shard's write lock, so the lock covers it. Keep the callback short and never call back into the same map from it, since that takes a lock you already hold.

Proving it correct

Sharding adds a routing layer, and the bugs it can introduce are the quiet kind: a key that lands in two shards, a lost update. This test hammers the map from many goroutines with Update and checks the totals, under the race detector:

package main

import (
	"fmt"
	"sync"
	"testing"
)

func TestUpdateCountsEveryIncrement(t *testing.T) {
	m := NewSharded[string, int](16)
	var wg sync.WaitGroup
	for range 8 {
		wg.Go(func() {
			for i := range 5000 {
				key := fmt.Sprintf("key-%d", i%50)
				m.Update(key, func(old int, _ bool) int { return old + 1 })
			}
		})
	}
	wg.Wait()

	if got := m.Len(); got != 50 {
		t.Fatalf("Len = %d, want 50 distinct keys", got)
	}
	total := 0
	for i := range 50 {
		v, ok := m.Load(fmt.Sprintf("key-%d", i))
		if !ok {
			t.Fatalf("key-%d missing", i)
		}
		total += v
	}
	if total != 8*5000 {
		t.Fatalf("total = %d, want %d: increments were lost", total, 8*5000)
	}
}

func TestSameKeyAlwaysSameShard(t *testing.T) {
	m := NewSharded[int, string](64)
	for i := range 1000 {
		if m.shardFor(i) != m.shardFor(i) {
			t.Fatalf("key %d routed to two shards", i)
		}
	}
	m.Store(7, "seven")
	m.Delete(7)
	if _, ok := m.Load(7); ok {
		t.Fatal("deleted key still present")
	}
}

=== RUN   TestUpdateCountsEveryIncrement
--- PASS: TestUpdateCountsEveryIncrement (0.03s)
=== RUN   TestSameKeyAlwaysSameShard
--- PASS: TestSameKeyAlwaysSameShard (0.00s)
PASS
ok  	example.test/lab	1.376s

Forty thousand increments over fifty keys land on exactly the expected total, so no increment was lost, and every key is findable afterwards, so routing is stable. If Update were written as Load followed by Store, the total assertion would fail. Run the test with -race -count=20 once after any change to the locking.

Does it help? Three mixes

The question that decides whether to use this at all is how it compares with the plain alternatives under realistic mixes. The benchmark runs a 4,096-key space at 90% reads, 50% reads and 100% writes, on one core and on all ten, for four implementations: one RWMutex map, one plain Mutex map, the 64-shard map and sync.Map:

package main

import (
	"fmt"
	"math/rand/v2"
	"sync"
	"testing"
)

type single struct {
	mu sync.RWMutex
	m  map[int]int
}

type plain struct {
	mu sync.Mutex
	m  map[int]int
}

func run(b *testing.B, writePercent int, load func(int), store func(int)) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewPCG(1, 2))
		for pb.Next() {
			k := r.IntN(4096)
			if r.IntN(100) < writePercent {
				store(k)
			} else {
				load(k)
			}
		}
	})
}

func BenchmarkMaps(b *testing.B) {
	for _, writes := range []int{10, 50, 100} {
		name := fmt.Sprintf("writes%d", writes)

		b.Run(name+"/RWMutex", func(b *testing.B) {
			s := &single{m: map[int]int{}}
			run(b, writes,
				func(k int) { s.mu.RLock(); _ = s.m[k]; s.mu.RUnlock() },
				func(k int) { s.mu.Lock(); s.m[k] = k; s.mu.Unlock() })
		})
		b.Run(name+"/Mutex", func(b *testing.B) {
			s := &plain{m: map[int]int{}}
			run(b, writes,
				func(k int) { s.mu.Lock(); _ = s.m[k]; s.mu.Unlock() },
				func(k int) { s.mu.Lock(); s.m[k] = k; s.mu.Unlock() })
		})
		b.Run(name+"/Sharded64", func(b *testing.B) {
			s := NewSharded[int, int](64)
			run(b, writes, func(k int) { s.Load(k) }, func(k int) { s.Store(k, k) })
		})
		b.Run(name+"/SyncMap", func(b *testing.B) {
			var m sync.Map
			run(b, writes, func(k int) { m.Load(k) }, func(k int) { m.Store(k, k) })
		})
	}
}

goos: darwin
goarch: arm64
pkg: example.test/lab
cpu: Apple M1 Max
BenchmarkMaps/writes10/RWMutex-10         	25203568	        46.47 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes10/Mutex-10           	 8833783	       148.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes10/Sharded64-10       	31834952	        38.16 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes10/SyncMap-10         	95580081	        11.62 ns/op	       6 B/op	       0 allocs/op
BenchmarkMaps/writes50/RWMutex-10         	15575060	        78.45 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes50/Mutex-10           	 6825841	       175.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes50/Sharded64-10       	25199296	        53.79 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes50/SyncMap-10         	32744761	        36.38 ns/op	      31 B/op	       1 allocs/op
BenchmarkMaps/writes100/RWMutex-10        	 6199306	       195.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes100/Mutex-10          	 5849221	       203.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes100/Sharded64-10      	21376480	        53.98 ns/op	       0 B/op	       0 allocs/op
BenchmarkMaps/writes100/SyncMap-10        	19027345	        63.04 ns/op	      63 B/op	       2 allocs/op
PASS
ok  	example.test/lab	16.703s

These are the results at ten cores, in nanoseconds per operation:

Three things stand out. A single lock is the slowest option at every mix, and by a wide margin: the plain Mutex cost 149 to 203 ns where the sharded map cost 38 to 54. That is the contention the pattern exists to remove. Second, the gap between one RWMutex and 64 shards grows with the write share, from 1.2 times at 10% writes to 3.6 times at 100%, because readers share an RWMutex happily but every writer takes the whole map. Third, sync.Map wins the read-heavy rows by a lot (12 ns at 10% writes against 38 for the shards) since its read path takes no lock for keys it already holds, and it falls behind only when nearly everything is a write, where it allocates on each store (63 ns, two allocations, 63 bytes).

So the answer to "should I shard?" depends on the workload. With a write-heavy mix on many cores, sharding is the clear winner among the options that keep ordinary typed maps. With a read-mostly mix over a stable key set, sync.Map or a copy-on-write snapshot is faster and simpler. With a small map or a quiet service, none of this matters, and a plain mutex is both the simplest and fast enough. Note too that these runs use a 4,096-key space spread evenly; a skewed workload, where a few keys take most of the traffic, narrows the gap because the hot keys share their shards' locks.

Choosing the shard count

More shards mean less chance that two goroutines collide, with diminishing returns. The collision probability for two simultaneous writers is about one in N, so going from 16 to 64 shards cuts it by four, while going from 64 to 1,024 helps almost nothing on a ten-core machine, where at most ten goroutines can be running at once. I pick a power of two between two and eight times the number of cores, then check it with a benchmark like the one above; the cost of too many shards is memory (each shard has a mutex and a map header) and a more expensive Len or full iteration, which must visit all of them.

Skew can defeat the whole design. If one key takes most of the traffic, it lives in one shard, and that shard's lock is the same bottleneck as before. A counter for the most popular page on a site is the usual example. For one hot key, the right fix is the sharded counter pattern for the value itself, not more shards for the map.

Operations that cross shards

Anything that needs the whole map pays for the sharding. Len locks each shard in turn and adds the lengths, so the result can be off by whatever changed while it ran. Iteration must lock a shard, copy or visit its entries, release, and move on, so a value written to an earlier shard during the scan is missed and one written to a later shard is seen; there is no consistent snapshot unless you lock every shard at once, which stalls all writers. If the program needs consistent whole-map operations often, sharding is working against it. Design the API so that callers cannot assume a snapshot: return a copy, call the result approximate in the doc comment, and expose Range rather than a slice of keys.

A final practical point: do not shard by hand when a library fits. Several third-party concurrent map packages exist, and sync.Map ships in the standard library. The version in this article is about eighty lines, which is small enough to own, understand and tune for a specific workload, and that is the situation where writing it makes sense. The hash/maphash documentation describes the hashing function used, and the Go FAQ on maps explains why the built-in map has no locking of its own. If the map shows up in a profile as lock time, lock contention is the next article.