UUIDv7 continues to increment timestamp after counter overflow

Bug report

Bug description:

I believe the uuidv7() implementation will increment the timestamp for every ID created after a counter overflow instead of just once.

For example, imagine you need to create ten UUIDv7s in a single millisecond and the first one is unlucky enough to get a counter value of 0x3ff_ffff_ffff (the maximum). When generating the second UUID the implementation will correctly increment the timestamp and pick a new counter (consistent with 6.2 Counter Rollover Handling). _last_timestamp_v7 is saved as now+1.

Unfortunately, the third UUID is generated in an unexpected way. At line 871 the code checks if the current time is less than the last saved timestamp. Since the wall clock hasn't progressed to the next millisecond and _last_timestamp_v7 is in the future, the check returns true. At line 872 the timestamp is incremented again, now two milliseconds in the future.

The remaining UUIDs continue to be generated further into the future such that the tenth UUID is nine milliseconds in the future.

Please consider this code to observe the behavior:

    def test_uuid7_overflow_bug(self):
        equal = self.assertEqual
        # 1 Jan 2023 12:34:56.123_456_789
        timestamp_ns = 1672533296_123_456_789  # ns precision
        timestamp_ms, _ = divmod(timestamp_ns, 1_000_000)

        new_counter_hi = random.getrandbits(11)
        new_counter_lo = random.getrandbits(30)
        new_counter = (new_counter_hi << 30) | new_counter_lo

        tail = random.getrandbits(32)
        random_bits = (new_counter << 32) | tail 
        random_data = random_bits.to_bytes(10)

        with (
            mock.patch.multiple(
                self.uuid,
                _last_timestamp_v7=timestamp_ms,
                # same timestamp, but force an overflow on the counter
                _last_counter_v7=0x3ff_ffff_ffff,
            ),   
            mock.patch('time.time_ns', return_value=timestamp_ns),
        ):   
            u = self.uuid.uuid7()
            equal(u.version, 7)
            # timestamp advanced due to overflow
            equal(self.uuid._last_timestamp_v7, timestamp_ms + 1) 
            unix_ts_ms = (timestamp_ms + 1) & 0xffff_ffff_ffff
            equal(u.time, unix_ts_ms)
            equal((u.int >> 80) & 0xffff_ffff_ffff, unix_ts_ms)
            # new counter was picked, not longer at risk of overflow
            self.assertNotEqual(self.uuid._last_counter_v7, 0x3ff_ffff_ffff)

            u = self.uuid.uuid7()
            equal(u.version, 7)
            # should not overflow again
            equal(self.uuid._last_timestamp_v7, timestamp_ms + 1) 
            unix_ts_ms = (timestamp_ms + 1) & 0xffff_ffff_ffff
            equal(u.time, unix_ts_ms)  # <-- Test fails here as the timestamp was unexpectedly incremented again
            equal((u.int >> 80) & 0xffff_ffff_ffff, unix_ts_ms)

Unfortunately, I think this can break the UUID generator as the timestamp will continue incrementing with each UUID generated, unless the wall clock catches up with the _last_timestamp_v7. Under high load (>= 2 UUID each second), the wall clock may never catch up and the UUIDv7s will travel further and further into the future. This likely breaks monotonocity in multi-node systems.

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-146606