Uuid: Got collisions for v1() when generating many IDs

[arnesten]

Hi,

I have been using node-uuid for a while, and it has in total generated about 500k IDs that I use. I now ran a check and found, to my surprise, 2 collisions among those IDs.

The collisions were generated in a sequence where 5-10 IDs are created synchronously and stored in the same database document. For one of the collisions it happened directly following the original entry. For the other collision there were 2 entries between them.

One of the collisions was:
e7a69040-b412-11e2-ad2c-57e3dd379c2d

Should this really be possible? Perhaps there is some flaw in the implementation.

I was using Node 0.8 at the time, if that matters.

[broofa]

Should this really be possible?

No. The RFC (which uuid.js conforms to) includes a clockseq counter that's supposed to prevent collisions, even if IDs are created at exactly the same instant.

Is it possible your code is somehow copying UUIDs between records? (Sorry, I have to ask)

If you know the sequence in which your ids are being generated, it'd be useful to know which IDs were generated immediately preceeding / following the collisions. Also, if you could paste the code you're using to generate IDs, that would be helpful.

[arnesten]

Here is the sequence surrounding one of the collisions (I only saved one of the collisions unfortunately):
e7a69041-b412-11e2-ad2c-57e3dd379c2d
e7a69040-b412-11e2-ad2c-57e3dd379c2d
e7a69040-b412-11e2-ad2c-57e3dd379c2d
e7a6b750-b412-11e2-ad2c-57e3dd379c2d

Basically the code that generates the IDs are very simple. It's a for loop where uuid.v1() is called and assigned to each item in a list. There is no function for duplicating the items belonging to the same document.

Could it be that the server time for some reason have changed while the sequence was generated and that is causing the collision?

[broofa]

Can you confirm those IDs are listed in the order they were generated? (I ask because the time_low field - the first 8 digits - looks a little odd if that's the case, and I'll want to investigate)

[arnesten]

It's likely that they are, but not with 100% certainty. There is a function in the system that changes the order of the items.

[broofa]

Re: the server time changing, the UUID spec (and uuid.js) are designed to handle this case by incrementing a "clock sequence" field. And I'm not seeing any initial indication of a clock anomaly in those. Will look into this when I have a bit more time.

[vasiliyb]

guys, is it all feasible if many cloud instances generate unique ids using v1()? ie
userObject.id = uuid.v1();

[broofa]

Yes. Each node-uuid instance has a 48-bit "node" field that is randomly generated.

Sent from my iPhone

On Sep 9, 2014, at 2:13 PM, Vasiliy [email protected] wrote:

guys, is it all feasible if many cloud instances generate unique ids using v1()?

—
Reply to this email directly or view it on GitHub.

[vasiliyb]

@broofa so what you're saying that if hundreds of node instances are generating v1() uids, its possible to get a collision?

[broofa]

@vasiliyb - You were asking whether it's feasible to use node-uuid across many instances to generate unique ID's, right? At least, that's the question I was attempting to answer.

Within a given node-instance, uuid.v1() will never generate the same ID. Across instances, a collision should only happen if two instances generate an ID w/in 100-nanoseconds of one another, and have also somehow managed to select the same node and clockseq values at random. The odds of the latter happening (identical node and clockseq) are, assuming reasonable RNG quality, 1-in-5 quintillion (4.6e18).

So, yes, it's theoretically possible. But should be astronomically rare. (as in, I'd be amazed if it actually happened in real-life unless there's a flaw in my code, or the random-number-generator)

[coolaj86]

Closing due to inactivity. Please reopen if this is still a demonstrable bug.

From skimming the comments it sounds like this may have been an related to the accidental inclusion of Math.random()?

[FreakTheMighty]

What was the take away from this thread? Is this the expected behavior?

[1, 2, 3].forEach( function(i) {
  console.log(i);
  console.log(uuid.v1())
});

outputs:

d8982ec0-275e-11e6-aaac-a53c3533f1ce
2
d89855d0-275e-11e6-aaac-a53c3533f1ce
3
d89855d1-275e-11e6-aaac-a53c3533f1ce

[ohtangza]

@FreakTheMighty The key seems to be different. Take a deep look at it :)