Укорачивание/повторное использование UUID

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

Я создаю распределенное приложение, где узлы удаленно создают объекты, идентифицированные с помощью UUID. В конце концов, все объекты должны быть собраны в выделенном дренаже node, который хранит все объекты, используя эти UUID.

Теперь я хочу создать дополнительные идентификаторы, которые более удобны для пользователей. Base64-кодирование UUID будет по-прежнему создавать идентификаторы с 22 символами, что не подходит для использования человеком. Поэтому мне нужно что-то вроде сервисов сокращения URL-адресов. Применение биективных функций не поможет, поскольку они не уменьшат информационное значение. Конечно, я знаю, что мне нужно потерять информацию, чтобы сократить идентификатор. И я также знаю, что любое уменьшение информации хэша увеличит вероятность столкновения. Я застрял, что наиболее подходящий способ уменьшить информацию, чтобы создать более короткие идентификаторы для людей.

Вот некоторые предварительные условия: я предоставил возможность сопоставить {UUID, сокращенный идентификатор} через мое хранилище данных. Я бы предпочел нецентрализованное решение. Мне, вероятно, никогда не понадобится больше, чем примерно миллион ID (~ 2 ^ 20).

Вот мысли, которые я придумал до сих пор:

~~Автоматически увеличивающиеся идентификаторы:~~ Если бы я использовал какой-то идентификатор с автоматическим увеличением, я мог бы передать этот идентификатор на обфускацию и передать это. Это был бы самый простой подход, и пока вокруг будет мало ключей, ключи будут не очень длинными. Однако я должен был бы представить централизованный объект, которого я действительно не хочу.
Сократите UUID: Я мог бы просто взять некоторые из бит исходного 128-битного uuid. Тогда я должен хотя бы учесть версию UUID. Или что-то еще не так с этим?
Повторное использование UUID: Я мог бы применить второй алгоритм хэширования в своем первоначальном UUID и сохранить сопоставление.

Есть ли другие подходы? Что выгодно?

Спасибо заранее!

Ответ 1

1) Чтобы сократить UUID, вы можете просто XOR верхнюю половину с нижней (и повторите, пока она недостаточно для вас). Это сохранит характеристики распределения. Как и любое решение, которое сокращает выход, это увеличит вероятность столкновения из-за парадокса дня рождения

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

3) Если вы готовы принять какое-то центральное руководство, это не должно быть болезненным. Центральный орган власти может выдавать узлы среднего размера адресного пространства каждому клиенту, а затем клиент может выполнять итерацию через этот поддиапазон при назначении идентификаторов. Это гарантирует отсутствие столкновений, но также позволяет избежать обратного хода для каждого идентификатора. Один из способов сделать это - использовать 32-битное целое число для идентификатора, одновременно выставляя 16-битный блок. Другими словами, первый клиент получает переданный 0001, который позволяет от 00010000 до 0001FFFF.

4) Вы можете вставить в базу данных UUID, но также иметь поле идентификации. Это обеспечит альтернативный, более компактный уникальный идентификатор, который может быть ограничен 32-битным int.

Ответ 2

Считаете ли вы использование внешнего подхода сглаживания, в котором вы выбираете словарь дружественных человеческим терминам и используете их, чтобы сделать (части) UUID более читаемыми:

de305d54-75b4-431b-adb2-eb6b9e546013

Использование словаря из 65536 слов может стать:

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

Маловероятно, что пользователи будут видеть умственное хеш-столкновение (зебра, встречающееся дважды) с этими человекочитаемыми именами, и ваша база данных не будет расти в размерах. Перевод является биективным и чисто UI.

Ответ 3

Просто пара вещей, которые приходят в голову:

Каков ваш прецедент? Если вы обеспокоены тем, что вы будете генерировать идентификаторы распределенным образом, одно решение - назначить каждой машине свой уникальный уникальный идентификатор и использовать его как префикс или суффикс для своих идентификаторов.

Это действительно не помогает, если вы не имеете центрального объекта, которое вы имеете в виду ничего, что отслеживает идентификаторы даже локально. Вы можете взять страницу из UUID и использовать системное время в сочетании с идентификатором машины, указанным выше. Это приведет вас к 64 бит + независимо от размера вашего идентификатора машины. В принципе, это схема UUID V1, за исключением того, что вы используете что-то меньшее, чем MAC-адрес для идентификатора машины. Учитывая, что вы знаете, что можете начать с дат >= 12 февраля 2010 года, возможно, вы сможете сократить еще больше.

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

Ответ 4

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

Этот алгоритм не предназначен для обеспечения безопасности или эффективности, но должен сделать трюк.

public class HashTools {

  final static String inputMapping = "0123456789ABCDEF";

  final static String[] outputMapping = new String[] {
      "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
      "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"
  };

  /* Input: String - containing mostly letters / numbers
   * Output: <hashLength> String using 0-9,A-Z encoding
   */
  public static String simpleHash(String str, int hashLength) {
    StringBuilder hashStr = new StringBuilder(hashLength);
    String strUpper = str.toUpperCase();
    int[] hash = new int[hashLength];

    int i, j, num;
    for (i = 0; i < strUpper.length(); i++) {
      char strChar = strUpper.charAt(i);
      num = mapCharToInt(strChar);

      j = i % hashLength;
      hash[j] += num;
    }

    for (i = 0; i < hashLength; i++) {
      hashStr.append(mapIntToHashChar(hash[i]));
    }

    return hashStr.toString();
  }

  private static int mapCharToInt(char hexChar) {
    return inputMapping.indexOf(hexChar);
  }

  private static String mapIntToHashChar(int num) {
    return outputMapping[num % outputMapping.length];
  }
}