Return to Generating a Unique Number

In a previous post I discussed generating a unique id number for an order in our database. Read the original post for the full story, but to sum up, I decided that playing around with rand(100_000_000) was good enough. Martin Ankerl posted a comment pointing out that I was vulnerable to the Birthday Problem. So after a quick trip to wikipedia, I found out that if you have 23 people in a room you might think you have a 23/365 chance of having 2 people with the same birthdays, but no, your chances are closer to 50%! This is because in a group of 23 people there are 253 pairs each of which have a 1/365ish chance to have the same birthday. The formula to calculate how many are needed to give you a 50% chance of having a birthday collision is:

.5 + sqrt(.25 + 2 * 365 * ln(2) ) = 22.9999

Which means the 50% chance of collision mark for 100,000,000 is:
.5 + sqrt(.25 + 2 * 100,000,000 * ln(2) ) = 11774.600235771

Holy crap! I'm screwed if I can only have 12,000 orders before I get a 50% chance of collision. But wait, I think I'm ok because every time I insert a key into the database I check to make sure it isn't already in there. This means that when I'm at 12,000 orders the next key has only a 1 / (100,000,000 - 12,000) chance of being a collision. I think I've changed from the "Birthday problem" to the "Same birthday as you" problem, which is way more intuitive. If I'm wrong I rely on you, the blogoshpere, to tell me so.

If you haven't already, go read the wikipedia article on the Birthday problem. It's pretty cool.

Comments

Anonymous said…
Hi! You are right and I was wrong, it's not a birthday problem. When you already use half of your numbers (50_000_000), the chance to find a free key is actually 50%, so that should be no problem.
February 20, 2008 at 12:56 AM
Shlomo said…
Jake,

I'm not much on doing the math unless I have to, so I thought I'd just try your algorithm with different numbers of carts. Here are my results:

15,000 carts only generated a couple of collisions on average (0.013%).

150,000 carts generated about 90 collisions on average (0.06%).

1,500,000 carts generated 10,000 to 12,000 collisions (0.73%).

15,000,000 carts generated 1,180,524 collisions (7.87%).

The most collisions I saw while trying to find a unique key was 5, and that was quite exceptional, more often there was one or no collisions before a unique key was found. It gets lots worse as you approach your ramdom factor, so my guess is that this thing will get inefficient as you get close to 100,000,000 carts, but it will still work. I tried generating 150,000 carts when the random factor and it was working, but it would take sometimes more than 10 attempts to find a unique key.

I also tried replacing your algo with truncated MD5. At 150,000 carts there were no collisions, but generating 150,000 MD5 hashes is really, really, really slow, In terms of performance, your system is much faster and imho good enough.
February 20, 2008 at 5:17 AM
AkitaOnRails said…
Why can't you simply use UUID?? Also called GUID? It's the standard way to create (virtually) collision free 128-bit identifiers. There are literally hundreds of implementations out there for almost every programming language, from C to Ruby. I can't think of any reason not to use UUID if collision is an issue.
February 20, 2008 at 8:12 AM
Jake Scruggs said…
Akita, the requirements of the business state that we can only have 11 digits in this key. GUIDs are way longer. See my first post on this for more background.
February 20, 2008 at 1:24 PM
Mike Lucas said…
I've successfully used a "truncated GUID" solution before. I looked into the java GUID generator I was using and determined that none of the digits were more or less random or significant than others, so I figured truncating was ok.

But with only 11 digits you're definitely giving up a lot of the 32 hex digits that make up a normal GUID.

If the business accepts any alphanumeric character for this ID, I would use a random generator that selects from all the allowed characters, that will give you the least chance of collision. The implementation would be very similar to a Random Password Generator solution (generate random characters from an allowed character set).
February 22, 2008 at 10:51 AM
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...
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