Lexicographic sorting broken in version 3.1.0? [PR created]

[mmakaay]

After upgrading to 3.1.0, I am getting some unexpected output from the following test code:

$ uv pip list | grep ulid
python-ulid        3.1.0

$ python3
Python 3.13.5 (main, Jun 11 2025, 15:36:57) [Clang 19.1.7 ] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from ulid import ULID
>>> miss = 0
>>> prev = ""
>>> miss=0
... for i in range(5000):
...     n = str(ULID())
...     if n < prev:
...         miss+=1
...         print(f"next {n} < prev {prev} !! {miss}")
...     prev=n
...
next 01K37AJA5QDYD4BP0K7WP36YBR < prev 01K37AJA5QJR2P2YEZV244F2WQ !! 1
next 01K37AJA5XHK1QAT1VKWG2AMX6 < prev 01K37AJA5XXC3CV5Z9M7T9WHR1 !! 2
>>>

This shows that the IDs are not following monotonic sort order.

Given the fact that for the first miss case, the IDs both start with 01K37AJA5Q (i.e. the timestamp), I suspect that the issue is somewhere in the new feature as mentioned in the 3.1.0 changelog:

When generating ULIDs within the same millisecond, the library will ensure monotonic sort order by incrementing the randomness component by 1 bit.

Looking as some context around the miss

When printing out the generated IDs, there is a clear jump in the output:
(the number at the start is the miss counter)

0 01K37BHXZ8REXFPRZW7KW6NDGC
0 01K37BHXZ8REXFPRZW7KW6NDGD
0 01K37BHXZ8REXFPRZW7KW6NDGE
1 01K37BHXZ8CQKKDCNFZ8EH5SXV
1 01K37BHXZ9CQKKDCNFZ8EH5SXW
1 01K37BHXZ9CQKKDCNFZ8EH5SXX

These all carry the same timestamp. Before and after the jump, there is incrementing going on on the random part, so that looks like the new feature in action.

In the same run, I also got:

1 01K37BHXZ9CQKKDCNFZ8EH5SYT
1 01K37BHXZ9CQKKDCNFZ8EH5SYV
1 01K37BHXZ9CQKKDCNFZ8EH5SYW
2 01K37BHXZ98VYMQHC24B0TNB9V
2 01K37BHXZA8VYMQHC24B0TNB9W
2 01K37BHXZA8VYMQHC24B0TNB9X
--------8<--------
2 01K37BHY08YGRGZNCG5B264WRG
2 01K37BHY08YGRGZNCG5B264WRH
2 01K37BHY08YGRGZNCG5B264WRJ
3 01K37BHY08HV9Y6H8VHCFNTQRM
3 01K37BHY09HV9Y6H8VHCFNTQRN
3 01K37BHY09HV9Y6H8VHCFNTQRP

[mmakaay]

The issue stems from the following sequence:

timestamp = int.to_bytes(cls.provider.timestamp(value), constants.TIMESTAMP_LEN, "big")
randomness = cls.provider.randomness()

The issue is that the first line calls cls.provider.timestamp(value) with a specific value, and that randomness() itself also calls self.timestamp() to get the current time. This results in a race condition issue.

Priming iteration:

1. ULID() calls ValueProvider.timestamp() and gets TS1
2. ValueProvider.randomness() is used to generate random data.
3. We have a nice ULID, and the value provider's previous timestamp is TS1.

Failing iteration:

1. ULID() calls ValueProvider.timestamp() and gets, again, TS1
2. It calls ULID.from_timestamp(TS1)
3. This method calls ValueProvider.timestamp(TS1) which returns TS1
4. This method calls ValueProvider.randomness()
5. The randomness method calls ValueProvider.timestamp() and gets a new TS2 <-- race condition started
6. The randomness method compares TS2 against the previous TS1 and decides to return pure random data
7. ULID.from_timestamp() receives the pure random data, but combines it with TS1

This is not caught by the tests, because these freeze time, causing the timestamp to never change at the race condition point. When I add the following test, it does show the issue most of the times (once in a while, the code manages to sneak past the issue):

def test_same_millisecond_monotonic_sorting_without_frozen_time() -> None:
    previous_ulid = "" 
    for i in range(10000):
        new_ulid = ULID()
        assert new_ulid > previous_ulid
        previous_ulid = new_ulid

Base on this, I will write a PR.

[mmakaay]

PR: #46

[mmakaay]

Did you have time to take a look at this issue report and the accompanying PR?

Currently, we have an extra wrapper around generating our ULIDs, to make sure that they actually are incremental at all times (by skipping the race condition cases). It would be nice to drop this work-around from our code base, in which we depend on the intended guaranteed incremental behaviour of this package.