Discussion: Monotonicity and Counters

[kyzer-davis]

All things Monotonicity and Counters to assist with sort ordering, db index locality, and same Timestamp-tick collision avoidance during batch UUID creation.

Sub-Topics: Counter position, length, rollover handling and seeding.

Extension of the thread: https://github.com/uuid6/uuid6-ietf-draft/pull/58#discussion_r810593208

Required Reading: https://github.com/uuid6/uuid6-ietf-draft/issues/41#issuecomment-907517063 and Research efforts

[LiosK]

I care about the peak performance

That's the point. You got it. A 16-bit zero-starting counter makes sense only when the work load is constant, and randomly seeded counters work much better in any other cases. You've been trying to serve the unrealistically constant supercomputer use cases by sticking to 16-bit zero-starting counters. A 40-bit randomly seeded counter fits much better to your important applications by behaving just as entropy in low load times while supporting 550 billion monotonic IDs per millisecond at peak. Now do you agree not to recommend zero-starting counters?

[sergeyprokhorenko]

@LiosK, It is not that simple. I care of write peaks to ensure monotonicity. Monotonicity, in turn, will provide a high speed search in the database. Ultimately, it is the search speed that matters. The zero-starting counter is much shorter and therefore it can provide faster search of records in a database table. I don't care at all if the counter fills up completely or not, because the risk of collisions is still low, especially in monolithic databases.

[LiosK]

UUID is a 128-bit opaque identifier and thus searching UUIDs based on a shorter component should not be a general use case. In addition, even if you really want to write such code, a 16-bit randomly seeded counter provides the same property. You can initialize the 16-bit counter with 15-bit random numbers to guarantee a reasonable space or use a 17-bit counter if you really stick to 65,536. Plus, if you don't even fill up the 65,536 counter space, the 48-bit timestamp component is generally sufficient for indexing/sharding purpose. Anyway, my impression here is that you're again talking about supercomputer use cases. Please consider general readers.

[sergeyprokhorenko]

@LiosK,

UUID is a 128-bit opaque identifier and thus searching UUIDs based on a shorter component should not be a general use case.

Nothing prevents you from using bit by bit of UUID to search using the binary search algorithm.

In addition, even if you really want to write such code, a 16-bit randomly seeded counter provides the same property. You can initialize the 16-bit counter with 15-bit random numbers to guarantee a reasonable space

This is a great idea. If it is included into the specification, then I am ready to refuse 16 bit zero-starting counters.

Just one bit and shorter randomly seeded counter will save the day: combined counter 0rrrrrrrrrrrrrrr, where 0 is zero-starting counter (for more capacity of the combined counter) and r is 15-bit randomly seeded counter.

Plus, if you don't even fill up the 65,536 counter space, the 48-bit timestamp component is generally sufficient for indexing/sharding purpose.

It depends on the situation.

Anyway, my impression here is that you're again talking about supercomputer use cases. Please consider general readers.

I'm not worried about general readers, but about the costs of general companies, which have to purchase extra computer hardware, software licenses and technical support services due to low performance of information systems.

[LiosK]

Just one bit and shorter randomly seeded counter will save the day

Deal! Awesome. I will draft a change proposal to the current text later.

It's actually very important to let implementers realize that an n-bit counter can be initialized by any of n-bit random, (n - 1)-bit random, (n - 2)-bit random, ... or 0-bit random (i.e. zero) and they can choose the ones most appropriate to their applications.

using bit by bit of UUID to search using the binary search algorithm

That's actually a very good point.

[peterbourgon]

@sergeyprokhorenko

I care of write peaks to ensure monotonicity. Monotonicity, in turn, will provide a high speed search in the database. Ultimately, it is the search speed that matters. The zero-starting counter is much shorter and therefore it can provide faster search of records in a database table.

Could you explain how search speed — presumably, finding a specific UUID in a sorted list of UUIDs — is impacted by the bitwidth of specific fields?

[sergeyprokhorenko]

@peterbourgon

87658765767657658765 this value is less 87658765767657658777 this value is greater 19th symbol of the ID is compared

8765876576constant7657658765 this value is less 8765876576constant7657658777 this value is greater 27th symbol of the ID is compared

IDs are compared bit by bit left to right. The shorter ID the faster comparison, which is part of search.

[peterbourgon]

Are you claiming that evaluating 0x01000000 == 0x02000000 is faster than evaluating 0x00000001 == 0x00000002?

[sergeyprokhorenko]

It can be faster

[kyzer-davis]

Deal! Awesome. I will draft a change proposal to the current text later.

@LiosK I look forward to reviewing this one. Please use the text of #85 as the base for any update and I will review for inclusion in that PR.

[LiosK]

@kyzer-davis, I would propose the following change to "Fixed-Length Dedicated Counter Seeding" section. This proposes to initialize an n-bit counter at n-bit random numbers by default and at (n - 1)-bit random numbers (instead of zero) in the high work load scenarios where many IDs are generated per millisecond and/or the counter rollover should be avoided.

---

Implementations utilizing fixed-length counter method MAYSHOULD randomly initialize the counter with each new timestamp tick.

...

Implementations utilizing fixed-length counter method MAY also choose to initialize the counter at zero to ensure the full bit-space is utilizedsmaller-bit random numbers than the counter length (e.g. initialize a 24-bit counter at 23-bit random numbers) to ensure a certain number of possible increments is guaranteed and help avoid counter rollovers. This approach has less entropy and more guessibility but ensures the most of the counter bit spacetypically claims 1-bit entropy but in effect ensures no counter rollover occurs.

---

I would propose the following change to "Fixed-Length Dedicated Counter Length" because the above proposal obscures the reason why too long counters should be avoided. Also, I think now it's safe to recommend a longer counter than 24 bits because implementers will not easily choose a zero-starting counter thanks to the above proposal.

---

Care MUST be taken to select a counter bit-length that can properly handle the level of timestamp precision in use. For example, millisecond precision SHOULD require a larger counter than a timestamp with nanosecond precision. In addition, care MUST be taken to leave sufficient trailing bits for randomness to ensure adjacent UUIDs are not predictable. If the entire rand_a and rand_b fields of UUIDv7 are utilized as a single counter, the next UUID after one UUID in a given millisecond is easily predicted by adding one to the previous UUID, which is a situation that should generally be avoided. General Guidance is that the counter SHOULD be at least 12 bits and no more than a maximum of 2440 bits.

---

I'd also like to propose to omit Method 2 because Method 2 is essentially a 74-bit (v7) / 72-bit (v7E) fixed-length counter, so all the discussions about fixed-length counters apply. Plus, Method 1 isn't that different from Method 2 any longer after the above proposals because now Method 1 also resets counters at random numbers. I am also concerned that Method 2 pushes implementers to the same pitfall as that ULID Monotonic has fallen: perfectly predictable adjacent IDs like the following:

062273da-cfc3-75dd-a8ef-2ca2f3d45f71
062273da-cfc3-75dd-a8ef-2ca2f3d45f72
062273da-cfc3-75dd-a8ef-2ca2f3d45f73
062273da-cfc3-75dd-a8ef-2ca2f3d45f74

Wording might need to be reviewed and changed; English is not my primary language. Thanks.

[kyzer-davis]

@LiosK,

Thanks for the text. Note that Method 2 has already been dropped. That being said, let me see what I can do to get this into #85 then comment back here for you to review.

[kyzer-davis]

@LiosK please check out the changes in Commit

[sergeyprokhorenko]

I would make a small correction to prevent counter rollover:

General Guidance is that the counter SHOULD be at least 1216 bits and no more than a maximum of 40 bits.

I would also drop these words: and wait for the timestamp to advance which ensures monotonicity is not broken, bacause small breach of monotonicity is not so dangerous for application as breach of UUID generation.

[LiosK]

@kyzer-davis,

I like the wording you have incorporated my proposals to the updated draft. Thanks.

By "Method 2" I meant the Monotonic Random approach. Monotonic random is equivalent to a 74-bit (v7) or 72-bit (v7E) fixed-length randomly-seeded counter and contradicts with the guidance to leave room for sufficient entropy in the random portion after the counter. That's why I would propose to drop the monotonic random section and provide general guidance to limit the counter length up to 40 bits or 56 bits as per this seemingly un-hated comment. Do you have any concerns about this approach?

@sergeyprokhorenko,

I would also drop these words: and wait for the timestamp to advance which ensures monotonicity is not broken,

This is a logical and consistent approach as general guidance because implementers usually utilize counters to ensure monotonicity, isn't it? Or, I'd suggest to tweak this line to limit the scope of this general guidance like: "The general guidance is that applications that care about sortability SHOULD freeze the counter and wait for the timestamp to advance which ensures monotonicity is not broken."

[kyzer-davis]

@sergeyprokhorenko, 12 bits were chose as the lower bound due to UUIDv7's rand_a between ver and var which is the logical place for a counter in that bit layout. 16 bits in UUIDv7E makes sense but with both in the text I need to ensure I think about it from both perspectives. I could call it out but then we are splitting hairs within the text.

@LiosK I see what you mean with monotonic random + some trailing bits. Let me maul it over. I may be able to add a one-liner about how to achieve unguessibility with that approach which is again, basically Method 1. Or at least say something along the lines of "For Implementations that require unguessibility Method 1, Fixed Length Dedicated Counters, MUST be utilized."

@sergeyprokhorenko, I like @LiosK's verbiage. We really are just giving some guidance and that is specific to storability. If they don't care they can take the hit. I need that sentence to convey that point and I think adding that simple "that care about sortability" really hits the nail on the head.

[peterbourgon]

implementers usually utilize counters to ensure monotonicity, isn't it?

Using plain counters (random_segment += 1) to implement monotonicity is a naïve approach which can work in a pinch but probably shouldn't be a sanctioned recommendation. I hate to keep harping on the point but the approach taken by oklog/ulid parameterizes the collision probability vs. entropy exhaustion within the time bounds, and is AFAICT a strictly superior approach.

[kyzer-davis]

@peterbourgon, if I missed a discussion about this I apologize. That being said this is a good point, Monotonic Random does not need to necessarily be a static +1 increment. I'll work this into the text tonight and report back.

[fabiolimace]

@peterbourgon

I wouldn't say this is a superior approach. The technique used is essentially the same, that is, a succession of increments over a random number. The difference is that the increment steps are random within a range of values. The superiority of this method is only intuitive, that is, without theoretical or practical verification, therefore it is also naive.

However, in fact, this approach can make it a little difficult to predict the next value that will be generated. I'm actually thinking of including a parameter like this in a personal project that generates ULIDs. I think it's a good idea, although it's also an approach that could be considered naive.

As for including this parameterization in the specification, that will depend on a little more discussion here.

[peterbourgon]

However, in fact, this approach can make it a little difficult to predict the next value that will be generated.

Not "a little difficult" but "impossible", right? e.g.

The technique used is essentially the same, that is, a succession of increments over a random number. The difference is that the increment steps are random within a range of values.

It's categorically different to increment the random portion from a default state of 0 by a random amount each step, vs. incrementing the random portion from a default state of an arbitrary value by 1.

[kyzer-davis]

I see some folks on, I am in here making edits to the XML. My current verbiage to add at the end of "Monotonic Random (method 2)"

Furthermore, with this method the actual increment of the counter MAY be a random integer of any desired length instead of using simplistic "plus one" logic found with Fixed Length Dedicated Counters. This random increment of the counter ensures the UUIDs retain the required level of unguessability characters provided by the underlying entropy.

[fabiolimace]

Not "a little difficult" but "impossible", right?

It was an euphemism. But, yes, that's right. Thanks.

[fabiolimace]

Furthermore, with this method the actual increment of the counter MAY be a random integer of any desired length instead of using simplistic "plus one" logic found with Fixed Length Dedicated Counters. This random increment of the counter ensures the UUIDs retain the required level of unguessability characters provided by the underlying entropy.

Looks good to me. Maybe @peterbourgon can do a better review of the text, for having introduced us to the approach.

[kyzer-davis]

@fabiolimace Thanks! @peterbourgon I hit it in my latest commit. Let me know if the text looks good here: https://uuid6.github.io/uuid6-ietf-draft/#name-monotonicity-and-counters @LiosK Peter's method for unguessibility in Monotonic random is sound from my point of view so I did not add any text pointing back to fixed-length counter method. Both methods solve unguessibility in slightly different ways. @sergeyprokhorenko I added LiosK's suggestion for folks that care about sortability.

---

All, I can't say enough how much I appreciate the feedback and support while authoring this text. As a group we always think of new ways to improve what we are doing with this specification.

[LiosK]

I don't disagree to the randomly-incremented counter approach because it's another sensible approach to ensure some levels of unguessability, but I don't really like the description of the current draft that generally discourages the fixed-length counter approach and pushes implementers to the naive plus-one monotonic random approach, even though Method 1 and 2 are now essentially the same approach. I would make a few proposals to the current draft:

With this method the rand_a sectionrand_a and rand_b sections of UUIDv7 MAY be utilized as fixed-length dedicated counter bits.

This line recommends an unreasonably short counter length so should be revised or omitted.

This is similar to the Fixed-Length Dedicated Counter Bits method described in the previous bullet but does not suffer from rollover issues, length problems, or wasted entropy bits plagued by fixed-length counter bit positions.

Rollover is a common issue over Method 1 and 2 and wasted entropy bits are no longer an issue of fixed-length counters because they too are initialized randomly. This line sends a wrong message that the discussion about rollovers and seeding is not relevant to Method 2, which is not the case. Implementers must handle rollovers with Method 2 and they can also adopt the portion-counter-initialization approach for Method 2.

As such, UUIDv7 SHOULD utilize this method to handle batch UUID generation during a single timestamp tick.

Now I don't think Method 2 is a clearly superior approach to Method 1 (because they are essentially the same).

Furthermore, with this method the actual increment of the counter MAYSHOULD be a random integer of any desired length instead of using simplistic "plus one" logic found with Fixed Length Dedicated Counters.

The randomly-incremented approach should be considered default if the whole 74 bits are dedicated to a counter because the plus-one approach damages to unguessability for no reason.

However, when the timestamp has not incremented; the counter SHOULD be frozen and incremented by one or by a random integer larger than zero. When utilizing a randomly seeded counter alongside Method 1; the The random MAY be regenerated with each counter increment without impacting sortability.

The randomly-incremented counter approach is applicable to any types of counters. So is the regeneration.

Care MUST be taken to select a counter bit-length that can properly handle the level of timestamp precision in use. For example, millisecond precision SHOULD require a larger counter than a timestamp with nanosecond precision. General Guidance is that the counter SHOULD be at least 12 bits but can be longer. Care SHOULD also be given to ensure that the counter length selected leaves room for sufficient entropy in the random portion of the UUID after the counter. This entropy helps improve the unguessability characteristics of UUIDs created within the batch. General guidance is that the counter SHOULD be at least 12 bits and at most 40 bits.

I'd provide a clearer guidance here for unguessability.

[peterbourgon]

Unless I misunderstand something, Method 1 produces guessable IDs, Method 2 doesn't.

[LiosK]

Method 1 proposes to utilize say 40 bits as a randomly initialized counter and leave the remaining 32 bits for entire randomness renewed every time. It's not guessable, is it?

[fabiolimace]

Furthermore, with this method the actual increment of the counter MAY be a random integer

I also think MAY can be replaced by SHOULD. The "plus one" is a special case of "plus one a random number in a range", but it is obviously no longer random.

[kyzer-davis]

@LiosK and @fabiolimace

Good feedback. I ran out of time today but I may have some cycles tomorrow to revise the section based on these changes. Hang tight for an updated set of text we can re-review.

[sergeyprokhorenko]

implementers usually utilize counters to ensure monotonicity, isn't it?

Using plain counters (random_segment += 1) to implement monotonicity is a naïve approach which can work in a pinch but probably shouldn't be a sanctioned recommendation. I hate to keep harping on the point but the approach taken by oklog/ulid parameterizes the collision probability vs. entropy exhaustion within the time bounds, and is AFAICT a strictly superior approach.

This, excuse me, is nonsense that everyone picked up despite LiosK's reasonable but weak objections. It would be shame to see it in such a thoughtful specification. A random increment quickly and unnecessarily depletes the capacity of the counter.

This is justified in oklog/ulid only because the WHOLE random segment is a frozen counter there. However, in the specification we are discussing, only the LEFT SIDE of the random is a counter, while the right side is truly random and changes for each UUID. This provides an excellent level of unguessability.

[sergeyprokhorenko]

@sergeyprokhorenko I added LiosK's suggestion for folks that care about sortability.

@kyzer-davis You should also add a suggestion for folks that care about continuity in generating UUIDs. It would be fair.

[LiosK]

I'd provide a couple of view points about recent updates. I don't expect these to be incorporated into the RFC but they will be helpful to make my points clear.

Plus-one approach vs. random increment approach

I don't necessarily disagree to the random increment approach because I did choose that a decade ago, but I'd point out that the random increment approach is not always superior to the plus-one approach. It's hard to analyze the statistical characteristics of the random increment approach, but based on the previous discussion and this Zendesk article, the random increment approach is likely to have weaker collision resistance than the plus-one approach if we measure collision resistance by the probability of at least one collision. Unguessability obtained by the random increment approach is not a free gift but comes at the sacrifice of collision resistance in the distributed use cases.

That being said, given the 74-bit counter/entropy space, it should be reasonable to spare, say, 32 bits for unguessability. The 74-bit counter with 32-bit random increment still provides stronger "collision resistance" (as defined above) than the entire 74-bit randomness. This is just a matter of finding a right balance, and the 32-bit random increment is likely a right balance.

42-bit fixed-length randomly seeded plus-one counter + trailing 32 bit random vs. 74-bit monotonic random + 32-bit random increment

Again, it's hard to analyze the statistical characteristics of the random increment approach, but the above two sets of techniques come out very similar bits; the leading 41 bits are relatively constant and the trailing 33 bits are almost random. So I assume they have similar characteristics in terms of collision resistance and unguessability. That's why I argued the fixed-length approach should be treated at least as prominent as the monotonic random in the draft RFC.

That said, IMO the 74-bit monotonic random + 32-bit random increment approach is worse than the fixed-length approach because of the following two reasons:

• The monotonic random approach requires 74-bit arithmetics, which need BitInt math and software emulation in the vast majority of languages and hardware, respectively. The 42-bit counter fits in uint64, int64, and the safe int range of double.
• It's more complex with the random increment approach to estimate the average number of IDs that can be covered by a given counter bit-length. Also, with the plus-one approach it's very easy to calculate the guaranteed number of IDs with the (n - 1)-bit random initialization technique, which is not the case at all with the random increment approach.

I usually ignore complexity because library authors are generally supposed to be professionals who make things done; however, I don't see any strong technical superiority of the 74-bit monotonic random + 32-bit random increment approach that justifies the above complexity.

Anyway, I don't necessarily disagree to the monotonic random + random increment approach because at least it is not unsafe. But this approach should never be introduced more prominently in the new RFC than the fixed-length + trailing random approach.

Priority of unguessability

I've been emphasizing unguessability, but I'd be clear that unguessability is not the priority of UUIDv7. We can't definitely say "XX-bit random provides sufficient unguessability" or something. Even 32 bits are not likely enough if an application is exposed to off-line attacks. Again, it's a matter of right balance. A 74-bit counter space is an overkill for most of applications, and thus I would recommend to spare some bits for unguessability by default so implementers do not expose a potential attack surface for no reason.

Conclusion

Implementers usually face many matters of finding right balances, so it's great if we can agree on and provide a sensible set of default parameters. But if we can't, I would like the new RFC to put guardrails around unsafe choices and extreme approaches to prevent implementers from falling in common pitfalls.

[kyzer-davis]

@LiosK Great writeup.

I would like the new RFC to put guardrails around unsafe choices and extreme approaches to prevent implementers from falling in common pitfalls.

This statement hits the nail on the head for the best practices section. I am working on the counter changes. Another update to come.

[kyzer-davis]

@LiosK, I merged the changes which are live now via https://uuid6.github.io/uuid6-ietf-draft/#name-monotonicity-and-counters

The text should now describe:

• Counter Method 1, Increment Type A
• Counter Method 1, Increment Type B
• Counter Method 2, Increment Type A
• Counter Method 2, Increment Type B

I removed the harsh verbiage against fixed-length counters. Both methods solve the problems. The bits being tallied are just in two different positions within the UUID layout. We are describing the solutions and their possible upsides/downfalls/challenges. Implementations pick the one that seems correct for them.

I also made the changes to the fixed-length seeding, length, rollover parts as per your comment https://github.com/uuid6/uuid6-ietf-draft/issues/60#issuecomment-1069723584

Lastly, I abstracted the "when to increment" sub-section to point to Counter Methods and Increment Types.

---

@sergeyprokhorenko, the text reads:

applications that care about absolute monotonicity and sortability SHOULD freeze the counter

This should be sufficient to cover the topic.

---

Edit: Personal note, I have always been a proponent of the fixed-length counter method. Drafts 01 and 02 never had monotonic random because of this personal bias. Any harsh verbiage against fixed-length counters in the previous stages of Draft 03 was not intended.

As we have iterated via this thread, both methods have proven sufficient at solving this problem. As a result in this latest revision both should be presented as equal solutions. If this is not the case please suggest an edit.

[sergeyprokhorenko]

As we have iterated via this thread, both methods have proven sufficient at solving this problem. As a result in this latest revision both should be presented as equal solutions. If this is not the case please suggest an edit.

@kyzer-davis, Now the text of section Monotonicity and Counters is confusing. It mixes the new and the outdated, the great and the bad. There is no need to list all possible options if some of them are obviously bad. It is better to use Occam's razor.

I'm convinced that both methods 1 and 2 should be dropped in favor of paragraph Fixed-Length Dedicated Counter Seeding. Both methods 1 and 2 are now obsolete thanks to LiosK's great idea.

We also need to drop Random Increment (Type B) in favor of Plus One Increment (Type A). See rationale from LiosK: https://github.com/uuid6/uuid6-ietf-draft/issues/60#issuecomment-1071898578 and from me: https://github.com/uuid6/uuid6-ietf-draft/issues/60#issuecomment-1071461232

[LiosK]

The new draft looks good! Thank you, @kyzer-davis. If I might add something, Counter Rollover Handling is also relevant to the monotonic random approach particularly when it's combined with the random increment strategy, and thus it should be placed under "The following sub-topics cover methods behind incrementing either type of counter method:".

[kyzer-davis]

@LiosK, good callout. I split into two sections for rollover handling and rollover guarding in the latest PR.

[edo1]

There is no need to list all possible options if some of them are obviously bad. It is better to use Occam's razor.

Completely agree.

@kyzer-davis, IMO current standard version is too loose, it is unclear and confusing. You seem to be assuming that each application uses its own customized UUID generator. In the real world, almost all applications use a generic implementation from some library, this implementation should "fit all".

1. Any reason to keep methods 1 and 2, types A and B?
2. Why is the recommended counter size not specified?
3. Why not use SHOULD here? Implementations utilizing fixed-length counter method MAY also choose to randomly initialize a portion counter rather than the entire counter. For example, a 24 bit counter could have the 23 bits in least-significant, right-most, position randomly initialized. SHOULD allows other implementations to be considered RFC-compliant, but makes it clear which approach is recommended.
4. Why not use SHOULD here? Implementations MAY use the following logic to ensure UUIDs featuring embedded counters are monotonic in nature: Compare the current timestamp against the previously stored timestamp. If the current timestamp is equal to the previous timestamp; increment the counter according to the desired method and type. If the current timestamp is greater than the previous timestamp; re-initialize the desired counter method to the new timestamp and generate new random bytes (if the bytes were frozen or being used as the seed for a monotonic counter).
5. The recommended approach to handle clock drift is not specified. Implementations SHOULD check if the the currently generated UUID is greater than the previously generated UUID. If this is not the case then any number of things could have occurred. Such as, but not limited to, clock rollbacks, leap second handling or counter rollovers My proposal was to reuse the last timestamp+counter if the jump is small enough (less than ≈2.5s), it will handle leap second and/or small clock drift due to NTP, VM migration, and so on.
6. The recommended approach to handle counter overflow is not specified. My proposal was to increment the timestamp (it shouldn't hurt because the suggested timestamp resolution was 100ns). ULID approach is to fail.

[LiosK]

3. Why not use SHOULD here? Implementations utilizing fixed-length counter method MAY also choose to randomly initialize a portion counter rather than the entire counter. For example, a 24 bit counter could have the 23 bits in least-significant, right-most, position randomly initialized. SHOULD allows other implementations to be considered RFC-compliant, but makes it clear which approach is recommended.

IMO MAY is fine here. With a 24-bit counter, on average 8 million IDs can be generated per millisecond and with a 99.9% chance at least 10,000 IDs can be generated. BTW, I am an advocate of 42-bit counters and in this case 2.2 trillion on average and with a 99.999999% chance at least 10,000 can be generated. These numbers are more than enough for most applications and only few extremely high-load applications and those that prefer short counters are adversely affected by the initialize-full-counter approach. On the other hand, if the spec recommends the initialize-portion-counter approach, the generic libraries might force every application to pay one bit entropy for the overflow guard not really relevant to most applications.

The initialize-portion-counter approach definitely solves some problems but is not a clearly superior approach that should be recommended to everyone.

5. The recommended approach to handle clock drift is not specified.
6. The recommended approach to handle counter overflow is not specified.

Your approaches are actually very interesting and creative if combined together. The timestamp state is simply incremented at a counter overflow and such an advanced timestamp state is accepted so long as the difference from the real clock is small enough. The generator will stall, reset state, or raise error only when the real clock is rewound so much or when the generator is "overheated" (i.e. when it experiences too many counter overflows). Very interesting! I would try this in my prototype. I'm not sure if many people think this approach is "right", but I'm kind of sure this works well in common scenarios.

[edo1]

On the other hand, if the spec recommends the initialize-portion-counter approach, the generic libraries might force every application to pay one bit entropy for the overflow guard not really relevant to most applications.

So you're advocating not using "N-1 rollover protection" as the default approach?

[LiosK]

N-1 approach shouldn't be default. Overflow protection isn't worth one bit entropy for most applications. Plus, counter overflow isn't a serious disaster if handled properly e.g. by your smart handling technique.

[edo1]

Plus, counter overflow isn't a serious disaster if handled properly e.g. by your smart handling technique.

I agree.

One note: in my proposal, the timestamp resolution was 100ns, which is overkill in most cases. So timestamp incrementing shouldn't hurt. I have some doubts about incrementing the timestamp with 1ms resolution

[LiosK]

1 ms is likely overkill in a scenario where distributed nodes use their own clocks, while even 100 ns increment can be problematic if a clock is shared by distributed nodes. I'm now trying to figure out in what conditions the timestamp increment can hurt and in what conditions not.

Anyway, using the timestamp field as a reserve counter is an eye opening but counterintuitive idea that not many implementers will come up with. I think it's worth discussing this here and in the RFC.

[kyzer-davis]

@edo1, great feedback on the section.

On the topics:

1. This section of document is written for any implementers (custom or those writing a library). But you are right, many will likely use a library and somebody has already made these decisions for them. However, the goal from Brad and I is to detail how to solve the problems so that the implementer of said library can make their choices based on our research here.
   1. Counter Methods 1 and 2 both solve the batch UUID creation problem when timestamp has not incremented. Each with some pro/cons that I want to clearly define.
   2. Increment Types A and Type B both provide some other pro/cons.
   3. There are many advocates for each; removing one will likely cause negative feedback from one group I am sure.
2. We have a counter range specified. Different languages have different speeds and may produce more/less than others. They can test and choose a length that fits them.
3. SHOULD vs MAY is always tricky. I believe somebody asked me to change this to SHOULD or vice versa. Maybe it was @fabiolimace?
4. Same as previous bullet.
5. I like this approach. I can add it to Counter Rollover Handling. Could you open a new Change Proposal issue for me to track?
6. Again, N-1 works, increasing timestamp as rollover guard works. They both solve the problem. Neither are wrong. Similar to Method 1/2 and Increment Type A/B. I can describe this rollover guard along with N-1 in Counter Rollover Handling section and let an implementation choose. To differentiate them from Counter Method and Increment Type I can define these as Rollover Guard Option i and ii. Same as previous. If you could open a Change Proposal I can get this into Draft 04.

---

Plus, remember, everything in this section also pertains to UUIDv8 where somebody may want to do it their own way. Rather than spend a ton of cycles on R&D; we have already vetted most problems/solutions and documented the pros/cons. They can implement what they need and be on their way.

---

Edit: Saw your other comment on timestamp length thread: I agree, implementers will likely not expose every single knob from the best practices section. They will likely have UUIDv7 libraries will likely have the minimum required parts:

• Timestamp
• Entropy
• This is is the fastest as you said (uuid_generate_v7_fast())

And MAY layer in a counter of parts:

• Counter Method
• Increment Type
• Rollover Guard Option
• of which will make things slower but improve collision resistance i.e uuid_generate_v7()

The folks using those libraries will take what they get and not need to think about all the other "best practices" defined in that section.

[sergeyprokhorenko]

N-1 approach shouldn't be default. Overflow protection isn't worth one bit entropy for most applications. Plus, counter overflow isn't a serious disaster if handled properly e.g. by your smart handling technique.

I agree to trade the N-1 approach for a timestamp increment. Complex problems require complex but ultimate tools. It's not a choice between green and purple UUIDs with an A/B test among Instagrammers

[sergeyprokhorenko]

6. Again, N-1 works, increasing timestamp as rollover guard works. They both solve the problem. Neither are wrong. Similar to Method 1/2 and Increment Type A/B. I can describe this rollover guard along with N-1 in Counter Rollover Handling section and let an implementation choose. To differentiate them from Counter Method and Increment Type I can define these as Rollover Guard Option i and ii. Same as previous. If you could open a Change Proposal I can get this into Draft 04.

It would be clearer if all options had short names instead of numbers, letters and counting sticks.

It seems to me that the merits and demerits of the options are less described in the RFC than in the GitHub issues. Therefore, the implementers will turn into Buridan donkeys. The RFC should indicate the preferred option, of course with justification. It seems to me that in the course of the discussion, the positions of the participants here quickly converge. Therefore, it should not be a problem to choose the preferred option. If something causes controversy, then it has not yet been sufficiently thought out.

It would be desirable to show an exact and unambiguous reference layout of UUID for example, for a marketplace or an international bank.

[fabiolimace]

SHOULD vs MAY is always tricky. I believe somebody asked me to change this to SHOULD or vice versa. Maybe it was @fabiolimace?

@kyzer-davis , I just wanted to suggest this change below as the Plus One increment type is a special case of Plus N (random increment).

With this increment the actual increment of the counter MAY SHOULD be a random integer of any desired length larger than zero. ...

I gave up on the idea of creating a Change Proposal issue because the deadline for submitting the draft was running out. We all want to see our collective effort specification published as a standard as soon as possible.

However, it is important that we correct small problems as they are discovered. So I want to take the opportunity to suggest further changes. Forgive me for saying this just now. I was looking forward to the submission of the new draft.

---

I really liked the two counter methods and the two increment types. The combinations produced by them seemed to resolve all the differences of opinion that there were. I mean if an implementer wanted to use method 1 with type 2 they would be free to do so with full approval of the specification.

However, while implementing a GitHub Gist to test the four combinations of counter methods and increment types, I realized that maybe it's not necessary to have 4 combinations. I'll explain.

1. The Method 1 and Type A combination seems to be accepted by many of us, although there are small details that are not unanimous, such as the rollover guard bit.

2. The Method 1 and Type B combination does not seem to be of much practical use, as it greatly reduces the increment space and increases the risk of rollover. Furthermore, it is identical to the Method 2 and Type B combination if we put the two side by side.

3. The Method 2 and Type A combination seems to be preferred by those who like the monotonic ULID. This combination has the problem of being easy to guess the next value, but it has the advantage of generating UUIDs at a very high speed, for applications that need it.

4. The Method 2 and Type B combination seems to be preferred by people who don't like the Method 1 and Type A combination. In practice both combinations have the same effect. So the preference of one or the other will depend on the ease of implementing in a given programming language.

So I would like to propose that there are only 2 combinations: Method 1 with Type A and Method 2 with Type B. With that I hope to remove the cons and just keep the pros. Of course you are all free to disagree.

The changes I want to propose in the text are the ones below. I just copy-pasted and changed some modal verbs.

Fixed-Length Dedicated Counter Bits (Method 1):

This references the practice of allocating a specific number of bits in the UUID layout to the sole purpose of tallying the total number of UUIDs created during a given UUID timestamp tick. Positioning of a fixed bit-length counter SHOULD be immediatly after the embedded timestamp. This promotes sortability and allows random data generation for each counter increment. With this method rand_a section of UUIDv7 MAY SHOULD be utilized as fixed-length dedicated counter bits. In the event more counter bits are required the most significant, left-most, bits of rand_b MAY be leveraged as additional counter bits.

With this increment logic the counter method is incremented by one for every UUID generation. When this increment method is utilized with Fixed-Length Dedicated Counter the trailing random generated for each new UUID can help produce unguessable UUIDs. (Copy-pasted from Type A)

Monotonic Random (Method 2):

With this method the random data is extended to also double as a counter. This monotonic random can be thought of as a "randomly seeded counter" which MUST be incremented in the least significant position for each UUID created on a given timestamp tick. UUIDv7's rand_b section SHOULD be utilized with this method to handle batch UUID generation during a single timestamp tick.

With this increment the actual increment of the counter MAY SHOULD be a random integer of any desired length larger than zero. When this increment method is utilized with Monotonic Random Counters the counter ensures the UUIDs retain the required level of unguessability characters provided by the underlying entropy. (Copy-pasted from Type B)

The increment of the countar MAY be 1. However when this increment method is utilized with Monotonic Random the resulting values are easily guessable. Implementations that favor unguessiblity SHOULD NOT utilize this method with the monotonic random method. (Copy-pasted and adapted from Type A)

[LiosK]

I'd rather suggest to subsume the monotonic random under the fixed-length counter because the monotonic random is just a 74-bit variation of fixed-length counters, but I don't have a strong opinion here as long as unsafe choices are properly quarantined.

it has the advantage of generating UUIDs at a very high speed

It's a very good point. I've been observing that UUIDv7 with counter is much faster than that without counter because even the blazing fast arc4random implementations are still much slower than incrementing a counter.

[edo1]

I've been observing that UUIDv7 with counter is much faster than that without counter because even the blazing fast arc4random implementations are still much slower than incrementing a counter.

I guess it will exactly the opposite in real life. Version with counter needs mutex or another lock.

[fabiolimace]

I'd rather suggest to subsume the monotonic random under the fixed-length counter because the monotonic random is just a 74-bit variation of fixed-length counters

Yes, monotonic random can be thought of as a 74-bit variation of fixed-length counters. I just thought "hey, maybe we can reduce the cognitive load if we omit the fixed-length counter that increments by a random number" (Method 1 with Type B). I don't have a strong opinion either.

I guess it will exactly the opposite in real life. Version with counter needs mutex or another lock.

I think it might be true if the pseudo-random generator is not cryptographically secure. I just tested this hypothesis in a project of mine using Random() (fast generator) instead of SecureRandom() (secure generator). But the benchmarks did not confirm this. Monotonic ULIDs were always faster than non-monotonic ULIDs, even using a fast non-cryptographically secure generator. Maybe it's due to my implementation, but I'm not sure.