4 ms·

> I need to remind that it has a sequential ID generation mode in its spec which is prone to conflicts on multi-threads, processes or hosts which kills the purp

by cpburns2009 11mo ago

> I need to remind that it has a sequential ID generation mode in its spec which is prone to conflicts on multi-threads, processes or hosts which kills the purpose of a "universal" identifier. Can you expand on how this can actually cause a problem? My understanding is different processes and hosts should never conflict because of the 80 bits of random data. The only way I can conceive of a conflict is multiple threads using the same non-thread-safe generator during the same millisecond.

sedatk 11mo ago
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.
- cpburns2009 11mo ago
  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.
  - sedatk 11mo ago
    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.
- 0x457 11mo ago
  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've switched to using UUIDv7 tho. It made sense to use ULID before v7, but now ULID only has one thing going on - smaller string representation. That doesn't matter if your storage can store UUIDs natively (i.e. as 128 bit integer) If your goal is to have global order intact, then neither ULID nor UUIDv7 is going to work for you.
  - vbezhenar 11mo ago
    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 timestamp - generate random part until it's greater than previous one. I think that's pretty good approach as well.
    - sedatk 11mo ago
      > I hope that's not literally incrementing a sequence It's literally incrementing it by one: https://github.com/ulid/javascript/blob/11c2067821ee19e4dc787ca4e0125a025485edc6/source/ulid.ts#L162 https://github.com/ulid/javascript/blob/11c2067821ee19e4dc78... https://github.com/ulid/javascript/blob/11c2067821ee19e4dc787ca4e0125a025485edc6/source/crockford.ts#L82 https://github.com/ulid/javascript/blob/11c2067821ee19e4dc78...
      - vbezhenar 11mo ago
        Well, that makes little sense for me, you can just use numeric identifier instead. Bulk inserts which generate identifiers in bulk are commonly used. But that's easy to fix, so just implementation quirk for this particular library, the idea is sound.
        sedatk 11mo ago
        > But that's easy to fix, so just implementation quirk for this particular library, the idea is sound. It's in ULID spec.
    - jasonwatkinspdx 11mo ago
      > 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.

sedatk 11mo ago

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.

cpburns2009 11mo ago
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.
- sedatk 11mo ago
  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.
0x457 11mo ago
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've switched to using UUIDv7 tho. It made sense to use ULID before v7, but now ULID only has one thing going on - smaller string representation. That doesn't matter if your storage can store UUIDs natively (i.e. as 128 bit integer) If your goal is to have global order intact, then neither ULID nor UUIDv7 is going to work for you.
- vbezhenar 11mo ago
  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 timestamp - generate random part until it's greater than previous one. I think that's pretty good approach as well.
  - sedatk 11mo ago
    > I hope that's not literally incrementing a sequence It's literally incrementing it by one: https://github.com/ulid/javascript/blob/11c2067821ee19e4dc787ca4e0125a025485edc6/source/ulid.ts#L162 https://github.com/ulid/javascript/blob/11c2067821ee19e4dc78... https://github.com/ulid/javascript/blob/11c2067821ee19e4dc787ca4e0125a025485edc6/source/crockford.ts#L82 https://github.com/ulid/javascript/blob/11c2067821ee19e4dc78...
    - vbezhenar 11mo ago
      Well, that makes little sense for me, you can just use numeric identifier instead. Bulk inserts which generate identifiers in bulk are commonly used. But that's easy to fix, so just implementation quirk for this particular library, the idea is sound.
      - sedatk 11mo ago
        > But that's easy to fix, so just implementation quirk for this particular library, the idea is sound. It's in ULID spec.
  - jasonwatkinspdx 11mo ago
    > 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.