Using a double buffer technique for concurrent reading and writing?

Question

I have a relatively simple case where:

1. My program will be receiving updates via Websockets, and will be using these updates to update it's local state. These updates will be very small (usually < 1-1000 bytes JSON so < 1ms to de-serialize) but will be very frequent (up to ~1000/s).
2. At the same time, the program will be reading/evaluating from this local state and outputs its results.
3. Both of these tasks should run in parallel and will run for the duration for the program, i.e. never stop.
4. Local state size is relatively small, so memory usage isn't a big concern.

The tricky part is that updates need to happen "atomically", so that it does not read from a local state that has for example, written only half of an update. The state is not constrained to using primitives and could contain arbitrary classes AFAICT atm, so I cannot solve it by something simple like using Interlocked atomic operations. I plan on running each task on its own thread, so a total of two threads in this case.

To achieve this goal I thought to use a double buffer technique, where:

1. It keeps two copies of the state so one can be read from while the other is being written to.
2. The threads could communicate which copy they are using by using a lock. i.e. Writer thread locks copy when writing to it; reader thread requests access to lock after it's done with current copy; writer thread sees that reader thread is using it so it switches to other copy.
3. Writing thread keeps track of state updates it's done on the current copy so when it switches to the other copy it can "catch up".

That's the general gist of the idea, but the actual implementation will be a bit different of course.

I've tried to lookup whether this is a common solution but couldn't really find much info, so it's got me wondering things like:

1. Is it viable, or am I missing something?
2. Is there a better approach?
3. Is it a common solution? If so what's it commonly referred to as?
4. (bonus) Is there a good resource I could read up on for topics related to this?

Pretty much I feel I've run into a dead-end where I cannot find (because I don't know what to search for) much more resources and info to see if this approach is "good". I plan on writing this in .NET C#, but I assume the techniques and solutions could translate to any language. All insights appreciated.

Answer 1

You actually need four buffers/objects. Two buffers/objects are owned by the reader, one by the writer, and one in the mailbox.

The reader -- each time he finishes a group of atomic operations on his newer object, he uses interlocked exchange to swap his older object handle (pointer or index doesn't matter) with the mailbox one. Then he looks at the newly obtained object and compares the sequence number to the object he just read (and is still holding) to find out which is newer.

The writer -- writes a complete copy of latest data into his object, then uses interlocked exchange to swap his newly written object with the mailbox one.

As you can see, the writer can steal the mailbox object at any time, but never the one that the reader is using, so read operations stay atomic. And the reader can steal the mailbox object at any time, but never the one the writer is using, so write operations stay atomic.

As long as the interlocked-exchange function produces the correct memory fence (release for the swap done in the writer thread, acquire for the reader thread), the objects can themselves be arbitrarily complex.

Answer 2

If I understand correctly, the writes themselves are synchronous. If so, then maybe it's not necessary to keep two copies or even to use locks.

Maybe something like this could work?

State state = populateInitialState();

...

// Reader thread
public State doRead() {
    return makeCopyOfState(state);
}

...

// Writer thread
public void updateState() {
    State newState = makeCopyOfState(state);

    // make changes in newState

    state = newState;
}

Answer 3

It looks like you are using the input-process-output pattern in a multithreaded pipeline. Sometimes the input and processing phases (or processing and output phases) are merged when the problem is simple.

You have added a C# tag so using something like a BlockingCollection might be a useful way to communicate between the input and output threads. Since the local state is relatively small (your words) then posting a data-object containing a copy of the local state from the input thread to the output thread could be a simple solution. This follows a share-nothing philosophy which satisfies the atomic requirement because a snapshot of the current state is queued. The "catch up" capability is satisfied because the queue contains the backlog of state changes.

Generally, Messaging Patterns and Conversation Patterns are useful resources when trying to work out what to communicate and how to communicate between 2 or more threads (or processes, services, servers, etc).