Copy-on-Write — Senior Level¶

Table of Contents¶

1. Introduction
2. Persistent Data Structures
3. Structural Sharing
4. HAMT and Persistent Maps
5. Finger Trees and Persistent Sequences
6. Tries and Path Copying
7. RCU-Style Updates
8. Quiescent-State Reclamation
9. Generational COW
10. Memory Cost Modelling
11. Snapshot Lifecycle Engineering
12. Lock-Free Writer Designs
13. Cross-Snapshot Transactions
14. COW in Distributed Systems
15. Hybrid Patterns
16. Production Case Studies
17. Failure Modes at Scale
18. Designing for Observability
19. Anti-Pattern Catalogue
20. Self-Assessment
21. Summary

Introduction¶

Focus: "I can build production COW systems. Now I want to understand structural sharing, persistent data structures, RCU as it appears in real systems, and the architectural shape of large-scale COW."

At the senior level, the question is no longer "should I use COW?" but "how do I make COW work at a million entries, ten thousand writes per second, and a one-millisecond p99 latency budget?" The answer is a constellation of techniques: persistent data structures with structural sharing, RCU-style update protocols, generational snapshots, and careful memory-cost modelling.

This file dives into the algorithmic core of why COW scales. The junior and middle levels treated the snapshot as a black box; the senior level cracks it open and shows you how to design snapshots that share structure with their predecessors, so that "rebuilding" only touches the changed parts.

After reading this file you will:

• Understand how persistent data structures share structure to make COW writes cheap.
• Implement a HAMT (hash array-mapped trie) and reason about its complexity.
• Apply RCU-style reasoning to your COW designs, including quiescence detection.
• Model the memory cost of long-lived snapshots.
• Architect lock-free writer designs without deadlock or starvation.
• Recognise the failure modes that appear only at scale.

Persistent Data Structures¶

A persistent data structure preserves its previous versions when modified. "Persistent" here does not mean "stored to disk" — it means "every version persists in memory, accessible to readers."

A naive COW map is persistent: every Set produces a new map; the old one is reachable from anyone who held its pointer. But the cost is O(N) per write, because the new map is a full copy.

The trick that makes persistent structures fast is structural sharing: the new version shares most of its representation with the old, copying only the parts that changed. A persistent HAMT achieves O(log N) writes by copying only the path from the root to the changed key — a logarithmic number of nodes.

A taxonomy¶

log32 N is small: for N = 1 million, log32 N ≈ 4. Four nodes copied per write instead of a million is a 250 000× speedup.

Why Go's standard library lacks persistent structures¶

Go's standard library is intentionally minimal. Persistent structures are useful but specialized; the team has consistently said they fit better in third-party libraries. The community has produced several:

• github.com/benbjohnson/immutable — persistent List, Map, SortedMap. Production-grade.
• github.com/exocortex/persistent — HAMT.
• github.com/HnH/queue — persistent queue.
• github.com/elliotchance/orderedmap — ordered map (not strictly persistent, but useful in COW contexts).

For production code, prefer a well-tested library. For learning, implement one yourself — the experience is invaluable.

The choice: rebuild vs share¶

For a 1 000-entry map at 1 write per second, a rebuild-COW is simpler and just as fast. The structural-sharing trade is worth it when:

• The map is large (>10 000 entries).
• Writes are frequent enough that GC pressure matters.
• You can tolerate O(log N) reads instead of O(1) reads. (Real HAMT reads are still very fast — a tree depth of 4 means 4 array lookups.)

Structural Sharing¶

The fundamental idea: a new version of a data structure points at unchanged parts of the old version. Only the modified path is copied.

Example: persistent linked list¶

type List[T any] struct {
    head T
    tail *List[T]
}

func (l *List[T]) Cons(v T) *List[T] {
    return &List[T]{head: v, tail: l}
}

Cons(v) allocates one node and points at the old list. Total cost: one allocation.

The old list is unchanged and unchanging. Any reader holding the old *List[T] sees its old contents. The new list shares the entire tail with the old.

A read at index i walks i nodes — O(N) for the last element. Useful when accesses cluster near the head; useless for random access.

Example: persistent tree with path copying¶

A balanced binary tree with values at leaves. Updating a leaf requires copying the path from root to leaf and the leaf itself.

type Node[T any] struct {
    left, right *Node[T]
    value       T
    isLeaf      bool
}

func (n *Node[T]) Set(idx, total int, v T) *Node[T] {
    if n.isLeaf {
        return &Node[T]{isLeaf: true, value: v}
    }
    half := total / 2
    if idx < half {
        return &Node[T]{
            left:  n.left.Set(idx, half, v),
            right: n.right, // shared with old tree!
        }
    }
    return &Node[T]{
        left:  n.left, // shared
        right: n.right.Set(idx-half, total-half, v),
    }
}

For a tree of N leaves, Set allocates log N internal nodes plus the new leaf. Total: O(log N) allocations.

The entire untouched subtree is shared between old and new. Memory cost per version: O(log N) new nodes; the rest of the tree is shared with the previous version.

Visualizing structural sharing¶

Old tree (8 leaves):
                root
               /    \
              A      B
             / \    / \
            C   D  E   F
           /\  /\  /\  /\
          1 2 3 4 5 6 7 8

Update leaf 3 to '3*':
              root'
             /    \
            A'     B        <- B shared
           / \    / \
          C   D' E   F      <- C and E and F shared
         /\   /\ /\  /\
        1 2  3*4 5 6 7 8

Allocated: root', A', D' (and possibly the leaf for 3*).
Shared:    B, C, E, F, and all unchanged leaves.

Only 3 internal nodes and 1 leaf are new. The rest is shared. The old tree remains fully functional.

Why this matters for COW¶

A COW snapshot built on a persistent structure has cheap writes. A persistent HAMT with 1 000 000 entries and a single Set allocates ~5 nodes and ~1 leaf — total ~200 bytes. Compare with a rebuild-COW that allocates ~50 MB per write.

The GC pressure for write-heavy persistent COW is orders of magnitude lower than for rebuild-COW. The trade-off: reads are O(log N) instead of O(1). In practice, log32(1 000 000) ≈ 4, so reads are still very fast.

HAMT and Persistent Maps¶

A HAMT (hash array-mapped trie) is the workhorse persistent map. Originally described by Bagwell (2001), it underlies Clojure's PersistentHashMap, Scala's HashMap, and most production persistent maps.

The data structure¶

• A trie over the bits of the key's hash code.
• Each internal node has 32 (or 64) slots, indexed by 5 (or 6) bits of the hash.
• Each slot is either empty, a leaf (key-value pair), or another internal node.
• A 32-bit bitmap per node tracks which slots are occupied (sparse-array representation).
• Worst-case depth: ceil(64/5) = 13 for 64-bit hashes.

A simplified Go implementation¶

package hamt

import "hash/fnv"

const (
    bitsPerLevel = 5
    branching    = 1 << bitsPerLevel // 32
    mask         = branching - 1
)

type Node[V any] struct {
    bitmap   uint32
    children []any // either *Node[V] or *kv[V]
}

type kv[V any] struct {
    hash uint32
    key  string
    val  V
}

type Map[V any] struct {
    root  *Node[V]
    count int
}

func New[V any]() *Map[V] { return &Map[V]{root: &Node[V]{}} }

func (m *Map[V]) Get(key string) (V, bool) {
    h := hash(key)
    node := m.root
    for level := uint(0); level < 64; level += bitsPerLevel {
        idx := (h >> level) & mask
        bit := uint32(1) << idx
        if node.bitmap&bit == 0 {
            var zero V
            return zero, false
        }
        pos := popcount(node.bitmap & (bit - 1))
        child := node.children[pos]
        if leaf, ok := child.(*kv[V]); ok {
            if leaf.key == key {
                return leaf.val, true
            }
            var zero V
            return zero, false
        }
        node = child.(*Node[V])
    }
    var zero V
    return zero, false
}

func (m *Map[V]) Set(key string, val V) *Map[V] {
    h := hash(key)
    newRoot, added := m.root.set(h, 0, key, val)
    count := m.count
    if added {
        count++
    }
    return &Map[V]{root: newRoot, count: count}
}

func (n *Node[V]) set(h uint32, level uint, key string, val V) (*Node[V], bool) {
    idx := (h >> level) & mask
    bit := uint32(1) << idx
    pos := popcount(n.bitmap & (bit - 1))
    if n.bitmap&bit == 0 {
        // new slot
        next := n.clone()
        next.bitmap |= bit
        next.children = insertAt(next.children, int(pos), &kv[V]{hash: h, key: key, val: val})
        return next, true
    }
    existing := n.children[pos]
    if leaf, ok := existing.(*kv[V]); ok {
        if leaf.key == key {
            next := n.clone()
            next.children[pos] = &kv[V]{hash: h, key: key, val: val}
            return next, false
        }
        // hash collision at this level — push to next level
        subNode := &Node[V]{}
        subNode, _ = subNode.set(leaf.hash, level+bitsPerLevel, leaf.key, leaf.val)
        subNode, _ = subNode.set(h, level+bitsPerLevel, key, val)
        next := n.clone()
        next.children[pos] = subNode
        return next, true
    }
    sub := existing.(*Node[V])
    newSub, added := sub.set(h, level+bitsPerLevel, key, val)
    next := n.clone()
    next.children[pos] = newSub
    return next, added
}

func (n *Node[V]) clone() *Node[V] {
    cs := make([]any, len(n.children))
    copy(cs, n.children)
    return &Node[V]{bitmap: n.bitmap, children: cs}
}

func insertAt(s []any, i int, v any) []any {
    out := make([]any, len(s)+1)
    copy(out, s[:i])
    out[i] = v
    copy(out[i+1:], s[i:])
    return out
}

func popcount(x uint32) uint32 {
    // hardware popcount on modern CPUs
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    return (x * 0x01010101) >> 24
}

func hash(k string) uint32 {
    h := fnv.New32()
    h.Write([]byte(k))
    return h.Sum32()
}

This is missing collision-list nodes and Delete, but conveys the structure. A real implementation handles ~64-bit hashes, deletes via tree compaction, and bulk operations for cache friendliness.

Wrapping a HAMT in COW¶

type Store[V any] struct {
    cur     atomic.Pointer[hamt.Map[V]]
    writeMu sync.Mutex
}

func NewStore[V any]() *Store[V] {
    s := &Store[V]{}
    s.cur.Store(hamt.New[V]())
    return s
}

func (s *Store[V]) Get(k string) (V, bool) { return s.cur.Load().Get(k) }

func (s *Store[V]) Set(k string, v V) {
    s.writeMu.Lock()
    defer s.writeMu.Unlock()
    s.cur.Store(s.cur.Load().Set(k, v))
}

Every Set allocates O(log N) nodes. For 1 M entries that is ~6 internal nodes. GC pressure is minimal.

Read performance¶

A HAMT read is:

• 1 atomic Load (~1.5 ns).
• 4–6 array indexings (cache-friendly; each is ~1–3 ns).
• 4–6 hash-bit extractions (constant time).

Total: ~10–25 ns per Get. Compared to a Go map (~5 ns) this is 2–5× slower. Compared to sync.Map Load (~30–80 ns) it is competitive.

When the trade-off pays off¶

HAMT shines as you scale up.

Finger Trees and Persistent Sequences¶

A finger tree is a persistent sequence with:

• O(1) amortized push/pop at either end.
• O(log N) random access.
• O(log N) split and concatenation.

Used for ordered logs, priority queues, ropes (efficient string editing), and version-controlled sequences.

High-level shape¶

A finger tree is a 2-3 tree with the leftmost and rightmost paths "fingered" — kept short for O(1) end access. Internal nodes are 2 or 3 elements; leaves carry the actual values.

When to use¶

• A timeline / event log read by many consumers, appended to occasionally.
• A persistent priority queue.
• A persistent rope (string with cheap edits at arbitrary positions).

Library: github.com/HnH/queue has finger-tree-based persistent queues.

Wrapping in COW¶

type Log struct {
    cur atomic.Pointer[fingertree.Sequence]
    mu  sync.Mutex
}

func (l *Log) Append(e Event) {
    l.mu.Lock()
    defer l.mu.Unlock()
    l.cur.Store(l.cur.Load().PushBack(e))
}

func (l *Log) Snapshot() []Event {
    // O(N) materialization
    return l.cur.Load().Slice()
}

PushBack is O(1) amortized. Snapshot iteration is O(N) but typically called rarely.

Tries and Path Copying¶

A simpler case: a string-keyed trie used as a routing table or autocomplete index. Updates require copying only the path from root to the changed node.

type Trie struct {
    value    string
    hasValue bool
    children map[byte]*Trie
}

func (t *Trie) Get(key string) (string, bool) {
    cur := t
    for i := 0; i < len(key); i++ {
        c, ok := cur.children[key[i]]
        if !ok {
            return "", false
        }
        cur = c
    }
    return cur.value, cur.hasValue
}

func (t *Trie) Set(key, val string) *Trie {
    return t.setAt(0, key, val)
}

func (t *Trie) setAt(i int, key, val string) *Trie {
    if i == len(key) {
        return &Trie{
            value:    val,
            hasValue: true,
            children: t.children,
        }
    }
    c := key[i]
    var child *Trie
    if existing, ok := t.children[c]; ok {
        child = existing.setAt(i+1, key, val)
    } else {
        child = (&Trie{children: map[byte]*Trie{}}).setAt(i+1, key, val)
    }
    next := &Trie{
        value:    t.value,
        hasValue: t.hasValue,
        children: make(map[byte]*Trie, len(t.children)),
    }
    for k, v := range t.children {
        next.children[k] = v
    }
    next.children[c] = child
    return next
}

For a key of length L, Set allocates L+1 new nodes (the path) and shares the rest of the trie. For a routing table with thousands of paths, this is very cheap per update.

Wrapping in COW gives a lock-free routing lookup with cheap updates.

RCU-Style Updates¶

Read-copy-update (RCU) is a synchronization discipline pioneered by the Linux kernel. It has three phases:

1. Read. Readers access the structure with no lock — same as COW.
2. Copy + modify + publish. Writers build a new version and atomically replace a pointer — same as COW.
3. Defer reclamation. Old versions are freed only after all in-flight readers have finished.

In Go, the third phase is handled by the garbage collector. But the discipline of thinking about reader quiescence still matters when:

• You need to perform cleanup beyond just freeing memory (e.g., closing a file handle in the old snapshot).
• You're using unsafe or cgo and the GC cannot see your references.
• You want to bound the memory used by old snapshots.

The quiescence concept¶

A reader is "in a critical section" while it holds a reference to a snapshot. The reader is "quiescent" when it has dropped that reference.

A snapshot is safe to reclaim when all readers that may have observed it have become quiescent.

In Go this happens implicitly: the GC traces live references and reclaims unreachable snapshots. You do not need to track readers manually.

But you may want to know when the last reader is done — for example, to close a file handle deterministically rather than relying on GC finalizers.

Manual quiescence tracking¶

type Snapshot struct {
    data    *Data
    refs    atomic.Int32 // reader count
    onClose func()
}

func (s *Snapshot) Hold() *Snapshot {
    s.refs.Add(1)
    return s
}

func (s *Snapshot) Release() {
    if s.refs.Add(-1) == 0 {
        s.onClose()
    }
}

var current atomic.Pointer[Snapshot]

func Load() *Snapshot {
    for {
        cur := current.Load()
        cur.Hold()
        // double-check: did we lose the race with a Store + reclaim?
        if current.Load() == cur {
            return cur
        }
        cur.Release()
    }
}

This is a hazard-pointer-like pattern. Note the race window: between Load and Hold, a writer may publish a new snapshot and the previous one may have been released to zero. The double-check after Hold re-verifies.

In practice, this manual reference counting is almost never needed in Go. The GC suffices. Use this pattern only when you have a definitive reason (e.g., closing a 100-MB mmap'd file the moment the last reader is done).

Reader counters and the SeqLock trick¶

Some lock-free patterns use a version counter and a SeqLock-like dance:

type Snapshot struct {
    data   *Data
    seq    atomic.Uint64
}

// Reader:
for {
    v1 := snap.seq.Load()
    if v1&1 == 1 { continue } // writer in progress
    d := snap.data
    v2 := snap.seq.Load()
    if v1 == v2 {
        use(d)
        break
    }
}

This is overkill for normal COW (atomic.Pointer handles it), but useful for snapshots that contain pointers to mutable data and you want a "consistent atomic read" without GC overhead.

When to think in RCU terms¶

• You need bounded memory: old snapshots cannot linger indefinitely.
• You need deterministic finalization: close a file, drop a connection.
• You're writing low-level systems code where GC overhead is unacceptable.

For 90% of Go COW code, the GC handles RCU's "deferred reclamation" phase invisibly.

Quiescent-State Reclamation¶

QSBR (quiescent-state-based reclamation) is RCU's most efficient flavor. It assumes there are well-defined moments at which a thread is known to hold no references — for example, between iterations of a request loop.

In a request-handling server¶

Every HTTP handler is a natural quiescent state: at the end of ServeHTTP, the handler's local state is gone. Snapshots held during the handler are released.

func (s *Server) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    snap := s.store.Get()
    // process request using snap
    // when handler returns, snap is no longer referenced
}

The Go GC observes this naturally: snap is a local variable that becomes unreachable on return. The snapshot it pointed to can be reclaimed on the next GC cycle.

In a goroutine loop¶

A long-running goroutine that loops forever may never reach a quiescent state — its snap variable is always live.

go func() {
    snap := s.store.Get()
    for {
        work(snap)
        // snap never released; pinned forever
    }
}()

Mitigation: re-load periodically:

go func() {
    for {
        snap := s.store.Get()
        work(snap)
    }
}()

Now snap is re-assigned each iteration. The previous snapshot becomes unreachable and can be reclaimed.

Quiescence intervals¶

Sometimes you want to know "all current readers will be done by time T." For example, before deleting a database file, you may want to know "all readers using the snapshot that referenced this file have finished."

A naive approach: count active snapshots; wait until count drops to zero. But this can starve under continuous reads.

Better: snapshot generation tags. The writer increments a generation counter on every publish. The cleanup waits until "the lowest in-flight generation > the generation being cleaned up."

type Tracker struct {
    gen      atomic.Uint64
    inFlight sync.Map // generation -> ref count
}

func (t *Tracker) BeginRead() uint64 {
    g := t.gen.Load()
    cnt, _ := t.inFlight.LoadOrStore(g, new(atomic.Int32))
    cnt.(*atomic.Int32).Add(1)
    return g
}

func (t *Tracker) EndRead(g uint64) {
    cnt, _ := t.inFlight.Load(g)
    cnt.(*atomic.Int32).Add(-1)
}

func (t *Tracker) PublishNew() uint64 {
    return t.gen.Add(1)
}

func (t *Tracker) WaitForQuiescence(g uint64) {
    for {
        stillReading := false
        t.inFlight.Range(func(k, v any) bool {
            if k.(uint64) <= g && v.(*atomic.Int32).Load() > 0 {
                stillReading = true
                return false
            }
            return true
        })
        if !stillReading {
            return
        }
        time.Sleep(time.Millisecond)
    }
}

This is the kernel-style approach distilled into Go. Real implementations are more sophisticated (epoch-based reclamation, hazard pointers), but the idea is the same: track who is reading what, then wait.

For most Go code: don't bother. Let the GC do it. Use this pattern only when GC-based reclamation is not enough.

Generational COW¶

Sometimes a single snapshot is too large to copy entirely on every write. Generational COW splits the data into:

• A large, stable "base" generation, updated rarely.
• A small, mutable "delta" generation, updated frequently.

Reads consult delta first, falling back to base.

type Layered struct {
    base  *Map
    delta *Map
}

func (l *Layered) Get(k string) (string, bool) {
    if v, ok := l.delta.Get(k); ok { return v, ok }
    return l.base.Get(k)
}

When delta grows large, compact: merge delta into base, publish a new Layered with empty delta.

func Compact(l *Layered) *Layered {
    newBase := mergeMap(l.base, l.delta)
    return &Layered{base: newBase, delta: &Map{}}
}

Compaction is expensive but rare. Per-write cost is now O(size(delta)) instead of O(size(base) + size(delta)).

When to compact¶

Heuristics: - When len(delta) > k * sqrt(len(base)). Balances per-read overhead and compaction cost. - When the read amplification (delta + base lookups) exceeds a threshold. - On a schedule (every minute, every hour).

Multiple delta layers¶

For extreme write rates, multiple delta layers form a log-structured merge tree (LSM). Each delta has a generation; reads consult them in order. Periodically, lower-generation deltas are compacted into the base.

LSM is the standard structure of RocksDB, LevelDB, Cassandra. It applies to in-memory COW as well.

Trade-offs¶

• Pro: per-write cost decoupled from base size.
• Pro: bursty writes are cheap; expensive compaction can be scheduled.
• Con: reads are more expensive (multiple lookups).
• Con: cache locality suffers (reads touch multiple structures).
• Con: complexity.

For most Go services this is overkill. Use it when: - Snapshots are >100 MB. - Write rate is >100 Hz. - You cannot use a persistent HAMT for some reason.

Memory Cost Modelling¶

A COW system at scale must be modelled for memory. The formula:

Total memory = current snapshot size + sum of pinned old snapshots

Pinned snapshots come from in-flight readers. With N concurrent readers, the worst case is N pinned versions.

Worked example¶

A service has:

• 100 KB snapshot.
• 10 K reads/sec, each holding the snapshot for 1 ms.
• 1 write/sec.

Average in-flight readers: 10 000 reads/sec × 0.001 sec/read = 10 in-flight.

Worst-case pinned snapshots: 1 current + 1 old (in-flight during last write) ≈ 200 KB total.

Worse example¶

Same service, but readers hold the snapshot for 1 second (e.g., long-running RPCs):

Average in-flight readers: 10 000 × 1 = 10 000 readers.

If writes happen every second, each writer publishes a new snapshot. Readers from time T hold snapshot version T; readers from time T+1 hold version T+1; etc.

Worst case: 10 versions pinned simultaneously × 100 KB = 1 MB.

For 1 MB snapshots and 10-second readers: 10 GB. This is when GC begins to struggle.

Mitigation strategies¶

1. Shorten reader lifetimes. Don't pin snapshots across long operations.
2. Reduce snapshot size. Persistent structures with structural sharing.
3. Reduce write rate. Batch updates.
4. Use generational COW. Pin only the small delta.
5. Use weak references (Go 1.24+) for caching the snapshot pointer.

The "snapshot age" metric¶

Track how old the oldest in-flight snapshot is. If it grows beyond expectations, you have a pinned-snapshot bug.

func (s *Snapshot) Age() time.Duration { return time.Since(s.PublishedAt) }

Emit max snapshot age across all readers as a gauge. Spikes correlate with stuck goroutines.

Snapshot Lifecycle Engineering¶

For long-running snapshots — those that may be held for seconds or minutes — engineer the lifecycle explicitly.

Pattern 1: Per-request snapshot¶

func (s *Server) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    snap := s.store.Get()
    ctx := context.WithValue(r.Context(), snapKey{}, snap)
    s.handler.ServeHTTP(w, r.WithContext(ctx))
    // snap dropped on return; GC reclaims it
}

Pattern 2: Snapshot refresh in long jobs¶

go func() {
    const refresh = 30 * time.Second
    last := time.Now()
    snap := s.store.Get()
    for {
        if time.Since(last) > refresh {
            snap = s.store.Get()
            last = time.Now()
        }
        process(snap)
    }
}()

Refresh every 30 seconds; bounded snapshot age regardless of work duration.

Pattern 3: Snapshot per batch¶

For batch processing of many items:

for batch := range batches {
    snap := s.store.Get() // one snapshot per batch
    for _, item := range batch {
        process(snap, item)
    }
}

Pattern 4: Forced re-load on staleness¶

type Reader struct {
    snap   *Snapshot
    maxAge time.Duration
}

func (r *Reader) Snap() *Snapshot {
    if r.snap == nil || r.snap.Age() > r.maxAge {
        r.snap = store.Get()
    }
    return r.snap
}

Bounds snapshot age; trades occasional re-loads for memory savings.

Pattern 5: Explicit Release¶

For cleanup-needing snapshots, count references and call onClose when count hits zero.

type ManagedSnap struct {
    data    *Data
    refs    atomic.Int32
    onClose func()
}

func (m *ManagedSnap) Acquire() { m.refs.Add(1) }
func (m *ManagedSnap) Release() {
    if m.refs.Add(-1) == 0 {
        m.onClose()
    }
}

The reader contract:

snap := store.Get()
snap.Acquire()
defer snap.Release()
use(snap.data)

Explicit reference counting is fragile (every Acquire needs a Release) but precise.

Lock-Free Writer Designs¶

Most COW uses a writer mutex. For extreme write rates, lock-free writers via CAS or single-writer designs become attractive.

Lock-free CAS writer¶

func (s *Store) Update(fn func(*Config) *Config) {
    for {
        old := s.cur.Load()
        next := fn(old)
        if s.cur.CompareAndSwap(old, next) {
            return
        }
    }
}

Pros: no mutex; writers never block each other. Cons: - fn runs once per attempt — must be idempotent and cheap. - Under heavy contention, CAS may starve some writers. - ABA-like issues if the snapshot pointer cycles (unlikely with GC but possible).

Single-writer goroutine¶

type WriterReq struct {
    apply func(*Config) *Config
    done  chan *Config
}

type Store struct {
    cur   atomic.Pointer[Config]
    queue chan WriterReq
}

func New(initial *Config) *Store {
    s := &Store{queue: make(chan WriterReq, 256)}
    s.cur.Store(initial)
    go s.writerLoop()
    return s
}

func (s *Store) writerLoop() {
    for req := range s.queue {
        old := s.cur.Load()
        next := req.apply(old)
        s.cur.Store(next)
        req.done <- next
    }
}

func (s *Store) Update(fn func(*Config) *Config) *Config {
    done := make(chan *Config, 1)
    s.queue <- WriterReq{apply: fn, done: done}
    return <-done
}

Pros: serialized writes without a mutex contention path; natural backpressure via channel buffer. Cons: channel send/recv overhead; the single writer is a bottleneck on writes.

Hybrid: batched single-writer¶

func (s *Store) writerLoop() {
    for {
        req := <-s.queue
        batch := []WriterReq{req}
    drain:
        for {
            select {
            case r := <-s.queue:
                batch = append(batch, r)
            default:
                break drain
            }
        }
        old := s.cur.Load()
        next := old
        for _, r := range batch {
            next = r.apply(next)
        }
        s.cur.Store(next)
        for _, r := range batch {
            r.done <- next
        }
    }
}

Drain the queue greedily, apply all updates, publish once. One snapshot allocation per batch.

When lock-free is worth it¶

• Writer throughput > 10 KHz.
• Writer mutex measured as a bottleneck.
• Latency tail matters (mutex queueing adds variance).

For most services, the plain mutex is good enough.

Cross-Snapshot Transactions¶

You sometimes need atomicity across multiple COW stores. Options:

Option 1: Combine into one store¶

Most common. Two related pieces of state become one snapshot type.

type AppState struct {
    Config   *Config
    Routing  *RoutingTable
}

One atomic pointer; one update; consistency automatic.

Option 2: Snapshot serialization¶

A single writer mutex covers both stores:

mu.Lock()
defer mu.Unlock()
a.Store(newA)
b.Store(newB)

Writers see consistent ordering. Readers may catch the moment between Stores.

Option 3: Version coordination¶

Each store has a version. Readers verify they read consistent versions:

for {
    v1 := a.Load().Version
    bSnap := b.Load()
    if a.Load().Version == v1 {
        // Consistent: a hasn't changed since we loaded b
        use(a.Load(), bSnap)
        return
    }
    // retry
}

Expensive (multiple loads); useful only when occasional inconsistency is catastrophic.

Option 4: STM-like multi-version¶

Implement a tiny STM (software transactional memory) over your COW stores. Writers tag their snapshot with a global version. Readers read at a specific version; if any store has advanced past that version, retry.

Few Go codebases need this; almost all use Option 1 (combine into one store).

COW in Distributed Systems¶

COW within one process is straightforward. Across processes or machines, the pattern changes.

Pattern 1: Local COW + control-plane fanout¶

Each process has its own COW store. A control plane publishes updates; each process applies them to its local store.

control-plane --[message]--> service A   (Update local COW)
              --[message]--> service B   (Update local COW)
              --[message]--> service C   (Update local COW)

Properties: - Reads are local and fast (single-process COW). - Updates have a propagation delay. - Snapshots may diverge briefly across processes.

This is how Consul, etcd, and feature-flag platforms typically work.

Pattern 2: Distributed consensus¶

For strong consistency, use a consensus protocol (Raft, Paxos). The "snapshot" is replicated to a majority before being applied.

• All processes have identical snapshots (modulo replication lag).
• Updates are linearizable.
• Reads can be local (eventually consistent) or via the leader (linearizable).

Pattern 3: Snapshot fetching¶

A new process boots by fetching the current snapshot from a peer or storage.

new-process: GET /snapshot
                          |
                          v
   peer/storage: returns serialized snapshot
                          |
                          v
new-process: store as initial snapshot, then subscribe to updates

The bootstrap snapshot avoids "thundering herd" of writes to a freshly-started process.

Pattern 4: COW + write-ahead log¶

Combine COW with a WAL for durability:

1. Append update to WAL.
2. Apply to in-memory COW.
3. On crash, replay WAL.

This is how SQLite and most embedded databases work.

Distributed COW pitfalls¶

• Snapshot divergence. Different processes briefly see different versions. Document this; design for it.
• Lost updates across processes. Two processes apply different updates to the same snapshot. Need a tiebreaker (last-write-wins, vector clocks, CRDTs).
• Snapshot serialization cost. A 100 MB snapshot is expensive to send over the wire; deltas are better.
• Schema evolution. Old and new processes may interpret the snapshot differently.

These are the realm of distributed systems, beyond COW per se.

Hybrid Patterns¶

Real systems combine COW with other patterns. Common hybrids:

Hybrid 1: COW + atomic counters¶

Use atomic counters for metrics within a snapshot:

type Snapshot struct {
    Data    *Data
    hits    atomic.Int64
    misses  atomic.Int64
}

func (s *Snapshot) Lookup(k string) (V, bool) {
    v, ok := s.Data.Get(k)
    if ok {
        s.hits.Add(1)
    } else {
        s.misses.Add(1)
    }
    return v, ok
}

The snapshot is "immutable" in the COW sense for its data; the counters are mutable but atomic. This is a small, controlled exception to the immutability rule.

When the snapshot is replaced, the counters of the old snapshot are abandoned (their values are still readable by anyone holding the old snapshot, but no one increments them anymore). For metrics, this is typically fine.

Hybrid 2: COW + sync.Map¶

A sync.Map inside a COW snapshot, with whole-snapshot replacement for "clear everything":

type Cache struct {
    store atomic.Pointer[sync.Map]
}

func (c *Cache) Get(k string) (any, bool) { return c.store.Load().Load(k) }
func (c *Cache) Set(k string, v any) { c.store.Load().Store(k, v) }
func (c *Cache) Clear() { c.store.Store(&sync.Map{}) }

Reads and writes go through sync.Map. Clear is COW: replace the whole map atomically.

Hybrid 3: COW + persistent structure¶

A persistent map inside a COW snapshot is what we built earlier. The COW provides the publishing semantics; the persistent map provides cheap writes.

Hybrid 4: COW + Mutex protected mutable parts¶

Sometimes part of the snapshot is genuinely mutable (e.g., a connection pool inside a config):

type Config struct {
    Settings *ImmutableSettings
    Pool     *MutablePool // has its own internal mutex
}

When publishing a new Config, you may pass the same Pool pointer through if the pool didn't change. Readers see a stable snapshot whose mutable parts have their own concurrency story.

Hybrid 5: COW + Background reconciler¶

A background goroutine watches some external source and rebuilds the snapshot:

func reconcile(ctx context.Context, src EventSource, store *Store) {
    for {
        select {
        case e := <-src.Events():
            store.Update(func(c *Config) error {
                applyEvent(c, e)
                return nil
            })
        case <-ctx.Done():
            return
        }
    }
}

External events drive the snapshot updates; the rest of the system reads the snapshot.

Production Case Studies¶

Case Study 1: Service registry (Eureka-like)¶

A microservice queries a service registry to find downstream services. The registry is updated by health checks and registration events.

Design. COW around a map[serviceName][]Instance. Reads happen on every outbound request; writes happen ~10/sec per service.

Numbers. 100 services × 5 instances = 500 entries. Snapshot size: ~50 KB. Reads: 100 K/sec. Writes: ~10/sec total.

Choice. Plain COW with rebuild. Per-write cost ~50 µs; per-second GC pressure ~500 KB. Trivial.

Read latency. ~5 ns (atomic load + map lookup). RWMutex would be ~30 ns.

Case Study 2: Distributed feature flags¶

A service uses 1 000 feature flags. The flags are stored in a control plane and pushed to each process.

Design. COW around map[string]bool. The push handler calls store.Update(...).

Numbers. 1 000 flags × ~10 bytes = ~10 KB snapshot. Reads: 100 K/sec per process. Writes: ~1 per minute.

Choice. Plain COW. Per-write cost is negligible.

Special concern. Stickiness across requests: a request should see consistent flags throughout. Snapshot pin at request boundary.

Case Study 3: Routing table for a reverse proxy¶

A reverse proxy routes 100 K req/sec across 50 K possible URL patterns. Routes update on every deploy.

Design. COW around a compiled routing trie.

Numbers. 50 K routes × ~100 bytes each = ~5 MB snapshot. Reads: 100 K/sec. Writes: ~once per deploy.

Choice. Plain COW. Per-write cost ~50 ms (build + sort + index); acceptable for once-per-deploy.

Read latency. ~20 ns per route lookup. Vital for proxy throughput.

Case Study 4: TLS certificate rotation¶

A web server with thousands of TLS connections; certificates rotate every 90 days.

Design. COW around tls.Config. Cert rotation publishes a new config.

Numbers. Snapshot is tiny (~10 KB). Reads (handshakes): ~100/sec. Writes: ~1 per quarter.

Choice. Plain COW. Stronger reads/writes ratio than even feature flags.

Case Study 5: 1 M-entry user-permission cache¶

A service caches user permissions for 1 M users. Permissions update every few seconds.

Design. Either sync.Map or persistent HAMT inside COW.

Numbers. 1 M entries × ~200 bytes = 200 MB snapshot. Reads: 100 K/sec. Writes: ~10/sec.

Choice with rebuild COW. Per-write: 200 MB allocation, ~100 ms rebuild. 10 writes/sec = 2 GB/sec allocation. Unacceptable.

Choice with sync.Map. Reads ~50 ns, writes ~200 ns. Acceptable but loses snapshot consistency.

Choice with persistent HAMT in COW. Reads ~25 ns (slower than sync.Map). Writes ~1 µs + a few KB allocation. Best of both worlds for this scale.

Case Study 6: Per-request configuration¶

A multi-tenant service has per-tenant configurations. Each tenant's config can change independently.

Design. Sharded COW: one atomic pointer per tenant.

Numbers. 10 K tenants × ~10 KB config each. Reads: many. Writes: per-tenant, infrequent.

Choice. Sharded COW. Each tenant's config is independently published; rebuilds are tiny.

Case Study 7: Read-only static data¶

Country codes, currency rates, IP geolocation tables. Loaded at startup, occasionally hot-reloaded.

Design. COW.

Choice. Plain COW. Single Store at startup; reads forever after.

Case Study 8: Telemetry / metric registry¶

expvar-style. Adding a new metric is rare; reading all metrics is constant (every Prometheus scrape).

Design. COW around map[string]Metric.

Choice. Plain COW. Add-metric writes are infrequent (program startup); scrape reads see consistent snapshots.

Failure Modes at Scale¶

Failure 1: GC stalls from write-heavy COW¶

A 50 MB snapshot rebuilt 10 times per second produces 500 MB/sec of allocations. The GC cannot keep up; pauses lengthen; latency degrades.

Detection: Go's runtime/metrics package exports /gc/heap/allocs:bytes. A sustained allocation rate above ~1 GB/sec on a single instance is concerning.

Mitigation: persistent data structures, batching, generational COW.

Failure 2: Pinned snapshots growing unbounded¶

A bug causes a goroutine to leak; it holds a snapshot pointer forever. Memory grows by one snapshot per writer cycle.

Detection: heap profiles show many versions of the snapshot type alive. The snapshot age metric on long-lived holders climbs without bound.

Mitigation: bound goroutine lifetimes; periodic snapshot refresh.

Failure 3: Writer mutex contention¶

100 writers competing for the same writer mutex. Latency for each write climbs from microseconds to milliseconds.

Detection: mutex profile (runtime.SetMutexProfileFraction) shows contention on the writer mutex.

Mitigation: shard the COW state; use single-writer goroutine for serialization; batch writes.

Failure 4: Snapshot replication divergence (distributed)¶

Across N processes, snapshots diverge because the control plane has a glitch. Some processes see version 100; others see version 99.

Detection: emit snapshot version as a gauge metric per process; alert on divergence.

Mitigation: idempotent updates; replay from a known version on reconnect.

Failure 5: Snapshot loss on reload¶

A bad config file is hot-loaded; validation fails; the old snapshot remains current. The operator believes the change has taken effect but it has not.

Detection: emit a counter for reload failures; alert if non-zero.

Mitigation: clear error messaging; CI validation of config files before deployment.

Failure 6: Slow watcher cascades¶

A subscriber's handler takes 5 seconds. Synchronous watchers block all writers and other watchers for 5 seconds.

Detection: writer latency spikes coinciding with watcher work.

Mitigation: async watchers; non-blocking channel dispatch with drop policy.

Failure 7: Memory blowup from clone-on-read¶

A defensive API clones the snapshot on every Get. With a 10 MB snapshot and 10 K reads/sec, you allocate 100 GB/sec of garbage. GC implodes.

Detection: alloc profile shows enormous Clone() traffic.

Mitigation: don't clone defensively; return read-only accessors or document the immutability contract.

Failure 8: Pointer escape preventing inlining¶

A poorly-written API stores the snapshot pointer in a context, which escapes to the heap unnecessarily. Allocations grow.

Detection: build with -gcflags '-m' to see escape decisions.

Mitigation: keep snapshot pointers in local variables when possible.

Designing for Observability¶

Production COW systems must be observable. The bare minimum:

Metrics¶

• snapshot_version (gauge): current version number.
• snapshot_age_seconds (gauge): time since current snapshot was published.
• snapshot_size_bytes (gauge): in-memory size of the current snapshot.
• reload_attempts_total (counter): total reload attempts.
• reload_failures_total (counter): total failed reloads.
• write_total (counter): total successful writes.
• write_latency_seconds (histogram): distribution of write latency.
• pinned_snapshots (gauge): estimated number of distinct snapshots held by in-flight goroutines.

Logs¶

• One log line per snapshot publish, including version, change summary, and source.
• Errors on reload failure with full context.

Traces¶

• Span: "reload snapshot" with sub-spans for load, validate, publish.
• Span: "snapshot read" with the loaded version as a tag, useful when correlating request behavior with snapshot version.

pprof and tooling¶

• runtime.SetMutexProfileFraction(1) to track writer mutex contention.
• pprof.SetGoroutineLabels(ctx, ...) to tag goroutines with the snapshot version they hold.
• expvar.Publish("snapshot", ...) for ad-hoc debugging.

Dashboards¶

A "snapshot health" dashboard should show:

• Current version + age across all instances.
• Reload success rate.
• Write latency p50/p99.
• Allocation rate from snapshot rebuilds.
• Snapshot version divergence (in distributed deployments).

A spike in reload failures, a stuck version, or a sudden allocation jump should each trigger an alert.

Anti-Pattern Catalogue¶

A consolidated list of senior-level anti-patterns.

Anti-pattern: Snapshot as god object¶

A Config snapshot containing every piece of mutable state in the system. Reloads become rare and risky. Different teams' changes collide.

Better. Multiple independent COW stores per logical domain.

Anti-pattern: Pinning snapshots for the lifetime of the program¶

A goroutine that loads once and runs forever. Memory accumulates.

Better. Periodic re-load; bounded snapshot age.

Anti-pattern: Recomputing the snapshot on every read¶

A "lazy" snapshot that doesn't materialize until Get is called, doing expensive work each time.

Better. Pre-materialize at write time; cache at the snapshot.

Anti-pattern: Hand-rolled hazard pointers¶

Manual reference counting and quiescence tracking when the GC would suffice.

Better. Trust the GC; use manual RCU only when GC is provably insufficient.

Anti-pattern: Persistent structure where rebuild would do¶

A 100-entry map using a HAMT to "save GC pressure". The HAMT's overhead exceeds the savings.

Better. Plain rebuild for small structures; reserve persistent structures for >1 K entries with frequent writes.

Anti-pattern: Cross-store transactions via locks¶

mu.Lock()
a.Store(newA)
b.Store(newB)
mu.Unlock()

Hides the inconsistency window from writers but readers still see it.

Better. Combine into one snapshot if true atomicity matters; otherwise document and accept the window.

Anti-pattern: Snapshot containing live goroutines¶

A snapshot whose field is a running goroutine. Replacing the snapshot doesn't stop the goroutine.

Better. Snapshots are pure data; goroutines belong elsewhere.

Anti-pattern: Schema-less snapshots¶

A Config of type map[string]any. No type safety; no validation; reads must type-assert.

Better. Typed snapshots with explicit fields.

Anti-pattern: Snapshot exposing internal mutability¶

func (c *Config) Hosts() *[]string { return &c.hosts } // returns mutable ref

Callers can mutate; immutability is broken.

Better. Return copies, accessor methods, or interfaces.

Anti-pattern: Snapshot of snapshots without lifetime story¶

Nested COW stores where the inner store's snapshots are independently pinned. Memory grows multiplicatively.

Better. Flatten if possible; document lifetime contracts if not.

Self-Assessment¶

• I can describe how a HAMT achieves O(log N) writes via structural sharing.
• I can implement a simple persistent linked list and tree.
• I can reason about quiescence and when it matters in Go.
• I can identify when a workload outgrows plain rebuild-COW.
• I can model the memory cost of a COW system in terms of snapshot size and reader lifetime.
• I can choose between CAS, single-writer goroutine, and mutex for writer coordination based on workload.
• I can describe the snapshot lifecycle in a long-running service and identify pinning bugs.
• I can design a sharded COW system with measured write throughput.
• I can list the metrics a production COW system should emit.
• I know three real production case studies and can map their requirements to design choices.

Summary¶

The senior level transforms COW from a primitive into an architectural toolkit. Persistent data structures keep write cost bounded as snapshots grow. RCU-style thinking guides snapshot lifecycle decisions even when the GC handles reclamation automatically. Generational COW and sharding split large snapshots into manageable pieces. Memory cost modelling becomes routine.

The professional level dives one layer deeper: the memory model that makes atomic.Pointer[T] correct, the runtime's interaction with the GC during COW workloads, and the codegen for atomic operations across architectures.

Closing Notes for Senior Level¶

A senior Go engineer should look at a system using COW and immediately ask:

• What is the snapshot size?
• What is the write rate?
• What is the reader lifetime distribution?
• Where does the snapshot pin in the request lifecycle?
• What happens when a reload fails?
• How is divergence across instances detected?
• Is the persistent-structure threshold approaching?

The answers determine whether the design is sustainable or a future incident. The patterns in this file are the toolkit for fixing systems when they grow past the limits of plain rebuild-COW.

The next file (professional.md) takes you under the hood: how atomic.Pointer[T] is compiled, why the Go memory model is what it is, how the GC interacts with COW, and the rare situations where you need to reach for unsafe or hardware-specific primitives.

Appendix A: Picking the Right Persistent Structure¶

A quick guide:

Most Go production code uses HAMT for the map case and falls back to rebuild for everything else. Specialized structures (RRB trees, finger trees) are worth the dependency only when their specific operations dominate the workload.

Appendix B: Persistent Data Structure Libraries¶

Survey of Go libraries:

• github.com/benbjohnson/immutable — List, Map, SortedMap, SortedMapStringer. Production-grade, used in InfluxDB. Implements HAMT-like maps with B-tree sorted maps.
• github.com/d4l3k/persistentds — collection of persistent structures including trees and queues.
• github.com/HnH/queue — persistent queue with finger-tree foundation.
• github.com/objectbox/objectbox-go — not strictly persistent but uses COW under the hood for queries.

Choose based on: - API ergonomics for your team. - Benchmark results for your data shape. - Maintenance activity.

Appendix C: Senior-Level Reading List¶

• Bagwell, Phil. "Ideal Hash Trees" (2001) — the HAMT paper.
• Hickey, Rich. "Persistent Data Structures" — Clojure's design philosophy.
• Linux RCU documentation — Documentation/RCU/whatisRCU.txt.
• Okasaki, Chris. Purely Functional Data Structures — the textbook.
• Bonwick & Ahrens. "ZFS: The Last Word in File Systems" — COW at the file-system level.
• Hugues, John. "Why Functional Programming Matters" — for the philosophical foundation of immutability.
• Go memory model: https://go.dev/ref/mem.
• Cox, Russ. "Hardware Memory Models" — for understanding why atomic.Pointer[T] is cheap on x86 and slightly more expensive elsewhere.

A senior engineer should have read all of the Go-specific items and at least skimmed the Bagwell HAMT paper.

Architectural Walkthrough: Designing a Production COW Tier¶

This section walks through the full design of a real COW subsystem at a hypothetical SaaS company. Every decision is annotated with the trade-off considered.

The system¶

A multi-tenant SaaS routes API calls to per-tenant backend pools. Each tenant has:

• A set of allowed origin hostnames.
• A set of rate-limit rules.
• Feature flags.
• An assigned backend region.

There are 50 000 tenants. Routes are consulted on every API request (~250 K req/sec total). Tenant configs change occasionally (admin actions, autoscaling-driven backend reassignment) at roughly 100 writes/sec aggregated across all tenants.

Design step 1: Snapshot granularity¶

Option A: one global snapshot containing all tenants.

• Snapshot size: 50 000 tenants × ~500 bytes = 25 MB.
• Per write: rebuild entire 25 MB → 100 × 25 MB = 2.5 GB/sec of allocations. GC dies.

Option B: one snapshot per tenant.

• Snapshot size: ~500 bytes per tenant.
• Per write: rebuild one tenant's snapshot → 100 × 500 bytes = 50 KB/sec. Trivial.
• But: 50 000 separate atomic.Pointer[Tenant] instances. The "container" itself becomes the bottleneck if we add/remove tenants.

Option C: sharded global snapshot.

• 64 shards, each containing ~800 tenants.
• Per-shard snapshot size: ~400 KB.
• Per write: rebuild one shard → 100 × 400 KB = 40 MB/sec of allocations. Acceptable.

Option D: persistent HAMT over tenants.

• Snapshot is a HAMT. Set(tenantID, newTenant) allocates O(log N) = ~6 nodes per write.
• Per write: ~1 KB allocation. 100 writes/sec = 100 KB/sec. Excellent.

Choose D for new code; choose C if the persistent-structure dependency is unacceptable.

Design step 2: Writer coordination¶

100 writes/sec aggregated across 50 K tenants means each tenant changes ~0.002 times/sec on average — extremely rare per tenant.

But: writes are bursty. A region failover may trigger updates for 5 000 tenants in 10 seconds — 500 writes/sec. Need to handle the burst.

Plain mutex serialization at 500 writes/sec is fine (~2 µs per CAS-then-publish). Pick mutex.

For absolute peace of mind: shard the writer mutex along with the data. 64 shards, each with own mutex. Bursts spread across shards.

Design step 3: Reader path¶

Hot read: given a tenant ID, find the route.

func RouteFor(tenantID string) (string, bool) {
    t, ok := tenants.Load().Get(tenantID)
    if !ok { return "", false }
    return t.Backend, true
}

One atomic load + HAMT lookup ~= 30 ns total. At 250 K req/sec across 32 cores, this consumes ~250 µs/sec of CPU. Negligible.

Design step 4: Snapshot consistency¶

Per-request consistency: load once per request, pass via context.

func (h *Handler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    snap := tenants.Load() // ONE load per request
    ctx := context.WithValue(r.Context(), snapKey{}, snap)
    h.next.ServeHTTP(w, r.WithContext(ctx))
}

All downstream calls within the request use the same snapshot. Snapshot pinned for ~10–100 ms.

Design step 5: Lifecycle and pinning¶

Average request: 50 ms. Steady-state in-flight requests: 250 000 req/sec × 0.05 sec = 12 500 in-flight.

Worst case: 12 500 pinned snapshots simultaneously. With a HAMT and structural sharing, this is fine — pinned snapshots share most structure with each other.

But: if a request gets stuck (held connection, slow downstream) and pins a snapshot for an hour, memory grows by one snapshot per pinned. With 100 writes/sec × 3600 sec = 360 000 versions, each ~25 MB if rebuild — yikes.

With HAMT structural sharing, the cost per version is the changed branches only — maybe 1 KB. 360 000 × 1 KB = 360 MB. Still real, but bounded.

Mitigation: bound request lifetimes via context deadlines. Anything stuck longer than 30 sec is logged + cancelled.

Design step 6: Updates and validation¶

func UpdateTenant(id string, fn func(*Tenant) *Tenant) error {
    shard := shardFor(id)
    tenantsMu[shard].Lock()
    defer tenantsMu[shard].Unlock()
    old := tenants.Load()
    cur, _ := old.Get(id)
    next := fn(cur) // returns a new *Tenant (must be fully built)
    if err := next.Validate(); err != nil {
        return err
    }
    tenants.Store(old.Set(id, next))
    return nil
}

Note: with a HAMT, tenants.Load().Set(...) returns the updated HAMT. The shard mutex serializes writes within a shard — but we have a single global HAMT, so all writes serialize on a single underlying structure.

Mid-design realization: if we use a single global HAMT, sharding the mutex doesn't help — writers still serialize on tenants.Store. To truly shard, use one HAMT per shard.

Design step 6 (revisited): True sharding¶

const Shards = 64

type TenantStore struct {
    shards [Shards]struct {
        cur atomic.Pointer[hamt.Map[*Tenant]]
        mu  sync.Mutex
    }
}

func (s *TenantStore) shardFor(id string) int {
    h := fnv.New32()
    h.Write([]byte(id))
    return int(h.Sum32() % Shards)
}

func (s *TenantStore) Get(id string) (*Tenant, bool) {
    return s.shards[s.shardFor(id)].cur.Load().Get(id)
}

func (s *TenantStore) Update(id string, fn func(*Tenant) *Tenant) error {
    sh := &s.shards[s.shardFor(id)]
    sh.mu.Lock()
    defer sh.mu.Unlock()
    old := sh.cur.Load()
    cur, _ := old.Get(id)
    next := fn(cur)
    if err := next.Validate(); err != nil {
        return err
    }
    sh.cur.Store(old.Set(id, next))
    return nil
}

Now writes truly parallelise across shards. 500 writes/sec across 64 shards = ~8 writes/sec/shard. Trivial contention.

Design step 7: Observability¶

Per-shard metrics: - tenant_count{shard="0..63"} — gauge. - tenant_updates_total{shard} — counter.

Aggregate metrics: - tenant_snapshot_size_bytes — gauge (sum across shards). - tenant_update_latency_seconds — histogram. - tenant_pinned_snapshots — gauge (in-flight requests × shards).

A dashboard correlates update latency spikes with regional failover events.

Design step 8: Failure modes¶

What happens if:

• A bad update slips through validation. It is published, then noticed in flight. Mitigation: per-update audit log, fast rollback by republishing the previous version.
• A region goes down and we update 5 000 tenants in 1 minute. Spread across 64 shards, this is manageable; per-shard burst ~80 writes per minute.
• The control plane sends an inconsistent batch update. Mitigation: idempotent update protocol with version checks.
• A pinned snapshot leaks because of a hung request. Mitigation: request timeouts via context.

Design step 9: Backup and recovery¶

In a crash, snapshot state is lost (it's in-memory). On restart:

• Fetch full snapshot from control plane (~25 MB transfer).
• Rebuild HAMT shards from the snapshot.
• Subscribe to incremental updates.

Bootstrap latency: ~5 sec from cold start. Acceptable for a service designed to scale-out and be replaced.

Design step 10: Putting it all together¶

The final design uses: - Sharded COW (64 shards) for write parallelism. - Persistent HAMT inside each shard for cheap writes. - Per-request snapshot pin via context for read consistency. - Per-shard mutex for writer coordination. - Validation before publish. - Structured metrics for observability. - Periodic refresh from control plane for crash recovery.

Expected production characteristics: - p99 read latency: ~50 ns. - p99 write latency: ~10 µs. - Memory: ~100 MB steady state, +50 MB transient during bursts. - GC pause: <1 ms. - Reload time on cold start: ~5 sec.

This is a senior-level COW design for a production system at scale.

Advanced Patterns: Snapshot Composition¶

Real systems compose snapshots in subtle ways. The patterns below extend the toolkit.

Composition pattern 1: Layered snapshots¶

A snapshot has a "base" and an "override" layer:

type Layered struct {
    Base    *Map
    Override *Map
}

func (l *Layered) Get(k string) (string, bool) {
    if v, ok := l.Override.Get(k); ok {
        return v, ok
    }
    return l.Base.Get(k)
}

The base is large and rarely updated. The override is small and updated frequently. Both are independently COW.

When the override grows large, "flatten" it into the base:

func Flatten(l *Layered) *Layered {
    newBase := l.Base
    l.Override.Range(func(k, v string) bool {
        newBase = newBase.Set(k, v)
        return true
    })
    return &Layered{Base: newBase, Override: New()}
}

This is the LSM-style hierarchy applied to in-memory COW.

Composition pattern 2: Hierarchical configuration¶

A snapshot has parent-child relationships:

type ConfigNode struct {
    Name     string
    Settings map[string]string
    Parent   *ConfigNode // shared!
}

func (n *ConfigNode) Lookup(k string) (string, bool) {
    if v, ok := n.Settings[k]; ok {
        return v, ok
    }
    if n.Parent != nil {
        return n.Parent.Lookup(k)
    }
    return "", false
}

Children point at parents. Updates to a child create a new child; the parent is shared. The whole tree is a snapshot.

Cost per child update: just the child. The rest of the tree is reused.

Composition pattern 3: Indexed snapshots¶

A snapshot maintains multiple indexes:

type Snapshot struct {
    byID      map[string]*Item
    byCategory map[string][]*Item
    byTag     map[string][]*Item
}

A single update touches all indexes. Build them all in the writer:

func (s *Store) AddItem(item *Item) {
    s.mu.Lock()
    defer s.mu.Unlock()
    old := s.cur.Load()
    next := &Snapshot{
        byID:       cloneMap(old.byID),
        byCategory: cloneMapOfSlices(old.byCategory),
        byTag:      cloneMapOfSlices(old.byTag),
    }
    next.byID[item.ID] = item
    next.byCategory[item.Category] = append(next.byCategory[item.Category], item)
    for _, tag := range item.Tags {
        next.byTag[tag] = append(next.byTag[tag], item)
    }
    s.cur.Store(next)
}

Readers can query by any index against a consistent snapshot. Writes are more expensive but rare.

Composition pattern 4: Snapshot deltas¶

Store only the diff from the previous snapshot:

type Delta struct {
    Prev    *Delta
    Adds    map[string]string
    Removes []string
}

func (d *Delta) Get(k string) (string, bool) {
    if d == nil { return "", false }
    for _, r := range d.Removes {
        if r == k { return "", false }
    }
    if v, ok := d.Adds[k]; ok { return v, true }
    return d.Prev.Get(k)
}