4

I'm an experienced Software Engineer but very weak in concurrency because of no prior experience in that. I've been interviewing with several companies in which I was asked similar kind of questions as given below:

  1. If you are designing a fantasy sports application in which there's a contest which can handle only 100 users. If 99 users are already registered for the contest and multiple users hit the PARTICIPATE button at the same time to become the 100th user, then how will you handle this in your application?

  2. If you are designing a chess game, where multiple users are selecting the users of same level of competence to play with them. Then suppose at same time, users A and B choose the user C (to play with) at the same time, then how will you handle this?

I usually answer this by saying that I'll use synchronized block in Java or on Database side, I'll use Locking concept. But I'm not sure of either of them. So, can anyone tell here how do you answer such questions? Should one answer this in terms of Java Multithreading or DBMS or both?

4
  • please don't cross post: stackoverflow.com/questions/68509095/…
    – gnat
    Jul 24 at 11:41
  • 1
    @gnat deleted from there. Jul 24 at 11:44
  • 2
    This can be viewed as either a software engineering question of how to handle the concurrency, or a political question, as, how would you fairly choose the next person out of a potential pool of applicants.
    – user10489
    Jul 24 at 13:55
  • @user10489 As a software engineer, if I was asked in an interview about being "unionized" I would assume they were asking about the state of lacking ions.
    – Michael
    Jul 24 at 19:46
7

This is a really broad question, since concurrency issues are handled in a variety of ways in complex system. For example a synchronized block in Java is only locked for other threads in the same process. If you have multiple web servers behind a load balancer running the same code, then synchronized blocks does not protect against racing conditions. If you have multiple servers using a single database, then you can check-and-register in a single transaction. But if you have multiple replicated databases and "eventual consistency" then it gets really thorny.

So I think you need to be more specific with the system constraints. Do you have a single shared ACID-compliant database? Then transactions is the way to go. Do you have single-process server or desktop application? Then code-level locking might be the simplest solution to the problem.

2
  • Can you briefly elaborate what check-and-register in a single transaction is? I am interested to understand
    – Adrian L
    Jul 30 at 9:59
  • @AdrianL: You check if there is less than 100 registrations and if that is the case, add a registration for the current user. But you have to do the check and the registration in a single transaction, otherwise you may get a racing condition.
    – JacquesB
    Jul 30 at 10:15
1

You typically use database transactions with their ACID properties (don't look at locking before you understand transactions). In your situations, a correctly written transaction will either commit successfully, which means that the client got the resource or reservation, or the commit operation will fail (presumably due to a conflicting concurrent transaction which was committed earlier).

4
  • 1
    It is perfectly possible to do transactions in code rather than the database. If it wasn't how would anyone ever create a database? You just need to understand how to design transactions in a way that makes them reliably atomic. Jul 24 at 14:30
  • That's true, but it may make things a bit more complicated than necessary. For example, if you run multiple backend processes (possibly on different servers) the process synchronisation can get somewhat involved. If you use a database with transactions, someone else solved that problem for you :-) Jul 24 at 16:22
  • If someone else solving the transaction problem is what you want you'll find plenty solutions here. Jul 25 at 15:51
0

Usually answer this by saying that I'll use synchronized block in Java or on Database side, I'll use Locking concept.

When we learn about multithreading, we are taught about locks, critical sections, transactions, etc. What we generally are not taught is that these are a last resort. Often you can solve concurrency problems without them, and when you can, you avoid a whole host of potential defects and performance issues (this is one of the reasons functional programming is so popular).

If you are designing a fantasy sports application in which there's a contest which can handle only 100 users. If 99 users are already registered for the contest and multiple users hit the PARTICIPATE button at the same time to become the 100th user, then how will you handle this in your application?

The temptation here is to create a counter, check if it has reached 100, then increment it with every registration. This is not a great approach because it creates lock contention over the counter. All threads will need to lock, inspect, and update it atomically, so threads will block each other waiting for their turn. If you don't wrap your counter check and update together in a critical section or transaction, you risk a TOCTOU situation. And if you acquire the locks in the wrong order, you risk a deadlock. Also, this solution has fault tolerance issues-- for example, if a process manages to increment the counter but throws an exception before it can register the user, it is nearly impossible to recover to a known good state.

Instead, this scenario can be handled very simply with this logic.

  1. When a user registers. store their user name with a datetime stamp specifying when exactly they registered, e.g

     INSERT Registration(UserID, RegistrationTime) VALUES (@UserID, GETDATE())
    
  2. To determine if their registration was accepted, select the top 100 users and see if the user is in it.

     SELECT COUNT(*) FROM 
     (
         SELECT TOP 100 UserID FROM Registration ORDER BY RegistrationTime
     )
     WHERE UserID = @UserID
    

This solution requires no locks or transactions other than the implicit transaction created by your insert statement, which is unavoidable. It's also inherently fault tolerant and much simpler to QA.

If you are designing a chess game, where multiple users are selecting the users of same level of competence to play with them. Then suppose at same time, users A and B choose the user C (to play with) at the same time, then how will you handle this?

Again, some simple logic will avoid the need for excessive locking.

  1. Allow any number of players to join a game. Record the datetime of when they joined.
  2. Start the game when there are two or more players
  3. As the first step in the game, sort the players by the datetime that they joined, then boot the 3rd and later players.

You can certainly solve either of these problems with locks or transactions, but it is also easy to avoid those mechanisms and the challenges that accompany them.

0

In all of the situations described in the OP, individual requests will arrive in a stream. That is to say, "one at a time." They will therefore be serviced by an "initial gatekeeper," which will make these go/no-go decisions. But that "gatekeeper" often consists of a pool of several processes.

In each case, however, there's only one "common source of record," which is the database. They will first use the database to inform their decision, then they will update the database to implement it. The process therefore devolves into making sure that the gatekeepers' accesses to that database do not conflict with one another.

This is the well-known purview of database transactions. And for this there are *"isolation levels." Such as: SET TRANSACTION ISOLATION LEVEL **SERIALIZABLE** ...

Your "multithreading" concerns, in this case, do not concern the internal structure of the clients who are making these requests to the database, but merely the final status of the database – to ensure that only one "transaction" that attempts to make these changes is able to COMMIT, forcing all the others to ROLLBACK and start over.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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