I wanted to ask this question that has been bugging my head for a long time. Recently, I have started to develop a distributed system which has continuous and frequent database lookups in a loop. Let me describe it to you.
There are entries in a queue, which can be matched mutually among themselves. For example, let's say we have a queue like :
A B C D E F
With certain rules, these can be matched like, A-B, C-E, D-F . Who matches with who and why is irrelevant for this question I think. One thing that is important is that there can only be ONE match for an element, and then it has to leave the queue.
A program is required to continuously work on this queue (or list, if we ignore the sequence) to find matches, and shrink the queue as fast as possible.
Assuming the number of elements in this queue can be very large, I think there should be multiple programs who work on this queue. So one thing I thought of was creating multiple nodes that run this program, which are called "Matchers" .
The problem is, if matcher1 matches A-B at a certain moment, and Matcher2 matches B-C , we have a race condition for B. Given the distributed nature of the matchers, the synchronization can possibly be on a database that provide consistency guarantee. Like when a is matched, it could be marked on the database which keeps the queue. However there seems to be no reliable way to be sure that other matchers will have the happens-before relationship with this operation, hence no guarantee that the change is observed. Especially if the database used is sharded or distributed so there needs to be some time for propagation. So I am not certain how well this would work.
Another solution I have come up with was, assigning certain groups in the queue exclusively to only one matcher. For example,
Matcher1 has A B C D Matcher2 has E F G H
Now matcher1 only matches A-B-C-D among themselves and matcher2 E-F-G-H. Hence, it is possible to keep Matchers with only one thread, so no race condition occurs. Or we could use a local mutex system to lock upon acknowledging a match, to see if there was another match at that moment, so this way we can also use multithreading in the nodes, while being safe with race conditions.
I am aware, what I have written might lack some coherency, but that exactly reflects how it is in my mind. I am fairly proficient with multithreading and parallelism, however I have never seen a real high end real time system, with race condition issues implemented, so I lack in the experience department.
I wanted to get some feedback on my ideas, and maybe receive some better ideas from you guys. Please direct me to fix my question, in case it is lacking severely.
EDIT: This question has very little to do with methods to synchronise a program running on a single machine. The same program is running on multiple nodes in a cluster, and they have to be synchronised.