CODEWITHSUNDEEP
javascriptnode.jsmongodb
Somename
Somename

Reputation: 3434

What is the guarantee of uniqueness of shortid?

I'm trying to include a field in Mongodb document called myId. I am using shortid. I am wondering, in case of big data, like millions of documents in a collections:

  1. What's the guarantee that the shortid will be always unique and never ever be repeated for any other document?
  2. What keeps a track of the generated ids?
  3. What are the chances of the id been repeated?

Upvotes: 2

Views: 2493

Answers (2)

Thomas
Thomas

Reputation: 12637

What's the guarantee that the shortid will be always unique and never ever be repeated for any other document

to cut a long story short: these shortids are pretty much just "hashed" timestamps. Not unix timestamps, their own breed, but non the less not much more than timestamps.

All that bling with Random is pretty much that, just bling.

As long as all these shortids are generated on the same computer (a single thread) with the same seed, collisions are impossible.

What keeps a track of the generated ids?

A counter that gets incremented when a you request ids to fast, so that the same timestamp is hit. This counter is reset to 0 as soon as a new timestamp is reached.

There's nothing significant, that is really random in there.

What are the chances of the id been repeated?

during usage, little to non existant.

As far as I can tell, the only two things that may lead to a collision are

  • changing the seed for the prng (leads to a new alphabet, so that newer dates may be encoded to ids that already have been generated with a different seed; although not very likely, but possible)

  • generating ids on multiple threads/machines because the counter is not synced.

Summary: I'd nag about pretty much everything in that code, but even as it is, it does the job, reliable. And I've told you the limitations.

Upvotes: 4

Bálint
Bálint

Reputation: 4039

Shortid generates a random 64 bit id. This is done in multiple step, but the base of it is this pseudo-random function:

function getNextValue() {
    seed = (seed * 9301 + 49297) % 233280;
    return seed/(233280.0);
}

To generate the same id twice, this function has to return the same exact values in the same exact order in the same exact second. This is very rare, but can happen if they reset the timer (based on the comments, they do, but it's still rare).

Upvotes: 0

Related Questions