collision analysis

[i3d]

Hi, I am investigating using this rand.Read API to generate random IDs (size around, [4 - 255]) using only DNS allowed character set. Could you help me picturing a bit on the collision rate analysis? (I saw you have bias analysis, assuming that's for the distribution, but not sure whether I saw collision rate one)

Thank you!
Jim

[i3d]

fyi, I am currently using crypto/rand but that's 1) much slower than your impl and 2) we don't really need cryptographic secure property, the ID is just need to be unique. (math/rand is slower than yours but still faster than crypto/rand but Go stdlib is deprecating it so it seems there isn't a non-crypto PRNG in go stdlib anymore)

[flyingmutant]

When talking about collision rate, what exactly do you mean?

[i3d]

For example, you have a comment in the code like this

// Generators returned by [New] (with empty or distinct seeds) are guaranteed
// to not run into each other for at least 2^64 iterations.

Does this mean that calling rand.New() 2^64 times will guarantee to generate 2^64 unique 64bit numbers? My main purpose here is to try to see whether I could use this lib to generate IDs which must be unique. The ID size could be [4 - 255] bytes in variations. I suppose 4 bytes (32bit) will likely require a trim down that could potentially increase the collision rate. but if the API can generate 8 byte (64bit) hash values without any collision within the output space, that would be a huge indicator to me that we should raise our ID size to at least 8 bytes...

[flyingmutant]

Any decent 64-bit generator does not generate 2^64 unique 64-bit numbers in a row. Pure random numbers are expected to repeat from time to time. My comment was about the fact that the generated sequence will not match any other generated sequence.

However, starting from 256 bits, you can expect that any generated value will be unique simply because chance of collision is virtually zero. So 256-bit (32 byte) random IDs are guaranteed to be unique. Depending on application, some people consider 128 bits of randomness to be good enough. 64 bits is definitely not enough -- due to birthday paradox, you will have 50% chance of generating colliding ID after only 2^32 IDs generated.

[i3d]

got you. 2^32 is ~4B, which we don't expect we could reach that in any near future, so I think that's a reasonable safe boundary for us. (aka, I think uint64 hash is good enough for us). So basically, it really depends on the output space, the bigger the better. We could consider 16bytes with some format like (8byte-8byte) if really really necessary...

Thank you!