Unable to obtain V1 UUID once limit of 3fff is reached

[nikomi]

The source of version 1.3.13 says

stepTime = do
  h1 <- fmap hundredsOfNanosSinceGregorianReform getCurrentTime
  modifyMVar state $ \s@(State mac' c0 h0) ->
   if h1 > h0
    then
      return (State mac' c0 h1, Just (mac', c0, h1))
    else
      let
        c1 = succ c0
      in if c1 <= 0x3fff -- when clock is initially randomized,
                      -- then this test will need to change
         then
          return (State mac' c1 h1, Just (mac', c1, h1))
        else
          return (s, Nothing)

Since c0 is never reset to 0 it seems that once 3fff is reached - i.e. after requesting a V1 UUID too fast 3fff times - no new V1 UUID will ever be returned.

Maybe the first return line should read (note the 0 instead of c0)

      return (State mac' 0 h1, Just (mac', 0, h1))

Or is there a reason for this behaviour, e.g. some specification that demands this?

[nikomi]

Sorry - should read: unable to obtain UUID too fast once limit is reached.

You can still obtain UUIDs if requesting slowly enough. Maybe that's why nobody ever encountered this.

[nikomi]

If resetting every time is taboo it could be done on roll-over only:

    let c0' = if c0 < 0x3fff then c0 else 0
    in return (State mac' c0' h1, Just (mac', c0', h1))

c0' could even be randomized if the original c0 was randomized.

[hvr]

Investigating this a bit, originally the clock sequence would be reset to 0 frequently but this was changed in cad54a8 (for reasons which aren't obvious to me).

However, quoting RFC 4122 which explains the purpose of the "clock sequence",

4.1.5. Clock Sequence

For UUID version 1, the clock sequence is used to help avoid duplicates that could arise when the clock is set backwards in time or if the node ID changes.

If the clock is set backwards, or might have been set backwards (e.g., while the system was powered off), and the UUID generator can not be sure that no UUIDs were generated with timestamps larger than the value to which the clock was set, then the clock sequence has to be changed. If the previous value of the clock sequence is known, it can just be incremented; otherwise it should be set to a random or high-quality pseudo-random value.

Similarly, if the node ID changes (e.g., because a network card has been moved between machines), setting the clock sequence to a random number minimizes the probability of a duplicate due to slight differences in the clock settings of the machines. If the value of clock sequence associated with the changed node ID were known, then the clock sequence could just be incremented, but that is unlikely.

The clock sequence MUST be originally (i.e., once in the lifetime of a system) initialized to a random number to minimize the correlation across systems. This provides maximum protection against node identifiers that may move or switch from system to system rapidly. The initial value MUST NOT be correlated to the node identifier.

Its purpose is not to be incremented whenever a UUID collision occurs but rather to ensure that UUID sequences don't overlap between system restarts (due to the system clock possibly being subject to some restart-induced offset).

In this context, what the code currently does seems a bit questionable.

That being said; it's very unlikely to run into such UUID collisions unless the resolution of the system clock is lower than the frequency by which UUID are requested; and I wasn't able to get even near such collisions on a non-virtualized Linux system.

In this context another section of RFC 4122 is relevant:

4.2.1.2. System Clock Resolution

The timestamp is generated from the system time, whose resolution may
be less than the resolution of the UUID timestamp.

If UUIDs do not need to be frequently generated, the timestamp can
simply be the system time multiplied by the number of 100-nanosecond
intervals per system time interval.

If a system overruns the generator by requesting too many UUIDs
within a single system time interval, the UUID service MUST either
return an error, or stall the UUID generator until the system clock
catches up.

A high resolution timestamp can be simulated by keeping a count of
the number of UUIDs that have been generated with the same value of
the system time, and using it to construct the low order bits of the
timestamp. The count will range between zero and the number of
100-nanosecond intervals per system time interval.

Note: If the processors overrun the UUID generation frequently,
additional node identifiers can be allocated to the system, which
will permit higher speed allocation by making multiple UUIDs
potentially available for each time stamp value.

So if there really are systems whose system clock resolution is too coarse you'd run into uuid exhaustion, I'd implement the suggestion mentioned above on how to simulate high-res timestamps.

Moreover, I plan to provide a way to explicitly query/set the global clock-sequence value in order to allow API consumers to implement the system-restart semantics as described in 4.1.5. for those rare use-cases where this is actually needed.