This reminds me a little bit of Twitter's snowflake: To generate the roughly-sorted 64 bit ids in an uncoordinated manner, we settled on a composition of: timestamp, worker number and sequence number.<p>Sequence numbers are per-thread and worker numbers are chosen at startup via zookeeper (though that’s overridable via a config file).<p><a href="https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake" rel="nofollow">https://blog.twitter.com/engineering/en_us/a/2010/announcing...</a>
Or just use the standards-track orderable UUID variants: <a href="https://uuid6.github.io/uuid6-ietf-draft/" rel="nofollow">https://uuid6.github.io/uuid6-ietf-draft/</a>
> If more than one ULID is generated within the same millisecond(so, the timestamp component is the same), the algorithm should increment the previously generated random by 1 bit.<p>This is bad approach. If you know one ULID, you can with high probability deduce next one. Don't use this approach.<p>Why with high probability? Because generating several ids within the same millisecond is extremely common case when you're doing batching.<p>I recently gave thought to it and actually implemented several algorithms and compared them each to each other. I don't care about standards, sorry (I think that standard UUID is oxymoron, UUID is 128 bit and that's about it).<p>So the best approach I've found is:<p>6 bits for version/variant (if you don't care about standards you can use those bits for better randomness)<p>first 48 bits is unix milliseconds.<p>Then you have 12 more bits in the fist 64 bits. There're two approaches to use them:<p>either use them as a nanoseconds (nanoseconds_part * 4096 / 1_000_000).<p>Or use them as a counter if several ids are generated in the same millisecond. It allows for 4096 values per millisecond. Counter should be used when you can't access nanosecond timer like with browser JavaScript.<p>Then you have 2-3 bits for variant and rest 62-61 bits for pure randomness. Or just 64 bits for randomness. This is enough for security.<p>If you need to generate more than one ID per 1/4 of microsecond (approach one) or more than 4096 ids per millisecond (approach two), you can just keep generating random part until it's greater than previously generated one. It slightly reduces randomness but not by much.<p>I'm pretty much sure that my approach is the best approach. It allows for high speed of generation (like 10 000 000 / second with nanosecond approach with unoptimized Java) and good security.<p>If you insist on using this ULID approach, I suggest to apply the aforementioned approach: don't just increment random bits, generate random bits until you've got higher value.<p>Of course one should only use this ascending UUID thing (that's what I call it) when you need it. Random UUIDs should be used by default and ascending UUIDs only when you use those as primary keys for RDBMS.<p>And of course keep in mind that you're leaking generation timestamp which might be a bad thing.
A lot of distributed systems’ clocks can’t tell you within 1 ms when an event happened, leading to assumptions that aren’t true. I don’t think we should commit to IDs being even partially ordered unless we have a set of monotonic clocks with sequence number generators, and record a timestamp, a sequence number, and which clock they came from.