V1 Generator Should not Always Increment Sequence Counter

posborne commented

2017-11-17 17:12:35 -06:00

(Migrated from github.com)

The V1 generation code (new_v1) rightly state the following in the documentation:

This function is only guaranteed to produce unique values if the following conditions hold:

The NodeID is unique for this process.

The Context is shared across all threads which are generating V1 UUIDs

The supplied seconds+nsecs values are monotonically increasing.

Items 1 and 2 can be reasonably guaranteed in a system but the 3rd item is nearly impossible to guarantee in practice as the value needs to be monotonically increasing across the entire life of the system (not just a given boot).

Both the RFC for UUID (RFC4122) and the DCE documentation provide similar guidelines on when the sequence should be modified.

I propose the following change (which I can create a PR for):

Make the UuidV1Context a trait so that the implementation can be plugged as needed. This is important if one wanted to, for instance, ensure that changes to the time/sequence were persisted.
Make the UuidV1Context responsible for storing the most recent time value (in resolution of 100nsecs).
Add a method for getting an appropriate sequence number from a context given the current generation time. As per the RFC recommendation, this sequence number would not change if the time was after the last time seen. If the time was the same or prior to the last time seen, then the sequence number would be incremented.

Per RFC4122:

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.

The V1 generation code (`new_v1`) rightly state the following in the documentation: > This function is only guaranteed to produce unique values if the following conditions hold: > 1. The NodeID is unique for this process. > 2. The Context is shared across all threads which are generating V1 UUIDs > 3. The supplied seconds+nsecs values are monotonically increasing. Items 1 and 2 can be reasonably guaranteed in a system but the 3rd item is nearly impossible to guarantee in practice as the value needs to be monotonically increasing across the entire life of the system (not just a given boot). Both the [RFC for UUID (RFC4122)](https://tools.ietf.org/html/rfc4122.html) and the [DCE documentation](http://pubs.opengroup.org/onlinepubs/9629399/apdxa.htm) provide similar guidelines on when the sequence should be modified. I propose the following change (which I can create a PR for): 1. Make the `UuidV1Context` a trait so that the implementation can be plugged as needed. This is important if one wanted to, for instance, ensure that changes to the time/sequence were persisted. 2. Make the `UuidV1Context` responsible for storing the most recent time value (in resolution of 100nsecs). 3. Add a method for getting an appropriate sequence number from a context given the current generation time. As per the RFC recommendation, this sequence number would not change if the time was after the last time seen. If the time was the same or prior to the last time seen, then the sequence number would be incremented. Per RFC4122: > 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.

radix commented

2018-01-26 17:36:33 -06:00

(Migrated from github.com)

Hi, if you want to create a PR, I can help review it! (I have no authority in the uuid project, just offering my assistance)

radix commented

2018-01-30 16:21:32 -06:00

(Migrated from github.com)

Hi @posborne, do you still have any time to implement this change? If not, I can take a crack at it.

kinggoesgaming commented

2018-02-05 11:20:51 -06:00

(Migrated from github.com)

hi @posborne are you still interested in providing a PR for this? I want this to be part of 0.7 release. Else @radix can work on it.

radix commented

2018-02-05 11:29:14 -06:00

(Migrated from github.com)

I will try to work on this today.

👍 1

radix commented

2018-02-05 15:17:56 -06:00

(Migrated from github.com)

Any recommendations for how to handle storing the "last updated" time in the context?

Stable rust only exports AtomicUsize, not things like AtomicU64 and AtomicU32. And even if those types were stabilized, they would not all be available on all platforms: https://doc.rust-lang.org/src/core/sync/atomic.rs.html#1439

If we want the default UuidV1Context datastructure to continue to support multi-threaded use, then we must use some internally-mutable type that supports multithreaded access. This means either Atomics or Mutexes...

maybe there's some way we could use Atomics, but there are apparently even platforms where usize == u16. That means we would need a way to store 96 bits of timestamp across up to 6 AtomicUsize values...

Just using Arc<Mutex<Timestamp>> for the timestamp would work, but this could end up slowing down new_v1 by a lot.

Any recommendations for how to handle storing the "last updated" time in the context? Stable rust only exports `AtomicUsize`, not things like `AtomicU64` and `AtomicU32`. And even if those types were stabilized, they would not all be available on all platforms: https://doc.rust-lang.org/src/core/sync/atomic.rs.html#1439 If we want the default `UuidV1Context` datastructure to continue to support multi-threaded use, then we must use some internally-mutable type that supports multithreaded access. This means either Atomics or Mutexes... *maybe* there's some way we could use Atomics, but there are apparently even platforms where usize == u16. That means we would need a way to store 96 bits of timestamp across up to 6 AtomicUsize values... Just using `Arc<Mutex<Timestamp>>` for the timestamp would work, but this could end up slowing down `new_v1` by a lot.

radix commented

2018-02-05 18:01:49 -06:00

(Migrated from github.com)

I have a WIP in the linked PR #136, using the Mutex approach for keeping track of the previous time.

Surprisingly to me, this only increases the runtime of v1 generation to about 2x the previous time. But it has another drawback too: the default context now requires std whereas the old one would work without it (mutexes are only available with std). Is this really okay? Should we add another context implementation identical to the old one, so we have something for people who want to generate v1 uuids without std?

I'm also wondering what the drawbacks to the old context. The RFC does say that we should update it when the timestamp might have stayed the same or gone backwards, but it doesn't forbid or even seem to say we SHOULDN'T increment it when the timestamp moves forward.

Of course, the trait is definitely a good idea, I'm just wondering what problems we're going to solve with the new implementation. Does anyone know if there was any rationale for this discussed elsewhere (during the libs blitz perhaps)?

I have a WIP in the linked PR #136, using the Mutex approach for keeping track of the previous time. Surprisingly to me, this only increases the runtime of v1 generation to about 2x the previous time. But it has another drawback too: the default context now requires std whereas the old one would work without it (mutexes are only available with std). Is this really okay? Should we add another context implementation identical to the old one, so we have something for people who want to generate v1 uuids without std? I'm also wondering what the drawbacks to the old context. The RFC does say that we should update it when the timestamp might have stayed the same or gone backwards, but it doesn't forbid or even seem to say we SHOULDN'T increment it when the timestamp moves forward. Of course, the trait is definitely a good idea, I'm just wondering what problems we're going to solve with the new implementation. Does anyone know if there was any rationale for this discussed elsewhere (during the libs blitz perhaps)?

radix commented

2018-02-05 20:36:52 -06:00

(Migrated from github.com)

I put up a more conservative PR at #137. It only adds the trait, and doesn't change the way sequences are generated. It's all backwards compatible.

kinggoesgaming commented

2018-02-05 23:05:21 -06:00

(Migrated from github.com)

Just a note that we don’t merge that PR until 0.6 is released

Dylan-DPC-zz commented

2018-03-22 05:07:11 -05:00

(Migrated from github.com)

@posborne the trait merged in #137 and released in 0.6.0 fullfills the needs of this issue. If anything else is needed, you may create a new issue for it :)

PrismaPhonic commented

2019-10-16 00:26:19 -05:00

(Migrated from github.com)

I know this has already been closed but I think offering a trait to "solve" this problem is the wrong approach. The default use of ClockSequence here is just plain wrong and should be corrected to follow spec.

Dylan-DPC-zz commented

2019-10-16 03:48:39 -05:00

(Migrated from github.com)

@PrismaPhonic thanks. We are always open to discussing issues and decisions. Moving this to a new issue for better traction.

Rows
Columns

V1 Generator Should not Always Increment Sequence Counter #106