Сокращение / перефразировка UUID

Question

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

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

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

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

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

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

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

Заранее спасибо!

Answer 1

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

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

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

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

Answer 2

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

de305d54-75b4-431b-adb2-eb6b9e546013

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

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

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

Answer 3

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

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

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

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

Answer 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];
  }
}