10

The requirement is to send a unique id to database when user click on submit button. So I am using Javascript Math.random method. I just want to know what are the chances or possibility to get same number and what bit size of using Math.random.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
Jitender
  • 7,593
  • 30
  • 104
  • 210
  • 5
    Terrible idea. Don't do it. Period. Your database should be capable of auto numbering fields, so use that. – Matt Burland Jan 28 '15 at 17:56
  • I'll prefer my own random number generated with timestamp and table id or something.. – Rahul Winner Jan 28 '15 at 17:57
  • Some alternatives: a) Let the DBMS do it. b) Check the database for clashes. c) Use UUID. d) ... – Biffen Jan 28 '15 at 18:00
  • @amit why do you prefer that anyway? is there any reasonable cause for you preference? – martskins Jan 28 '15 at 18:05
  • Ya, i agree to u Matt.. We can include some user info too. As i understood the question, it's about sending unique number from web page to database. So i believe this approach should be suffice.. – Rahul Winner Jan 28 '15 at 18:12
  • 3
    Another thing to consider; you are only thinking about the possibility of an accidental collision. What about the possibility of a deliberate collision? Where a client deliberately sends you the same id in an attempt to get around some restriction you impose on the use of your API? For that reason, you should leave the generation of ids to the backend. If the client needs it for some future operation, it should be returned to them on the first request and they will have to wait for that returned value. – Matt Burland Jan 28 '15 at 18:50
  • 1
    For any reasonable chance of random IDs being unique, you need at least 128 bits, preferably 256. And you need a cryptographically secure PRNG. Javascript's Math.random() fails on both counts. It's only 56 bits, and not secure. – Lee Daniel Crocker Jan 29 '15 at 17:22

3 Answers3

29

You're up against something called the birthday problem: even though there are 366 possible birthdays, when you get only 26 people in a room, the chance that some pair will have the same birthday is better than 50-50. In general, collisions are likely when your numbers approach the square root of the sample size (26 is in the neighborhood of the square root of 366).

Javascript's Math.random() has about 52 bits of randomness. Therefore, collisions should be likely as your record count approaches 2**26, which is about 60 million, a quite modest size for a database.

You should use a cryptographically-secure PRNG with at least 128 bits, preferably 256, to avoid collisions. There are probably ready-to-use UUID libraries for this available.

For an given number of keys k, and a keyspace N, the approximate odds of collision are:

1 - exp((-k * (k-1))/(2 * N))

So for k=1 million records, N=2**52, that comes to about 1 in 9000, if I did the math right. That's further assuming that Javascript's Math.random() is truly using the fill 52 bits of randomness available to it...that too is an assumption I wouldn't make.

Lee Daniel Crocker
  • 12,927
  • 3
  • 29
  • 55
  • Can you please tell me the formula to get possibilities. I have 1 million record and I have set an unique id using math.random so in 1 million how many number may be duplicate – Jitender Jan 29 '15 at 19:31
3

Don't do it. Trusting (multiple) clients to come up with unique values is not going to work.

Even if each client is guaranteed to generate unique values, you could have two clients generate the same value. Since most pseudo-random number generators are seeded with the current time, that becomes more likely as you get more users.

If you're creating database records, your database should provide some functionality like this. Most or all SQL databases have an auto-increment concept, and many NoSQL databases have an equivalent (Mongo certainly does for IDs). Allowing the database to handle this can be good for performance (it can set up indexes and allocate space to handle the IDs well) and the DB has the final say on the data, so it can guarantee that IDs are unique.

Failing that, you can have your server-side generated some unique identifier (like a UUID) and use that. Having the server do it and using a known-good algorithm, like a type 4 UUID, guarantees sufficient randomness that conflicts should never occur. Note that using UUIDs, unless your database has a type for them, will have very different index performance than sequential IDs.

ssube
  • 47,010
  • 7
  • 103
  • 140
  • Isn't the change of two `GUID`s to be the same roughly one in 10 billion? – Mouser Jan 28 '15 at 18:03
  • @Mouser I believe it's much lower than that, from http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates – ssube Jan 28 '15 at 18:05
  • Nice, the change of getting hit by a meteorite is actually higher than me calculating a GUID that collides. – Mouser Jan 28 '15 at 18:06
  • @Mouser: Unless your guid generating algorithm is seriously flawed, no. – Matt Burland Jan 28 '15 at 18:08
  • 1
    I'm pretty sure the collision issues can be mitigated by using `crypto.getRandomValues`, where supported (IE11+); it's guaranteed to be seeded with a good entropy source (and therefore not current time). But the real problem with client-side random values is that they're susceptible to being tampered with. – Retsam Jan 28 '15 at 18:52
  • I would think that trusting *arbitrary clients* is a much bigger issue than trusting collision-prone random numbers. Depends on what is actually done with these numbers of course, but don't forget the security implications. – Bergi Jan 28 '15 at 19:19
0

I'll prefer my own random number generated with the use of timestamp, client or user related identifier.

Rahul Winner
  • 430
  • 3
  • 16
  • Why use a salted random number when databases have support for counters, and we have UUIDs and the like? – ssube Jan 28 '15 at 18:02
  • This question about sending some unique number from client to database. Database counters may not be helpful. – Rahul Winner Jan 28 '15 at 18:09
  • The question specifies unique (which the client cannot guarantee) and IDs (which databases definitely have special support for). – ssube Jan 28 '15 at 18:10
  • 2
    @RahulWinner If two clients generate IDs at the same time or a single client generates two IDs within the step of the timer (usually 10ns or so), using timestamps, they will clash. It's usually very easy for this to happen. – ssube Jan 28 '15 at 18:38
  • That's why i added in my comment above to use user (client) related info as well.. Please refer my comments under question.. – Rahul Winner Jan 28 '15 at 18:58