UUID version 7 implementation sorting incorrect?

[excitement-engineer]

I tried running the following code to ensure that the ordering of the UUID v7 is correct:

val test = (0..20).map { Generators.timeBasedEpochGenerator().generate() }
    val sorted = test.sorted()

    test.forEachIndexed { index, uuid ->
        println( uuid == sorted[index])
    }

expect the equality check returns false for almost all entries. I have tried to run the same test with the library com.github.f4b6a3:uuid-creator:5.2.0 and there the checks always return true using the following code:

val test = (0..20).map { UuidCreator.getTimeOrderedEpoch() }
    val sorted = test.sorted()

    test.forEachIndexed { index, uuid ->
        println( uuid == sorted[index])
    }

Is this a mistake in the implementation?

[cowtowncoder]

I don't know but it does sound like there might be a problem. Thank you for reporting this.

I would need a stable reproduction (in plain Java) & then time to look into this to say more.

@Hellblazer WDYT?

[fabiolimace]

It's not a problem.

UUID v7 only requires the first 48 bits to be continually increasing, just like the ULID specification.

Some implementations use an optional counter to provide additional monotonicity for identifiers created by the same generator. But it's not required.

Best regards

[cowtowncoder]

Thank you @fabiolimace. If I understand this correctly, it'd be nice to guarantee such invariant. JUG does use counters to provide virtual 100 nano resolution with counter for "old" time/location based variant so it would seem reasonable to do it here, if it isn't. I'd have to double-check this aspect.

But the other thing I was wondering about was whether this could be related to sortability (or lack thereof) of UUID type itself; JUG does not provide its own type but relies on java.util.UUID. If I recall correctly, sortability uses naive bit comparison. As per https://docs.oracle.com/javase/8/docs/api/java/util/UUID.html#compareTo-java.util.UUID- :

The first of two UUIDs is greater than the second if the most significant field in which the UUIDs differ is greater for the first UUID.

Conversely it is possible the other library referenced might be using its own UUID type abstraction that would be using better comparator definition.

FWTW, #13 sounds like similar report from the past.

[cowtowncoder]

Ah ha. JUG provides com.fasterxml.uuid.UUIDComparator because, as per Javadocs:

/**
 * Default {@link java.util.UUID} comparator is not very useful, since
 * it just does blind byte-by-byte comparison which does not work well
 * for time+location - based UUIDs. Additionally, it also uses signed
 * comparisons for longs which can lead to unexpected behavior
 * This comparator does implement proper lexical ordering: starting with
 * type (different types are collated
 * separately), followed by time and location (for time/location based),
 * and simple lexical (byte-by-byte) ordering for name/hash and random versions.
 */

However! This class has NOT been updated along with addition of new variants so implementation could probably be improved.

@excitement-engineer Would it be possible for you to see if use of com.fasterxml.uuid.UUIDComparator would result in proper ordering?

[Hellblazer]

arg. late top the party. will take a look and see

[excitement-engineer]

@cowtowncoder Even with com.fasterxml.uuid.UUIDComparator I am not seeing the proper ordering.

[Hellblazer]

D'oh. deleted a bogus test of mine. apologies

[Hellblazer]

I'm able to reproduce this with this test:

public void testSortingV7() {
    Random entropy = new Random(0x666);
    final TimeBasedEpochGenerator generator = Generators.timeBasedEpochGenerator(entropy);
    List<UUID> created = new ArrayList<UUID>();
    for (int i = 0; i < 1000; i++) {
        created.add(generator.generate());
    } 
    List<Comparable<?>> sorted = new ArrayList<Comparable<?>>(created); 
    sorted.sort(new Comparator() {

        @Override
        public int compare(Object o1, Object o2) { 
            return UUIDComparator.staticCompare((UUID) o1, (UUID) o2);
        }
    });
    for (int i = 0; i < created.size(); i++) {
        assertEquals("error in index: " + i,  created.get(i), sorted.get(i));
    }
}

[Hellblazer]

okay, was able to repro that with just 2 entries in the above test - lol.

[cowtowncoder]

Ok. So the issue is about making sure "random" part that was used will be changed to "random only for new 48-bit timestamp value; increment as sequence if same time part". But that sorting may work as-is, with UUIDComparator.

Than kyou @Hellblazer -- I'll try to get this merged ASAP.

[cowtowncoder]

Fix merged; will now publish 4.1.1 with this fix.