Question 10: Uncontended contention
Mitch is building a distributed system wherein each process reads some data from a database, performs some computations on it and writes it back. Most processes operate on separate parts of the data and do not compete with other processes for the same data. Mitch does not want to use locks because it will only add the overhead of acquiring and releasing locks even though there is no actual contention in the common case (different processes operating on different parts of the data). However, he still needs to ensure that if two processes do happen to work on the same piece of data, only one of them succeeds with the final write. Can you suggest a mechanism to help Mitch with this problem?
Solution
Mitch should use a form of optimistic concurrency control. Each process can read its desired data, perform the computations without any locking. When it tries to write the data, it should confirm that the current state of the data matches what it read. If there is a mismatch, the process should discard its computation and start again.
In the common case that there is no actual contention, most processes will be able to proceed without any locking. In the rare cases that there is a contention (two processes worked on the same piece of data), the first writer would win.
This is a canonical reference for optimistic concurrency control methods. This is an example of implementing optimistic concurrency in AWS DynamoDB using conditional writes (i.e., writes which check for certain condition before succeeding).