How to create a Semi-Fair Read-Write-Lock using an Unfair Read-Write-Lock and a Fair-Lock

Background

We had multiple algorithms running and performing data manipulation over a DB. The algorithms were separated into 2 main groups:

• Algorithms that read the data and can run in parallel to each other
• Algorithms that write the data and cannot run while other read or write algorithms run

Our algorithms are written in Java and were running inside a single process on different threads so we could use the java.util.concurrent.locks.ReentrantReadWriteLock and set it to fair mode and it worked fine.

The challenge

After a while, in the process of scaling our server we had to separate these algorithms to different processes.

We now had a challenge, we needed to synchronize these algorithms when they don’t share the same process, even not the same server.

We already used Redis so we looked up and found a distributed lock library over Redis named Redisson that had this feature. The problem was that the Read-Write-Lock implementation there is unfair. This meant that the writer task can be starved if there are a lot of reader tasks running.

So we looked for another library that uses Redis but all our searches lead to Redisson. We looked at Redisson’s features and found that it also has a Fair-Lock. So after some thinking we found a way to create a Semi-Fair Read-Write-Lock using a Fair-Lock and an Unfair Read-Write-Lock.

So how did we do it?

The flows are presented as a sequence of 2 letters, the first letter is the lock type, the second letter is whether we lock or unlock it.

F is for fair lock, R is for read lock, W is for write lock, L is for lock and U is for unlock. So FL is fair-lock lock and WU is write lock unlock.

The reader flow: FL > FU > RL > read algorithm > RU

The writer flow: FL > WL > write algorithm > WU > FU

• If there are only readers coming, they will pass one by one in the barrier (FL > FU) and then run together inside the read algorithm stage.
• If there is a writer now, he will be blocked in the fair-lock stage until his turn to pass it will arrive. He will take the fair lock and all the rest of the readers that will arrive from this point on will be blocked on the fair-lock.
• There might be some race between readers that passed the barrier (FL>FU) and the writer that passed the FL and this is why we call this solution semi-fair.
• Now the writer will wait until all the readers inside the read algorithm will finish. Also the readers that passed the barrier (FL>FU) might overtake the writer (all or some). After that, the writer will execute the write algorithm and release all the locks.
• After the writer finishes and releases the locks, now the fair-lock will make sure the next one that enters is the first that tried, reader or writer.

This solution works. There are no dead locks that might occur. The readers cannot be starved forever. The writers cannot be starved forever. The writers might overtake some readers that passed the barrier (FL>FU) and this is why it is semi-fair, but in our case it is fair enough.

Hope this post will help someone else…