Sortable UUID v1 for multi-platform application

Question

We are looking for a solution to generate a unique id for messages/signals that are exchanged between clients on the Web, iOS, and Android and later persisted on the backend.

• Solution have to be standardized

• available on multiple platforms

• sortable by created time, indexable by the database

The UUID v1 have these properties except one small thing that sorting and indexing require rearranging of string identifier.

UUID documentation explains that order of time blocks is reversed(starts from milliseconds) (link).

  UUID                   = time-low "-" time-mid "-"
                           time-high-and-version "-"
                           clock-seq-and-reserved
                           clock-seq-low "-" node
  time-low               = 4hexOctet
  time-mid               = 2hexOctet
  time-high-and-version  = 2hexOctet
  clock-seq-and-reserved = hexOctet
  clock-seq-low          = hexOctet
  node                   = 6hexOctet

Because of the UUID representation, we can not sort IDs simply by the string representation of the IDs, and we have to use compare function.

const toSortableUUID = uuidV1 =>
  uuidV1.replace(/^(.{8})-(.{4})-(.{4})/, '$3-$2-$1');

const uuidCompare = (uuidV1A, uuidV1B) => {
  if (uuidV1A === uuidV1B) {
    return 0;
  }
  const a = toSortableUUID(uuidV1A);
  const b = toSortableUUID(uuidV1B);
  return a < b ? -1 : 1;
};

const sortedArrayOfUUIDV1 = arrayOfUUIDV1.concat().sort(uuidCompare);

Do you know another standardized approach that will not have this issue?

Would it be correct to use UUID v1 but exchange it between clients rearranged so clients can sort by string representation and do not have to use compare function every time for sorting?

Live test: https://codesandbox.io/s/q5oRxgnp

Answer 1

If you rearrange the bits of a UUID, you no longer have a UUID.

Also note that one of the purposes of the UUID standard is to allow the mixing of values of the different versions of UUID. In other words, generally you should not assume your UUIDs are all entirely of one version.

UUIDs were never intended to be torn apart, never to be considered as a container. Clever programmers who conceive of doing so are being too clever for their own good.

Nevertheless, some people do alter the structure or content of their UUID. I do not recommend that.

Instead I suggest you identify and separate your concerns.

• Identifier
  If you need to uniquely identify your entities across time and space without coordinating with a centralized server, then use a UUID proper.
• Sort
  If you also want to sort, then add another field for the sort value. For example, if you want to sort chronologically, store a timestamp value if supported by your database or data sink. If not supported, store a textual representation of a date-time value in UTC in standard ISO 8601 format. This format is wisely designed so that when sorted alphabetically it is also chronological.

2017-01-23T01:23:45.123Z

Answer 2

You seem to be looking for a COMB (combined time-GUID) codec written in JS.

There is a very long debate about it in the uuid js lib issues ending on a thread requiring implementing a draft RFC addressing it

Waiting for it, you can use this implementation which would probably suits your needs.

But this UUIDv7 (draft RFC) implementation developed by an active contributor of uuid js is really interesting too

As explained here, it provides a mix between UUIDv1 and UUIDv4:

As you read, the “Ordered UUID” is kinda new. It is something between UUID v1 (time based, guessable) and UUID v4 (randomly based, improbable to guess). What makes this UUID special is… well, it can be conveniently ordered.

If you want to understand some pros and cons of COMB (for a purely DB side), this article is mentioned in Ramsey's implementation. But as it's old, it doesn't take in consideration the new context of distributed systems.

Considering distributed contexts, they speak about implementing a an id of the machine running the script to avoid collisions but not the mac address contrary to Uuid v1.

Finally, here is a really simple explanation of the differences between UUID v1, v4 and v5

Answer 3

The main answer is a little misleading and lead me astray so I would like to clarify a few things here.

1. Sorting - Rearranging UUIDs is not recommended, but that does not mean you can't sort by the value. Cassandra does that, and it's perfectly valid. They basically use the same method as the OP suggested, but only as a sort function.
2. Rearranging - If you're building a system that you completely control, then rearranging a UUID, while not recommended, would still work fine and be completely unique. It might not be universally unique but it would be unique in your system assuming you do this uniformly.

Defining a Custom Sort Function

As mentioned above, Cassandra already defines a built-in sort function that sorts UUIDs. You can do the same in other systems if you have the capabilities, but as a cannonical Javascript example, given the following UUIds you could sort this like this:

// Rearrange, only used for the purpose of sorting
const rearrangeId = uuid => {
  let [low, mid, hiAndVersion] = uuid.split('-')

  return [hiAndVersion, mid, low].join('')
}

// Sorting, using our rearrange function
uuids.sort((id1, id2) => {
  let rearranged1 = rearrangeId(id1)
  let rearranged2 = rearrangeId(id2)

  if (rearranged1 > rearranged2) {
    return 1
  }

  return -1
}

Hope this helps someone!