Сортируемый UUID v1 для мультиплатформенного приложения

Question

Мы ищем решение для генерации уникального идентификатора для сообщений / сигналов, которыми обмениваются клиенты в Интернете, iOS и Android и которые впоследствии сохраняются в бэкэнде.

• Решение должно быть стандартизировано

• доступно на нескольких платформах

• сортируется по времени создания, индексируется базой данных

UUID v1 имеет эти свойства, за исключением одной маленькой вещи, которая заключается в том, что для сортировки и индексирования требуется переопределение строкового идентификатора.

В документации UUID объясняется, что порядок временных блоков меняется на обратный (начинается с миллисекунд) ( ссылка).

  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

Из-за представления UUID мы не можем сортировать идентификаторы просто по строковому представлению идентификаторов, и мы должны использовать функцию сравнения.

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);

Знаете ли вы другой стандартизированный подход, который не будет иметь этой проблемы?

Было бы правильно использовать UUID v1, но обменивать его между клиентами, переставив так, чтобы клиенты могли сортировать по строковому представлению и не использовать функцию сравнения каждый раз для сортировки?

Живой тест: https://codesandbox.io/s/q5oRxgnp

Answer 1

Если вы переставите биты UUID, у вас больше не будет UUID.

Также обратите внимание, что одна из целей стандарта UUID - разрешить смешивание значений разных версий UUID. Другими словами, как правило, вы не должны предполагать, что все ваши UUID полностью соответствуют одной версии.

UUID никогда не предназначались для разрыва, никогда не рассматривались как контейнер. Умные программисты, которые думают об этом, слишком умны для их же блага.

Тем не менее, некоторые люди изменяют структуру или содержание своего UUID. Я не рекомендую это.

Вместо этого я предлагаю вам определить и разделить ваши проблемы.

• Идентификатор
  Если вам необходимо однозначно идентифицировать ваши объекты во времени и пространстве без координации с централизованным сервером, используйте соответствующий UUID.
• Сортировать
  Если вы также хотите отсортировать, добавьте другое поле для значения сортировки. Например, если вы хотите отсортировать в хронологическом порядке, сохраните значение временной метки, если оно поддерживается вашей базой данных или приемником данных. Если не поддерживается, сохраните текстовое представление значения даты и времени в формате UTC в стандартном формате ISO 8601. Этот формат разработан так, что при сортировке по алфавиту он также является хронологическим.

2017-01-23T01: 23: 45.123Z

Answer 2

Кажется, вы ищете кодек COMB (комбинированный time-GUID) , написанный на JS.

Об этом очень долго спорят в uuid js libпроблемы, заканчивающиеся в потоке, требующем реализации черновика RFC для их решения

В ожидании этого вы можете использовать эту реализацию , которая, вероятно, удовлетворит ваши потребности.

Но эта реализация UUIDv7 (проект RFC) , разработанная активным участником uuid jsтоже очень интересно

Как объяснено здесь , он обеспечивает сочетание между UUIDv1а также UUIDv4:

Как вы читали, «Упорядоченный UUID» — это что-то новое. Это нечто среднее между (основанным на времени, угадываемым) и UUID v4(случайно, угадать невозможно). Что делает этот UUID особенным, так это… ну, это может быть conveniently ordered.

Если вы хотите понять некоторые плюсы и минусы COMB (для чисто БД), эта статья упоминается в реализации Рэмси. Но поскольку он старый, он не принимает во внимание новый контекст распределенных систем.

Принимая во внимание распределенные контексты, они говорят о реализации идентификатора машины, на которой запущен скрипт , чтобы избежать коллизий, но not the mac addressвопреки Uuid v1.

Наконец, вот действительно простое объяснение различий между UUID v1, v4а также v5

Answer 3

Основной ответ немного вводит в заблуждение и сбивает меня с пути, поэтому я хотел бы уточнить здесь несколько вещей.

1. Сортировка - изменение порядка UUID не рекомендуется, но это не означает, что вы не можете сортировать по значению. Кассандра делает это, и это совершенно верно. В основном они используют тот же метод, что и предложенный OP, но только как функцию сортировки.
2. Изменение порядка - если вы создаете систему, которую полностью контролируете, то изменение UUID, хотя и не рекомендуется, все равно будет работать нормально и быть полностью уникальным. Возможно, он не будет универсально уникальным, но он будет уникальным в вашей системе, если вы будете делать это единообразно.

Определение пользовательской функции сортировки

Как упоминалось выше, Cassandra уже определяет встроенную функцию сортировки, которая сортирует UUID. Вы можете сделать то же самое в других системах, если у вас есть возможности, но в качестве канонического примера Javascript, учитывая следующие UUId, вы можете отсортировать это следующим образом:

// 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
}

Надеюсь, это кому-то поможет!