CODEWITHSUNDEEP
ruby-on-railsrubyalgorithmcombinationsprobability
dcangulo
dcangulo

Reputation: 2107

What are the chances of getting a duplicate when using SecureRandom.hex?

I am planning to use SecureRandom.hex to generate API keys for my users.

So far here is the output in 3 executions:

Loading development environment (Rails 5.2.1)
2.3.5 :001 > SecureRandom.hex
 => "0369e9b7c6ffa07bd8d0a263f7b4cfa6" 
2.3.5 :002 > SecureRandom.hex
 => "1a8a168d7f70676451e3d59353e22693" 
2.3.5 :003 > SecureRandom.hex
 => "94cc188e9e5c3abfe587510fa79993ce"

What are the chances of me getting a duplicate result?

And will this method that I created will really avoid producing duplicate content?

def generate_string
  string = SecureRandom.hex

  generate_string if Model.where(:key => string).count > 0

  string
end

unique_string = generate_string

I am using recursion that if the string is already stored in the database, it will just produce another.

And also, since I am not getting a duplicate, how many strings can I produce with SecureRandom.hex before it rans out of combinations to produce?

Upvotes: 0

Views: 2512

Answers (3)

spickermann
spickermann

Reputation: 106882

In your example (when using SecureRandom.hex with the default length of 32) there are 

16**32 = 340282366920938463463374607431768211456

different hex values possible. That means there is a chance of 1:340282366920938463463374607431768211456 to create a duplicate. This chance is extremely low and IMHO it doesn't make much sense to worry too much about it.

When you are going to store that key in the database then I would suggest adding a unique index to that database column to ensure - on the database level - that it is impossible to store any duplicates.

Furthermore, you asked if your example code is enough to avoid duplicates. The answer is No. It is highly theoretical because of the low probability, but you might run into race conditions in which two jobs generating the same keys at the same time, checking both that there isn't such a key in the database and that both jobs store the same value into the table.

tl;dr Chance of duplicates are extremely low. Only a unique index on the key column in the database ensures that there will never be any duplicates (because of race conditions or keys generated bypassing this method).

Upvotes: 5

sawa
sawa

Reputation: 168101

The length of the keys seem to be 32 in your setting.

  • The chances of not getting duplicates in three executions is:

    ((16**32 - 1)/16**32) * ((16**32 - 2)/16**32)

    So the chances of getting (at least a pair of) duplicates somewhere in three executions is:

    1 - ((16**32 - 1)/16**32) * ((16**32 - 2)/16**32)
= 8.8162076e-39

  • There are:

    16**32 = 3.4028237e+38

    different strings.

  • Your method can avoid duplicates when it works as intended, but it also has an unimaginablly slim chance of falling into perpetuality and never terminating.

Upvotes: 1

yzalavin
yzalavin

Reputation: 1836

Since it is a base 16 numeral system there are 16 ** SecureRandom.hex.length possible variations which is quite a lot.

Better use loop with an exit condition if you do not want to overflow your stack when the quantity of users will increase.

MAX_ATTEMPTS = 3 # For you to choose.

def key
  MAX_ATTEMPTS.times do
    hex = SecureRandom.hex
    return hex unless Model.where(key: hex).exists?
  end

  fail 'No attempts to generate a key left.'
end

Upvotes: 2

Related Questions