14

We cannot serialize registrations as there are millions of users registering at the same time. Parallel registrations need to happen.

Let's say the database doesn't contain username 'user1'. When two users try to register at the same moment with 'user1' it'll accept it. But it will later cause problems. This shouldn't happen.

I'm looking for a logical solution. Not anything specific. Just an idea to solve this.

14
  • 4
    It's a legitimate software architecture problem. Not the kind of problem that only makes a good interview question and nothing else. Aug 29, 2016 at 17:48
  • 1
    I liked the question more before you edited. It was not a good question to start with. Went from thousands to millions at the same time. What are they registering for? The Internet does not have that capacity? A DDOS attack does not hit a sever with millions of hits at the same time.
    – paparazzo
    Aug 29, 2016 at 18:14
  • 10
    Millions of users registering at the same time? Really? If you have millions of users registering at the same time, you have bigger problems - like handling billions of registered users. And probably the money to afford servers that handle it.
    – gnasher729
    Aug 29, 2016 at 18:27
  • 2
    @AddzyK This is a hypothetical problem faced in the future that you want a logical solution to? Pretty sure that is out of scope here.
    – paparazzo
    Aug 29, 2016 at 18:28
  • 4
    Heres a hypothetical answer: pay someone else to do it that already knows what to do. With millions of new users/second, you'll have the cash. Aug 29, 2016 at 18:38

6 Answers 6

20

Let's say the database doesn't contain username 'user1'. When two users try to register at the same moment with 'user1' it'll accept it.

Why would it accept it? It's simple to apply a unique constraint, use username as a primary key, or simply run the check in application code inside a transaction.

You should absolutely be able to use a database transaction to use the database to prevent this from occurring. Otherwise, no application would be able to maintain invariants in database data.

In terms of scaling, databases already invented the technologies you need, like various modes of locking depending on exactly what kind of consistency you need, distributed databases for multiple database servers, etc.

5
  • Does locking the registrations not prevent other users from registering at the same time?
    – Addzy K
    Aug 29, 2016 at 18:41
  • 4
    +1, Just ran some rough math, and even Facebook only averages a few signups per second. So relying on the database's own constraints should be sufficient. Aug 29, 2016 at 18:56
  • 3
    @AddzyK: Locking only occurs for the brief moment that the database must enforce the constraints. Yes, other users registering simultaneously must wait in line, but that wait is very short, and rarely occurs anyway, even on the largest systems. Aug 29, 2016 at 18:59
  • 1
    @GrandmasterB The averages may not tell the full story here. I assumed based on the question that this was for handling heavy peak load- for instance the Australian census stuff.
    – DeadMG
    Aug 29, 2016 at 19:08
  • @AddzyK It might do. Essentially, you can get away with only locking part of the table. There are numerous schemes for dealing with this, such as gnasher729's answer, but I believe that you should be able to get an off-the-shelf distributed database product that can handle this for you. Even if you have to roll your own partial locking scheme, there are plenty of known ways to handle it, such as DHT.
    – DeadMG
    Aug 29, 2016 at 19:10
10

There is a standard solution to this. Create multiple workers to do the registrations. Each request has a hash applied to the username, and the hash determines which worker processes the request. This way there is no possible way for two requests for the same username could be processed concurrently.

For this kind of volume of requests consider a distributed key value store such as riak instead of an all database as the data store.

3

Is it a problem ?

Letting two users finish their registration with a non unique username is not acceptable if the username (and not the user email) is used for the login.

If the username is not used for authentication, you can use use some background process to identify and flag the doubles (for example based on timestamp) and force user to change his username on next logon

Yes it is a problem

As you're asking, I suppose that the username is supposed to be a unique id. Following approaches could be used:

  1. Before: In the registration process, foresee a step where the new user has to check availability of his name. When doing so, prereserve the available account name with a temporary status and an session id that will allow finishing registration.
  2. Same time: A more general and flexible variant of gnasher729 reply, would be to use a simple hash function (like the ones used for managing symbol tables), to assign the id to a unique registration server i (i = h(username) modulo number_of_servers) that will handle uniqueness on his limited/segmented scope
  3. After: At the end of the registration, when the user clicks on register send the request to your transactional database, if you can define the field as unique. Upon error, send the unlucky user "oops, there was a problem" message and ask him to choose another id.
  4. Asynchronous: register the user. Reread the user record just after to ensure it's unchanged and the single one. If it's a problem either ask user to change (not so asynchronous), or send him a mail that there was a problem (asynchronous, but annoying from user perspective), or let him register but ask him for his email (to disambiguate) and force him to change username as part of the login procedure.
2

Reconsider what you think of as the unique identifier for a user. Each user already has a unique email address, so that problem has already been solved for you. Of course, this means that multiple users will be able to register the same name, like "Mike Nakis". Is there a problem with that? Are you sure? It is not a problem for facebook, for example. There exist multiple facebook users called "Mike Nakis". Look at the facebook login page: it asks for "email or phone" and "password".

0

With millions of users registering at the same, you just use 26 x 26 registration servers, one for users starting with aa, one for users starting with ab and so on. As a result, there are only thousands of users registering at each server at the same time. If you still can't handle that, use 26 x 26 x 26 servers.

5
  • 6
    ...and then your product owner wants to go international...
    – Telastyn
    Aug 29, 2016 at 18:30
  • 3
    The same principles apply to Unicode strings as long as they are in a normalized form, such as NFKD. You could also hash the username and apply it based on hash. However, this answer is basically just implementing your own distributed database.
    – DeadMG
    Aug 29, 2016 at 18:35
  • 2
    You mean they have millions of users registering at the same time in one country? In that case they should have enough money to pay more for a real solution.
    – gnasher729
    Aug 29, 2016 at 19:10
  • 1
    More specifically, this is just the start of how DHTs are done.
    – DeadMG
    Aug 29, 2016 at 19:13
  • how does this fix the problem of two users registering the same name at the same time - both names would start with the same two characters and so be handled by the same registration server?
    – HorusKol
    Aug 30, 2016 at 23:25
0

This is obviously an interview type of question. The interviewer should be satisfied with the following two-word answer:

Use GUIDs.

That having been said, GUIDs are terrible to work with, so in any practical scenario you are advised to try every other solution that you can think of, before resorting to using them. In the real world, there is no such thing as millions of users trying to register at the same time. Serializing registrations is always an option.

More on GUIDs here: https://blog.michael.gr/2017/06/on-uuids-and-guids.html

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.