Shard Your Locks in Go: Benchmarking Four Cache Designs

In my previous post I built the same in-memory cache four times in Zig and measured how each version behaves when you add threads. The idea came from a post that does this in Go with six designs and I promised myself a Go version of my own, on the same machine and with the same method, so that the two sets of numbers can sit next to each other and this post has the Go side. The ranking is the same as in Zig. One mutex gets slower as you add cores, the read-write lock helps less than you expect and sharding the lock is what scales. The absolute numbers are different though and the difference comes from the map and not from the locks.

The contenders Link to heading

All four designs store string keys with string values in a map[string]string and offer the same Get() and Put() methods. They differ only in how they lock the map.

• mutex. One sync.Mutex around one map. Every operation, read or write, takes the same lock.
• rwlock. One sync.RWMutex around one map. Readers take the lock with RLock() and many of them can hold it at the same time. A writer takes it with Lock() and waits for all readers to leave.
• sharded. The data is split into 64 maps and each one has its own sync.Mutex. The hash of the key picks the map, so two goroutines that work on different keys rarely touch the same lock.
• sharded-rw. The same 64 shards, each one with a sync.RWMutex instead of a mutex.

I left out sync.Map and the copy-on-write design of the original post on purpose. The point of this post is to compare the same four designs with the Zig post and both of those designs have no equivalent in Zig. The original post measures both of them.

The code Link to heading

package main

import (
	"fmt"
	"hash/maphash"
	"math/rand/v2"
	"os"
	"runtime"
	"strconv"
	"sync"
	"sync/atomic"
	"time"
)

const (
	nKeys    = 1_000_000
	totalOps = 8_000_000
	useDefer = true
	padBytes = 112 // pads a shard to one 128-byte cache line, 0 to switch it off
)

var seed = maphash.MakeSeed()

// Locker is what a shard needs: a lock with a read side and a write side.
type Locker interface {
	LockRead()
	UnlockRead()
	LockWrite()
	UnlockWrite()
}

// MutexLock gives sync.Mutex the read/write interface of a RWMutex.
type MutexLock struct{ mu sync.Mutex }

func (l *MutexLock) LockRead()    { l.mu.Lock() }
func (l *MutexLock) UnlockRead()  { l.mu.Unlock() }
func (l *MutexLock) LockWrite()   { l.mu.Lock() }
func (l *MutexLock) UnlockWrite() { l.mu.Unlock() }

type RwLock struct{ mu sync.RWMutex }

func (l *RwLock) LockRead()    { l.mu.RLock() }
func (l *RwLock) UnlockRead()  { l.mu.RUnlock() }
func (l *RwLock) LockWrite()   { l.mu.Lock() }
func (l *RwLock) UnlockWrite() { l.mu.Unlock() }

type shard[L any] struct {
	lock L
	m    map[string]string
	_    [padBytes]byte
}

// Cache splits the keys among n shards, each with a lock of type L.
type Cache[L any, PL interface {
	*L
	Locker
}] struct {
	shards []shard[L]
	mask   uint64
}

func NewCache[L any, PL interface {
	*L
	Locker
}](n int) *Cache[L, PL] {
	if n&(n-1) != 0 {
		panic("shards must be a power of two")
	}
	c := &Cache[L, PL]{shards: make([]shard[L], n), mask: uint64(n - 1)}
	for i := range c.shards {
		c.shards[i].m = make(map[string]string, nKeys/n)
	}
	return c
}

func (c *Cache[L, PL]) shardOf(key string) *shard[L] {
	if len(c.shards) == 1 {
		return &c.shards[0]
	}
	return &c.shards[maphash.String(seed, key)&c.mask]
}

func (c *Cache[L, PL]) Get(key string) (string, bool) {
	s := c.shardOf(key)
	PL(&s.lock).LockRead()
	if useDefer {
		defer PL(&s.lock).UnlockRead()
		v, ok := s.m[key]
		return v, ok
	}
	v, ok := s.m[key]
	PL(&s.lock).UnlockRead()
	return v, ok
}

func (c *Cache[L, PL]) Put(key, value string) {
	s := c.shardOf(key)
	PL(&s.lock).LockWrite()
	defer PL(&s.lock).UnlockWrite()
	s.m[key] = value
}

type cache interface {
	Get(key string) (string, bool)
	Put(key, value string)
}

var sink atomic.Int64

func worker(c cache, keys []string, ops int, readPct int, seed uint64, wg *sync.WaitGroup) {
	defer wg.Done()
	rng := rand.New(rand.NewPCG(seed, seed))
	found := 0
	for range ops {
		key := keys[rng.IntN(len(keys))]
		if rng.IntN(100) < readPct {
			if v, ok := c.Get(key); ok {
				found += len(v)
			}
		} else {
			c.Put(key, "updated")
		}
	}
	sink.Add(int64(found))
}

func run(c cache, keys []string, readPct, nGoroutines int) float64 {
	for _, key := range keys {
		c.Put(key, "initial")
	}
	ops := totalOps / nGoroutines
	var wg sync.WaitGroup
	start := time.Now()
	for i := range nGoroutines {
		wg.Add(1)
		go worker(c, keys, ops, readPct, uint64(i+1), &wg)
	}
	wg.Wait()
	elapsed := time.Since(start)
	return float64(elapsed.Nanoseconds()) / float64(ops*nGoroutines)
}

func main() {
	if len(os.Args) != 5 && len(os.Args) != 6 {
		fmt.Fprintln(os.Stderr, "usage: locks <mutex|rwlock> <shards> <read_pct> <goroutines> [procs]")
		os.Exit(1)
	}
	design := os.Args[1]
	shards, _ := strconv.Atoi(os.Args[2])
	readPct, _ := strconv.Atoi(os.Args[3])
	nGoroutines, _ := strconv.Atoi(os.Args[4])
	procs := nGoroutines
	if len(os.Args) == 6 {
		procs, _ = strconv.Atoi(os.Args[5])
	}
	runtime.GOMAXPROCS(procs)

	keys := make([]string, nKeys)
	for i := range keys {
		keys[i] = "key-" + strconv.Itoa(i)
	}

	var c cache
	switch design {
	case "mutex":
		c = NewCache[MutexLock](shards)
	case "rwlock":
		c = NewCache[RwLock](shards)
	default:
		fmt.Fprintln(os.Stderr, "unknown design:", design)
		os.Exit(1)
	}

	nsPerOp := run(c, keys, readPct, nGoroutines)
	fmt.Printf("%s,%d,%d,%d,%.1f\n", design, shards, readPct, nGoroutines, nsPerOp)
}

The two small types at the top, MutexLock and RwLock, give the mutex and the read-write lock the same four methods, which is what the Locker interface asks for. The MutexLock type implements LockRead() with a plain Lock(), because a mutex has no shared mode. The Cache type is generic over the lock type. The second type parameter, PL, is the usual trick for calling pointer methods on a generic value. It says that *L implements Locker, so PL(&s.lock).LockRead() compiles and the call is direct and not through an interface. The NewCache() function takes the number of shards, which has to be a power of two because shardOf() masks the hash. With one shard it skips the hash and returns the only shard there is. With more shards it hashes the key with hash/maphash, which is the hash function that Go maps use internally, with a random seed of its own.

Each shard holds its lock, its map and a padding field of 112 bytes. A sync.Mutex is 8 bytes and a map is a pointer, so 112 bytes of padding make the mutex shard exactly 128 bytes, which is one cache line on Apple Silicon. This way two mutex shards never share a cache line. A sync.RWMutex is 24 bytes, so the shard of the sharded-rw design is 144 bytes and I left it at that. I come back to this near the end of the post. The worker() function is what every goroutine runs. It picks a random key, reads it with probability readPct and overwrites it otherwise. The sum of the lengths goes to an atomic package variable so that the compiler cannot remove the reads. The run() function fills the cache with every key, starts the goroutines, waits for them with a sync.WaitGroup and divides the elapsed time by the total number of operations.

How I measured Link to heading

The setup is the same as in the Zig post. The program creates one million keys up front, from key-0 to key-999999 and inserts all of them before the clock starts, so every read finds its key. The goroutines perform 8 million operations in total, split evenly among them. The read ratio is 100, 90, 50 or 10 percent and the number of goroutines is 1, 2, 4 or 8. The program sets GOMAXPROCS to the number of goroutines, so a run with 4 goroutines uses 4 cores, which is what the original post does too. I built the program with go build and no flags and ran every combination 5 times. The numbers that follow are the medians. The experiments ran on macOS on a Mac with an Apple M4 Pro CPU, which has 10 performance cores and 4 efficiency cores, so 8 goroutines fit on the performance cores. The Go version is 1.27.3.

Save the code as locks.go in its own directory and run one combination like this:

$ go version
go version go1.27.3 darwin/arm64
$ go mod init locks
$ go build -o locks .
$ ./locks mutex 1 50 8
mutex,1,50,8,346.1
$ ./locks mutex 64 50 8
mutex,64,50,8,40.8

The arguments are the lock type, the number of shards, the read percentage and the number of goroutines and the output is one CSV line with the nanoseconds per operation at the end. An optional fifth argument sets GOMAXPROCS on its own, so ./locks mutex 64 50 1024 8 runs 1024 goroutines on 8 cores, which is what the fourth plot below uses. The format is the same as in the Zig program, so the shell loop and the Python script that made the plots for the Zig post made these plots as well.

The results Link to heading

The first plot shows how each design scales on the balanced workload, where half of the operations are reads. The y axis is the speedup over the run with one goroutine, so a design that scales perfectly would follow the dashed line.

The single mutex gets slower when you add cores. One goroutine needs 173 ns per operation and 8 goroutines on 8 cores need 346 ns, so the cache does half the work per second with eight times the cores. Every Lock() and Unlock() call is an atomic operation on the same memory location, so the cache line that holds the mutex moves from core to core on every operation. When a goroutine finds the mutex taken it spins for a moment and then parks itself and the goroutine that unlocks has to wake it up through the scheduler. A sync.Mutex also has a starvation mode. When a goroutine waits for more than a millisecond the mutex starts handing itself directly to the goroutine at the head of the queue, which is fair and slow, because every handoff is a context switch. The read-write lock also gets slower with more cores, but less so and I come back to it with the second plot. The sharded design reaches 4.6 times the speed of one goroutine with 8 goroutines. It does not reach 8 because almost every lookup in a map of one million entries misses the CPU caches, so at some point the memory system is the limit and not the locks. The sharded design with read-write locks starts the same and falls behind the plain sharded design from two goroutines on.

The second plot shows the cost per operation with 8 goroutines on 8 cores for every workload. The y axis is logarithmic, because the slowest design is fifteen times slower than the fastest one.

This is where Go differs from Zig. In Zig the read-write lock lost to the mutex as soon as there were writes. In Go the sync.RWMutex beats the sync.Mutex with 8 goroutines under every workload, from 86 ns against 343 ns with only readers to 295 ns against 337 ns on the write-heavy workload. The read-write lock is still not fast, because with writes it is six times slower than sharding. The Go mutex is very slow under heavy contention because of the handoffs that I described above and the read-write lock lets the readers overlap, which keeps it away from the worst of the contention. The two sharded designs are between 23 and 69 ns in every column. The sharded design with read-write locks is the fastest of all when there are no writes and loses to the plain sharded design as soon as there are some, because a writer has to wait for all readers of its shard to leave and readers that arrive while a writer is waiting have to queue behind it.

The third plot shows what the number of shards does on the balanced workload with 8 goroutines. One shard is the mutex design.

Going from 1 to 64 shards makes the cache nine times faster. Going from 64 to 256 gives another 27 percent and 1024 shards are almost the same as 256. With 8 goroutines and 64 shards the chance that another goroutine is in your shard at the same time is about one in ten, which is what the step to 256 removes. After that the locks are no longer the problem and the time goes to the memory system. The original post picks 256 shards and my curve says the same thing. I kept 64 in the other plots so that the numbers can be compared with the Zig post. The shard count matters much more for the slowest operations than for the mean and I measured that in a follow-up post that times every operation.

The fourth plot only makes sense in Go. Threads are expensive, so in the Zig post the thread count stops at the number of cores. Goroutines are cheap and a server has thousands of them, so the interesting question is what happens to each design when far more goroutines than cores fight for the same cache. The plot keeps GOMAXPROCS at 8 and runs the balanced workload with 8 to 1024 goroutines.

The mutex gets slowly worse, from 330 ns with 8 goroutines to 412 ns with 1024, because the queue of parked goroutines gets longer and the mutex spends more of its time in starvation mode. The read-write lock holds at about 250 ns up to 64 goroutines and then climbs to 385 ns with 1024, where it is almost as slow as the mutex. The sharded design is not affected. It stays between 36 and 40 ns from 8 goroutines to 1024, because with 64 shards and 8 cores the number of goroutines that can run at the same time is still 8 and they rarely meet. The sharded design with read-write locks behaves differently. It gets faster when you add goroutines, from 66 ns with 8 to 43 ns with 64, because when a goroutine blocks on a writer the scheduler runs another goroutine on that core instead of leaving it idle. More goroutines than cores is not a problem for a sharded cache and the plain mutex per shard is still the best choice.

The plots show the shape of the results and the two tables below have the numbers behind them. The first table has one row per design and read ratio and one column per goroutine count, with GOMAXPROCS set to the same number, so the 4 goroutines column means 4 goroutines on 4 cores. Every cell is the median of 5 runs in nanoseconds per operation, so lower is better. Read across a row to see what adding cores does to one design and down a column to compare the designs at the same core count. The 8 goroutines column is what the second plot shows and the 50% rows are what the first plot shows, divided by their first cell.

The first column says that with one goroutine the choice does not matter. All sixteen cells are between 137 ns and 213 ns and most of that is the map lookup. The designs separate in the 2 goroutines column. The mutex goes from 173 ns to 293 ns with the second core alone, which is the biggest step in the row and the moment the lock starts to bounce between two cores, while the sharded design halves its time as it should. Down the 8 goroutines column the four rows of the mutex are within 20 ns of each other and the four rows of the sharded design within 10 ns. Once you hold the lock a read and a write cost about the same, so the read ratio makes no difference to either of them. The read ratio does change the numbers of the two designs with read-write locks, from 86 ns to 295 ns for the single lock and from 23 ns to 69 ns for the sharded one, because a read-write lock is only a different lock when there are readers to overlap.

The second table has the numbers behind the fourth plot. It keeps GOMAXPROCS at 8 and runs the balanced workload with 8 to 1024 goroutines, so the only thing that changes across a row is how many goroutines wait for the same locks. The 8 goroutines column should match the 50% rows of the 8 goroutines column above and it does within the noise of separate runs.

Read across the rows. The mutex row drifts up by a quarter from 8 to 1024 goroutines and never gets better. The read-write lock row is flat up to 64 goroutines and then jumps by 40 percent between 256 and 1024, because by then hundreds of readers and writers are parked on the same lock and every wake-up goes through the scheduler. The sharded row moves by 4 ns across the whole table, which is within the noise. The sharded-rw row goes down first and up later and the 64 goroutines cell is its best one, for the reason I gave under the plot.

Go against Zig Link to heading

The ranking is the same in both languages and the shapes of the curves are the same, but every Go number is bigger. With one goroutine the mutex design needs 173 ns per operation in Go and 55 ns in Zig. With 8 goroutines the sharded design needs 41 ns in Go and 19 ns in Zig. The locks are not the reason. I measured the pieces of the single goroutine case on their own and the random number generator costs 7 ns, an uncontended Lock() and Unlock() pair costs so little that it hides in the noise and a lookup in a map with one million entries costs about 120 ns. The same lookup in a map with 16000 entries costs 13 ns. Most of the time goes to the map, which is slow because one million entries do not fit in any cache and every lookup goes to memory. The Zig hash map pays for the same memory accesses, but in my measurements it pays less and I did not dig into why. For this post it does not matter. The locks behave the same way in both languages and sharding fixes them in the same way.

What is different is the mutex under contention. The Zig mutex with 8 threads costs 135 ns per operation on the balanced workload and the Go mutex costs 346 ns. The Zig mutex is only a futex with a three-state word. The Go mutex has the spinning, the parking, the wake-ups through the scheduler and the starvation mode and all of that is good for fairness and bad for throughput when 8 cores fight for the same lock. That is also why the read-write lock beats the mutex in Go and loses to it in Zig. In Go the mutex is slow and that is what makes the read-write lock look good.

Hash seed, padding and defer Link to heading

Go takes care of the hash seed for you. In the Zig post my first version of the sharded cache was three times slower than it should have been, because the function that picked the shard and the function that picked the slot inside the hash map were the same function with the same seed, so every map could use only one slot in 64. You cannot make this mistake in Go. The runtime map uses a hash seed that you cannot see and every map gets a different one. The hash/maphash package that picks the shard uses its own random seed from maphash.MakeSeed(), so the shard bits and the slot bits are never related. If you write a sharded map in a language where you control the hash function, remember the seed.

The shard struct has a field of 112 bytes that does nothing. A sync.Mutex is 8 bytes and a map is a pointer, so the padding makes every mutex shard exactly 128 bytes, which is one cache line on Apple Silicon. The shards of the sharded-rw design are 144 bytes because of the bigger lock, so some of them still share a line. Without the padding, several shards share a cache line and a goroutine that locks shard 5 invalidates the line of the goroutine that works on shard 6, even though they never touch the same data. This is called false sharing. On the balanced workload with 8 goroutines the padded version needs 35 ns per operation and the unpadded one 39 ns, so the padding is worth about 10 percent. In Zig it was worth 13 percent. The cost is 8 KB for 64 shards.

The original post found that calling Unlock() by hand instead of with defer made the hot path about 8 percent faster. The useDefer constant in the program switches Get() between the two styles. On the read-only workload with 8 goroutines the version with defer needs 30 ns per operation and the version without it 28.5 ns, so about 5 percent and with one goroutine the difference is 1 percent. A defer in Go has been cheap since Go 1.14, but it is still a few instructions that run at every return and the hot path of a cache is where a few instructions show. In Zig there was no difference at all, because defer there is only a rule about where the compiler places the code. I still use defer for the unlock in both languages and I would only remove it from a path that a profile says is hot.

What to actually use Link to heading

• Start with sharded mutexes. The design is 40 lines of code, it is the fastest or close to it under every workload, it keeps getting faster as you add cores and it stays flat no matter how many goroutines you run.
• Use a single sync.Mutex when the data is small, when there is little contention or when the program runs on one or two cores. With one goroutine it is as fast as anything else.
• Use sync.RWMutex when you measured that it is faster than the mutex. In Go it was faster than the mutex under contention in every workload, which was not the case in Zig, but it was never close to the sharded design.
• Never share a plain map between goroutines without a lock. The runtime detects a concurrent write and crashes the program with fatal error: concurrent map writes. Zig does not detect anything and the map gets corrupted silently, so the crash in Go is the better outcome.

The Zig post and this one agree on the ranking. The absolute numbers are two to three times bigger in Go, mostly because of the map and the Go mutex suffers more under contention than the Zig one, but the design that scales is the same in both languages.

You can purchase Practical Systems Programming in Go from amazon.com or Packt Publishing. All code from the book is available in the official GitHub repository.