Pull to refresh

Comments 40

Спасибо за статью, было интересно!
Расскажите про эти странные пресеты для UUID5, например DNS?
P.S. теги читаю ))

Теги то читаешь, а ярлычки к статьям нет)
Вы наверняка уже использовали в своих проектах UUID и полагали, что они уникальны.

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

Из-за того что в UUID входит рандомная составляющая, его после генерации надо куда-то сохранить. Например, в файл. А файлы внезапно можно копировать. Ну и дальше при копировании забывают перегенерировать UUID, в результате получаем в системе две сущности с одинаковым UUID.

какую альтернативу вы видите?

К примеру если это код, то рядом (а может и в заголовке на видном месте) с таким UUID ставим название программы и реальный UUID делаем через XOR с именем (самое примитивное). При копировании новый программист скорее всего поменяет имя программы.

Зачем xor, когда в стандарте описан способ генерации uuid из другого uuid и произвольной строки?

Так это же отлично.
Только не понятно, мне "-" поставили за идею или за примитивную реализацию? Если за реализацию, так я и не скрываю, что это примитивное «демо», а в реале по другому нужно.
Звучит как «не вяжи меня начальник, я серийник на винду подобрал, долбил по клаве неделю»
Дублирование обычно возникает, когда среди авторов появляется умный и начинает генерировать всякие 70726573-7469-6469-6769-746174696f6e или вообще 01234567-89ab-cdef-0123-456789abcdef руками.
Тоже встречал. Но там генератор был самописный на php, в основе которого rand().
Проблема была связана со слишком малой длиной числа.
В статье, на мой взгляд, не хватает ответа на самый главный вопрос: а что собственно использовать?

Мой ответ такой:

Версии 1 и 2 (время + идентификатор хоста) в теории надежна, но с практической точки зрения опасна, поскольку создает два неявных требования: корректное течение системного времени и уникальность MAC адресов. Вы, как разботчик софта, эти факторы не контролируете. Только вопрос времени (или MAC адреса), когда одно из этих требований нарушится.

Версии 3 и 5 (SHA-1 или MD5 хеш) неоправданно вычислительно дорогие, и при этом не надежные. Для обоих функций уже найдены коллизии. Это означает, что если на идентификтор, от которого берется хеш, влияет кто-то из вне (пользователи), ждите беды. Можно применять только в случаях, когда генерация UUID зависит только от доверенных данных (но все равно не стоит).

Версия 4 (ГПСЧ). Самая быстрая и надежная, при корректном использовании. Корректное использование заключается в следующем:

  1. Используйте генератор псевдослучайных чисел полного цикла (xorshift или PCG).
  2. Убедитесь, что состояния вашего генератора – 128 бит.
  3. Убедитесь, что вы инициализурете ваш генератор истинно случайной энтропией (/dev/random, как минимум 128 бит).
  4. НЕ используйте только /dev/random как постоянный генератор UUID, кроме случаев, когда сама возможность угадать UUID должна быть невозможной.

Если все сделать правильно, генерация UUID будет быстрой, надежной и зависеть только от вашего кода, и это хорошо (ну и еще от адекватности /dev/random).

А еще, если у вас нет требования использовать именно стандарт UUID, то посмотрите в сторону nanoid, благо его поддержка уже реализована на 17 языках. Он в короче (21 байт вместо 36), надежнее (126 бит против 122), быстрее и гибче чем UUID.

И да, при непрекращающейся генерации на скорости 1000 идентификаторов в секунду, понадобится больше 1000 лет, чтобы иметь 1% шанс хотя бы одной коллизии для случайных 16-символьных base32 идентификаторов вроде «GByvN46iRhqfJ1vi».

Так что прекращайте захламлять память своими {3422b448-2460-4fd2-9183-8000de6f8343}.
> А еще, если у вас нет требования использовать именно стандарт UUID, то посмотрите в сторону nanoid, благо его поддержка уже реализована на 17 языках. Он в короче (21 байт вместо 36), надежнее (126 бит против 122), быстрее и гибче чем UUID.

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

И ещё вопрос: как хранить nanoid, например, в постгресе или в любой иной другой базе данных? Для uuid там нативная поддержка есть, а как быть с этим стандартом?

UPD: А, дошло. Имелась в виду длина строкового представления. Nanoid просто используют base64(или кастомный алфавит, что здорово), в отличие от uuid. Но в БД их всё равно придётся хранить как числовое поле по 16 байт, без магии.
Вот тут я споткнулся. Как при сравнимом порядке числа значимых бит он может короче?

Элементарно же, base64 вместо hex и отсутствие разделителей. По крайней мере, лично я стал бы задачу решать именно так. Разумеется, экономия достигается только в строковой форме, в форме же массива байт в обоих случаях их будет 16 штук.


Хранить в БД можно прямо в поле для UUID :-)

Версии 1 и 2 (время + идентификатор хоста) в теории надежна, но с практической точки зрения опасна, поскольку создает два неявных требования

ещё они могут приводить к нежелательной деанонимизации (напоминает как в ipv6-адрес сначала включили mac, а потом удаляли).


ИМХО вообще версии UUID стоит изучать только ради общего образования, на практике отличное от 4 не используется (а где используется — зря)


А еще, если у вас нет требования использовать именно стандарт UUID, то посмотрите в сторону nanoid, благо его поддержка уже реализована на 17 языках. Он в короче (21 байт вместо 36), надежнее (126 бит против 122), быстрее и гибче чем UUID.

всё-таки UUID — мейнстрим. он и в БД бинарно хранится, и в куче протоколов уже используется, …

на практике отличное от 4 не используется (а где используется — зря)

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

UFO just landed and posted this here
Это несколько не так.

Версии 1 и 2 имеют дополнительное поле Clock sequence, которое защищает от ненадёжного течения времени. Оно заполняется рандомом либо отслеживается в системе и инкрементируется, когда часы сдвигаются назад.
Что до ненадёжности MAC, то даже от этого в принципе есть кое-какое средство: купить отдельную сетевую карту от приличного производителя, записать её MAC, уничтожить её физически, генерить UUID с записанным MAC и за пределы генерящей системы его не сообщать. Конечно, затратно. Но с таким MAC, нормальными часами и Clock sequence версия 1 даёт хотя бы призрачный шанс сделать UUID действительно 100% уникальным для тех, кому это по странному ТЗ действительно надо.

Что касается версий 3 и 5, они, строго говоря, не для ввода UUID от пользователей или внешних источников. Они годны лишь для специальных сценариев – есть, представим, стандартная библиотека .NET, и надо каждому классу в ней назначить UUID. Причём чтоб он не менялся между версиями и правками. Руками создавать их и вставлять в код муторно, есть немаленький шанс ошибки copy+paste. Но можно из имён классов (вместе с namespace) их сгенерить именно в виде хеша. Хеш даст повторяемость. Использование стандартного UUID позволит их смешивать с редкими назначенными вручную (уже версии 4). Вероятность коллизий невелика, и от них даже можно защититься. Криптографически стойкая необратимость тут даром никому не нужна.

Так что на разные задачи подойдут разные версии. На типовой уникальный идентификатор – да, версия 4 лучше всего, качественный генератор случайных чисел – обязателен.
Версии 1 и 2 имеют дополнительное поле Clock sequence, которое защищает от ненадёжного течения времени.
Насколько защищают? Гарантированно защищают или «чуть-чуть» защищают? Можете предоставить качественное сравнение, скажем с UUID4?
купить отдельную сетевую карту от приличного производителя, записать её MAC, уничтожить её физически
Чем данный ритуал принципиально отличается от случайной генерации MAC, кроме того, что полагается на благоразумность производителя, требует финансовых затрат и бесмысленных усилий?

Каким образом такой подход защищает от ситуации, когда админ скопирует MAC системы, на которой выполняется генерация (или клонирует виртуальную машину)?
даёт хотя бы призрачный шанс сделать UUID действительно 100% уникальным для тех, кому это по странному ТЗ действительно надо
Меня, как архитектора, не устраивает «дает призначный шанс» от слова совсем.
Но можно из имён классов (вместе с namespace) их сгенерить именно в виде хеша.
UUID – universally unique identifier. Это значит, что он должен быть глобально уникальным, а не только в рамках некоторой системы. Хеш, взятый от простой строки, нельзя считать уникальным. Как планируете гарантировать глобальную уникальность?
Хеш даст повторяемость.
Подскажите, а зачем вам воспроизводимость идентификаторов? Точнее, зачем вам идентификаторы, которые необходимо воспроизводить? Можно ли значения, которые необходимо воспроизводить, называть идентификаторами?
Вероятность коллизий невелика
Какая?
и от них даже можно защититься
Если вы защищаетесь от коллизии идентификаторов, значит ваши идентификаторы – не идентификаторы, и в действительности ваши идентификаторы – это что-то другое. Тут уж выбирайте, либо «защита от коллизии UUID», либо «чтоб он не менялся между версиями и правками» (переименование класса – тоже правка).
Так что на разные задачи подойдут разные версии.
Только если задача поставлена как «использовать такую-то версию UUID». Во всех остальных случаях использование 4й версии наиболее оправдано. Хотя бы потому, что ее свойства поддаются количественным оценкам.
Версии 1 и 2 имеют дополнительное поле Clock sequence, которое защищает от ненадёжного течения времени.
Насколько защищают? Гарантированно защищают или «чуть-чуть» защищают? Можете предоставить качественное сравнение, скажем с UUID4?
Чем данный ритуал принципиально отличается от случайной генерации MAC, кроме того, что полагается на благоразумность производителя, требует финансовых затрат и бесмысленных усилий?

Каким образом такой подход защищает от ситуации, когда админ скопирует MAC системы, на которой выполняется генерация (или клонирует виртуальную машину)?
Смысл ритуала в том, чтобы завести систему, в памяти которой MAC, которого больше нигде нет. Вариант «админ скопирует» нужно давить организационно, для этого и условие «за пределы системы его не сообщать».

Если при этом в системе ещё и отследить любые переводы часов назад, и на каждом такому переводе увеличивать счётчик, помещаемый в Clock sequence, то получается UUID, которые действительно 100% не будут повторяться, пока счётчик не переполнится. В Clock sequence 14 бит.

Разумеется, это затратная штука. И, очевидно, уязвимая на практике. Простому разрабу обычно ничего этого не нужно. Но… жизнь сложная и разнообразная, и иногда попадаются, скажем так, особенные заказчики и ситуации. Поэтому, по-моему, не стоит забывать про такое использование версии 1, хотя бы чтобы не изобретать велосипеды, если вдруг.

Подскажите, а зачем вам воспроизводимость идентификаторов? Точнее, зачем вам идентификаторы, которые необходимо воспроизводить? Можно ли значения, которые необходимо воспроизводить, называть идентификаторами?
Зачем? Чтобы поместить в общее пространство идентификаторов UUID нечто частное, что обычно идентифицируется строками, так что у людей в сознании есть только строки. UUIDы при этом зачем-то технологически нужны, но получается так, что map строк в UUID некому отслеживать. А новые строки время от времени появляются.
UUID – universally unique identifier. Это значит, что он должен быть глобально уникальным, а не только в рамках некоторой системы. Хеш, взятый от простой строки, нельзя считать уникальным. Как планируете гарантировать глобальную уникальность?
Версия 4 не гарантирует глобальной уникальности, а даёт её только с некоторой вероятностью. Это как-то никому не мешает.
Вероятность коллизий невелика

Какая?
Обычная для хеша. Раз используется 122 бита от хеша, значит, 2^-61. Это хуже, чем версия 4, и обычно лучше к этому не прибегать. Это костыль, он несколько портит глобальную уникальность, но за счёт него можно состыковать сценарии и данные, с которыми иначе не получается.

И да, пока в тупик никто не загнал, пользуйтесь только версией 4. Я с этим не спорю, только хочу заметить, что у других есть свои, очень узкие и ненормальные сферы применения. Количественные оценки у всех версий есть, но с учётом затрат у версии 4 они почти всегда лучше.

А в чём прикол совершенно разные алгоритмы, обладающие совершенно разными характеристиками называть одним именем? Да ещё и тратить драгоценные биты на указание версии.

Итоговый формат полностью одинаковый. Видимо для удобства
А в случае с версией 1 часы обнулятся только в 3603 году. Так что если вы не планируете поддерживать работу своего сервиса ещё 1583 года, то вы в безопасности.
Можно спать спокойно
UFO just landed and posted this here
Я все равно так и не понял, что мешает дважды сделать Random(2^64-1), чтобы Random основывался на текущем показании системных часов.

В принципе ничего не мешает: вы получите 128 случайных бит )

Ну вот, и уникальность обеспечивается равномерным распределением вероятности по всему диапазону, разве нет?

Вот с распределением бит тут хорошо бы эксперта спросить :) вполне возможно что там не так всё рандомно, как хотелось бы)

Random не всегда криптостойкий. И не всегда можно его получить качественно.
Бывают быстрые компьютеры (или ОС с огрублением текущего времени, например, из-за Spectre или кластер компьютеров, работающих параллельно и с одним точным временем), которые в тот же момент времени могут сгенерировать несколько UUID — тогда Random будет одинаковый и них всех и UUID, соответственно, тоже.

С каких пор random, пусть даже не самый качественный, зависит от времени? Не надо создавать новый ГПСЧ для генерации каждого числа, вот и всё...

Я отвечал на конкретный комментарий
чтобы Random основывался на текущем показании системных часов.

И да, такое извращение реально бывает.
procedure Randomize;
var
  Counter: Int64;
begin
  if not QueryPerformanceCounter(Counter) then
    Counter := GetTickCount;
  RandomizeProc( (UInt64(Random(MAXINT)) shl 32) xor UInt64(Counter) );
end;

Delphi 10.3

А я генерировал uuid просто рандомом, не задавал биты версии. Надеюсь негативных последствий не будет?..

Вот блин..




А если серьезно?

В теории возможны ошибки валидации при передачи таких id во внешние системы, но я с таким не встречался.
Postgres например эти биты не проверяет.

Sign up to leave a comment.