Lock-free Interprocess Communication

Algorithm Four (Read-optimized Registry)

A common problem is implementing a "registry" optimized for reads, but allowing updates. A standard implementation would be to use std::map and putting locks (critical sections for Windows) around any modifications or reads to/from this map.

Another implementation inspired by the above lock-free technique combines the standard technique of using mutexes and light pipes described above. The algorithm involves a main copy of registry data (one instance of class Registry) and views (or subscribers) of this registry (many instances of class RegistryView) which have local copies of registry data. (See Figure 5.)

Figure 5: Multiple subscribers to an instance of Registry.

Light pipes (KeyValuePipe instances) are used to send updates from the main copy of data to every local copy asynchronously. Every update is applied to the main copy of data at first and then this update is coded and written to every pipe which eventually leads to the update of every local copy of data.

Every subscriber, before reading from its local copy of data, checks for updates which come from the Registry. If some data is found in the pipe then this data is applied to the local copy and then the read operation is performed from the local updated copy of data.

Since updates are rare, the most common scenario is that no updates are found in the pipe. In this case the check is eventually just one read from the pipe's buffer and positive comparing the result to zero.

The standard technique is used only in two cases:

1. When a process needs to write data to the registry. Since writes are considered rare events, then using mutexes should not decrease performance much.
2. When there is a subscriber which reads from the registry more rarely than the registry is updated. This will lead to a situation where the light pipe to this subscriber overflows with data. In this case, a Reset command is written to this pipe as the last command to notify the subscriber that all changes should be ignored and the subscriber must get the main copy of data from the Registry and set it to the local copy. Using mutexes in this case also will not decrease overall performance much.

It should be clearly understood that the above mechanism allows every reader to achieve almost the same speed of reading updated data as the speed of reads from the local copy by introducing some latency between data updates of the main copy and updates of the local copies. It is normal that the local copy is slightly behind the main copy of data for a short period of time. On the other hand, all changes to the local copy are consistent and the sequence of changes is guaranteed to be the same as for the main copy. In many cases, this behaviour is sufficient. Examples could be implementations of different routing tables which are repeatedly read and relatively rarely updated. For them, some latency and asynchrony in data updates do not play a vital role as well, but consistency is important.