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

[mwhudson]

BPO	6598
Nosy	@mwhudson, @warsaw, @pitrou, @allenap, @bitdancer, @serhiy-storchaka
Files	make_msgid.diff make_msgid_2.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2015-11-13.11:57:05.364>
created_at = <Date 2009-07-30.00:32:14.943>
labels = ['type-bug', 'library']
title = 'calling email.utils.make_msgid frequently has a non-trivial probability of generating colliding ids'
updated_at = <Date 2015-11-13.11:57:05.362>
user = 'https://github.com/mwhudson'

bugs.python.org fields:

activity = <Date 2015-11-13.11:57:05.362>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-11-13.11:57:05.364>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2009-07-30.00:32:14.943>
creator = 'mwh'
dependencies = []
files = ['15339', '39405']
hgrepos = []
issue_num = 6598
keywords = ['patch']
message_count = 18.0
messages = ['91073', '91074', '91251', '91378', '91410', '95281', '236504', '236527', '243394', '243398', '243411', '243417', '243561', '243562', '243585', '254458', '254461', '254600']
nosy_count = 10.0
nosy_names = ['mwh', 'barry', 'ggenellina', 'pitrou', 'allenap', 'r.david.murray', 'BreamoreBoy', 'python-dev', 'serhiy.storchaka', 'varun']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue6598'
versions = ['Python 2.7', 'Python 3.4', 'Python 3.5']

[mwhudson]

If you call email.utils.make_msgid a number of times within the same
second, the uniqueness of the results depends on random.randint(100000)
returning different values each time.

A little mathematics proves that you don't have to call make_msgid
*that* often to get the same message id twice: if you call it 'n' times,
the probability of a collision is approximately "1 -
math.exp(-n*(n-1)/200000.0)", and for n == 100, that's about 5%. For n
== 1000, it's over 99%.

These numbers are born out by experiment:

>>> def collisions(n):
...     msgids = [make_msgid() for i in range(n)]
...     return len(msgids) - len(set(msgids))
... 
>>> sum((collisions(100)>0) for i in range(1000))
49
>>> sum((collisions(1000)>0) for i in range(1000))
991

I think probably having a counter in addition to the randomness would be
a good fix for the problem, though I guess then you have to worry about
thread safety.

[mwhudson]

A higher resolution timer would also help, of course.

(Thanks to James Knight for the prod).

[ggenellina]

This patch replaces the random part with an increasing sequence (in a
thread safe way).
Also, added a test case for make_msgid (there was none previously)

[pitrou]

Is it ok if the message id is predictable?
Besides, _gen_next_number() can more efficiently be written as:

_gen_next_number = itertools.cycle(xrange(N))

[ggenellina]

--- El jue 6-ago-09, Antoine Pitrou <report@bugs.python.org> escribió:

Antoine Pitrou <pitrou@free.fr>
added the comment:

Is it ok if the message id is predictable?

I don't know of any use of message ids apart from uniquely identifying the message, but we could still keep a random part followed by the sequence.

Besides, _gen_next_number() can more efficiently be written
as:

_gen_next_number = itertools.cycle(xrange(N))

Written that way it will eventually hold a list with 100000 integers forever.

  Yahoo! Cocina

Encontra las mejores recetas con Yahoo! Cocina.

http://ar.mujer.yahoo.com/cocina/

[ggenellina]

An updated version of the make_msgid patch.
Includes a random part plus a sequential part. Testing takes at most 3
seconds now (we're interested in those msgids generated in a whole
second)

[BreamoreBoy]

Can we have a patch review please. If nothing else xrange will have to change for Python 3.

[serhiy-storchaka]

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

[serhiy-storchaka]

Here is a patch that changes the generating of message IDs:

1. The datetime is taken with higher precision, 2 decimal digits after dot.
2. The datetime is written as Unix time in 0.01 second units, not as YYYYmmddHHMMSS. This is more compact and faster.
3. The random part is taken as the random integer in the range 0 from to 2**64, not from 0 to 10**5.

This increases the length of generated part of the ID from 26 to 39 characters in average. Perhaps in new releases we can use non-decimal or even non-alphanumeric characters in ID for compactness.

[bitdancer]

Looking at my mail store, it looks like one more more mail clients use a GUID for the messageid, which is 36 characters. So 39 doesn't seem so bad. There's even one that is 74 characters long. There are also shorter ones, though, so compactifying the result wouldn't be a bad thing.

[warsaw]

An increase of 13 characters doesn't seem so bad.

[serhiy-storchaka]

Currently the maximal length of local part is

14+1+len(str(2**16))+1+len(str(10**5-1)) == 26

With the patch it will be

len(str(2**31*100))+1+len(str(2**16))+1+len(str(2**64)) = 39

If encode all three numbers with hexadecimal, it will be

len('%x'%(2**31*100))+1+len('%x'%(2**16))+1+len('%x'%(2**64)) = 34

If encode their with base32:

math.ceil((31+math.log(100)/math.log(2))/5)+1+math.ceil(16/5)+1+math.ceil(64/5) = 27

Using base64 or base85 can be not safe, because message ID can be used as file name in case-insensitive file system.