Сокращение/Перефразирование UUID
в первую очередь, я хочу гарантировать, что я знаю о факте, что перефразирование является разумной темой. Однако я хотел бы услышать некоторые Ваши мнения, что приближается, Вы взяли бы здесь.
Я создаю распределенное приложение, где узлы удаленно создают объекты, определенные UUID. В конечном счете все объекты должны быть собраны в специализированном узле дренажа, который хранит все объекты при помощи этих UUID.
Теперь я хочу создать дополнительные идентификаторы, которые более удобны для пользователей - людей. Base64-кодирование UUID все еще создало бы идентификаторы с 22 символами, который не подходит для человеческого использования. Таким образом, мне нужно что-то как сокращающие URL сервисы. Применение биективных функций не поможет, потому что они не уменьшат информационное значение. Конечно, я знаю, что должен потерять информацию для сокращения идентификатора. И я также знаю, что любое сокращение информации хеша увеличит вероятность коллизии. Я застреваю, что самый соответствующий путь состоит в том, чтобы уменьшить информацию для создания более коротких идентификаторов для людей.
Вот некоторые предпосылки: Я обеспечу способность отобразить {UUID, сокращенный идентификатор} через мое хранение данных. Я все еще предпочел бы нецентрализованное решение. Мне, вероятно, никогда не будут нужны больше, чем приблизительно миллион идентификаторов (~2^20) всего.
Вот мысли, которые я придумал до сих пор:
Автоматические увеличенные идентификаторы:Если я использовал бы некоторый автоувеличенный идентификатор, я мог бы передать этот идентификатор запутываемой строке и раздать это. Это было бы самым легким подходом, и, пока существует немного ключей вокруг, ключи не были бы очень длинны. Однако я должен был бы представить централизованный объект, который я действительно не хочу.- Сократите UUID: Я мог просто взять некоторые биты исходных 128 битов uuid. Затем я должен взять по крайней мере во внимание версию UUID. Или есть ли что-либо еще неправильно с этим?
- Перефразирование UUID: Я мог применить второй алгоритм хеширования для своего начального UUID и сохранить отображение.
Есть ли какие-либо другие подходы? Что благоприятно?
Заранее спасибо!
2 ответа
1) Чтобы сократить UUID, вы можете просто XOR верхнюю половину с нижней (и повторять до тех пор, пока он не станет достаточно коротким для вас). Это сохранит характеристики распределения. Как и любое решение, укорачивающее вывод, это увеличит вероятность коллизии из-за парадокса дня рождения
2) XOR равносилен тривиальному хэшу, но поскольку дополнительного смешивания не требуется, это вполне подходит. Вы можете использовать CRC или некриптографический хэш для вашего UUID, но я не верю, что это улучшит ситуацию.
3) Если вы готовы принять некоторое централизованное управление, оно не обязательно должно быть болезненным. Центральный орган может раздать каждому клиенту блоки адресного пространства среднего размера, а затем клиент может итеративно просматривать этот поддиапазон при назначении идентификаторов. Это гарантирует отсутствие коллизий, а также позволяет избежать обхода каждого идентификатора. Один из способов сделать это - использовать 32-битное целое число для ID, выдавая по 16-битному блоку за раз. Другими словами, первому клиенту передается 0001, что позволяет использовать от 00010000 до 0001FFFF.
4) Вы можете вставлять в базу данных UUID, но при этом иметь поле идентификации. Это обеспечит альтернативный, более компактный уникальный ID, который может быть ограничен 32-битным числом.
Просто пара вещей, которые приходят на ум:
Каков ваш сценарий использования? Если вас беспокоит то, что вы будете генерировать идентификаторы распределенным образом, то одним из решений является присвоение каждой машине собственного уникального int id и использование его в качестве префикса или суффикса для идентификаторов.
Это не очень помогает, если под отсутствием центральной сущности вы подразумеваете ничего, что отслеживало бы идентификаторы даже локально. Вы можете позаимствовать страницу из самого UUID и использовать системное время в сочетании с идентификатором машины, назначенным, как указано выше. Это позволит вам сократить время до 64 бит + любой размер идентификатора машины. По сути, это схема UUID V1, за исключением того, что вы используете для идентификатора машины что-то более короткое, чем MAC-адрес. Учитывая, что вы знаете, что можете начать с дат >= 12 февраля 2010 года, вы можете сократить еще больше.
Просмотрите статью UUID в Википедии, если вы еще этого не сделали, возможно, вы почерпнете оттуда пару идей о том, как создать свой собственный.