ULID: Universally Unique Lexicographically Sortable Identifier • Hacker News Board

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#31

Post by jasonwatkinspdx » Wed, Dec 10, 2025, 1:09 AM UTC

Dylan16807 wrote: post #27

jasonwatkinspdx wrote: post #18

Earlier quoted context omitted.

No, ULID has a "monotonic" feature, where if it detects the same millisecond timestamp in back to back calls, it just increments the 80 bit "random" portion. This means it has convoying behavior. If two machines are generating ids independently and happen to choose initial random positions near each other, the probability of collision is much higher than the basic birthday bound. I think this "sort of monotonic but n…

> If two machines are generating ids independently and happen to choose initial random positions near each other, the probability of collision is much higher than the basic birthday bound. But the chance of the initial random positions being near each other is very very low. If you pick a billion random numbers in an 80 bit space, the chance you have a collision is one in a million. (2^80 / (2^30)^2) If you pick a th…

Right, but the point is there's no reason to accept this limitation. Likewise why hardcode millisecond scale timestamps in a world where billions of inserts per second are practical on a single server?

Or if what you want is monotonic distributed timestamps, again, HLC is how you do that properly.

So you're embracing this weird limitations for no real benefit.

And as you can see in the rest of this comment thread, a lot of people simply do not even know this behavior and are assuming the 80 bit portion is always random. Which is my whole point about having a not really an invariant invariant just being a bad way to go fundamentally.

Edit: just to reply to the below since I can't do so directly, I understand the arithmetic here. What I'm saying is there's zero reason to choose this weird scheme vs something that's just the full birthday bound and you never think about it again.

As another comment points out: just consider neighbor guessing attacks. This 80 bit random but not random field is a foot gun to anyone that just assumes they can treat it as truly random.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#32

Post by N_Lens » Wed, Dec 10, 2025, 1:09 AM UTC

sedatk wrote: post #29

N_Lens wrote: post #25

Earlier quoted context omitted.

ULID's initial segment is timestamp generated, with a random suffix at the end. This kind of collision you're concerned about is not an issue at all, across multi-threads, processes or hosts.

Not if the same ULID generator instance is used across threads.

That depends on if the specific implementation of the generator instance is thread safe. Highly implausible to use the same generator instance between different threads/processes/hosts because there's no benefit at all and only additional downsides.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#33

Post by listenallyall » Wed, Dec 10, 2025, 1:11 AM UTC

jasonwatkinspdx wrote: post #18

listenallyall wrote: post #14

Earlier quoted context omitted.

Under what circumstances is it prone to conflicts? On separate threads/hosts/processes, id's created within the same millisecond would be differentiated by the 80 bits of randomness (more than UUID v7).

No, ULID has a "monotonic" feature, where if it detects the same millisecond timestamp in back to back calls, it just increments the 80 bit "random" portion. This means it has convoying behavior. If two machines are generating ids independently and happen to choose initial random positions near each other, the probability of collision is much higher than the basic birthday bound. I think this "sort of monotonic but n…

I dont think this holds up. Define "near each other" in an 80-bit random space. Further, the likelihood of a potential conflict is offset by the fact that you have far fewer "initial random positions" instead of every single element defining its own random position. And the extra random bits (over UUID7) reduce conflict possibilities by orders of magnitude.

I concede I'm no mathematician and I could be wrong here, but your analysis feels similar to assuming 10-11-12-13-14-15 is less likely to be a winning lottery ticket because the odds against consecutive numbers are so massive.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#34

Post by listenallyall » Wed, Dec 10, 2025, 1:17 AM UTC

jasonwatkinspdx wrote: post #31

Dylan16807 wrote: post #27

Earlier quoted context omitted.

> If two machines are generating ids independently and happen to choose initial random positions near each other, the probability of collision is much higher than the basic birthday bound. But the chance of the initial random positions being near each other is very very low. If you pick a billion random numbers in an 80 bit space, the chance you have a collision is one in a million. (2^80 / (2^30)^2) If you pick a th…

Right, but the point is there's no reason to accept this limitation. Likewise why hardcode millisecond scale timestamps in a world where billions of inserts per second are practical on a single server? Or if what you want is monotonic distributed timestamps, again, HLC is how you do that properly. So you're embracing this weird limitations for no real benefit. And as you can see in the rest of this comment thread, a…

It's not a "limitation", he's saying there is much, much, much less chance of having any collisions with ULIDs - one in a million vs one in a trillion

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#35

Post by jasonwatkinspdx » Wed, Dec 10, 2025, 1:18 AM UTC

listenallyall wrote: post #33

jasonwatkinspdx wrote: post #18

Earlier quoted context omitted.

No, ULID has a "monotonic" feature, where if it detects the same millisecond timestamp in back to back calls, it just increments the 80 bit "random" portion. This means it has convoying behavior. If two machines are generating ids independently and happen to choose initial random positions near each other, the probability of collision is much higher than the basic birthday bound. I think this "sort of monotonic but n…

I dont think this holds up. Define "near each other" in an 80-bit random space. Further, the likelihood of a potential conflict is offset by the fact that you have far fewer "initial random positions" instead of every single element defining its own random position. And the extra random bits (over UUID7) reduce conflict possibilities by orders of magnitude. I concede I'm no mathematician and I could be wrong here, bu…

No, the calculation is straightforward and I'm not making the fallacious assumption you say there at the end about a magical lottery ticket number.

My basic point is the probability of collision is lower than the birthday bound, there's no need for this, and as comments in this thread make clear people are not understanding this limitation even exists with the specification.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#36

Post by sedatk » Wed, Dec 10, 2025, 1:24 AM UTC

vbezhenar wrote: post #23

0x457 wrote: post #20

Earlier quoted context omitted.

You only need to lock sequence if you care about IDs being ordered within a millisecond. That generally only matters when you create a batch of IDs at once, in that case you don't need to lock anything: generate ULID, keep incrementing sequence in that batch either by doing on the same thread, or by moving it from thread to thread. Kinda like creating an iterator and zip'ing it with iterator of thing you need IDs for…

I hope that's not literally incrementing a sequence. Because it would lead to trivial neighbor ID guessing attacks. I've implemented this thing, though not called it ULID. I've dedicated some bits for timestamp, some bits for counter within millisecond and rest for randomness. So they always ordered and always unpredictable. Another approach is to keep latest generated UUID and if new UUID requested within the same t…

> I hope that's not literally incrementing a sequence

It's literally incrementing it by one:

https://github.com/ulid/javascript/blob/11c2067821ee19e4dc78...

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#37

Post by jasonwatkinspdx » Wed, Dec 10, 2025, 1:26 AM UTC

vbezhenar wrote: post #23

0x457 wrote: post #20

Earlier quoted context omitted.

You only need to lock sequence if you care about IDs being ordered within a millisecond. That generally only matters when you create a batch of IDs at once, in that case you don't need to lock anything: generate ULID, keep incrementing sequence in that batch either by doing on the same thread, or by moving it from thread to thread. Kinda like creating an iterator and zip'ing it with iterator of thing you need IDs for…

I hope that's not literally incrementing a sequence. Because it would lead to trivial neighbor ID guessing attacks. I've implemented this thing, though not called it ULID. I've dedicated some bits for timestamp, some bits for counter within millisecond and rest for randomness. So they always ordered and always unpredictable. Another approach is to keep latest generated UUID and if new UUID requested within the same t…

> I hope that's not literally incrementing a sequence. Because it would lead to trivial neighbor ID guessing attacks.

It is and it does.

Also the ULID spec suggests you use a CSPRNG, but doesn't mandate that or provide specific advice on appropriate algorithms. So in practice people may reach for whatever hash function is convenient in their project, which may just be FNV or similar with considerably weaker randomness too.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#38

Post by sedatk » Wed, Dec 10, 2025, 1:28 AM UTC

cpburns2009 wrote: post #19

sedatk wrote: post #16

Earlier quoted context omitted.

You're right, not hosts or processes in that case. I forgot about random part as it's been a while since I looked at it. However, a single instance of a ULID generator must support this mode, which means that on multi-threaded architectures, it must lock the sequence as it still uses a single random value. That again, kills the purpose of a client-side, lock-free generation of universal identifiers as you said.

If you really need lock-free generation, you can use an alternate generator that uses new random bits for every submillisecond id. That's what the `ulid-py` library for Python does by default instead of incrementing the random bits.

Yes, the problem is that this mode is supported and required per the spec. So, a developer must know the pros/cons of this mode. It requires them to correctly assess the consequences. It's quite easy to shoot themsleves in the foot especially when a solid alternative like UUIDv7 exists.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#39

Post by jasonwatkinspdx » Wed, Dec 10, 2025, 1:32 AM UTC

sedatk wrote: post #28

0x457 wrote: post #20

Earlier quoted context omitted.

You only need to lock sequence if you care about IDs being ordered within a millisecond. That generally only matters when you create a batch of IDs at once, in that case you don't need to lock anything: generate ULID, keep incrementing sequence in that batch either by doing on the same thread, or by moving it from thread to thread. Kinda like creating an iterator and zip'ing it with iterator of thing you need IDs for…

> You only need to lock sequence if you care about IDs being ordered within a millisecond Yes, and that's when sequences are only used. I guess that's to avoid hogging the CPU or emptying the OS entropy pool during high loads. However, that "optimization" is a failure mode if you're not aware how ULID internals work. It's easy to shoot yourself in the foot by blindly trusting ULID will always generate a unique ID acr…

> or emptying the OS entropy pool during high loads.

Just a heads up that's not really a thing. If the CSPRNG is initialized correctly you're done. There's nothing being depleted. I know for ages the linux docs said different, they were just wrong and a maintainer was keeping a weird little fiefdom over it.

Re: ULID: Universally Unique Lexicographically Sortable Identifier

#40

Post by marifjeren » Wed, Dec 10, 2025, 1:36 AM UTC

sedatk wrote: post #30

marifjeren wrote: post #24

Earlier quoted context omitted.

> If you need a sequential ID, just use an integer Are monotonic/sequential ULIDs as easily enumerated as integers? It's the ease of enumerability that keeps a lot of folks away from using sequential integers as IDs

You mean someone who wants to attack your system might be discouraged by Base32 encoding?

Sorry, I'm not familiar with the ULID spec. You seem to be, hence my asking. Are you saying monotonic/sequential ULIDs are just (or just as easily enumerated as) Base32-encoded integers?

Oh and yeah, I guess I do think lots of script / AI kiddies would be discouraged by, or fail to see an opportunity when presented with, something that does not look like the numbers they saw in school.