Сокращение / Перефразирование UUIDS

Question

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

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

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

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

Вот мысли, которые пришли мне в голову на данный момент:

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

Есть ли какие-то другие подходы?Что является благоприятным?

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

Answer 1

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

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

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

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

Answer 2

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

de305d54-75b4-431b-adb2-eb6b9e546013

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

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

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

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