1

I'm considering generating unique identifiers for data in javascript using one of the uuid methods discussed here. Most likely something along the lines of this one since it uses window.crypto if it's available.

These id's don't need to be globally unique, only unique per user. Will this generate sufficiently unique ids for a large scale application? Is there any reason to think this will result in id collisions? Can javascript generate a sufficiently random uuid for this to work? It looks like window.crypto is fairly widely available and this particular project already requires reasonably modern browsers.

MORE INFO: some background about the problem can be found here

Community
  • 1
  • 1
herbrandson
  • 2,357
  • 2
  • 30
  • 44

1 Answers1

1

From the comments on this answer:

... (cont'd) The odds of two IDs generated by this function colliding are, literally, astronomically small. All but 6 of the 128 bits of the ID are randomly generated, which means that for any two ids, there's a 1 in 2^^122 (or 5.3x10^^36) chance they'll collide. – broofa

That's a 1 in 5,316,911,983,139,663,491,615,228,241,121,378,304 (5.3 undecillion) chance of collision.

Also make sure to validate that when a user attempts to create a new record with this uuid, that the uuid is not already in use. This falls under the larger strategy of never trusting user input.

You can also test this generator if you aren't convinced:

function getUUID() {
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
    return v.toString(16);
  });
}

var uuids = [];
var last;
var numGenerated = 0;
do {
  last = getUUID();
  if (uuids.indexOf(last) === -1) {
    uuids.push(last);
    numGenerated++;
    console.log(numGenerated);
  } else {
    break;
  }
} while (true);

console.log('Got collision after ' + numGenerated + ' generated UUIDS.');

I'm running it in Node.js (V8) right now and am still collision-free after 170,000 ids. Edit: 240,000.

Community
  • 1
  • 1
Jackson
  • 9,188
  • 6
  • 52
  • 77
  • I saw that, but a few comments later it also says "As long as Math.random yields only pseudo-random numbers, your calculation of the odds seems to be wrong" – herbrandson Apr 19 '14 at 01:35
  • There are replacement RNGs ...' – Jeremy J Starcher Apr 19 '14 at 02:02
  • If you want a "more random" seed you could do something like detect mouse movement with an `onmousemove` event. However, any technique you use will be useless if a user submits his own UUID by bringing up a console and changing a variable. Ultimately you will still have to validate server-side; since checking for collisions is inevitable anyway, you should be satisfied with a UUID solution that is mostly (if not completely) collision-free. – Jackson Apr 19 '14 at 02:15