Left-Right: Wait-free Reading While Writing

The main features of the Left-Right construction are the following:

1. 1.

   It’s generic, works with any data structure, and doesn’t affect the time complexity of any operations.

2. 2.

   Reads and writes can happen concurrently.

3. 3.

   Reading is always wait free.

4. 4.

   No allocation is required, so no garbage is generated, and no garbage collector is required.

5. 5.

   A writer cannot be starved by readers.

The fifth property—that writers cannot be starved by readers—means that a write operation will never be prevented from completing by read operations. It is also the trickiest part of Left-Right.

To begin with, I’m going to describe the so-called ”No Version” variation of Left-Right. It satisfies the first four properties, but readers can (in very unlikely scenarios) starve a writer.

Once you’ve got your head around this version of Left-Right, adding in the starvation freedom property is much easier to understand.

We’ll begin by describing how to use Left-Right to read a data structure. This will show the first key idea of Left-Right: It maintains two versions of the data-structure, allowing reads to proceed concurrently with a writer.

To keep the description of reads simple, we’ll assume the existence of a so-called ”Read Indicator”, that is used to communicate in-progress reads with potential writers. Here’s the interface a read-indicator exposes:

interface IReadIndicator
{
    // A reader calls this to tell writers that it is
    // reading the data structure
    void Arrive();
    // A reader calls this to tell writers that
    // it is no longer reading the data structure
    void Depart();
    // Returns true if a read is in progress (i.e.,
    // any calls to Arrive without a matching Depart call)
    bool IsOccupied { get; }
}

We’ll ignore the implementation of IReadIndicator for now. Implementations can be very simple – a single atomic counter will do (and be unscalable in the presence of many threads), or they can be quite intricate and more scalable.

With our read-indicator in hand, the implementation of a read looks something like this:

// An array of the two instances of the data
// structure we are coordinating access to. For this example, a List
List[] _instances;
// An index (either 0 or 1) that tells readers
// which instance they can safely read.
int _readIndex;
// A read indicator, that a reader can use to inform a potential
// writer that a read is in progress.
IReadIndicator _readIndicator;
int Read()
{
    _readIndicator.Arrive();
    var idx = _readIndex;
    var result = read(_instances[idx]);
    _readIndicator.Depart();
    return result;
}

This code is hopefully self-explanatory: readers just record their presence during reading.

Writing is a bit trickier than reading, and goes something like this: Write to the instance of the data structure that we’re sure there can be no readers reading, wait for readers to finish reading the other instance, and then write to that instance.

A (toy) implementation would look something like this:

void Write()
{
    lock(_writersMutex)
    {
        var readIndex = _readIndex;
        var nextReadIndex = Toggle(readIndex);
        write(_instances[nextReadIndex]);
        _readIndex = nextReadIndex;
        while(_readIndicator.IsOccupied) ;
        write(_instances[readIndex]);
    }
}

The first thing to note about this is that writes are blocking: there can only be a single write in progress at once, hence the _writersMutex.

Recall that readers mark _readIndicator to communicate their reads to the writer. It is the wait on _readIndicator.IsOccupied that opens up the possibility of writer starvation: new readers could continuously arrive, indefinitely delaying an in-progress write.

Clearly, for the writer to avoid starvation it cannot wait on a _readIndicator that new readers can mark. This echoes the original idea of Left-Right: keep two copies of the data structure so that writes can proceed during reads. So the key to avoiding starvation is to have two read-indicators also.

Reading is similar to reading with a single read-indicator; there is just one additional step, readers read a variable _versionIndex that determines which read-indicator they will mark:

// An array of the two instances of the data
// structure we are coordinating access to.
List[] _instances;
// An index (either 0 or 1) that tells readers
// which instance they can safely read.
int _readIndex;
// An index (either 0 or 1) that tells readers
// which read-indicator they should mark.
int _versionIndex;
// An array of two ’read indicators’ so a
// reader can inform writers that it has a
// read in progress
IReadIndicator[] _readIndicators;
int Read()
{
    var versionIndex = _versionIndex;
    var readIndicator = _readIndicators[versionIndex];
    readIndicator.Arrive();
    var idx = _readIndex;
    var result = read(_instances[idx]);
    readIndicator.Depart();
    return result;
}

This is so similar to the ”No Version” read mechanism above that there isn’t much to say about it, instead, let’s look at writing, where the real differences lie.

Writing is again similar to the simpler ”No Version” Left-Right, but includes two waits. Roughly the way writing works is: Write to the instance we’re sure no readers are reading, change _readIndex so readers read the version we just wrote to, wait for any outstanding reads on that _readIndex we want to write next, change _versionIndex so readers mark the other read-indicator, wait for the outstanding reads to clear, and do the final write. That explanation is a bit of a mess, hopefully the code makes things a little clearer:

void Write()
{
    lock(_writersMutex)
    {
        var readIndex = _readIndex;
        var nextReadIndex = Toggle(readIndex);
        write(_instances[nextReadIndex]);
        _readIndex = nextReadIndex;
        var versionIndex = _versionIndex;
        var nextVersionIndex = Toggle(versionIndex);
        while(_readIndicators[nextVersionIndex].IsOccupied) ;
        _versionIndex = nextVersionIndex;
        while(_readIndicators[versionIndex].IsOccupied) ;
        write(_instances[readIndex]);
    }
}

Hopefully writing makes some intuitive sense, getting a confident feel for exactly why it enforces both mutual exclusion between readers and writers, as well as ensures writing is starvation free is a little more effort. We’ll try and do that in the next section.

There is still a large gap in the description of Left-Right given so far: it omits all details of memory fencing. The descriptions above all rely on viewing the code as sequentially consistent. An actual implementation is likely to diverge from this. Generally speaking, in my experience, a good working assumption for code implementing a mutex (or lock free or wait free code in general) is that any implementation that hasn’t been model-checked in some way – even where the underlying construction has been proved correct – is buggy. The source code for this Left-Right implementation (including a simple RelaSharp test) is here, and the original NuGet package is SharpLeftRight.