cockroachdb / cockroachdb/cockroach

syncutil: use a more efficient implementation of RWMutex

Open
#142,625 0 comments 0 reactions 0 assignees View on GitHub
C-enhancement C-performance o-perf-efficiency
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.

Image

**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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.