ULID Generation

Everytime you call nextULID, a new ULID is generated. It get's current millisecond time using ZIO's Clock and 10 random bytes using ZIO's Random. It then encodes the time and random bytes into a ULID. However, this simple implementation can cause random collision if you generate ULIDs in the same millisecond.

How is random collision avoided?

To avoid it, ULIDGen is a stateful layer. It stores the last millisecond when ULID was generated and the last random bytes used. When nextULID is called, it compares current milliseconds with last milliseconds and if they are same, it does not generate new random bytes. Instead, it increments the last random bytes by 1, combines it with current milliseconds and encodes it into a ULID. It also stores the current milliseconds and random bytes in the state. To access and modify this state in a threadsafe manner, it uses ZIO's Ref.

This behaviour is called monotonical increase. And because of this behaviour, ULIDs generated by ULIDGen are lexicographically sortable.

How is overflow avoided?

Maximum value of random bytes, as per spec encoding is ZZZZZZZZZZZZZZZZ. What if we have a huge compute power and we are able to generate lots of (more than 2^80 - 1) ULIDs in the same millisecond? In that case, we will run out of random bytes.

ZIO-ULID does not return error in such case. Instead, within same millisecond ULIDGen checks if the last generated random bytes is ZZZZZZZZZZZZZZZZ. If it is, it waits for 1 millisecond and then generates a new ULID.

Note

Monotonical increase to avoid random collision and waiting for 1 millisecond to avoid overflow both are scoped to a millisecond. ULIDs generated in different milliseconds are not affected by these behaviours.

Note2

Both these concepts are taken from airframe-ulid implementation. Implementation is different since ZIO-ULID is implemented in ZIO.