sync.Map: Two Maps, A Miss Counter and Why Read-Mostly Wins

TL;DR: sync.Map used to be two maps — a lock-free read map and a mutex-guarded dirty map — plus a misses counter that promoted dirty to read. That implementation is gone: the type is now a wrapper around internal/sync.HashTrieMap, a 16-way hash trie whose reads take no locks at all.

If you learned Go concurrency from the sync package, you learned sync.Map as a piece of cleverness: a fast read path with no mutex, a slow write path with one, and a heuristic that promotes the slow map to the fast one when the reads outnumber the writes.

That description is now history. The type in the Go 1.28 tree looks like this:

go
// src/sync/map.go:11
// Map is like a Go map[any]any but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
// Loads, stores, and deletes run in amortized constant time.
//
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate [Mutex] or [RWMutex].
//
// The zero Map is empty and ready for use. A Map must not be copied after first use.
//
// In the terminology of [the Go memory model], Map arranges that a write operation
// “synchronizes before” any read operation that observes the effect of the write, where
// read and write operations are defined as follows.
// [Map.Load], [Map.LoadAndDelete], [Map.LoadOrStore], [Map.Swap], [Map.CompareAndSwap],
// and [Map.CompareAndDelete] are read operations;
// [Map.Delete], [Map.LoadAndDelete], [Map.Store], and [Map.Swap] are write operations;
// [Map.LoadOrStore] is a write operation when it returns loaded set to false;
// [Map.CompareAndSwap] is a write operation when it returns swapped set to true;
// and [Map.CompareAndDelete] is a write operation when it returns deleted set to true.
//
// [the Go memory model]: https://go.dev/ref/mem
type Map struct {
	_ noCopy

	m isync.HashTrieMap[any, any]
}

One field. Every method is a one-line forward:

go
// src/sync/map.go:44
// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key any) (value any, ok bool) {
	return m.m.Load(key)
}

// Store sets the value for a key.
func (m *Map) Store(key, value any) {
	m.m.Store(key, value)
}

So let’s do this in two parts: first, how the old design worked (because it explains the name of the type, and the guidance that survived), and second, what is actually in the tree now.

The old design: two maps and a miss counter

Until Go 1.23, sync.Map held roughly this:

text
type Map struct {
    mu    sync.Mutex
    read  atomic.Pointer[readOnly]   // immutable snapshot, read without a lock
    dirty map[any]*entry             // guarded by mu; the "current" map
    misses int                        // read misses on read while it was amended
}

type readOnly struct {
    m       map[any]*entry
    amended bool                      // true if dirty holds keys not in m
}

The read path was the whole point. Load first consulted read.m — an ordinary Go map published through an atomic pointer, so reading it needed no lock at all. Only if the key was missing and read.amended was true (meaning dirty had entries not yet in read) did it take the mutex.

The write path always took the mutex and wrote to dirty. That made writes expensive but kept the lock-free map stable, because mutating a map that concurrent readers are walking is not allowed.

That leaves the obvious problem: dirty accumulates everything, read stays stale, and every read of a key that was written after the last promotion has to fall back to the mutex. The misses counter was the fix. Every time a read missed in read and had to go to dirty under the lock, misses went up by one. When misses reached len(dirty), the map concluded that the reads were overwhelmingly hitting dirty, and promoted it:

text
   read.m  --(misses >= len(dirty))-->  read.m = copy of dirty
                                           dirty = nil
                                           amended = false

Promotion copies dirty into a fresh read map so the old one can keep being read without a lock. It is expensive, and it is amortised: it happens roughly once per len(dirty) misses.

The other elegant piece was the expunged sentinel. When a key was deleted, its entry in the read-only map had to be marked somehow, because a plain delete would mutate a map concurrent readers are walking. The old code did not delete the key; it replaced the entry’s atomic pointer with a pointer to a special sentinel expunged entry. A tombstone. That tombstone mattered during promotion: if the key was later re-added to dirty, the promotion had to know that the delete had already been observed by readers, so the key must not come back from the dead. expunged said “this deletion is already public”.

So the classic algorithm was: reads are lock-free when the read map is warm, writes are always locked, and a miss counter decides when to pay for a promotion.

What replaced it: a hash trie

The tree now delegates to internal/sync.HashTrieMap, the same structure the unique package uses. The design goal is stated at the top of the file:

go
// src/internal/sync/hashtriemap.go:14
// HashTrieMap is an implementation of a concurrent hash-trie. The implementation
// is designed around frequent loads, but offers decent performance for stores
// and deletes as well, especially if the map is larger. Its primary use-case is
// the unique package, but can be used elsewhere as well.
//
// The zero HashTrieMap is empty and ready to use.
// It must not be copied after first use.
type HashTrieMap[K comparable, V any] struct {
	inited   atomic.Uint32
	initMu   Mutex
	root     atomic.Pointer[indirect[K, V]]
	keyHash  hashFunc
	valEqual equalFunc
	seed     uintptr
}

There is no mu, no read, no dirty, and no misses. There is a root pointer and a hash function.

Initialisation is lazy and one-time

go
// src/internal/sync/hashtriemap.go:30
func (ht *HashTrieMap[K, V]) init() {
	if ht.inited.Load() == 0 {
		ht.initSlow()
	}
}

//go:noinline
func (ht *HashTrieMap[K, V]) initSlow() {
	ht.initMu.Lock()
	defer ht.initMu.Unlock()

	if ht.inited.Load() != 0 {
		// Someone got to it while we were waiting.
		return
	}

	// Set up root node, derive the hash function for the key, and the
	// equal function for the value, if any.
	var m map[K]V
	mapType := abi.TypeOf(m).MapType()
	ht.root.Store(newIndirectNode[K, V](nil))
	ht.keyHash = mapType.Hasher
	ht.valEqual = mapType.Elem.Equal
	ht.seed = uintptr(runtime_rand())

	ht.inited.Store(1)
}

Two things worth noticing. The hash function is the runtime’s own map hasher, obtained from the map type — so HashTrieMap hashes keys exactly the way a map[K]V would. And the seed is random, per map instance, mixed into every hash. That is the same defence against hash-flooding that ordinary Go maps use, and it is why the trie needs no external seed parameter.

The read path takes no locks

This is the part that matters most, and it is short:

go
// src/internal/sync/hashtriemap.go:64
func (ht *HashTrieMap[K, V]) Load(key K) (value V, ok bool) {
	ht.init()
	hash := ht.keyHash(abi.NoEscape(unsafe.Pointer(&key)), ht.seed)

	i := ht.root.Load()
	hashShift := 8 * goarch.PtrSize
	for hashShift != 0 {
		hashShift -= nChildrenLog2

		n := i.children[(hash>>hashShift)&nChildrenMask].Load()
		if n == nil {
			return *new(V), false
		}
		if n.isEntry {
			return n.entry().lookup(key)
		}
		i = n.indirect()
	}
	panic("internal/sync.HashTrieMap: ran out of hash bits while iterating")
}

No mutex. No atomic read-modify-write. Just a walk down the trie following bits of the hash, loading an atomic pointer at each level. atomic.Pointer loads are ordinary atomic loads, so this is safe against concurrent writers — the writer publishes new nodes with slot.Store(...) and the reader either sees the old node or the new one.

The fan-out is 16:

go
// src/internal/sync/hashtriemap.go:530
const (
	// 16 children. This seems to be the sweet spot for
	// load performance: any smaller and we lose out on
	// 50% or more in CPU performance. Any larger and the
	// returns are minuscule (~1% improvement for 32 children).
	nChildrenLog2 = 4
	nChildren     = 1 << nChildrenLog2
	nChildrenMask = nChildren - 1
)

// indirect is an internal node in the hash-trie.
type indirect[K comparable, V any] struct {
	node[K, V]
	dead     atomic.Bool
	mu       Mutex // Protects mutation to children and any children that are entry nodes.
	parent   *indirect[K, V]
	children [nChildren]atomic.Pointer[node[K, V]]
}

So a 64-bit hash gives you 64 / 4 = 16 levels of 4 bits each. The mu in an indirect node is the only lock in the whole structure, and it protects one node’s children — not the whole map. That is the crucial difference from the old design: the old sync.Map had one mutex for the entire map, so two goroutines storing to different keys still serialised. Here, two goroutines storing to different branches of the trie usually take different node locks and never meet.

The leaves are entries, with an overflow chain for genuine hash collisions:

go
// src/internal/sync/hashtriemap.go:563
// entry is a leaf node in the hash-trie.
type entry[K comparable, V any] struct {
	node[K, V]
	overflow atomic.Pointer[entry[K, V]] // Overflow for hash collisions.
	key      K
	value    V
}

func newEntryNode[K comparable, V any](key K, value V) *entry[K, V] {
	return &entry[K, V]{
		node:  node[K, V]{isEntry: true},
		key:   key,
		value: value,
	}
}

func (e *entry[K, V]) lookup(key K) (V, bool) {
	for e != nil {
		if e.key == key {
			return e.value, true
		}
		e = e.overflow.Load()
	}
	return *new(V), false
}

Note that the entry’s value is not atomic — it is immutable. An update replaces the whole entry node rather than mutating it in place, which is what makes the lock-free read path safe: a reader that has loaded a node sees a consistent key/value pair, and an updater publishes the replacement with a single atomic store.

The write path: double-checked locking on one node

Writing is where the lock is taken, and the pattern is textbook double-checked locking over an atomic pointer:

go
// src/internal/sync/hashtriemap.go:126
		// Grab the lock and double-check what we saw.
		i.mu.Lock()
		n = slot.Load()
		if (n == nil || n.isEntry) && !i.dead.Load() {
			// What we saw is still true, so we can continue with the insert.
			break
		}
		// We have to start over.
		i.mu.Unlock()
	}
	// N.B. This lock is held from when we broke out of the outer loop above.
	// We specifically break this out so that we can use defer here safely.
	// One option is to break this out into a new function instead, but
	// there's so much local iteration state used below that this turns out
	// to be cleaner.
	defer i.mu.Unlock()

The optimistic walk is done without the lock, and only if the slot looks like it needs changing does the code take the node’s lock and re-check. If the state changed underneath — another goroutine split the node, or the node was deleted — it drops the lock and starts the whole walk over.

The other interesting write path is expand, which handles two keys that hash to the same slot:

go
// src/internal/sync/hashtriemap.go:165
// expand takes oldEntry and newEntry whose hashes conflict from bit 64 down to hashShift and
// produces a subtree of indirect nodes to hold the two new entries.
func (ht *HashTrieMap[K, V]) expand(oldEntry, newEntry *entry[K, V], newHash uintptr, hashShift uint, parent *indirect[K, V]) *node[K, V] {
	// Check for a hash collision.
	oldHash := ht.keyHash(unsafe.Pointer(&oldEntry.key), ht.seed)
	if oldHash == newHash {
		// Store the old entry in the new entry's overflow list, then store
		// the new entry.
		newEntry.overflow.Store(oldEntry)
		return &newEntry.node
	}
	// We have to add an indirect node. Worse still, we may need to add more than one.
	newIndirect := newIndirectNode(parent)
	top := newIndirect
	for {
		if hashShift == 0 {
			panic("internal/sync.HashTrieMap: ran out of hash bits while inserting (incorrect use of unsafe or cgo, or data race?)")
		}
		hashShift -= nChildrenLog2 // hashShift is for the level parent is at. We need to go deeper.
		oi := (oldHash >> hashShift) & nChildrenMask
		ni := (newHash >> hashShift) & nChildrenMask
		if oi != ni {
			newIndirect.children[oi].Store(&oldEntry.node)
			newIndirect.children[ni].Store(&newEntry.node)
			break
		}
		nextIndirect := newIndirectNode(newIndirect)
		newIndirect.children[oi].Store(&nextIndirect.node)
		newIndirect = nextIndirect
	}
	return &top.node
}

Two keys with the same hash become an overflow chain — the old expunged-style linked list, but for collisions rather than deletions. Two keys that merely collide in a slot get an extra level of indirection, growing the trie until their hashes diverge. The trie therefore has a bounded depth (16 levels for a 64-bit hash) no matter how many keys you put in it, which is exactly the property that stops the old hash table from degrading into a linear scan.

Range walks the tree

go
// src/internal/sync/hashtriemap.go:498
func (ht *HashTrieMap[K, V]) iter(i *indirect[K, V], yield func(key K, value V) bool) bool {
	for j := range i.children {
		n := i.children[j].Load()
		if n == nil {
			continue
		}
		if !n.isEntry {
			if !ht.iter(n.indirect(), yield) {
				return false
			}
			continue
		}
		e := n.entry()
		for e != nil {
			if !yield(e.key, e.value) {
				return false
			}
			e = e.overflow.Load()
		}
	}
	return true
}

No snapshot, no lock, no dirty-map fallback. The old sync.Map.Range had to fall back to the dirty map when read.amended was true, which meant Range could see the same key twice or hold the mutex for the whole iteration. The trie does not need any of that: it walks the live tree, and the doc comment is explicit about the weaker guarantee.

go
// src/sync/map.go:102
// Range calls f sequentially for each key and value present in the map.
// If f returns false, range stops the iteration.
//
// Range does not necessarily correspond to any consistent snapshot of the Map's
// contents: no key will be visited more than once, but if the value for any key
// is stored or deleted concurrently (including by f), Range may reflect any
// mapping for that key from any point during the Range call. Range does not
// block other methods on the receiver; even f itself may call any method on m.
//
// Range may be O(N) with the number of elements in the map even if f returns
// false after a constant number of calls.
func (m *Map) Range(f func(key, value any) bool) {
	m.m.Range(f)
}

Note the Clear method too — the old sync.Map had to walk its maps to clear them; the trie can drop the root on the floor and start over.

Why read-mostly still wins

The guidance in the doc comment has not changed, and the reason it has not changed is that it is not really about the implementation. It is about contention patterns.

A plain map[K]V guarded by a sync.RWMutex has one lock. Every reader takes it (in read mode). Readers scale reasonably, but any writer blocks every reader, and writers serialise against each other.

sync.Map is better when:

Entries are written once and read many times. A cache that is populated once and then read. Reads are lock-free; writes are rare and paid for.
Goroutines work on disjoint key sets. With the old design, two goroutines storing to different keys still serialised on the single mutex. With the trie, they usually take different node locks. This case got dramatically better with the rewrite.

It is worse when the workload is write-heavy or the key set is shared: you pay for a lock-free-read data structure and get a per-node mutex plus the cost of growing the trie. For that case, map[K]V plus a sync.RWMutex (or sync.Mutex) is simpler and usually faster.

The old misses counter was a heuristic for “the reads have moved to the dirty map, so promote”. The trie replaces that heuristic with structure: there is no dirty copy to promote, because there is only one copy, and the parts of it that are being written are protected by narrow locks while everything else is read without any lock at all.

Trade-offs

What the trie buys:

Lock-free reads. Load is a pure pointer walk. No atomic RMW, no shared cache line being written on the read path.
Fine-grained write locking. The lock is per trie node, not per map. Disjoint key sets genuinely do not contend any more.
Bounded depth. Sixteen levels maximum, so lookup is O(16) pointer hops regardless of map size. No rehash-the-world, no long probe chains.
Cheap Clear. Drop the root, allocate a new one.

What it costs:

More memory per key. Every key lives in an entry struct with a key, a value, an overflow pointer and a node header — more than a slot in a Go map.
More pointers to chase. A map lookup is one hash, one bucket, one comparison sequence. A trie lookup is a hash plus up to sixteen pointer dereferences.
any boxing. sync.Map is HashTrieMap[any, any], so every key and value is an interface. Storing a string key boxes it, and comparisons go through the runtime’s equality function rather than a direct string compare.
No snapshot iteration. Range is not consistent, and in a write-heavy workload it can be O(N) even if your callback returns false immediately.

Caveats

sync.Map is not a faster map. It is a different data structure with different trade-offs. The doc comment is right there: “Most code should use a plain Go map instead, with separate locking or coordination, for better type safety”.

Do not copy a Map. The struct embeds noCopy, and the hash trie’s root pointer and lazily-initialised state make a copy meaningless.

Clear exists now but the zero value still must not be copied. Clear drops the root and the next operation re-initialises.

The seed is per-instance. Two sync.Maps hash the same key differently, which is good for hash-flooding resistance and bad for anything that assumes stable hashing.

Range is weakly consistent. If you need a stable view, copy into a plain map under your own lock.

Watch for the any tax. sync.Map cannot be typed. HashTrieMap can, but it is internal. If you are storing a large number of values, the interface boxing and the per-key entry allocation are real costs.

The old implementation is not coming back. If you are reading a blog post or a book that describes read, dirty, amended, misses and expunged, that describes sync.Map as it was up to Go 1.23. The public API is identical; the internals are a completely different machine.

Wrapping up

The one thing to remember: sync.Map in this tree is internal/sync.HashTrieMap — a 16-way hash trie with an atomic root, lock-free reads, and a per-node mutex for writes. There is no dirty map and no misses counter to promote.

The part people get wrong: believing that sync.Map is faster than a plain map plus a mutex. It is not, in general. It wins in exactly two situations — write-once/read-many caches, and disjoint key sets — and the doc comment says so in the second paragraph.

What to go do about it: benchmark your actual pattern. If your map is written once per key and read many times, sync.Map will win; if it is written as often as it is read, map[K]V with a sync.RWMutex will win and will be far easier to reason about. And if you need the typed version of the trie, the unique package is the public face of the same code.