1

Here's a scenario I need help with.

Say you have a dating app (distributed, multiple instances), that has a table likes

| id | user_id | liked_id |notification_sent|

If User A likes User B
    Insert into likes
    If likes contains (B likes A)
        Send match notification(A,B)
        Set notification_sent true for both rows 

Now, what happens if both users A and B like each other at the same time? (race condition)? there's a chance that the second if will be missed, as the rows are not inserted yet.

Solution A: Have a background service that runs periodically, checking for A likes B AND B likes A AND notification_sent=false

that's not really realtime

Solution B: Always retry the 2nd check, but that just seems wasteful.

Solution C: Lock the whole table! Nope!.

Is there any othert solution to force order of events/avoid the race condition?

2
  • Lock the relationship ? Aug 1, 2021 at 10:01
  • Proper database engines can lock just the affected rows, which will be amply fast enough for your purpose. Aug 1, 2021 at 11:57

2 Answers 2

2

From what I understand, the 2nd if condition is always supposed to be missed, since there must be a "User A likes User B" first (where the if condition will be missed) and then a "User B likes User A" (where the if condition is hit).

The only race condition I see that might be unwanted is when a thread yields to the other thread just after "Insert into likes". Which might cause the operation "Send match notification(A,B)" to run twice.

In your case you know then that "Send match notification(A,B)" will run at-least once.

Now, if you want to change this to a run only-once, then you have to create a lock on the "likes" tables on rows A likes B and B likes A.

If User A likes User B
    Insert into likes
    If likes contains (B likes A)
        Lock both rows
        if A likes B has notification_sent is false
            Send match notification(A,B)
            Set notification_sent true for both rows
        Unlock both rows

This will ensure that the notification is only sent only once.

9
  • 2
    If the whole block under If User A likes User B uses a single database transaction with a commit only at the end, then it is possible that two threads at the same time insert a record for A->B or B->A in the database, but don't find the reverse record as that transaction wasn't committed yet. Aug 1, 2021 at 17:44
  • @BartvanIngenSchenau this is exactly the problem
    – Omar Gamil
    Aug 2, 2021 at 0:47
  • 1
    Ok, then I'll think this as an event-driven process, where the event is an entry on the likes table. The producing and the consumption of the events should not be handled in a single "process" (e.g. transaction). The producer simply inserts the event (a likes entry) and a consumer listens for insert event and reacts accordingly. A recovery mechanism should always be put in place because something can go wrong and you want all events to be handled. You can implement something like solution A, however, be aware of the cases where an error will always occur no matter how many times you retry.
    – fnmps
    Aug 2, 2021 at 1:39
  • And as for the real-time issue, it does not seem like an issue at all, most of the notifications will be sent in real time (probably 99% of the time), only for the error cases that will not be the case. But there is not much you can do about that, you can always run the recovery process in a relative short interval, but if it gave an error just a few milliseconds before, it is likely that the error will just repeat itself.
    – fnmps
    Aug 2, 2021 at 1:49
  • 1
    @fnmps yes, this way it should prevent the deadlock. It was important to mention it as it is not quite obvious for readers who are less familiar with concurrency issues ;-)
    – Christophe
    Aug 3, 2021 at 12:10
1

In short

Yes there is a race condition in your system. Depending on the isolation level and the timing, you might either miss the match or send notifications without the notification flags being set. Among your solutions, only A would seem suitable, but there are better options that are not listed.

The two main reasons for the race conditions are the transaction isolation and the redundancy: there is only one match, but in your database schema the match is represented by two unidirectional matches.

More details

Race condition issue 1: missed matches

With an isolation level set to serializable, repeatable reads or reads committed, the race could cause a missed match, if B looks for the likes before A committed its transaction (so they don't even need to be exactly at the same time for problem to happen):

       A                                      B
---------------------------------------------------------------
insert A likes B                       insert B likes A
Look if B likes A:                     Look if A likes B:
 -> No (B's insert not yet visible)     -> No (A's insert not yet visible)
 -> No match detected                   -> No match detected
Commit transaction:                    Commit transaction:
 -> new like visible for all            -> new like visible for all          

To avoid this you could set isolation level to read uncommitted but this is not recommended, or -- much better -- immediately commit each insert.

First conclusion: the insert of a "like" and the identification of a "match" are related, but are two distinct operations, that deserve to go into two different transactions.

Race condition issue 2: inconsistencies

If you immediately commit the inserts, either one will be faster and the slowest will catch up and detect the reciprocal likes (normal situation that your algorithm handles correctly), or the two are committed at the same time (and both threads will see and try to process the reciprocal likes):

       A                                      B
---------------------------------------------------------------
Insert A likes B                       Insert B likes A
Commit                                 Commit
Look if B likes A:                     Look if A likes B:
 -> Yes!                                -> Yes! 
 -> send notification                   -> send notification
 -> update notificaton_send on both     -> update notification send on both

the last operation above is a source of troubles:

  • In the best case, you'll have two notifications sent and both notification_sent updated twice with the same value.

  • In the worst case, depending on how your RDBMS and your locking statement, the updates might cause a deadlock, e.g. if A first locks A's "like" and then tries to lock B's "like", but at the same time B already locked B's "like" and tries to acquire the now locked A's "like". Fortunately, the RDBMS detects these deadlocks. But the result will be the roll-back of the update transactions: This notifications were sent but the flag not updated.

Second conclusion: it's always dangerous to mix non-database operations (notifications) and database operations that tell if it's done if the success of the DB operation is not guaranteed.

Race condition issue 3: preventive locking is not sufficient

If you don't commit the insert, preventive locking will be useless: you'd still miss the matches.

With a committed insert, the preventive locking the flags (on both rows, before sending the notification) is a wise recommendation made by fnmps: it makes sure that the notification is sent once, and that the update may happen, so DB in sync with reality.

However, the preventive lock does not prevent deadlocks! You may check on StackOverflow for your favourite RDBMS, but here an example of deadlock that might happen. The golden rule to prevent deadlock is to ensure an absolute order for all the resources that might be locked and always lock them in the same order in all the threads.

Third conclusion: the fact that you have two rows that are partially used to describe the same match is a source of troubles. The whole speach about normalization is exactly to prevent these kind of troubles.

Conclusion: with a committed insert before the match-check + the preventive lock done the right way (see comments on fnmps' question) your system would prevent race conditions.

Other approaches

You may also consider to separate concerns, breaking down your packed algorithm into smaller pieces, each doing one thing and doing them well:

  • Inserting "likes", simplifiying the table keeping only the "like" releated data (user liked, when, etc...) with a match processing status (not processed/processed).
  • Detecting matches, based on unprocessed likes. Identify matches in a separate match-table, because the match is bidirectional. One match, one row: to facilitate collision avoidance, use a like_id1 and a like_id2, always the lowest id in 1. You may then easier follow-up on matches, with a notification status (to be notified, notified).
  • sending notifications, reading the unprocessed matches.

A more radical approach would be to use event-streams to manage processing of these steps, and keep the RDBMS to just maintain the status for easy query. It's not without reason that popular social medias rely on Kafka and similar event-streamers to deal with trillions of notifications per day ;-)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.