Title: BRAVO - Biased Locking for Reader-Writer Locks,
Abstract: Designers of modern reader-writer locks confront a difficult trade-off
related to reader scalability. Locks that have a compact memory representation
for active readers will typically suffer under high intensity read-dominated
workloads when the "reader indicator"' state is updated frequently by a diverse
set of threads, causing cache invalidation and coherence traffic. Other
designs, such as cohort reader-writer locks, use distributed reader indicators,
one per NUMA node. This improves reader-reader scalability, but also increases
the size of each lock instance.
We propose a simple transformation BRAVO, that augments any existing
reader-writer lock, adding just two integer fields to the lock instance.
Readers make their presence known to writers by hashing their thread's identity
with the lock address, forming an index into a visible readers table. Readers
attempt to install the lock address into that element in the table, making
their existence known to potential writers. All locks and threads in an address
space can share the visible readers table. Updates by readers tend to be
diffused over the table, resulting in a NUMA-friendly design. Crucially,
readers of the same lock tend to write to different locations in the array,
reducing coherence traffic.
Specifically, BRAVO allows a simple compact lock to be augmented so as to
provide scalable concurrent reading but with only a modest increase in
footprint.