Generating a unique, but apparently random, identifier without loop+retry

Question

I'm trying to come with an algorithm to generate unique nonsequential tokens for a model in my rails app.

For instance:

MyModel.create.token #=> '183685'
MyModel.create.token #=> '456873'
MyModel.create.token #=> '813870'

The only way I can think to handle this is to create a random thing, check for a clash, and retry. This seems kind of code smelly to me, in a bute force kind of way.

class MyModel < ActiveRecord::Base
  before_create :set_token

  def set_token
    existing_model_count = nil

    # Loop while we have a token that already belongs to an existing model.
    while existing_model_count.nil? || existing_model_count > 0
      random_token = TokenGenerator.random_token
      existing_model_count = MyModel.where(token: random_token).count
    end

    # Loop exited, meaning we found an unused token.
    self.token = random_token
  end
end

Is there a better way to do this that doesn't involve a while loop which will iterate an unknown number of times?

While the examples here are ruby, this is sort of generic algorithmic issue which can apply to any language, so solutions in other languages are welcome.

You can generate longer tokens (eg. UUID) and make assumption that they are very probable unique. http://stackoverflow.com/questions/39771/is-a-guid-unique-100-of-the-time http://en.wikipedia.org/wiki/Universally_unique_identifier — MetalRain, Mar 22 '13 at 20:47
Sadly, I'm looking for far fewer bits than that. Something easily written down or stated over the phone. — Alex Wayne, Mar 22 '13 at 20:50
You could persistently enumerate all the valid tokens in your token range, then make `TokenGenerator.random_token` just randomly pick one and delete it. — dbenhur, Mar 22 '13 at 21:21
Do you know in advance how many tokens you will need (approximately, maybe)? Or are you looking for a completely open-ended unique token generation algorithm? — AnT stands with Russia, Mar 22 '13 at 22:13

score 6 · Answer 1 · edited May 23 '17 at 10:25

If your "token" is an integer value from some range and you know the number of tokens in advance, then simple Bob Floyd's algorithm (described in Bentley's "Programming Peals" or here) generates a unique random number without making any retries. It uses additional storage to "mark" the already used numbers, but still it cleverly manages to instantly come up with an unused number if the randomly generated one is already taken (i.e. no repetitive trial-and-error iterations).

One problem with that algorithm though is that even though the numbers it generates are not generally ordered, the order is still not completely random. In other words, even though the algorithm guarantees uniform distribution for each individual number it picks from the range, it does not guarantee the uniform distribution of the resultant sequence among all possible resultant sequences.

Whether it is a big deal for you or not - only you can decide. If the number of tokens you generate is small compared to the length of the range, then this algorithm will provide very satisfactory results. If the number of tokens is close to the length of the range, then this algorithm will generate "almost sorted" sequences.

score 2 · Answer 2 · answered Mar 22 '13 at 21:33

2

One way you can do it is by obfuscating the number. I explain this in some detail in my article Obfuscating Sequential Keys. The code samples are C#, but shouldn't be tough to translate.

answered Mar 22 '13 at 21:33

Jim Mischel

131,090
20
188
351

score 2 · Accepted Answer · answered Mar 22 '13 at 22:22

2

Run a cronjob every few hours which repopulates a Redis collection with unused identifiers. Let it run in the background so when you need one, just pop it off the Redis collection.

answered Mar 22 '13 at 22:22

000

26,951
10
71
101

sawa · Answer 4 · 2013-03-22T22:45:55.673

2

cipher = OpenSSL::Cipher::AES.new(128, :CBC).encrypt
cipher.update(MyModel.create.object_id.to_s(36))

edited Mar 22 '13 at 22:45

answered Mar 22 '13 at 22:34

sawa

165,429
45
277
381

score 1 · Answer 5 · answered Mar 22 '13 at 21:24

1

Take the number from a sequence. Implement a feistel network to scramble the number. An example I found is here: https://gist.github.com/Xeoncross/3715367

answered Mar 22 '13 at 21:24

maniek

7,087
2
20
43

score 1 · Answer 6 · answered Mar 22 '13 at 21:57

1

You can use SecureRandom.uuid. I think it guarantees unique random UUID token.

answered Mar 22 '13 at 21:57

Iuri G.

10,460
4
22
39

Generating a unique, but apparently random, identifier without loop+retry

6 Answers6