How It Works: Reader / Writer Synchronization

This post is not about a specific SQL Server object but instead outlines a technique used in various locations to reduce contention while still providing thread synchronization.  There are hundreds of locations throughout the SQL Server code base that must account for multi-threaded access.   A common technique used in multi-threaded coding is a reader, writer lock.

The idea behind a reader, writer synchronization object is to allow reader parallelization in conjunction with writer synchronization.  Let’s look at a simple pattern of a single path synchronization object.  (Example: spinlock)

• T1 – Acquires access for read
• T1 – Starts doing some work
• T2 – Attempts to acquire access for read – BLOCKED and spins, burning CPU and not making forward progress

 

• T1 - Release access
• T2 – Stops spinning and finishes acquire
• T2 – Does some work
• T2 - Releases access

A spinlock can be as simple as a while loop using InterlockedCompareExchange to place 1 into the variable as long as the value at the time of exchange is 0.

while(0 != InterlockedCompareExchange(&lock, 1, 0))
{
_pause();
}

Following the steps above T1 would have exchanged 1 into the lock location.  Then T2 would have spun because when it tried to place 1 into the lock variable the previous value was already 1, not 0.  When T1 is done with the lock it sets the lock back to 0 so T2 is able to acquire the lock.

In a practical example this might look a lot like waiting in line to checkout at the grocery store.   The single access pattern prevents parallel operations even for readers.  A reader, writer implementation changes the behavior to allow multiple readers as long as there is not a conflict with a writer.  This allows parallel operations, better throughput and better use of existing resources.

A reader, writer implementation often takes advantage of the CPU’s, Interlocked* instruction set while treating the lock variable as a bit field.  For example, taking a 4 byte integer value we can break down the bits and treat the bits as a structure that might look something like the following.

struct MyLock
{
int WriterBit : 1;
int SpinlockBit : 1;
int HasWaitersBit : 1;
int ReaderCount : 29;
}

Instead of just exchanging a single value the reader, writer can leverage the requested mode and bits to determine if the lock can be acquired or a wait is required.  Going back to our example lets use a reader/writer implementation.

• T1 – Acquires access for read
• T1 – Starts doing some work
• T2 – Attempts to acquire access for read – IS ALLOWED TO ACQUIRE
• T2 – Starts doing some work
• T1 – Releases
• T2 – Releases

The algorithm might look something like the following.

MyLock myLocalCopy = 0;
MyLock originalCopy = lock;

if(read == requestMode)
{
// A valid reader can only update reader bits so keep other bits zeroed
myLocalCopy.ReaderCount = originalCopy .ReaderCount +1;

   if(originalCopy != InterlockedCompareExchange(&lock, myLocalCopy, originalCopy))
{
retry or add to waiter list
}

}

As long as no waiter, writer or spinlock bits are held the reader count can be incremented.  When T1 acquires the lock the ReaderCount = 1 and when T2 acquires the lock ReaderCount is incremented to 2.  As they release the counts are decremented.

If a writer is required, the writer bit is set which prevents other writers or readers as the writer, has waiters and spinlock bit has to be 0 to increment the readers and the readers, has waiters and spinlock as to be 0 to set the writer bit.

This allows SQL Server and related components to take advantage of reader, writer behavior.   Just imagine of all the times SQL Server may need to lookup something in a cache.  Using a reader, writer object allows multiple threads on multiple CPUs to do the lookups in parallel versus lining up behind a single, gated synchronization object design.

Bob Dorr - Principal Software Engineer SQL Server

Comments

• Anonymous
  August 14, 2016
  Thanks a lot for a great blog again sir, I have learnt the behavior of Interlock synchronization( Taking read/write synchronization as synonym to interlock) itself is lockless, Am i correct ? and also these can support only some subset of operations? I also learnt SQL Server uses these interlocks very rare (atleast in previous versions) , does this going to improve :)? Thanks a lot for looking in to this comment.