Appendix B-Build-From-Scratch Data Structures and Patterns¶
A working Go engineer should have implemented each of the following at least once, with - race - clean tests, allocation benchmarks, and goroutine-leak verification (where concurrent). This appendix sketches the minimal-viable design for each.
B.1 Lock-Free SPSC Ring Buffer¶
When: real-time control loops, log shippers, audio paths, any 1-producer-1-consumer with strict latency budgets.
Design:
- [Cap]T backing array (Cap a power of two for cheap modulo).
- head and tail are atomic.Uint64, each on its own cache line ([7]uint64 padding).
- Producer: load tail (relaxed), check space against head, write slot, store tail with release semantics (in Go: any atomic store).
- Consumer: symmetric.
- Wait-free per side; needs no CAS, only atomic loads/stores.
Lab outcomes: cache-line awareness, the Go memory model in practice, why chan T is not always the answer.
B.2 Lock-Free MPMC Bounded Queue¶
When: work-stealing schedulers, bounded work pools where contention is significant.
Design:
- Slot array; each slot is atomic.Uint64 encoding (seq, occupied flag).
- Producer CAS the seq from "empty at lap N" to "occupied at lap N".
- Consumer CAS from "occupied at lap N" to "empty at lap N+1".
- Avoids the ABA problem; same algorithm as Vyukov's bounded MPMC queue.
Lab outcomes: encoding state in atomics, lock-free without epoch reclamation, why the modular-arithmetic seq counter is correct.
B.3 Sharded Map¶
When: high-concurrency read+write workloads. Always consider this before reaching for sync.Map.
Design:
- N shards (typically 16–64), each struct{ sync.RWMutex; m map[K]V }.
- Hash key, mod N, lock the shard, perform the op.
- Iteration: lock shards in order, snapshot or hold each.
Lab outcomes: sync.Map vs sharded vs RWMutex+map comparison; xxhash for non-string keys; the cost of interface{} boxing at the API boundary (use generics).
B.4 LRU Cache¶
When: API caches, decoded-value caches, anything where hot data fits and cold should evict.
Design: - Doubly-linked list of entries; map from key to list-element. - On hit: move to front. On miss + full: evict back; allocate new at front. - Concurrent variant: shard by key, per-shard mutex + per-shard list.
Lab outcomes: pointer hygiene in linked structures; the standard container/list is fine but allocates an extra struct per entry-for hot caches, an inlined doubly-linked list of the entries themselves saves ~30% memory.
B.5 Bloom Filter¶
When: "definitely-not-in-set" pre-checks in front of expensive lookups (DB, network).
Design:
- Bit array of size m, k hash functions.
- Add: set k bits.
- Contains: all k bits set ⇒ probably in set; any unset ⇒ definitely not.
- Tune m and k for target false-positive rate.
Lab outcomes: hash mixing (hash/maphash is the right primitive in modern Go), the math of false positives, when not to use one (size of input, write-amplification).
B.6 Concurrent Skiplist¶
When: ordered concurrent maps; the foundation of, e.g., RocksDB-style memtables.
Design: - Tower of forward pointers per node, height geometrically distributed. - Insert: build new node bottom-up, link levels via CAS. - Removal: logical (mark deleted) then physical (unlink).
Lab outcomes: lock-free with non-trivial structure, randomization in algorithm design, the alternative to balanced trees in concurrent settings.
B.7 Worker Pool With Backpressure¶
When: every production service.
Design:
- N workers consuming from a buffered task channel.
- Submission: non-blocking try-send with overflow → drop-with-metric, or blocking send for back-pressure.
- Per-task timeout: derived context.
- Panic isolation: each worker's task call is wrapped in defer recover().
- Graceful shutdown: ctx.Done() triggers drain with a deadline.
Lab outcomes: this is the worker pool from week 12, refined.
B.8 Rate Limiter¶
When: ingress protection, downstream-call throttling, fair multi-tenant scheduling.
Design:
- Token bucket (golang.org/x/time/rate): refill at fixed rate up to a burst capacity.
- Leaky bucket: same shape, different metaphor.
- For per-key limiting: an LRU-bounded map of token-buckets.
Lab outcomes: study x/time/rate source-it is small and elegant; understand the difference between Allow() (immediate decision), Wait(ctx) (block until token), Reserve() (return a reservation that can be cancelled).
B.9 Circuit Breaker¶
When: any client of an external service.
Design:
- Three states: Closed (normal), Open (fail fast), HalfOpen (probe).
- Counts failures; on threshold → Open.
- After cooldown → HalfOpen; one probe → Closed on success, Open on failure.
- sony/gobreaker is a battle-tested reference; read its source then build your own.
Lab outcomes: state machines without globals; per-endpoint instances; the metric exports that operations actually wants (state changes, failure rate).
B.10 Singleflight¶
When: cache stampede mitigation, deduplicating concurrent identical requests.
Design:
- A map[key]*call where call holds the result/error and a sync.WaitGroup.
- First caller for a key creates the call, runs the work, signals completion.
- Concurrent callers for the same key wait on the WaitGroup, share the result.
Lab outcomes: study golang.org/x/sync/singleflight; understand why the result-shape is (value, err, shared) (the shared flag matters for caches).
B.11 Lock-Free Counter / Histogram¶
When: high-frequency metrics where contention on a single atomic kills throughput.
Design:
- N per-CPU (or per-P) counters; aggregate on read.
- Use runtime.GOMAXPROCS + manual sharding, or sync/atomic with cache-line padding per shard.
- Prometheus's prometheus.NewCounter is single-atomic and is fine for most uses; only build this when profiling shows contention.
Lab outcomes: why atomic.AddInt64 becomes the bottleneck at >10M/s/core; the cost of false sharing in metrics implementations.
Difficulty Ranking¶
| Tier | Structures |
|---|---|
| Warmup | Worker pool, LRU, Sharded map |
| Intermediate | Rate limiter, Circuit breaker, Bloom filter, Singleflight |
| Advanced | SPSC ring, MPMC queue, Lock-free counter |
| Expert | Concurrent skiplist |
Pick at least one from each tier. Ship with - racetests, allocation benchmarks, andgoleak`.