A spanking new ReaderWriterSpinlock

Well, I never. There is life in the old spinlock yet!

Being a synchronisation fetishist, I took great interest in last week’s great blog post by Sanjay Mishra and Arvind Shyamsundar about the ReaderWriterSpinlock added in 2016 CU2. Great story, happy ending, room for a sequel, all good news.

We have already seen recent improvement in the reader-writer lock algorithm, so clearly people are finding more corners to squeeze. Now what, pray tell, is a reader-writer spinlock?

When I’m 64

In Bob Ward’s PASS Summit session last year, he mentioned SQLOS spinlocks being eight bytes in size. Funny thing is, I had observed them to be four bytes. As it turned out, we were both right. SQL Server 2016 bumped them up from 32 bits to 64, and with the benefit of hindsight, we can now see where we were heading.

As a quick refresher, a traditional SQLOS spinlock is a 32-bit integer, or of course 64-bit as of 2016, with a value of either zero (lock not acquired) or the 32-bit Windows thread ID of the thread that owns it. All very simple and clean in terms of atomic acquire semantics; the only fun part is the exponential backoff tango that results from a collision.

We have also observed how the 2016 flavour of the SOS_RWLock packs a lot of state into 64 bits, allowing more complicated semantics to be implemented in an atomic compare-and-swap. What seems to be politically incorrect to acknowledge is that these semantics boil down to a simplified version of a storage engine latch, who is the unloved and uncool grandpa nowadays.

Clearly a lot can happen in the middle of 64 bits.

ReaderWriterSpinlock layout and read acquisition

The new template class ReaderWriterSpinlock picks up some of the slack left by the fact that only the lower 32 bits within a 64-bit spinlock are used, and is reminiscent of a highly simplified and compacted SOS_RWLock. Usual caveat: member names are my own, but the semantics are clear.

The usage of the lower 32 bits is pretty much the same as for a regular spinlock. If you can make your mark there – i.e. atomically find it to be zero and then write your own thread ID in there – you will be the exclusive owner.

However, the high 32 bits are more interesting. Of those, 31 bits represent a reader count, as with a latch or SOS_RWLock, and read acquisition is very similar between the two when there are no writers in the picture. No matter how many readers there are, once the lock is held in read mode (ReaderCount > 0) there is always room for one more, and the read request will be granted immediately through an atomic increment. As an edge case, that atomic increment could fail if another read acquisition got granted while we were setting up our state though. Here behaviour diverges from the SOS_RWLock: instead of aggressively retrying, the ReaderWriterSpinlock immediately enters the exponential backoff code path. This means that it is less optimistic, but a bit kinder on the rest of the system.

A visit from the Writers’ Guild

Given that writers and readers will block each other, but readers can pile up in large numbers, we have a bit of a conundrum. Even though the readers will individually relinquish their claim on the spinlock by decrementing ReaderCount, the number may stay nonzero pretty much forever. And in that case the poor waiting writer will never get a word in edgeways, and will just sit there burning CPU cycles and clogging up its scheduler.

This is where the IntentToWrite flag comes in. If an aspiring writer manages to grab this bit (i.e. the bit wasn’t set to begin with), two things happen:

1. It assumes the position of being the next writer in waiting.
2. No new read requests will be granted, so the writer will get its chance once all readers have released their existing claims on the lock.

In this capacity, IntentToWrite functions a bit like a database lock held in Update mode by a single grantee, with the option of upgrading to Exclusive, but it adds the behaviour of blocking future read-mode requests. This second is reminiscent of a writer in a latch’s wait list blocking read requests that came after it, without the cost of maintaining a wait list, which would have involved, hmmmm… a spinlock?

The granting of a write-mode acquisition on a contended spinlock then follows a two-step process, each having the standard exponential backoff behaviour:

1. Granting of IntentToWrite, either immediately (if the lock is currently held in read mode) or after spinning (if a prior write request is already waiting or granted).
2. Granting of exclusive ownership once all other grantees have left for greener pastures.

An uncontended lock does however qualify for an immediate one-step grant in write mode: if it’s zeroes all the way, both IntentToWrite and ExclusiveOwner are set at the same time.

Note that IntentToWrite is only cleared when a writer relinquishes the lock. This means that writers can’t gang up on readers in a write convoy, much as readers can’t clog up the lock indefinitely.

Reflections

Remember the days when there were clear lines of distinction between hatchbacks, sedans and SUVs? Yup, like the car industry, Lockland has moved on, and we are getting more interesting crossovers here.

However, while the internal mechanics start looking more alike, one clear distinction remains, and that is in the outward behaviour you get in a contended scenario. All synchronisation classes except spinlocks act super polite, calling into the SOS Scheduler, which means we get normal scheduler housekeeping (I/O list, timer list) and the chance of yielding to a sibling worker. In contrast, spinlocks of both flavours continue to hog the SOS Scheduler while waiting, and even though their SwitchToThread() behaviour yields the CPU to other waiting threads, these threads will not be workers on the same SOS Scheduler, and will most likely be preemptively scheduled background work.

Even here, things aren’t really that cut and dried. As we’ve seen, both SOS_RWLocks and latches are very aggressive when they want to acquire their internal spinlocks, and the optimism could theoretically backfire by burning CPU very selfishly.

One cute side effect of the move from 32 bits to 64 bits on the little-endian Intel architecture is that one can still read an exclusively acquired 64-bit spinlock of either variant as a 32-bit one. Because the higher 32 bits follow the lower 32 in memory, at the memory location where you might expect a 32-bit spinlock consisting solely of ExclusiveOwner, you’ll still find ExclusiveOwner.

This SQLOS ReaderWriterSpinlock implementation is very close to one described by Joe Duffy here. The only difference is that exclusive ownership in his lock is marked by a single bit whereas we get the luxury of a 32-bit thread ID, meaning that memory dumps come with smoking guns instead of just entry wounds.

Finally, where next? I am imagining that the first two use cases for this spinlock were identified as low-hanging fruit, but it feels reasonable to assume that someone is playing around with migrating other spinlock types. Which ones are chosen might tell us a lot about the kinds of workloads out there!