Production Structures

LRU Cache

A cache trades memory for time: keep the answers that were expensive to compute or fetch. Memory is bounded, so when the cache is full something must be removed. Least recently used removes the entry untouched for the longest time, on the bet that recent use predicts future use. The demo is 73_lru_cache.go.

Two Structures, One Cache

To make every operation O(1), two structures cooperate. A hash map finds an entry by key. A doubly linked list keeps the entries in recency order: the front is the most recently used, the back is the next victim. Neither works alone: a map has no order, and a list cannot find a key without walking it.

The map points into the list. A hit moves the node to the front; eviction takes the node before TAIL.

Two sentinel nodes, head and tail, remove every special case: the list is never empty, and unlinking a node is always the same four pointer writes (the same idea as the sentinel list in Linked Lists).

type node[K comparable, V any] struct {
	key        K
	val        V
	expires    int64 // 0 means "never"
	prev, next *node[K, V]
}

func (c *LRU[K, V]) unlink(n *node[K, V]) {
	n.prev.next = n.next
	n.next.prev = n.prev
}

func (c *LRU[K, V]) pushFront(n *node[K, V]) {
	n.prev = &c.head
	n.next = c.head.next
	c.head.next.prev = n
	c.head.next = n
}

func (c *LRU[K, V]) Get(k K) (V, bool) {
	n, ok := c.items[k]
	if ok && n.expires != 0 && c.now() >= n.expires {
		c.remove(n) // expired: treat as a miss
		ok = false
	}
	if !ok {
		c.Misses++
		var zero V
		return zero, false
	}
	c.Hits++
	c.unlink(n)
	c.pushFront(n) // now the most recently used
	return n.val, true
}

Note that the node stores its own key. When the tail node is evicted, the cache must also delete that key from the map, and the node is the only place that remembers which key it was.

Put mirrors Get. If the key exists, update it and move it to the front. Otherwise, if the cache is full, remove the node before tail (and its map entry), then insert the new node at the front. An optional OnEvict callback lets the owner flush or log what leaves.

Testing Against a Slow LRU

The oracle is a slice ordered by recency with a linear search: about ten lines, and obviously right. The demo replays 200,000 random operations (a third of them writes) on 120 distinct keys with capacity 50 through both caches, and compares every result and, every thousand steps, the full recency order. The result is 0 disagreements. A generic random test like this catches the bugs hand-written examples miss: an update that forgets to move the node, or an eviction that leaves the key in the map.

Time to Live

Cached data goes stale. PutTTL stores an expiry time, and Get removes an expired entry when it meets one (lazy expiry): no background thread, no timer per entry. The cost is that expired entries that nobody asks for still occupy memory until the LRU order pushes them out, which is bounded by the capacity anyway.

The clock is a func() int64 given to NewLRU. In production pass time.Now().UnixMilli; in a test pass a variable that the test advances. The demo puts a session with a 30-unit TTL and a token with a 10-unit TTL into the cache and reads at t = 0, 9, 10, 29, 30: the token disappears exactly at 10, the session exactly at 30, and the size drops from 2 to 1 to 0. Nothing sleeps, and nothing can flake.

How Big Should It Be?

Real request streams are skewed: a few keys are very popular. The demo draws 100,000 requests from 10,000 keys with a Zipf distribution and measures the hit ratio for different capacities:

The first hundred entries buy two thirds of the benefit, and doubling from there gives less each time. Measure the hit ratio of your own traffic before choosing a size: it decides whether memory spent on the cache is worth it.

The Weakness: Scans

LRU assumes that a key touched once is likely to be touched again. A report, a backup or a crawler reads many keys exactly once. The demo warms a 200-entry cache on skewed traffic (hit ratio 0.893), then reads 500 cold keys once each. Afterwards none of the 20 hottest keys is still cached, and the next 2,000 hot requests start with a hit ratio of only 0.859 while the cache refills. Remedies, in increasing effort: bypass the cache for bulk reads; use segmented LRU or 2Q, where a key must be seen twice before it can push out a proven one; or use an admission policy such as TinyLFU that compares a newcomer's estimated frequency (a Count-Min sketch) with the victim's.

One Caveat

Get writes (it moves a node), so even readers of an LRU need exclusive access. A plain sync.RWMutex does not help: use a sync.Mutex, or shard the cache (see Sharded Locks) so that different keys use different locks.

Rate Limiters

A rate limiter answers one question per request: allow or refuse? It protects a service from one client asking too often, and protects the client from its own retry loop. "At most 10 requests per second" sounds like one rule but has several implementations that differ in memory, in accuracy, and in what a clever client can get away with. The demo is 74_rate_limiters.go; all four limiters implement Allow(nowMs int64) bool.

Four Policies

The Boundary Attack

The fixed window resets its counter at every whole second. A client that sends 10 requests at 981–990 ms and 10 more at 1000–1009 ms is within the limit in both windows, yet 20 requests arrived within 30 ms. The demo sends exactly that traffic to all four limiters and reports the largest number accepted in any span of 1,000 ms:

The sliding log is exact, and the sliding counter is off by one here because it estimates the previous window's contribution. The token bucket passes the burst it has tokens for and nothing more.

The Token Bucket

Picture a bucket that holds at most burst tokens and gains rate tokens per second. A request removes one token and is allowed; with no token it is refused. The rate limits the average, the bucket size limits the burst, and the state is two numbers.

No timer refills the bucket: the refill is computed from the elapsed time when a request arrives.

// Tokens are stored in thousandths so the arithmetic stays exact in integers.
type TokenBucket struct {
	burstMilli  int64
	ratePerSec  int64
	milliTokens int64
	last        int64
	initialized bool
}

func (b *TokenBucket) Allow(now int64) bool {
	if !b.initialized {
		b.last, b.initialized = now, true
	}
	// ratePerSec tokens per 1000 ms is ratePerSec milli-tokens per ms
	b.milliTokens = min(b.burstMilli, b.milliTokens+(now-b.last)*b.ratePerSec)
	b.last = now
	if b.milliTokens < 1000 {
		return false
	}
	b.milliTokens -= 1000
	return true
}

Floating-point tokens would work too, but repeated additions of 0.001 drift; integer milli-tokens make the demo's results exact. The demo's timeline uses rate 2 per second and burst 4, and requests at 0, 0, 0, 0, 0, 100, 500, 1000, 1000, 1500, 2000 ms and six at 6000 ms. The pattern of answers is YYYYnnYYnYYYYYYnn: four instant tokens, refusals while the bucket is empty, one token per 500 ms afterwards, and after a long silence the bucket refills only to the burst size, so four of the six requests at 6000 ms pass and two do not.

A second test sends a burst of 25 at t = 0, then 20 requests per second for two seconds. Every limiter accepts only 10 of the burst. Over the next two seconds the three window limiters accept 20 of the 40 requests, exactly 10 per second. The token bucket accepts 29: it refilled its 10 tokens during the pause and spends that saved burst on top of the steady rate. Neither behavior is wrong; they are different promises.

Which Guarantee Do You Need?

The demo also sends 20 random traffic patterns of 200 requests over 5 seconds to each limiter and records the worst span of 1 second:

For an API quota ("1000 calls per hour") a fixed window is simple and adequate. To protect a fragile backend, use a sliding window or a small bucket. When bursts are acceptable but the average must be bounded, which is the common case for user-facing traffic, use a token bucket. To limit a whole fleet, keep the counter in a shared store; the same arithmetic applies, but every check becomes a network round trip, so a per-node bucket that refills from a global budget is a common compromise.

Consistent Hashing

A cache or database is split over N servers. The obvious rule is server = hash(key) % N. It balances well, but when a server is added N changes, and almost every key maps somewhere new: a cache loses nearly all its contents at once, and the database behind it takes the whole load. The demo is 75_consistent_hashing.go.

The Ring

Hash the servers onto a circle of 2⁶⁴ positions, and hash every key onto the same circle. A key belongs to the first server met walking clockwise from the key. Adding a server takes over only the arc before its points, about 1/(N+1) of the keys; everything else stays where it is.

The red arc is all that changes when D joins.

The ring is a sorted slice of (hash, server) points. A lookup is one binary search, O(log P) for P points, with a wrap to index 0 when the search runs off the end:

func (r *Ring) Get(key string) string {
	h := hash64(key)
	i := sort.Search(len(r.points), func(i int) bool { return r.points[i].hash >= h })
	if i == len(r.points) {
		i = 0 // past the last point: wrap around to the first
	}
	return r.points[i].server
}

The oracle is the definition itself, by brute force: the point with the smallest clockwise distance from the key, computed with uint64 subtraction, which wraps around exactly like the circle. The two agree on all 50,000 test keys.

How Many Keys Move?

The demo goes from 10 servers to 11 and counts how many of 100,000 keys change server:

The ring also guarantees where keys move: not one key moved between two old servers; all of them went to the new one. Removing a server works in reverse. After removing one of ten, 9.9% of the keys move, none of them stays on the dead server, and none moved that did not have to.

Virtual Nodes

With one point per server the arcs have very different lengths. Give each server many points ("node-03#0", "node-03#1", ...) and the arcs average out. The demo hashes 100,000 keys onto 10 servers:

With one point one server carries 5.4 times the average and another almost nothing. The imbalance shrinks roughly like 1/√(virtual nodes), so each tenfold increase in memory buys a threefold improvement, and 100 to 200 points per server is a common choice. Virtual nodes also let you give a stronger machine more points than a weaker one.

Replicas and Rendezvous Hashing

To store each key on three servers, walk clockwise from the key and collect the first three distinct servers (skipping further points of a server already chosen). The demo prints such lists, for example user:1 → [node-00 node-02 node-05]. When a server dies, its keys already have copies on the next servers along the ring.

Rendezvous hashing (highest random weight) needs no ring. Give every (server, key) pair a score, hash(server + "|" + key), and pick the server with the highest one. When a server is added it wins exactly the keys for which it has the top score, about 1/(N+1) of them, and the distribution is perfectly even without virtual nodes. The price is O(N) work per lookup, which is fine for tens of servers and too slow for thousands. Its stateless simplicity makes it a good default for small clusters.

Concurrent Structures

A Go map, slice or linked list is not safe for use by several goroutines at once. Two writers can corrupt the structure, and the runtime may stop the program with fatal error: concurrent map writes. A shared structure needs a plan. The demo is 76_concurrent_structures.go: eight goroutines, 50,000 operations each. Every check has one right answer, so the output is identical on every run even though the schedule is not. Also run it with go run -race where the race detector is available: it reports unsynchronized access even when the result happens to be right.

From Simple to Delicate

Start at the top of the table. A mutex around a map is correct, simple and fast enough far more often than expected. Move down only when a profile shows contention.

Counters: Mutex and Atomic

Incrementing n++ is three steps (read, add, write). Two goroutines can read the same value and both write back the same result, losing one increment. Both the mutex and the atomic version of the demo produce exactly 400,000 for 8 × 50,000 increments:

var mu sync.Mutex
locked := 0
parallel(func(int) {
	for i := 0; i < perWorker; i++ {
		mu.Lock()
		locked++
		mu.Unlock()
	}
})

var atom atomic.Int64
parallel(func(int) {
	for i := 0; i < perWorker; i++ {
		atom.Add(1) // one hardware instruction, no lock
	}
})

The atomic is cheaper, but it protects exactly one variable. As soon as two values must change together (a balance and a counter), you need the mutex.

Sharded Locks

One lock around one map serializes every operation. Split the map into 16 shards, each with its own lock, and choose the shard by hashing the key: two goroutines wait for each other only when their keys fall in the same shard.

type Sharded struct {
	shards []SafeMap // each has its own RWMutex and map
}

func (s *Sharded) shard(k string) *SafeMap {
	h := fnv.New32a()
	h.Write([]byte(k))
	return &s.shards[h.Sum32()%uint32(len(s.shards))]
}

func (s *Sharded) Add(k string, d int) { s.shard(k).Add(k, d) }

In the demo both versions give the same answers: 1,000 keys and a total of 400,000. Speed is a separate question that depends on the machine, so measure it with a benchmark (go test -bench) rather than trusting a rule of thumb. The cost of sharding is visible in Len(), which must lock and visit every shard, and it gives no consistent snapshot unless all shards are locked together. Go's sync.Map is a different tool: it is tuned for keys written once and read many times, or for goroutines that touch disjoint keys.

A Lock-Free Stack

A lock-free structure has one shared word and changes it with compare-and-swap (CAS): "set the head to new only if it still equals old; tell me whether it worked". If another goroutine changed it first, read again and retry. No goroutine ever waits holding a lock.

type Stack[T any] struct {
	head atomic.Pointer[stackNode[T]]
}

func (s *Stack[T]) Push(v T) {
	n := &stackNode[T]{val: v}
	for {
		old := s.head.Load()
		n.next = old
		if s.head.CompareAndSwap(old, n) {
			return
		}
	}
}

func (s *Stack[T]) Pop() (T, bool) {
	for {
		old := s.head.Load()
		if old == nil {
			var zero T
			return zero, false
		}
		if s.head.CompareAndSwap(old, old.next) {
			return old.val, true
		}
	}
}

The demo pushes 400,000 distinct numbers from 8 goroutines, then pops them from 8 goroutines and marks each one in a table. Result: 400,000 popped, 0 duplicates, 0 missing. In C this design suffers from the ABA problem: a node is popped, freed, reallocated at the same address and pushed again, so a stale CAS succeeds when it should not. Go's garbage collector never reuses a node that some goroutine still references, so the problem cannot occur here. Do not extend the idea casually: a lock-free queue or map is a research-grade exercise, and the standard library and well-tested packages already have them.

Bounded Queues and Worker Pools

A buffered channel is a bounded concurrent queue. The producer blocks when the buffer is full, which gives backpressure: a slow consumer slows the producer down instead of letting memory grow without limit.

jobs := make(chan int, 64) // at most 64 waiting jobs
results := make(chan int, 64)

var wg sync.WaitGroup
for w := 0; w < workers; w++ {
	wg.Add(1)
	go func() {
		defer wg.Done()
		for j := range jobs { // ends when jobs is closed and drained
			results <- j * j
		}
	}()
}
go func() { // producer
	for i := 1; i <= 10000; i++ {
		jobs <- i
	}
	close(jobs)
}()
go func() { wg.Wait(); close(results) }()

The demo sums the squares of 1 to 10,000 through eight workers and gets 333,383,335,000, the value of the formula n(n+1)(2n+1)/6. The closing order matters: the producer closes jobs, the workers finish, and only then is results closed, by the goroutine that waits for the workers. Closing a channel from a sender that is not the last one is a panic.

Cache Stampede and Call Collapsing

A popular cache entry expires. In the next millisecond 200 requests miss, and all 200 run the same slow database query. The database, which the cache was there to protect, is hit hardest at the worst moment. Call collapsing (the idea of golang.org/x/sync/singleflight) lets the first caller run the load while the others wait and share its result:

func (g *Group) Do(key string, load func() string) string {
	g.mu.Lock()
	if c, ok := g.calls[key]; ok { // a load is in flight: wait for it
		g.mu.Unlock()
		c.wg.Wait()
		return c.val
	}
	c := &call{}
	c.wg.Add(1)
	g.calls[key] = c
	g.mu.Unlock()

	c.val = load() // only this goroutine loads
	c.wg.Done()

	g.mu.Lock()
	delete(g.calls, key)
	g.mu.Unlock()
	return c.val
}

To test it without depending on timing, the slow load in the demo finishes only after a counter shows that the other 199 callers have joined it. Result: all 200 callers get 42 rows and the "database" ran exactly 1 load. This version does not share errors or handle a panicking loader; the library version does, so prefer it in real code.

Choosing a Structure

Common Pitfalls

Calling time.Now() Inside the Logic

Code that reads the wall clock directly can only be tested by sleeping, which is slow and flaky. Pass the time in, as the demos do. In production also prefer a monotonic clock for durations, since the wall clock can jump when it is adjusted.

Forgetting Half of an Eviction

An LRU removes the node from the list and the key from the map. Missing either leaves a dangling pointer or a leak. The random test against a slow oracle finds this at once; a few hand-picked examples usually do not.

Unbounded Caches

A map used as a cache with no eviction is a memory leak with a delay. Every cache needs a capacity, a TTL or both, and its hit ratio should be a metric you watch.

Locking Readers That Write

A read lock is only valid if the "read" really does not modify anything. An LRU Get moves a node, so a RWMutex read lock around it is a data race that may work for months.

Rebuilding a Ring Per Request, or Too Few Points

Build the ring once and share it; rebuild only when membership changes, and swap in the new ring atomically. Also do not run with one or a few points per server: the load is then visibly uneven.

Goroutines That Never End

A worker blocked on a channel nobody closes, or a waiter on a load that never finishes, stays alive for the life of the process. Every goroutine needs a way to stop: closing the input channel, a context, or a timeout.

Holding a Lock While Calling Out

Do not hold a mutex while calling a function that may block or lock something else (the load in a cache miss, an eviction callback that logs to a slow sink). Copy what you need, unlock, then call. Two locks taken in different orders in different places will eventually deadlock; keep one order.

Practice Lab

Each exercise breaks one detail. Predict what will fail, run the demo, and explain which check notices.

Run the Demos

1. In 73_lru_cache.go, remove the two lines c.unlink(n) and c.pushFront(n) from the hit path of Get. The cache still returns correct values. Which check now fails, and why does a cache that is never wrong about values still count as broken? Then change >= to > in the expiry test: which of the readings at t = 10 and t = 30 changes?
2. In 74_rate_limiters.go, change b.milliTokens -= 1000 to b.milliTokens = 0 (empty the bucket on every request). How does the answer pattern in the timeline demo change? Then in SlidingLog.Allow change >= to > in len(s.stamps) >= s.limit: which check reports 11?
3. In 75_consistent_hashing.go, change the wrap-around in Get from i = 0 to i = len(r.points) - 1. Which comparison notices, and which keys are affected (hint: those beyond the last point)? Then set the vnodes in the first demo to 1: how much of the movement guarantee survives?
4. In 76_concurrent_structures.go, replace atom.Add(1) with n++ on a plain shared int. What total do you get, does it change between runs, and what does -race report? Then change CompareAndSwap(old, n) in Push to a plain store s.head.Store(n): how many popped values go missing?

Exercises

1. LFU cache. Evict the least frequently used entry instead. Keep a map from frequency to a list of keys plus the current minimum frequency so that every operation stays O(1). Replay the scan experiment: does one scan still flush the hot keys?
2. Segmented LRU. Split the cache into a probation segment and a protected segment. A key enters probation and moves to protected only on its second hit. Measure the hit ratio after the scan against plain LRU.
3. Leaky bucket. Implement the limiter that drains a queue at a constant rate and refuses when the queue is full. How does its output differ from a token bucket's?
4. Per-client limits. Keep one token bucket per client id in an LRU cache so memory stays bounded. What should happen when a client's bucket is evicted, and can a client exploit that?
5. Weighted ring. Give one server three times the virtual nodes of the others. Confirm that it receives about three times the keys, then remove it and check that its keys spread over the others.
6. Jump consistent hash. Look up Google's jump hash: it maps a key to one of N buckets in O(1) space and moves only 1/(N+1) of the keys when N grows. What can it not do that a ring can?
7. Concurrent LRU. Shard the LRU into 16 independent caches by key hash. Compare the total hit ratio with a single cache of the same total size, and explain the difference.

This lesson completes Phase 4. Continue with Demo Examples for the full list of runnable programs, then the samples and references.