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

Question

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

Answer 1

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

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

Answer 2

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

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

...

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

...

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

Answer 3

Кто-нибудь может поделиться опытом?

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

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

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

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

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

---

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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

Answer 8

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

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

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

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

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

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

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

Answer 9

Я не эксперт, но так как все говорили о теории, я думаю, что могу кое-что добавить к обсуждению, приведя практический пример. В моей базе данных около 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-0ba00060fe64"

"be87a209-2114-45b3-9d5a-86d00060fe64"

"4a8a74a6-e972-4069-B480-bdea1177b21f"

"12fb4958-bee2-4c89-8cf8-edea1177b21f"

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

Answer 10

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