Насколько хорош UUID.randomUUID в Java?

311

Я знаю, что рандомизированные UUID имеют очень, очень, очень низкую вероятность коллизии в теории, но мне интересно на практике, насколько хороши Java с randomUUID()точки зрения отсутствия коллизий? У кого-нибудь есть опыт, которым можно поделиться?

Alvin
источник
10
По моему опыту, я никогда не видел столкновения ;-)
Тило
4
Алгоритмы указаны в RFC1422: ietf.org/rfc/rfc4122.txt
skaffman
8
@skaffman: RFC абсолютно ничего не говорит об алгоритме, используемом для генерации случайных цифр.
Майкл Боргвардт
4
Так как это более открытый вопрос, я думаю, я не буду отмечать любой ответ как правильный ответ; вместо этого я дам один голос на каждый из ответов, которые я считаю хорошими :)
Элвин,
5
Из википедии: ... Другими словами, только после генерирования 1 миллиарда UUID каждую секунду в течение следующих 100 лет вероятность создания только одного дубликата составит около 50%.
MaVRoSCy

Ответы:

168

Использует UUID java.security.SecureRandom, который должен быть «криптографически сильным». Хотя фактическая реализация не указана и может варьироваться между JVM (это означает, что любые конкретные высказывания действительны только для одной конкретной JVM), она требует, чтобы выходные данные проходили статистический тест генератора случайных чисел.

Реализация всегда может содержать скрытые ошибки, которые разрушают все это (см. Ошибка генерации ключа OpenSSH), но я не думаю, что есть какая-то конкретная причина для беспокойства по поводу случайности Java UUID.

Майкл Боргвардт
источник
34
«Реализация всегда может содержать тонкие ошибки ...» - или (надевая шляпу из фольги) ... преднамеренные тонкие недостатки. <:-)
Стивен С,
25
Криптографическая стойкость совершенно не имеет отношения к вопросу о столкновениях.
OSA
14
@osa: отсутствие коллизий (больше, чем следует ожидать от идеальной случайности) является в значительной степени самым низким требованием к качеству для ГСЧ, в то время как криптографическая стойкость является самой высокой. Другими словами, криптографически сильный ГСЧ определенно не вызовет большего количества столкновений, чем ожидалось.
Майкл Боргвардт
3
Тем не менее, может быть полезно отметить, что если вы, например, запустите JVM, производящую UUID внутри blogs.vmware.com/cto/… , вы, вероятно, получите много-много коллизий. Все программные RNG являются PRNG, и в конечном итоге они так же хороши, как и их источник энтропии; два PRNG, которые будут заполнены одинаково, также будут вести себя одинаково, и это может происходить на удивление часто с согласованными, точно дублирующимися настройками сервера и процедурами запуска.
user508633 25.09.15
@ user508633: Я действительно ожидал бы получить 100% -ную частоту коллизий в этом конкретном случае, но это действительно очень специфический случай, который выходит далеко за рамки «согласованных, точно дублированных настроек сервера и процедур запуска». Я почти уверен, что вы не получите никакого увеличения частоты столкновений, если просто клонируете виртуальную машину и запускаете ее нормально. Самосев SecureRandom изо всех сил пытается получить реальную энтропию, вплоть до блокировки выполнения, если он не может ее найти: seancassidy.me/wiggle-the-mouse-to-fix-the-test.html
Michael Боргвардт
114

У Википедии очень хороший ответ http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

количество случайных UUID версии 4, которые должны быть сгенерированы для того, чтобы иметь 50% -ную вероятность хотя бы одного столкновения, составляет 2,71 квинтиллиона, рассчитывается следующим образом:

...

Это число эквивалентно генерации 1 миллиарда UUID в секунду в течение примерно 85 лет, и файл, содержащий такое количество UUID, по 16 байт на UUID, будет примерно 45 эксабайт, во много раз больше, чем самые большие базы данных, которые в настоящее время существуют, порядка сотен петабайт.

...

Таким образом, чтобы вероятность дублирования составляла один на миллиард, необходимо сгенерировать 103 триллиона UUID версии 4.

Шеки
источник
56
Я также цитирую на этой странице: «Вероятность одного дубликата составила бы около 50%, если бы каждый человек на земле имел 600 миллионов UUID».
Джефф Аксельрод
24
Это верно только для истинной случайности, а не для псевдослучайных чисел, таких как javas UUID.
Маркус
9
@ Маркус: совершенно не так. Вероятность столкновений для хороших псевдослучайных ГСЧ, особенно криптографически сильных, ничем не отличается от «истинной» случайности.
Майкл Боргвардт
6
@Eric - я думаю, что ты обязан поддержать свое утверждение. FWIW, единственные сценарии, которые я могу придумать, где UUID типа 4 будут сталкиваться чаще, что теория вероятности говорит, что они должны быть: 1) плохой источник криптографических случайных чисел, или 2) библиотека UUID, которая была скомпрометирована.
Стивен С
13
Это не отвечает на заданный вопрос. Вопрос заключается в качестве случайности в Java UUID.randomUUID(), а не в теоретических шансах для данного идеального генератора случайных чисел.
Кратенко
69

У кого-нибудь есть опыт, которым можно поделиться?

Существуют 2^122возможные значения для UUID типа 4. (В спецификации сказано, что вы теряете 2 бита для типа и еще 4 бита для номера версии.)

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

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

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

Однако если вы используете JVM с «сломанным» генератором криптослучайных чисел, все ставки отключены. (И это может включать некоторые обходные пути для проблем «нехватки энтропии» в некоторых системах. Или вероятность того, что кто-то возился с вашей JRE, либо в вашей системе, либо в восходящем направлении.)


1 - Предполагая, что вы использовали «некое двоичное btree», как предложено анонимным комментатором, каждому UUID потребуются O(NlogN)биты оперативной памяти для представления Nразличных UUID, предполагающих низкую плотность и случайное распределение битов. Теперь умножьте это на 1 000 000 и количество секунд, для которых вы собираетесь запустить эксперимент. Я не думаю, что это практично в течение периода времени, необходимого для проверки на столкновения высококачественного ГСЧ. Даже с (гипотетическими) умными представлениями.

Стивен С
источник
4
«(И чтобы обнаружить дубликат, вам нужно решить проблему сравнения 1 миллиона новых UUID в секунду со всеми ранее сгенерированными UUID!)» - эта часть относительно проста, если вы сохранили свои uuids в некоторых вид бинарной древовидной структуры, это будет просто один спуск дерева на новый uuid. Вам не нужно будет фактически сравнивать его отдельно со всеми ранее сгенерированными uuids.
user467257
20

Я не эксперт, но я бы предположил, что достаточно умные люди смотрели на генератор случайных чисел Java на протяжении многих лет. Следовательно, я бы также предположил, что случайные UUID хороши. Таким образом, у вас должна быть теоретическая вероятность коллизии (которая составляет около 1: 3 × 10 ^ 38 для всех возможных UUID. Кто-нибудь знает, как это меняется только для случайных UUID? Это 1/(16*4)из вышеперечисленного?)

Из моего практического опыта я никогда не видел каких-либо столкновений. Я, наверное, отрасту удивительно длинную бороду в день, когда получу свою первую;)

sfussenegger
источник
10
Из википедии: ... Другими словами, только после генерирования 1 миллиарда UUID каждую секунду в течение следующих 100 лет вероятность создания только одного дубликата составит около 50%.
MaVRoSCy
1
На самом деле Википедия говорит, что это в течение следующих 85 лет ... Я говорю, не рассчитывайте на это, кто-то где-то сгенерировал тот же UUID, что и вы
smac89
12

У бывшего работодателя у нас была уникальная колонка, в которой содержался случайный uuid. Мы получили столкновение в первую неделю после его развертывания. Конечно, шансы низкие, но они не равны нулю. Вот почему Log4j 2 содержит UuidUtil.getTimeBasedUuid. Он будет генерировать UUID, который является уникальным в течение 8 925 лет, при условии, что вы не генерируете более 10 000 UUID / миллисекунду на одном сервере.

rgoers
источник
2
Да. Но вопрос задается о случайных (то есть тип 4) UUID.
Стивен С
1
Он спрашивает о вероятности столкновения. Подразумевается, что он хочет быть уверенным, чтобы избежать их.
rgoers
1
(Скорее всего, столкновение произошло из-за разбитого источника случайности для посева PRNG. Я подумал, что вполне возможно, что это произошло из-за чистой случайности.)
Стивен С.
9

Первоначальная схема генерации UUID состояла в том, чтобы объединить версию UUID с MAC-адресом компьютера, который генерирует UUID, и с числом интервалов в 100 наносекунд с момента принятия григорианского календаря на Западе. Представляя одну точку в пространстве (компьютер) и время (количество интервалов), вероятность столкновения значений практически равна нулю.

Alex2Ustas
источник
1
Это объяснение заставляет меня оптимистично не видеть столкновения на практике. Можете ли вы указать какую-либо ссылку на это утверждение (некоторый исходный код был бы еще лучше)?
Драган Марьянович
Нашел это в спецификации ietf.org/rfc/rfc4122.txt . Тем не менее было бы здорово увидеть реализацию.
Драган Марьянович
1
Однако эта схема не является той, что реализует Java. Java реализует UUID типа 4, который является чисто случайным и не включает MAC-адрес или время. Кстати, поскольку сейчас существует много физических и виртуальных устройств, где вы можете выбрать свой MAC-адрес, оригинальный алгоритм не гарантирует уникальности.
Сорен Бойсен
8

Во многих ответах обсуждается, сколько UUID должно быть сгенерировано, чтобы достичь 50% вероятности коллизии. Но вероятность столкновения 50%, 25% или даже 1% бесполезна для приложения, где столкновение должно быть (практически) невозможно.

Программисты обычно отклоняют как «невозможные» другие события, которые могут и происходят?

Когда мы записываем данные на диск или в память и снова читаем их, мы считаем само собой разумеющимся, что данные верны. Мы полагаемся на исправление ошибок устройства, чтобы обнаружить любое повреждение. Но вероятность необнаруженных ошибок на самом деле составляет около 2 -50 .

Разве не имеет смысла применять подобный стандарт к случайным UUID? Если вы это сделаете, вы обнаружите, что «невозможное» столкновение возможно в наборе около 100 миллиардов случайных UUID (2 36,5 ).

Это астрономическое число, но такие приложения, как поэлементное выставление счетов в национальной системе здравоохранения или регистрация данных высокочастотного датчика на большом множестве устройств, могут определенно выйти за эти пределы. Если вы пишете следующее Руководство автостопом по Галактике, не пытайтесь назначать UUID для каждой статьи!

Эриксон
источник
Для сравнения, шанс выиграть джекпот в Powerball составляет 1 к 300 миллионам, но продажи билетов от 10 до 20 миллионов являются типичными. Дело в том, что многие люди определяют «невозможное» как нечто меньшее, чем один шанс из сотен миллионов.
Эриксон
4

Так как большинство ответов были сосредоточены на теории, я думаю, что могу что-то добавить к обсуждению, дав практический тест, который я сделал. В моей базе данных около 4,5 миллионов UUID, сгенерированных с помощью Java 8 UUID.randomUUID (). Следующие из них - только некоторые, которые я узнал:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb


b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64


4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

Если бы это было действительно случайно, вероятность наличия подобных идентификаторов UUID была бы значительно ниже (см. Редактирование), поскольку мы рассматриваем только 4,5 миллиона записей. Так что, хотя эта функция хороша, с точки зрения отсутствия коллизий, для меня она не кажется такой хорошей, как это было бы в теории.

Редактировать :

Многие люди, похоже, не понимают этого ответа, поэтому я проясню свою точку зрения: я знаю, что сходство «мало» и далеко не полное столкновение. Однако я просто хотел сравнить UUID.randomUUID () в Java с генератором истинных случайных чисел, что является актуальным вопросом.

В истинном генераторе случайных чисел вероятность возникновения последнего случая будет около = 0,007%. Поэтому я думаю, что мой вывод верен.

Формула объясняется в этой статье вики en.wikipedia.org/wiki/Birthday_problem

Андре Пинейро
источник
6
Это неправда. Подобные сходства могут возникнуть даже при использовании генератора истинных случайных чисел на 4.5M единиц. Сходства между UUID, которые вы дали, невелики и слишком далеки от полного столкновения.
user3711864
Я полностью согласен с вами, что сходство «мало» и далеко не полное столкновение. Однако я просто хотел сравнить UUID.randomUUID () в Java с генератором истинных случайных чисел (это вопрос). С помощью некоторых вычислений мы можем видеть, что в истинном генераторе случайных чисел вероятность возникновения последнего случая будет около 1-е ^ (- 4500000 ^ 2 / (2 * 36 ^ 11)) = 0,007% = 1 в 13k. Мне бы очень повезло :)
Андре Пинейро
1
С 4,5 миллиона единиц и 1 в 13k шанс, что не частичное столкновение подобное было бы ожидать 346 раз?
Бен Ли
Нет @BenLee, я рассчитал вероятность того, что это событие произойдет, учитывая, что у нас есть 4,5 миллиона товаров. Это не шанс 1 к 13 КБ для каждого предмета. Формула, которую я использовал, может быть найдена в этой статье вики en.wikipedia.org/wiki/Birthday_problem
Андре Пиньейру
2
Каковы были ваши ожидания? Подобное не то же самое, не так ли?
Корай Тугай
3

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

документ: http://tools.ietf.org/html/rfc4122

Тип 1: не реализовано. Столкновение возможно, если UUID генерируется в тот же момент. impl может быть искусственно синхронизирован, чтобы обойти эту проблему.

Тип 2: никогда не видеть реализацию.

Тип 3: хэш md5: возможна коллизия (128 бит-2 технических байтов)

Тип 4: случайный: возможно столкновение (как лотерея). обратите внимание, что в jdk6 не используется «истинное» безопасное случайное число, поскольку разработчик не выбирает алгоритм PRNG, и вы можете заставить систему использовать «плохой» алгоритм PRNG. Так что ваш UUID предсказуем.

Тип 5: хэш sha1: не реализовано: возможно столкновение (160 бит-2 технических байтов)

Giher
источник
4
Вероятность выиграть в лотерею может быть один к 10 или 100 миллионам (10 ^ 7 или 10 ^ 8) или что-то в этом роде. Вероятность столкновения со 128-битным случайным числом составляет 3,4 * 10 ^ 28. Дайте мне лотерейный билет в любое время!
Стивен С.
0

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

Afsar
источник