Multiple ULIDs per millisecond not guaranteed

[dragondave]

If, in the extremely unlikely event that, you manage to generate more than 2^80 ULIDs within the same millisecond, or cause the random component to overflow with less, the generation will fail.

Given the width of the random space is 80 bits, the latter is guaranteed to happen first (or at the same time).

There is also no guarantee that the number randomly generated is not very close to 2^80 -- should implementations consider a maximum number they will accept from the random number generator, and that they will change random numbers greater than to? (Or choose a number lower than)?

[alex-ilin]

I don't mean to hijack this thread, but I have a related question that needs clarification before the @dragondave's question can be answered, so I decided against creating a separate issue. The Sorting section says that "Within the same millisecond, sort order is not guaranteed", and then the Monotonicity section tries to establish exactly that guarantee (implementation is supposed to throw exception in exactly the same case when the sort order within a millisecond is threatened by overflow). Which is correct? Is either of those sections to be considered optional? I'm confused.

If throwing exception on overflow is optional, then multiple ULIDs per millisecond are not an issue (within 2^80, of course). If throwing is mandatory, then the Sorting section is wrong, and @dragondave's question needs to be answered.

Technically, it's possible to generate 79 bits of entropy and still have plenty of space for incremented values without performance loss.

[lxcid]

nanoid have a great website to help figuring out the collision for layman like me.

https://zelark.github.io/nano-id-cc/

So I was calculating the 16 characters random component collision chances (1% probability of collision) when generating 1,000,000 id/milliseconds is about ~3 mins or about ~180,000 ms…

Because its scoped by millisecond, that I believe chance is way lower… or if I am not calculating incorrectly, we'll have to generate about:

~180,000,000,000 id/milliseconds to hit 1% probability of collision.

I guess that make the uuid claim holds. 👍

[lxcid]

@alexiljin monotonicity is stateful per function created by the factory function, I would avoid reusing it on concurrency scenario.

You should generated one function per thread/concurrency unit.

https://github.com/ulid/javascript/blob/f45529c95994019125cdd5a497ab792e00ef57f2/lib/index.ts#L160-L178

Otherwise it should be fine.

[alex-ilin]

@lxcid, I asked whether the Sorting or the Monotonicity section's claim was optional. I read your answer to mean that the Monotonicity is optional: if we have concurrency, there is no monotonicity anyway. So, basically, in the general case, sorting order within a millisecond is not guaranteed.

It seems to me, that after establishing that there is no sorting guarantee, it's a little too much trouble to detect the same-millisecond condition, which means storing the extra state between invocations of the ULID generator, and then implementing the increment with overflow on an 80-bit value, and add a new exception type for the client code to worry about, etc. The spec would be much cleaner if it stopped at saying there is no sorting guarantee between milliseconds, period. The Monotonicity sections seems more like documentation of a specific implementation, not a general spec, especially since it says "we can provide some guarantees...", which is not clear whether it should be followed by a conforming implementation, or optional.

I noticed that a lot of listed implementations don't throw the monotonicity exceptions, or even try to detect them, which prompted me to ask this question. It seems that the spec is unclear in this regard. If that's an optional feature, it should be clearly marked as such.

Shall I offer a PR?

[lxcid]

Ahh I see, I agree with your observation. The monotonicity in millisecond behaviour does introduce a bit of statefulness and extra cases to worry about and in a distributed environment (multi node/machine; horizontal scaling), that guarantee would be broken.

There might be cases where that extra guarantee for millisecond is useful but I view it as more of an edge cases. Would have been cleaner to keep this part optional as it come with a few caveats.

[RobThree]

We're having some discussion over at the .Net implementation as well (I noticed more discussion elsewhere). Quite honestly I think this monotonicity isn't well thought out and I vote for it to be removed from the spec. Arguments for why I vote for removal can be found here but I'll sum up what I've come across in different places by different people:

• Monotonicity can cause problems in multithreading environments (though that could be solved with some locking / lock-free algorithms, it adds complexity)
• The behaviour is undefined on what happens on an 'overflow' when lots of ULID's are generated in the same millisecond and the initial random-part is very high causing the overflow eventually Okay, my bad, the defined behaviour is that it should throw; but then each millisecond there's a different (potential!) number of ULID's you can (theoretically) produce, entirely based on chance because the start is random
• It causes confusion on the sort order; without monotonocity the sort order is random within the same millisecond, when monotonicity is used then suddenly the sort order is defined for the entire ulid and the 'random part' isn't so 'random' anymore (one side effect is that you can gauge from looking at ID's how many of them were generated approximately in that millisecond; that may be an undesirable property; at the very least the random-part should be much more carefully documented as being 'not-so-random' when monotonicity is used)
• It adds little to no value in my humble opinion, especially for the added complexity it adds to implement (incrementing 80-bit integers isn't exactly simple in all languages (and usually also not without drastic costs in performance!) and then we're not even talking keeping state etc.)
• As it's currently standing there seem to be differences in opinions on the exact implementation (if at all) which could cause problems between implementations across the board / incompatibilities. I think before it's too late we need to 'nip this in the bud'. (Maybe someone can map out which implementation does/did what with monotonicity (if at all implemented)?).

I'd love to hear your thoughts.

[dragondave]

My understanding from a code review of the ulid/javascript version (which I'm taking as a reference implementation):

• The default ULID factory does not support monotonicity
• The optional monotonicFactory does, with a few quirks:
  • Generating a ULID with an earlier timestamp generates one for the current millisecond, as if it arrived right now, which is a surprise [see section of ulid/javascript docs, below]
  • Generating a ULID with a later timestamp does change the random seed

From a very cursory code review:
Python:
mdipierro/ulid -- no monotonic behaviour observed in main file
ahawker/ulid -- no monotonic behaviour observed in main file
mdomke/python-ulid -- no monotonic behaviour observed in main file

Powershell:
PetterBomban/posh-ulid -- no monotonic behaviour observed in main file

Ruby:
rafaelsales/ulid -- no monotonic behaviour observed in main file

Go:
oklog/ulid -- not spec compliant but an interesting stab at fixing the problem of being able to trivially guess other ULIDs in the same timestamp. Not enabled by default.

// Monotonic returns an entropy source that is guaranteed to yield
// strictly increasing entropy bytes for the same ULID timestamp.
// On conflicts, the previous ULID entropy is incremented with a
// random number between 1 and inc (inclusive).
//
// The provided entropy source must actually yield random bytes or else
// monotonic reads are not guaranteed to terminate, since there isn't
// enough randomness to compute an increment number.
//
// When inc == 0, it'll be set to a secure default of math.MaxUint32.
// The lower the value of inc, the easier the next ULID within the
// same millisecond is to guess. If your code depends on ULIDs having
// secure entropy bytes, then don't go under this default unless you know
// what you're doing.

JS:
aarondcohen/id128 -- monotonic behaviour in separate file [ulid-monotonic] -- same rules as reference.

From reference notes:

const ulid = monotonicFactory()

// Strict ordering for the same timestamp, by incrementing the least-significant random bit by 1
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRB
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRC

// Even if a lower timestamp is passed (or generated), it will preserve sort order
ulid(100000) // 000XAL6S41ACTAV9WEVGEMMVRD 

[andrzejmartyna]

BTW. I've found a very nice article about history of unique identifiers:
https://segment.com/blog/a-brief-history-of-the-uuid/
I was surprised how rich the history is so we can for sure learn from it ;)

[itdaniher]

I actually added monotonicity to Python's ULID2 recently - https://github.com/valohai/ulid2/pull/8/files

Ran into some of the issues called out here, but found it to be worthwhile.

[sergeyprokhorenko]

We're having some discussion over at the .Net implementation as well (I noticed more discussion elsewhere). Quite honestly I think this monotonicity isn't well thought out and I vote for it to be removed from the spec. Arguments for why I vote for removal can be found here but I'll sum up what I've come across in different places by different people:

• Monotonicity can cause problems in multithreading environments (though that could be solved with some locking / lock-free algorithms, it adds complexity)
• The behaviour is undefined on what happens on an 'overflow' when lots of ULID's are generated in the same millisecond and the initial random-part is very high causing the overflow eventually Okay, my bad, the defined behaviour is that it should throw; but then each millisecond there's a different (potential!) number of ULID's you can (theoretically) produce, entirely based on chance because the start is random
• It causes confusion on the sort order; without monotonocity the sort order is random within the same millisecond, when monotonicity is used then suddenly the sort order is defined for the entire ulid and the 'random part' isn't so 'random' anymore (one side effect is that you can gauge from looking at ID's how many of them were generated approximately in that millisecond; that may be an undesirable property; at the very least the random-part should be much more carefully documented as being 'not-so-random' when monotonicity is used)
• It adds little to no value in my humble opinion, especially for the added complexity it adds to implement (incrementing 80-bit integers isn't exactly simple in all languages (and usually also not without drastic costs in performance!) and then we're not even talking keeping state etc.)
• As it's currently standing there seem to be differences in opinions on the exact implementation (if at all) which could cause problems between implementations across the board / incompatibilities. I think before it's too late we need to 'nip this in the bud'. (Maybe someone can map out which implementation does/did what with monotonicity (if at all implemented)?).

I'd love to hear your thoughts.

RobThree,

I believe that monotonic ULIDs are necessary to reduce and guarantee the minimum search time in highload systems that use ULIDs as primary keys of tables. So we need monotonicity within a database (not in multithreading environments).

My suggestion is here: ahawker/ulid#306 (comment)

[RobThree]

I don't understand; you still have a random part in your suggestion?

I also don't see why highload systems would have any problems with a ULID as-is? I don't see what specific problem it solves?

[sergeyprokhorenko]

RobThree,

I don't understand; you still have a random part in your suggestion?

Yes, there is a true random part in my suggestion. It provides global key uniqueness. It's necessary for:

1. merging of records from different databases
2. generating records on the client
3. key collision avoidance during replication
4. key collision avoidance in distributed database
5. key collision avoidance in multithreading software
6. links between records in different databases
7. accurate search by ULID and queries on the Internet
8. inability to predict the key by the attacker
9. polymorphic associations between any database tables
10. ability to find a record by ID without knowing the table

I also don't see why highload systems would have any problems with a ULID as-is? I don't see what specific problem it solves?

Lack of strict monotonicity cause unpredictable search time and performance issues in databases:

1. we have to periodically recluster every table according to its primary index (i.e. ULID) (see SQL Command CLUSTER in PostgreSQL)
2. if for a long time there was no reclustering than search time for some records may be very long

[RobThree]

Yes, there is a true random part in my suggestion. It provides global key uniqueness. It's necessary for

I understand perfectly well what the random part is for, but exactly because of having a random part you won't be able to make any guarantees which you were talking about and what is was referring to 😉 You see, as soon as a random component is involved it will be very hard to make guarantees. You will be able to make some very likely assumptions and predictions (especially when the RNG produces very well distributed values) but guarantees are... well, at the very least a risky part of the equation by then.

Also, as I said, depending on the load (assuming it's quite constant/even) you will be able to make pretty accurate predictions if the random part is evenly distributed. Only when you have very short, specific, spikes in the load where one ms you're generating thousands or more ULID's and the other ms there's little to none there could be some unpredictability in some systems (I can imagine some TSDB's don't like that); and then it will not be due to the random part but because of the 'spiking'-part.

Lack of strict monotonicity cause unpredictable search time and performance issues in databases

See, you're again on the "unpredictable search time".

Either way; I disagree. The search time will be very predictible, even with a standard ULID as-is without monotonicity. The search time will be largely, if not almost(!) entirely, dependent on the timestamp part. Only a very small part of the search space will be left for the random part and most of that will likely have been stored in the same (consecutive) page(s) of the database. If used as a primary key and the index is clustered the inserts will be a tiny bit more 'expensive' but then the end result is that the ULID's will be in order physically anyway after inserting.

To simply illustrate: Let's assume you generate 1.000.000.000 ULID's p/hour. That means you generate 277.777 ULID's per second and 277 ULID's per ms. You'll have 3.600.000 ordered 'buckets' of random ULID's, each containing only 277 randomly ordered ULID's (if not stored in a clustered manner anyway). So the searchspace is then only 277 ULID's out of a billion. That's 0,0000277%. You can increase the numbers by a factor 100 or a billion, the net result is still that each bucket will contain the same percentage of randomly ordered ULID's (again, assuming an even load during the entire hour and assuming the ULID's aren't stored in order (worst case). I think it's safe to assume the ULID's will be generated 'out of order' but stored in-order).

Unless you have a system that generates loads of ULID's in the same millisecond and then does nothing "for the rest of the day" (so you only have "spikes" in your load in over a few ms once or a few times a day) the ULIDS will be largely sorted anyway because of the timestamp. And so the random part isn't as important (in most cases maybe even negligible, depending how the database is set up, which (if any) key clustering is used etc).

And even if it turns out to be a problem in, say, PostgreSQL (or any other RDBMS or any system for that matter) but other systems are fine then isn't it just that? A problem for PostgreSQL (or whatever system)? Is it up to the ULID to account for all possible problems any random system in the world could have with a ULID and try to find a solution for it? Or would it be better, if a ULID doesn't work in a specific scenario, to advise to simply pick any other available ULID alternative that's better suited for the task/system at hand instead of trying to fit a square peg in a round hole and modify the ULID spec to accommodate for that very specific scenario and create a ULIDv1.1 introducing monotonicity and other confusion (and complexity)?

(see SQL Command CLUSTER in PostgreSQL)

Sorry, my Russian sucks 😜 I'll take a look at https://postgrespro.com/docs/postgresql/11/sql-cluster