Uuid:uuid4() collisions

[giorgiosironi]

We are generating about 1M UUID4 a day, and we are getting several hundred collisions a day, such as:

[2015-08-26 21:29:19 +0200] [production-onebipws-1.apache - 17819] [DEBUG] [Request] 
time_total=0.145
"request_id":"fdfb98c1-4367-4f22-b68a-d7cdaedcc069" 

[2015-08-27 00:36:16 +0200] [production-onebipws-1.apache - 17819] [DEBUG] [Request] 
time_total=0.016
"request_id":"fdfb98c1-4367-4f22-b68a-d7cdaedcc069"

The issue seem to be correlated with the same Apache process regenerating the same UUID after several hours. It also seem to be correlated with particular EC2 machines which presents the problem.

We checked to have openssl_random_pseudo_bytes and if it was using a strong algorithm:

root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r "var_dump(function_exists('openssl_random_pseudo_bytes'));"                                      
bool(true)
root@dev-all-onebip:~/projects/.../onebip-ultimate$  (master) # php -r 'openssl_random_pseudo_bytes(16, $strong); var_dump($strong);'
bool(true)

How can we debug this problem?

[ircmaxell]

Which version of UUID are you using? Can you try switching to master?

[giorgiosironi]

We are on 2.8.1, but from what I see the code for uuid4() is identical to master:

public static function uuid4()
{
    $bytes = self::generateBytes(16);
    // When converting the bytes to hex, it turns into a 32-character
    // hexadecimal string that looks a lot like an MD5 hash, so at this
    // point, we can just pass it to uuidFromHashedName. 
    $hex = bin2hex($bytes);
    return self::uuidFromHashedName($hex, 4);
}

private static function generateBytes($length)
{
    if (self::hasOpensslRandomPseudoBytes()) {
        return openssl_random_pseudo_bytes($length);
    }
    ...
}

Here is a sample of the duplicated UUIDs:
https://gist.github.com/giorgiosironi/f1ce4682868ca6a6279d

[ramsey]

I wonder if you'll experience the same if you switch to using @ircmaxell's RandomLib.

Using master or 3.0.0-alpha3, you can do so like this:

$uuidFactory = new \Ramsey\Uuid\UuidFactory();
$uuidFactory->setRandomGenerator(new \Ramsey\Uuid\Generator\RandomLibAdapter());
\Ramsey\Uuid\Uuid::setFactory($uuidFactory);

$uuid = \Ramsey\Uuid\Uuid::uuid4();

[giorgiosironi]

Currently I am trying to reproduce the problem with a cli script to avoid impacting the production system, if I have a test that produces collisions I will try rerun it with RandomLib.

[ramsey]

Can you share your test that produces collisions? Does it consistently reproduce them, and is it always reproducing them for the same UUIDs?

[fabre-thibaud]

Yup, would be interesting to have more information on your setup (OS version, openssl version, machine architecture (x86 vs x86_64) ... the more the better)

I'm unable to get a single collision on a 12M set:

<?php

require_once 'vendor/autoload.php';

while (1) {
    file_put_contents('uuids.txt', \Rhumsaa\Uuid\Uuid::uuid4() . PHP_EOL, FILE_APPEND);
}

thibaud@thibaud-zbox:~/Workspaces/uuid$ wc -l uuids.txt 
12143446 uuids.txt
thibaud@thibaud-zbox:~/Workspaces/uuid$ sort uuids.txt | uniq -d
thibaud@thibaud-zbox:~/Workspaces/uuid$

EDIT This is with OpenSSL enabled

[ircmaxell]

Try generating them on multiple servers. Part of mt_rand()'s output is based on server timestamp, so collisions are probable there (assuming openssl disabled).

[giorgiosironi]

I do not have yet a script reproducing the problem (it's production traffic presenting the issue), but it happens on a single server, also as stated in the first comment we have the openssl extension enabled.
Versions:

root@production-onebipws-1:~$  # openssl version
OpenSSL 1.0.1 14 Mar 2012
root@production-onebipws-1:~$  # php -v
PHP 5.4.43-1+deb.sury.org~precise+1 (cli) (built: Jul 15 2015 12:05:17) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2014 Zend Technologies
    with Zend OPcache v7.0.2, Copyright (c) 1999-2013, by Zend Technologies

[ircmaxell]

That's a very serious problem then. Could you check to see if the $strong parameter of openssl_random_pseudo_bytes() is showing true or false on this server?

[fabre-thibaud]

@ircmaxell He mentionned in the first post that it returns true :)

@giorgiosironi Does it happen on any other server or only that one ? Is there a software (OS, PHP, OpenSSL) version difference between that specific server and the others that do not collide ?

[ircmaxell]

He may be getting true from the command line. That doesn't mean it can't
return different values during load, or when these collisions are
generated...
On Aug 27, 2015 12:10 PM, "Thibaud Fabre" notifications@github.com wrote:

@ircmaxell https://github.com/ircmaxell He mentionned in the first post
that it returns true :)

@giorgiosironi https://github.com/giorgiosironi Does it happen on any
other server or only that one ? Is there a software (OS, PHP, OpenSSL)
version difference between that specific server and the others that do not
collide ?

—
Reply to this email directly or view it on GitHub
#80 (comment).

[ramsey]

Any more word on this? @renan reported similar findings on Twitter:

https://twitter.com/renan_saddam/status/637024558038544388

[giorgiosironi]

What we have done until now:

• implemented retry on collisions with a new generation to avoid data loss
• extracting data lost in the last two months
• reimporting it in the system
• switched back the code to the uniqid()+mt_rand() previous implementation, which has still caused collisions in the past but at a 1% rate with respect to openssl

[fabre-thibaud]

@giorgiosironi Did you manage to find out if openssl_random_pseudo_bytes was storing a false flag in the $strong argument when you get collisions ?