> > Due to the birthday paradox, sqrt(n) is roughly the number you need to > > have a 50% collision chance when picking items at random from an > > inexhaustible set of n items. (0, sys.maxint - 1) is currently the > > random range. On 32-bit platforms the collision bound is thus quite > > low as sqrt(2^31) is about 46 000 keys. > > This isn't correct. The birthday paradox models a situation of choices > *with replacement* from a set. That is, when multiple entities can have > the same value. We don't have replacement. You have a set of X active > sessions, all unique (since that's a database constraint) and somebody > is trying to guess one of them at random. So the probability is X/N, not > something approaching sqrt(N)/N.
random.randint(0, n) *is* a set with choices with replacements. Multiple picks can, should and, as demonstrated at http://code.djangoproject.com/ticket/1180#comment:26 , do create collisions at around sqrt(n) picks and less. I entirely agree that collisions in picks from the random value set shouldn't directly manifest in collisions in the session key set as 1) time.time() is used as another varying input 2) collision is explicitly checked for in a loop until a unique value is created So, for a session key collision to occur, multiple threads should simultaneously enter the function, get the same time value and a colliding random value (and negative result from the uniqueness check). Admittedly this looks very unlikely when random values collide at around 46 000 picks. However, according to the report http://code.djangoproject.com/ticket/1180#comment:31 , collisions do exist when random range is (0, 2^31) and do not exist when it is (0, 2^63). So perhaps we miss something. To properly solve the problem, the particular scenario that leads to the collision should be pinpointed. Then we can make an informed decision about the amount of randomness needed. Until that, 63 bits can be used as it is safer than 31, does not cause much performance penalty and has proven to be enough to fix the problem. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Django developers" group. To post to this group, send email to django-developers@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/django-developers?hl=en -~----------~----~----~----~------~----~------~--~---
