cockroachdb / cockroachdb/cockroach
syncutil: use a more efficient implementation of RWMutex
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
**Is your feature request related to a problem? Please describe.**
`sync.RWMutex` has some implementation details that can make it not perform efficiently:
##### Scales poorly with high CPU counts (https://github.com/golang/go/issues/17973)
Some of the intuition here is that `RWMutex` is larger than `Mutex`, so accessing its internal fields can have poor CPU cache coherence. Also, it performs atomic add operations to keep track of the reader count, which is more expensive than the compare-and-swap that a normal `Mutex` does.
#### Biased towards writer locks
That means that readers can end up waiting for a longer time. Consider this example:
- some goroutines have a read lock
- another goroutine A calls `Lock`
- a bunch of other goroutines call `RLock`
- yet another goroutine B calls `Lock`
In this example, all of the goroutines in step 3 will block until both goroutines A and B call `Unlock`. Furthermore, all of the queued readers will get to the critical section at the exact same time, which can cause a thundering herd of access to whatever resource was being protected.
Some other resources for these topics are this [internal thread](https://cockroachlabs.slack.com/archives/C4X2J0RH6/p1741533763240089), this [article](https://zephyrtronium.github.io/articles/rwmutex.html) by zephyrtronium, this [discussion](https://groups.google.com/g/golang-nuts/c/zt_CQssHw4M/m/F9L3vSdyyVMJ) on golang-nuts, and this [Deep Research report](https://chatgpt.com/share/e/67cf510c-5664-8012-8a67-fdec67d0576b) I generated.
**Describe the solution you'd like**
There are other implementations we could try. They are not drop-in replacements, since they have a different API (`RLock` returns a token or callback that is used to release the read lock).
- [xsync.RBMutex](https://github.com/puzpuzpuz/xsync?rgh-link-date=2021-08-25T18%3A16%3A50.000Z#rbmutex)
- It seems well maintained.
- A tradeoff is that acquiring write locks is more expensive.
- Biases towards readers.
- https://github.com/jonhoo/drwmutex
- Hasn't been maintained much.
- Requires architecture specific implementations; right now only linux x86 is supported.
- It works by sharding the reader counts by CPU core.
- Implement our own locks based on ideas in [this paper](http://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.pdf)
- The paper describes a tree-like data structure that is used to track reader counts, rather than a single atomic integer.
We probably should start by moving a few important usages. One data point to guide that decision is this [mutex profile](https://github.com/user-attachments/files/19170317/mutex.pb.gz), which I grabbed by running `./dev bench ./pkg/sql/tests --filter BenchmarkParallelSysbench --test-args '-test.mutexprofile=mutex.pb.gz -test.cpu=8'`. These are the RWMutexes with the highest contention.
**Additional context**
https://github.com/cockroachdb/cockroach/issues/142621 is an issue tracking an investigation into changing some existing `RWMutex` usages to `Mutex` instead.
Jira issue: CRDB-48450
Contributor guide
Research direction
Start with the mutex profile and the benchmark command for ./pkg/sql/tests, then inspect the highest-contention RWMutex usages mentioned by the issue. Read issue 142621 for related investigation context; the work needs a scoped implementation or migration plan and benchmark evidence showing its effect.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- backend, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100