Generating a Unique Number

Weird requirement at work today: We needed a number that was alpha-numeric, exactly 11 digits, unique, and non-sequential. At first we thought of using a hash, but MD5 and Sha1 give you way too many digits. We could truncate to 11, but not knowing much about hashing, that made me pretty nervous that we'd have collisions. After a bunch of discussion, we decided on this:

MAXIMUM_FOR_10_DIGITS = 0xffffffffff
(MAXIMUM_FOR_10_DIGITS + cart_id + Time.now.to_i + rand(100_000_000)).to_s(16)
I was thinking about using hex, but I was worried about what would happen if the number got too big and went to 12 digits. So I did this calculation:

irb(main):001:0> 0xfffffffffff - 0x10000000000
=> 16492674416639
Turns out there's all sorts of room between the lowest and highest 11 digit hex number. Paul and Schubert did some quick calculations assuming lots of carts per day and figured out that we have about 250,000 years before we run out of space. Now since we use a random number, there is a chance that we could get two matching numbers so we do a database lookup to make sure that a generated number hasn't been used before. There is still a small chance that two identical numbers could be generated in the time between generation and saving to the database, but I think we can live with that.

Update: After some interesting comments, I wrote a follow up post. Check it out for more math goodness.

Comments

Unknown said…
If your only requirement is to have unique non-sequential value it would be much easier to just to multiply it by a large prime.

PRIME = 2654435761
MAX = 2**44-1
"%.11X" % (VALUE * PRIME & MAX)"
January 17, 2008 at 8:44 AM
Anonymous said…
I dare say that using 11 first chars of an hash would have given you the same result. That is, with the same collision probability.

I'm not quite sure about that, but I think the average number of steps after which you get a collision in a set of N elements is sqrt(N). So that you'll probably need to wait till you got more than 300.000 ids to find one!
January 17, 2008 at 11:21 AM
Anonymous said…
You may run out of space in 250 thousand years, but you might be having too many collisions before then.

Why not just start at 0 and count up sequentially (or the opposite)?
January 17, 2008 at 4:11 PM
Jake Scruggs said…
We, of course, argued for a sequential number but the business said no. They don't want anyone figuring out how many orders they get in a day. We also tried to talk them into a Globally Unique Identifier but they didn't want that many digits. 11 was as high as they were willing to go. I thought that truncating a hash would probably work, but I wasn't sure enough (and neither was anyone on the team) so we went with the algorithm described above. The prime thing sounds cool, though.
January 17, 2008 at 6:02 PM
Anonymous said…
1) Hash distribution is (theoretically) even. Put in terms of bits, the fequency of any bit being 1 or 0 is the same as any other bit. Therefore, a truncated version is just as evenly distributed as the longer version (you're just picking a subset of the bits, all of whom have equal frequency of 1-ness.)

2) You do not need a hash, you need a random number. As you are already checking for collisions, you could just rand(max) and then convert to your base of choice (which leads me to mynext point)
January 17, 2008 at 6:25 PM
Anonymous said…
Hi, I am not sure if you don't run into the birthday problem with this. Time.now.to_is is a 31 bit number, rand(100_000_000) gives a 27 bit number. I assume your cart ID is pretty low to. You just add these numbers, so basically the part that changes are only the last 27 bits.

When you have about 15000 keys in your database, the probability of a collision is over 50%. When you have 50000 keys, you have a probability of 99.999% of a match! So it gets almost impossible to find a free key.

I think you should try to use the maximum possible randomness to get around this problem. The largest number is

largest = ("Z"*11).to_i(26+10)
id = rand(largest).to_s(26+11)

Then you have about 56 bit of randomness which is a lot more. The chance to get a collision here is about 50% when you have 400 million keys. With 800 million keys the probability is 91%.
February 19, 2008 at 7:55 AM
Anonymous said…
an alpha numeric gives you 26*2 characters but 10 digits. If you can squeeze in another 2 legal symbols in your number you have each alpha numeric having 1 of 64 possible states (base64 encoding?). That gives you 73,786,976,294,838,206,464 unique 11 possible IDs. All you need to do is use the following forumula:

((current Unix Time to the nanosecond precision) * 1000) + rand(1000)

You're only chance of collision with this number 1/1000 if two requests for an ID number is made within the same nanosecond. You will have several thousand years before this value will wrap around but even then you have very little chance of collision. This will not correlate your order id to a sequential number and should satisfy the business requirement. You can also avoid any chance of predictability by obfuscating the result by picking a secret prime number < MAX_ORDER_ID and do:

(PRIME**orderID) % PRIME.

Check out : http://en.wikipedia.org/wiki/Coprime
December 8, 2009 at 2:53 PM
Post a Comment

Popular posts from this blog

What's a Good Flog Score?

I've been using Flog to measure the complexity of my Ruby code and I was wondering how others interpret Flog numbers. I'll go first with my opinions: Score of Means 0-10 Awesome 11-20 Good enough 21-40 Might need refactoring 41-60 Possible to justify 61-100 Danger 100-200 Whoop, whoop, whoop 200 + Someone please think of the children (note: these are scores for an individual method) The 20 - 60 range is interesting to me. Sometimes the complexity of what you're doing will justify the score and other times the method is in desperate need of refactoring. The highest Flog score I've seen in the wild was in the 300's. What's you're personal high and what do you think of my rankings? In other news, I've redesigned the look of my blog so if you only see my post through a reader you might want to stop on by, take a look, and tell me what you think.
Read more

SICP Wasn’t Written for You

The number of software luminaries who sing the praises of “ Structure and Interpretation of Computer Programs ” (referred to as SICP) is such a long list that you might think only a crazy person would take issue with it. However, to ignore SICP’s problems and continue to blindly recommend it seems just as crazy. SICP was the textbook for MIT’s introductory programming class and was a bit of a departure from other into to computer science textbooks at the time.  Wikipedia sums it up nicely:  “Before SICP, the introductory courses were almost always filled with learning the details of some programming language, while SICP focuses on finding general patterns from specific problems and building software tools that embody each pattern.”  Which sounds awesome, but does essentially say that abstract principles will be introduced before the nuts and bolts of a language.  If you think about that for a minute, you may see where the problems will be. When I was training to be a teacher I took a b
Read more

Point Inside a Polygon in Ruby

Recently my team needed to find out if a point was inside a given polygon and, as usual, we found some code on the internet that did what we wanted. And, as usual, there wasn't much explanation as to what it was doing. Here's the code (after we converted it to Ruby): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def contains_point? (point) c = false i = -1 j = self .size - 1 while (i += 1 ) < self .size if (( self [i].y <= point.y && point.y < self [j].y) || ( self [j].y <= point.y && point.y < self [i].y)) if (point.x < ( self [j].x - self [i].x) * (point.y - self [i].y) / ( self [j].y - self [i].y) + self [i].x) c = !c end end j = i end return c end end So, you know, it works and I'm grateful to somebody for posting it but we had no idea how it works. So we wrapped 2 tests around it (one where the point is not in the polygon and another where it is
Read more