v7: Proposal: Incorporate counter into "subsecond time", explicit layouts for "subsecond time" field width

[broofa]

There's a lot to like about Draft 2, version 7 UUIDs. They solve many of the main issues people have raised in version 1. I especially appreciate the fractional binary format for subsecond values. However there are two issues that continue to nag at me.

Problem 1: The layout of time/counter bits .vs. random bits is ambiguous. For example, if you examine the 3 example layouts (Draft 2, §4.4.4.1), you'll note that the high order bits of the subsec_seq_node field may be used for subsecond time and seq information (Fig 4 & 5), or simply set randomly (Fig 3). Unfortunately there's no way of distinguishing which is which. This may prove problematic where such IDs become comingled and need to be sorted or sharded within a database.

Problem 2: Dedicating a fixed number of bits to monotonically increasing state (subsec_a and subsec_b fields) leads to endless debate about whether or not the size of those fields is insufficient, sufficient, or excessive. Use cases that require low rates of UUID creation result in wasted bits (bits that rarely change), while cases with high creation rates result in possible counter overflow issues. We have seen arguments from both sides of this problem. (I suspect most of us have argued both sides of this problem!)

Proposal:

[Note: This is highly derivative of the current Draft 2 proposal and incorporates ideas that have been floated in other comments elsewhere. Please forgive any verbiage that may sound like I'm claiming credit for any of this as being particularly original.]

There are two parts to this proposal...

Part 1: This is more a matter of semantics, but I believe being explicit about this will simplify both the spec, and the discourse we're having around it. Basically I'd like to take §4.2.1.2 of the original RFC where it talks about how a counter may be used to populate the low-order bits of the timestamp and generalize it thusly:

"Subsecond time" refers to a combination of two pieces of state. The high order bits MUST be obtained from the subsecond state provided by the system clock (expected to be at least millisecond precision). Any remaining low order bits MUST be obtained from a count of the number of IDs generated in the current system clock time interval. The distribution of bits between system clock vs UUID counter will be implementation dependent.

(Where exactly this goes in the spec is TBD, but maybe replace section 4.4.2 of Draft 2...?)

The idea here is that by explicitly incorporating the notion of a "counter" into "subsecond time", we can do away with debate about how many bits are / aren't allocated to seq or counter fields and, instead, focus on the rate at which IDs may be generated which is, after all, what people really care about.

However, in order to do that we need the second part of this proposal...

Part 2: tl:dr; Define a handful of "subsecond time" precisions and layouts that allow for a reasonable range of creation rates, and identify these layouts using a [new] "pr" field. The pr field can be small (two bits), and will allow implementors to select a layout most appropriate for their use case, thereby maximizing how the the remaining bits are distributed between subsecond time and random entropy. Specifically, if pr is a two-bit field, we can use it to define the following layouts:

pr	subsecond field size (max ids per second)	Bit allocation examples (system clock : counter)
0b00	10 bits (1024)	10 : 0 (msec clock, no counter) 0 : 10 (1-second clock, 10-bit counter)
0b01	20 bits (1 x 106)	10 : 10 (msec clock, 10-bit counter) 20 : 0 (usec clock, no counter)
0b10	30 bits (1.1 x 109)	10:20 (msec clock, 20-bit counter 20: 10 (usec-clock, 10-bit counter)
0b11	40 bits (1.1 x 1012)	20:20 (usec clock, 20-bit counter) 30: 10 (nsec-clock, 10-bit counter)

Location of the pr field is TBD (and I'm not sure how important this decision is), but immediately following the var field seems like an obvious choice. This would allow for the following layouts:

Layout 0b00 (10-bit subsec field)

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            unixts                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|unixts |       subsec      |ran|  ver  | ...dom                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|0 0|                     rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Layout 0b01 (20-bit subsec field)

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            unixts                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|unixts |       subsec          |  ver  |       subsec  | rand  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|0 1|                     rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Layout 0b10 (30-bit subsec field)

 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            unixts                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|unixts |       subsec          |  ver  |       subsec          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|1 0|subsec     |   rand    |                 rand          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Layout 0b11 (40-bit subsec field)

 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            unixts                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|unixts |       subsec          |  ver  |       subsec          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|1 1|       subsec                  |          rand         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             rand                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

[NOTE: subsec field here uses fractional-binary format as described in Draft 2]

Summary

Draft 2 Version 7 fixes the number of dedicated subsecond time bits at 24 (subsec_a and subsec_b). This allows for a generation rate of ~4M uuids/second. That's pretty much it. Creating IDs faster than that requires setting state in the subsec_seq_node field, which becomes meaningless as soon as the ids in question are comingled with IDs that may have been generated with other layouts. And in cases where IDs are created slowly (< 1 / msec), 12 bits go unused, resulting in only 62 bits of entropy to help avoid collisions.

Contrast to this proposal where the fast case allows for 10 trillion uuids/second (pr = 0b11) with 46 bits of entropy. And, in the slow case (pr = 0b00), allows for 1000 uuids /second and 74 bits of entropy. And has the added benefit of allowing recipients of IDs to identify exactly which bits are and are not monotonic in nature.

[sergeyprokhorenko]

No need to waste scarce bits describing the UUID structure. To do this, it is enough to use the parameters in the function that generates the UUID.

But this is a good idea: The distribution of bits between system clock vs UUID counter will be implementation dependent. Because when we consider effective clock resolution of timestamp + counter, then the counter is much more efficient than the timestamp. The counter bits saved during idle time are consumed when the load is high. But timestamp accuracy is important for monotonicity when UUIDs come from multiple sources.

I also like the suggested 30-bit subsec/counter field.

[broofa]

No need to waste scarce bits describing the UUID structure.

Hopefully the "cost" of using two-bits for the pr field is more than offset by the benefits that come from an adaptable field size. For example, the pr field solves the counter overflow problem. Generators can start with the smallest appropriate field size, then switch (on-the-fly!) to a larger field size if there is risk of a counter overflow (e.g. counter > max_counter_value / 2). They need only bit-shift the current counter value accordingly to insure monotonicity is maintained, and can even revert back to the smaller layout at the start of the next interval if desired.

To do this, it is enough to use the parameters in the function that generates the UUID.

The problem is that unless the input parameters to the function are recorded somewhere, any recipient of a UUID that cares about monotonicity must currently assume the worst (where only subsec_a and subsec_b are monotonic) because there are no guarantees about how the subsec_seq_node field bits are set.

[LiosK]

I like the idea to subsume the counter (or seq) under the sub-second fraction field. In this way, the spec becomes much simpler and both fields can be efficiently encoded in a given bit length. Here is a working example of the concept: https://github.com/LiosK/uuidv7

I don't really see the benefits of having explicit layouts of subsecond fields, though. I like the following part of the draft 02 as it is very simple. Plus, I don't really find a common use case where the structure of a UUID needs to be analyzed by a decoder.

When decoding or parsing a UUIDv7 value there are only two values to be considered:

1. The unix timestamp defined as unixts
2. The sub-second precision values defined as subsec_a, subsec_b, and subsec_seq_node

[broofa]

common use case where the structure of a UUID needs to be analyzed by a decoder

Any time-series database with better-then-microsecond precision (e.g. InfluxDB?) - where there may be value in using the entire subsecond time field for indexing or sharding - is likely to be concerned about this.

When decoding or parsing a UUIDv7 value there are only two values to be considered ... and subsec_seq_node

If there's no way to determine the nature of the various bits in subsec_seq_node (monotonic vs. random), then there's little point in ever parsing it and we should probabily remove it from this section.

Here is a working example of

... and once again I'm parroting stuff you've thought through months ago. 🤣

[sergeyprokhorenko]

...switch (on-the-fly!) to a larger field size if there is risk of a counter overflow

@broofa, It's a good idea, but we don't need the pr field for this

[sergeyprokhorenko]

If there's no way to determine the nature of the various bits in subsec_seq_node (monotonic vs. random), then there's little point in ever parsing it and we should probabily remove it from this section.

Yes!!! No parsing, please!!! We need as opaque UUID as possible

[broofa]

@broofa, It's a good idea, but we don't need the pr field for this

Please explain how you expand a counter on the fly while maintaining monotonicity of the subsecond field without some indication of the size of said field. I assert it can't be done.

Yes!!! No parsing, please!!! We need as opaque UUID as possible

There's a difference between parsing, and signaling which bits are / aren't monotonic. That's really all this is about. The impetus for v6 and v7 is to provide IDs that allow for good DB locality based on time. That requires understanding which time bits are monotonic and which aren't. Version 7 is, frankly, pretty sloppy about this at the moment.

If we're not going to encode the size of the subsecond time field, then we should specify what it size is unambiguously. Draft 2 does not do that, as seen in Fig's 3-5.

[sergeyprokhorenko]

Monotony is not black or white. Small breaks in monotonicity are acceptable. They only slightly slow down the search for records in the database table by UUID. If we have already allowed the counter to overflow, then it is quite possible to sacrifice such trifles. We can increment the counter by a few bits without letting anyone know. The monotonicity will be better than if we just freeze the counter at maximum. Now it is important not to gradually take up the entire random part for the counter.

By the way, when you replace random bits with counter bits, you also break monotonicity, because random bits could be ones, and the counter bits that appeared in their place could be zeros. To avoid this, it would be necessary to quickly fill the entire random part with ones. This would overflow the entire UUID. That is, an excessive desire for monotony is dangerous. It may be sufficient to freeze the counter before overflowing, as well as lengthening the counter based on performance calculations.

[LiosK]

I don't really see the point to discuss the monotonicity at field level. As of the draft 02, a UUIDv7 can be parsed as if it had any of the second-, millisecond-, microsecond, or nanosecond-precision monotonic timestamp, though the lower bits may be filled with a counter and/or random numbers. Essentially, UUIDv7 can be seen as a 128-bit timestamp encoded as a fixed-point number, so decoder can pick an arbitrary number of leading bits and treat them as a monotonically ordered field no matter whether the lower bits are a real timestamp or random number. I like this simple, elegant, and genius design of UUIDv7.

In addition, UUIDv7s have a different ID space every second (, millisecond, microsecond, etc.), so a generator can employ a different subsecond precision and/or counter length every second (, millisecond, etc.) without breaking the monotonicity or letting users notice the change. The generator might need to wait for up to one second (most commonly up to a millisecond) to switch from one strategy to another, but it can almost be seen as on-the-fly.

Small breaks in monotonicity are acceptable.

The monotonicity will certainly be broken in the real world applications due to distributed timestamp sources and rewinded system clocks, but does the RFC need to allow the broken monotonicity explicitly? The distributed timestamp sources might be out of the scope of the RFC. The rewinded or broken system clocks are a kind of force majeure situation where a generator can only reset its internal state to random values and restart. It might be good to mention such a force majeure behavior in the RFC, but I don't think the UUIDv7 spec needs to be always aware of such a situation.

[sergeyprokhorenko]

@LiosK, you are reasoning as if UUIDv7 were used by smart developers with flexible thinking. But this is absolutely not the case. Decisions will be made by stupid managers with stereotyped thinking who have become adept at intrigues. Therefore, the standard should offer a simple menu with ready-made examples for typical situations. Of course, there should be no restrictions in the standard that bind creative developers of advanced solutions, but ready-to-use examples are much more important for the success of this standard.