Collision probability

[kishaningithub]

Can the readme document the collision probability? A link to another page which has this info is also fine.

[peterbourgon]

Define probability?

[kishaningithub]

@peterbourgon For example, take the case of uuid

the probability to find a duplicate within 103 trillion version-4 UUIDs is one in a billion.

Source: https://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

[peterbourgon]

So collision probability with ULIDs is a function of entropy within the time granularity, which isn't a single fixed number. But it is well-defined, and as far as I'm aware the README and/or documentation explains precisely how that works. What's missing for you?

[NorbertSandor]

I've just run into: https://medium.com/zendesk-engineering/how-probable-are-collisions-with-ulids-monotonic-option-d604d3ed2de

[peterbourgon]

oklog/ulid does not use the monotonic algorithm suggested by the spec. It's unfortunately rather naïve. In fact I've been trying to get it clarified or removed altogether, but the repo seems to be unmaintained.

[kishaningithub]

#71 (comment)
@peterbourgon Regarding this, assuming the random generator is "truly random" what is the probability of collision that you see in ULID? May be the documentation on this is already there but i am not able to find it..

#71 (comment)
If you see here the UUID V4 gives a number based on the probablility calculation. If something like that is there for ULID it would be easier to convince "the managers"

[peterbourgon]

what is the probability of collision

As stated in the documentation with normal entropy there are

1.21e+24 unique ULIDs per millisecond (1,208,925,819,614,629,174,706,176 to be exact)

which means the probability of collision in a given millisecond is 1 out of 1,208,925,819,614,629,174,706,176.

If you use monotonic entropy, that probability increases proportionate to your inc parameter.