Read Locks Are Not Your Friends

The code examples are confusing. The show the code that takes the locks, but they don’t show any of the data structures involved. The rwlock variant clones the Arc (makes sense), but the mutex variant does not (is it hidden inside inner.get)?

In any case, optimizing this well would require a lot more knowledge of what’s going on under the hood. What are the keys? Can the entire map be split into several maps? Can a reader hold the rwlock across multiple lookups? Is a data structure using something like RCU an option?

This is drawing broad conclusions from a specific RW mutex implementation. Other implementations adopt techniques to make the readers scale linearly in the read-mostly case by using per-core state (the drawback is that write locks need to scan it).

One example is folly::SharedMutex, which is very battle-tested: https://uvdn7.github.io/shared-mutex/

There are more sophisticated techniques such as RCU or hazard pointers that make synchronization overhead almost negligible for readers, but they generally require to design the algorithms around them and are not drop-in replacements for a simple mutex, so a good RW mutex implementation is a reasonable default.

Lock contention is a real issue for any multi-threaded system, and while a RW mutex is useful when you have a longer executing critical section, for something very short lived there is still a cache coordination cost. In many of the HashiCorp applications, we work around this by using an immutable radix tree design instead [1].

Instead of a RW mutex, you have a single writer lock. Any writer acquires the lock, makes changes, and generates a new root pointer to the tree (any update operation generates a new root, because the tree is immutable). Then we do an atomic swap from the old root to the new root. Any readers do an atomic read of the current point in time root, and perform their read operations lock free. This is safe because the tree is immutable, so readers don't need to be concerned with another thread modifying the tree concurrently, any modifications will create a new tree. This is a pattern we've standardized with a library we call MemDB [2].

This has the advantage of making reads multi-core scalable with much lower lock contention. Given we typically use Raft for distributed consensus, you only have a single writer anyways (e.g. the FSM commit thread is the only writer).

We apply this pattern to Vault, Consul, and Nomad all of which are able to scale to many dozens of cores, with largely a linear speedup in read performance.

[1] https://github.com/hashicorp/go-immutable-radix [2] https://github.com/hashicorp/go-memdb

If implementation is task based and task always runs on same virtual CPU (slots equaling CPUs or parallelism), wonder if something like below might help.

RW lock could be implemented using an array of length equal to slots and proper padding to ensure each slot is in its own face line (avoid invalidating CPU cache when different slot is read/written).

For read lock: Each task acquires the lock for their slot.

For write lock: Acquire lock from left most slot to right. Writes can starve readers when they block on in-flight reader at a different slot when moving from left to right.

I do not know how Rust RW locks are implemented.

It always amazes me the amount these folks are willing to work and struggle just to avoid reading basic database literature.

Also Fedor Pikus has some nice cppcon talks from years ago on all this. Very low level.

I'd be super interested in how this compares between cpu architectures, is there an optimization in Apple silicon that makes this bad while it'd fly on Intel/AMD cpus?

Take a look at crates like arc_swap if you have a read often write rarely lock case. You can easily implement the RCU pattern. Just be sure to read about how to use RCU properly.

Well done this pattern gives you nearly free reads and cheap writes, sometimes cheaper than a lock.

For frequent writes a good RWLock is often better since RCU can degrade rapidly and badly under write contention.

claudes love to talk about The Hardware Reality

Does this apply also to std::shared_mutex in C++? This is a timely article if so; I’m in the middle of doing some C++ multithreading that relies on a shared_mutex. I have some measuring to do.

I’ve seen so many people fall into this trap. Have to wonder if it’s the API design of rwlock that’s wrong because it leads to misuse.