[SDRuby] Re: Unique Identifier

[Nic Benders]

On Apr 21, 2009, at 8:34 AM, Ryan Felton wrote:

Thanks for all the tips.

I had thought of the random generator, given that's what the Rails
Engine Substruct uses, but I was worry more about collisions as proven
here:

http://thedailywtf.com/Articles/The-Quest-for-the-Unique-ID.aspx

The KC Ruby group had suggested SHA1 truncated as shown here: 
http://gist.github.com/99156
. I'm thinking this is the solution I'm leaning towards...

Ryan

You can calculate the odds of a collision with this code snippet:

# Approximates the chance of at least one collision in a random
# distribution of k items across n possible IDs.  Adapted from
# Karsten's approximate calculator at http://tinyurl.com/5zt6ol
def collision_probability( k, n )
  1 - Math.exp((-k ** 2) / ( 2.0 * n).to_f)
end



collision_probability( 1.9 * (10**8), 2**64 ) #=> 0.000978013893024765

Because SHA creates a randomly distributed, non-reversible hash, you are just as likely to have a collision as you are in randomly selected string. So that 16 character hex string has the same 64-bit characteristics as the 13 character Base-36 one. The advantage of using a hash is that SHA1 is considered cryptographically secure, while the default Ruby rand() is not. For example, to calculate the odds of a collision using a 64-bit keyspace and 190 million randomly distributed keys:

smime.p7s
Description: S/MIME cryptographic signature