TimeBasedEpochGenerator should prevent overflow

[chadparry]

After monotonicity was added to the UUIDv7 implementation, ( 5563381 ), it became susceptible to rollover. That's a risk for any UUIDv7 implementation with a seeded monotonic counter. But most implementations try to mitigate the risk so that it won't happen unless a huge number of UUIDs are requested. With this implementation, the worst case is that it may fail even if only two UUIDs are requested within one time slice. The probability of that happening is 2^-80, which makes it more of a theoretical risk. It is important enough to the specification that it actually warns against this though, ( https://www.rfc-editor.org/rfc/rfc9562#section-6.2-7.2 ). To be pedantically correct, the implementation could follow the specification's advice to zero out the first bit of randomness in the seed. That way the counter always starts out very far from an overflow.

Note that the carry logic doesn't take advantage of every single bit of entropy. Because it checks each byte against 0xff, the highest valid counter value is 0xfefefefefefefefefefe instead of 0xffffffffffffffffffff.

java-uuid-generator/src/main/java/com/fasterxml/uuid/impl/TimeBasedEpochGenerator.java

Line 131 in 314366d

c = _lastEntropy[i] == (byte) 0xff;

That could be corrected by comparing each byte to 0x00 instead, so that the carry bit gets handled just like in regular arithmetic.

[cowtowncoder]

Ok thank you for reporting the issue, @chadparry . Too bad I did not spot this in contribution; the original nanosecond timer does in fact guard against overflow.

If you have time and interest, a PR would be most welcome. But if not I hope I or someone else has time to address the issue.

[chadparry]

Hey, good to hear from you! I didn't know that was you until I saw your full name in the GitHub alert just now.

[cowtowncoder]

And I was about to ask if it was you (and not just name collision :) ).

Small world, indeed!

[chadparry]

If you have time and interest, a PR would be most welcome.

This bug isn't a big deal, but since it's your project, I can make time. :)

Note that the carry logic doesn't take advantage of every single bit of entropy. Because it checks each byte against 0xff, the highest valid counter value is 0xfefefefefefefefefefe instead of 0xffffffffffffffffffff.

I had originally read the code wrong; it used a temp variable to correctly check for 0xff before incrementing. However, I found a different counter bug. The UUIDUtil.constructUUID helper discards 6 entropy bits to make room for the version and variant. That means that duplicate UUIDs would get produced whenever the entropy differed only in those bits. Like the other bugs, this is more of a theoretical risk, since it's still possible to generate 2⁶² UUIDs before the next 3×2⁶² UUIDs would be duplicates. I decided to fix it so it wouldn't feel sloppy.