[dansingerman]

You say 'only millions records'. Even if you had 2^36 records (that's over 68 billion) the chances of a collision should be 0.0000000000000004

That really is vanishingly small.

So, rationally, I'd guess it is more likely there is a problem with the implementation of UUID you are using, or just perhaps there is some other cause of the collision...like a bug?

[WorldMaker]

Also possibly a problem with the version of UUID used. A v1 UUID is somewhat likely to collide if machines share MAC addresses and/or have problematic clocks.

The likelihood of a v4 collision is tied to the strength of the platform's (crypto) RNG.