sync: RWMutex Readers can starve writers for many seconds

[evanj]

Go version

go version go1.25.5 darwin/arm64

Output of go env in your module/workspace:

AR='ar'
CC='cc'
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_ENABLED='1'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
CXX='c++'
GCCGO='gccgo'
GO111MODULE=''
GOARCH='arm64'
GOARM64='v8.0'
GOAUTH='netrc'
GOBIN=''
GOCACHE='/Users/evan.jones/Library/Caches/go-build'
GOCACHEPROG=''
GODEBUG=''
GOENV='/Users/evan.jones/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFIPS140='off'
GOFLAGS=''
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/pp/tvwz4y2x2qz97pf8bftqxhrw0000gp/T/go-build2627804322=/tmp/go-build -gno-record-gcc-switches -fno-common'
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMOD='/Users/evan.jones/unfairlocks/go.mod'
GOMODCACHE='/Users/evan.jones/go/pkg/mod'
GOOS='darwin'
GOPATH='/Users/evan.jones/go'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go/1.25.5/libexec'
GOSUMDB='sum.golang.org'
GOTELEMETRY='on'
GOTELEMETRYDIR='/Users/evan.jones/Library/Application Support/go/telemetry'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go/1.25.5/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.25.5'
GOWORK=''
PKG_CONFIG='pkg-config'

What did you do?

A contented RWMutex allows readers to starve waiting writers for an extremely long time (e.g. >10 seconds). I believe this is because RWMutex.Unlock() first unblocks all readers, before unchecking if there are any waiting writers. I think this disagrees with the documentation of RLock: "a blocked Lock call excludes new readers from acquiring the lock".

We observed this causing some goroutines for an "overloaded" server to be blocked for a very long time (at least >1 second). For this scenario, I think it would be better if Unlock() did not unblock readers if there is another writer waiting. This would then allow continuously arriving writers to starve readers instead, but I think that would better match the package documentation.

The attached program simulates how Datadog's metrics package datadog-go uses an RWMutex for a map of counters in aggregator.count:

• RLock()
• Read the map. If the counter key exists: increment it.
• RUnlock()
• If the key did not exist:
  • Lock()
  • Check for the key again, increment or insert the new key
  • Unlock()

I think the following is happening in both the attached demo program and the production server:

• A writer acquires the RWMutex.Lock().
• Many more writers block in the internal Mutex.Lock().
• Many readers block in Mutex.RLock().
• The writer calls RWMutex.Unlock(). It releases all blocked readers (// Announce to readers there is no active writer. in RWMutex.Unlock ).
• New readers can now acquire the RLock(). Since requests are continuously arriving, there are always running readers.
• The writer unblocks all blocked readers with a for loop in Unlock.
• The writer unblocks the next waiting writer (// Allow other writers to proceed.)
• The unblocked writer get scheduled, then finally blocks new readers.
• The next writer now must wait for all readers to finish, and the writer can finally enter the critical section.
• Repeat this for the next writer. The result is it takes ~100 ms to get to each writer in the queue.

Demo program: https://github.com/evanj/unfairlocks/blob/main/unfairlocks.go#L47

What did you see happen?

In servers that use this in a very hot loop, we occasionally see "stuck" goroutines that are blocked for > 1 second.

The attached demo program prints "slow" increment requests. When I run it with increasing numbers of requests, the slowest increment time continues to increase. It appears the waiting time is basically unbounded. I can make an increment block basically ~forever by continuously adding more simulated requests.

$ go run . -requests=50000
...
Shard shard-35 increment duration: 598.276583ms
$ go run . -requests=500000
...
Shard shard-32 increment duration: 6.82352725s
$ go run . -requests=5000000
...
Shard shard-31 increment duration: 17.665173458s

This output shows the waiting time increases as I add more requests. The last line shows some goroutines were blocked for up to ~17 seconds. With this particular program and configuration, this is the worst delay I can observe: after that, the queue of blocked writers is gone.

What did you expect to see?

The mutex should sometimes be unfair, but not exceptionally unfair, and it should not starve writers ~forever. The demo program also prints timing of a version that only uses a Mutex, and it only shows waits up to ~200 ms.

[ianlancetaylor]

As you say, it's a choice of who to starve. I agree that the RLock documentation doesn't seem to match the implementation, but we do have the option of changing the documentation. I don't think we can easily guarantee that if a writer holds the lock, and there are multiple readers and writers waiting to acquire the lock, that a waiting writer will get the lock instead of a waiting reader. To make that guarantee would make the implementation even more complex. It might be OK to release the readers after unlocking the mutex which would give a slight edge to the waiting writers. But I'm not sure that is safe.

As a separate note, a RWMutex is only preferable if the lock is held for a long time, and if there are many more readers than writers. If readers and writers only hold the lock briefly, or if writers are about as common as readers, you will usually be better off using a plan Mutex, which is simpler and, in the current implementation, has considerably better support for handling contention.

[evanj]

Changing the documentation would definitely be a fix. I'm happy to attempt an update to make it clearer.

In this particular library, sync.Map is probably a superior replacement, but the demo application does show an advantage to RWMutex: When there are no writers, it does not block. After the map is filled it is substantially faster. On my M4 Max laptop, it takes the Mutex implementation ~1.40s to process 100k "requests", with occasional latency outliers above ~150 ms, while the RWMutex implementation takes ~0.65s, with no latency outliers, since it is just doing an atomic increment/decrement.

[cespare]

I think that the implementation mostly does match a strict reading of the documentation. To quote the full sentence from the RLock doc:

It should not be used for recursive read locking; a blocked Lock call excludes new readers from acquiring the lock. See the documentation on the RWMutex type.

So in context, "blocked Lock call" is referring to a Lock call blocked by a reader (though perhaps it should explicitly say that). And then if we go to the full documentation for RWMutex, it has more to say about the behavior:

If any goroutine calls RWMutex.Lock while the lock is already held by one or more readers, concurrent calls to RWMutex.RLock will block until the writer has acquired (and released) the lock, to ensure that the lock eventually becomes available to the writer. Note that this prohibits recursive read-locking.

Note that it says "while the lock is already held by one or more readers". You are referring to the case where the lock is held by another writer.

---

Regarding the actual behavior: it's true that you can generate large periods of writer starvation as your demo shows. However, let's think about what's actually happening here:

• The first writer blocks all readers
• While the first writer holds the lock, readers and writers queue up
• When the first writer unlocks, all the queued up readers are unlocked and the next writer starts blocking future readers

The net result is a pattern like:

• A batch of readers proceed.
• One writer proceeds.
• Another batch of readers proceed.
• Another writer proceeds.
• ...

This seems like a fairly reasonable way to behave (given that we're already dealing with an overloaded contended lock). In particular, it seems good that it alternates between writers and readers.

I would distinguish this from the kind of starvation you'd get with a pure writer-priority policy. In that world, even with a bounded number of readers and writers (even just 2 writers and 1 reader), the reader can get starved forever if the writers continuously alternate taking the lock.

---

I took at look at your demo code. (One thing I did immediately was move the map construction inside the "trial" loop; otherwise, only the first trial does anything interesting because after that the counter map is already populated.)

I don't fully understand all the behavior that's happening (don't have much more time to investigate atm). But one thing I noticed was that there's a large amount of variance in how long the delay is, and it seems to be based on some luck in terms of how many writers you have. That is, every increment does a read and then maybe a write, and the number of writes you get can vary dramatically. In the best case scenario only the first 50 increments Lock the RWMutex; in the worst case, 50,000 increments Lock the RWMutex (because there are 50,000 concurrent increments).

---

Finally, in my experience writing a bunch of high-performance concurrent code, when you run into issues with a read-write mutex, the solution is nearly always to change the approach, not to improve the rwmutex implementation. There are just a lot of subtle problems with tail latency when you use rwmutexes at all, no matter what tradeoffs the implementation chooses to make.

(@nelhage's excellent Reader/reader blocking in reader/writer locks is well worth internalizing here.)

For example, in the use case you describe, it seems that the map is mostly written at the beginning and then, once it is populated, it should be mostly reads. This is a "shape" of problem that sync.Map fits fairly well. If I write a sync.Map implementation of your interface:

type syncMapCounter struct {
	m sync.Map // string -> *atomic.Int64
}

func (c *syncMapCounter) increment(id string) {
	n, ok := c.m.Load(id)
	if ok {
		n.(*atomic.Int64).Add(1)
		return
	}
	n, _ = c.m.LoadOrStore(id, new(atomic.Int64))
	n.(*atomic.Int64).Add(1)
}

then on my machine it doesn't seem to suffer from those same latency outliers and also gets better throughtput than both the Mutex and RWMutex implementations. (You'll have to figure out how to address Flush.)

There are certainly other approaches as well, such as a sharded lock or lock-free techniques. But that's how I'd approach your issue.