[issue6598] calling email.utils.make_msgid frequently has a non-trivial probability of generating colliding ids

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

The probability of a collision when generated n numbers from 0 to m-1 is

    1 - factorial(m)/factorial(m-n)/m**n

When n << sqrt(m), it is approximately equal to n**2/(2*m). When m = 1000000, we have problems for n about 1000. When increase m to 2**32, the probability of collisions is decreased to 0.01%. When increase m to 2**64 as recommended in [1], it is decreased to 2.7e-14. I.e. when generate 1000 IDs per second, collisions happen one per a million years.

We could also take datetime with larger precision. E.g with 2 digits after the dot, as recommended in [1].

When apply both changes, we could generate 100000 IDs per second with one collision per 10000 years or 10000 IDs per second with one collision per 1000000 years.

[1] https://tools.ietf.org/html/draft-ietf-usefor-message-id-01

----------
nosy: +serhiy.storchaka

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue6598>
_______________________________________