Безопасно ли считать, что GUID всегда будет уникальным?

Question

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

Бонусный вопрос

Оптимальный способ проверить GUID на уникальность? Фильтр Блума может быть?

Answer 1

Да, вы можете. Поскольку GUID длиной 128 битов, по общему признанию, возможна минутная вероятность столкновения, но слово «минута» далеко не достаточно сильное. Существует столько GUID , что если вы сгенерируете несколько триллионов из них случайным образом, вы все равно с большей вероятностью получите удар от метеорита, чем даже от одного столкновения (от Википедия ). И если вы генерируете их не случайно, а например , используя алгоритм MAC-адреса и отметки времени, то они также будут уникальными, поскольку MAC-адреса уникальны среди компьютеров и метки времени уникальны на вашем компьютере.

Редактировать 1: Чтобы ответить на ваш бонусный вопрос, оптимальный способ проверить набор GUID на уникальность - просто предположить, что все они уникальны. Зачем? Потому что, учитывая количество генерируемых вами GUID, вероятность столкновения GUID меньше, чем вероятность того, что космический луч чуть-чуть перевернется в памяти вашего компьютера и испортит ответ, полученный любым «точным» алгоритмом, который вам нужен. бежать. (См. этот ответ StackOverflow по математике.)

Существует огромное количество GUID . По словам Дагласа Адамса Автостопом по Галактике :

«Пространство, - говорит он, - велико. Действительно велико. Вы просто не поверите, насколько оно невероятно велико. Я имею в виду, что вы можете подумать, что это долгий путь к химику, но это просто арахис в космос, слушай ... "

И поскольку во вселенной имеется около 7 × 10 ^{22 * ​​1031 * звезд и чуть меньше 2 128 GUID, то их приблизительно 4,86 ​​× 10 15 - почти пять квадриллионов - ЖИДКОСТИ для каждой звезды. Если бы у каждой из этих звезд был мир с таким же процветающим населением, как у нас, то вокруг каждой звезды} каждый человек или инопланетянин, который когда-либо жил , имел бы право на более чем сорок пять тысяч GUID. Для каждого человека в истории на каждой звезде во вселенной. Пространство GUID находится на том же уровне огромности, что и размер всей вселенной. Вам не нужно беспокоиться.

( Редактировать 2: Размышляя об этом: вау. Я не осознал себя , что это значит. Пространство GUID непостижимо велико. Я в восторге от она.)

Answer 2

Краткий ответ: для практических целей да.

Однако вы должны рассмотреть парадокс дня рождения!

Я рассчитал несколько репрезентативных вероятностей столкновения. С 122-битными UUID, указанными в статье Википедии , вероятность коллизии равна 1/2, если вы генерируете как минимум 2.71492e18 UUID. С 10 ^ 19 UUID вероятность составляет 0,999918. С 10 ^ 17 UUID, 0,000939953.

Некоторые цифры для сравнения можно найти в Википедии. Таким образом, вы можете безопасно назначить UUID для каждого живущего человека, каждой галактики в наблюдаемой вселенной, каждой рыбы в океане и каждого отдельного муравья на земле. Однако , столкновения почти вероятны, если вы генерируете UUID для каждого транзистора, который человечество производит за год, каждого насекомого на Земле, каждой песчинки на Земле, каждой звезды в наблюдаемой вселенной или чего-то большего. 1014 *

Если вы генерируете 1 миллиард UUID в секунду, потребуется около 36 лет , чтобы получить вероятность столкновения в 10%.

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

Answer 3

Анализ возможности столкновения доступен в Википедии: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

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

Существует также возможность ошибки в коде генератора GUID; в то время как шансы невелики, они, вероятно, выше, чем шансы столкновения, основанные на математике.

Может пригодиться фильтр Блума; он может быстро сказать, является ли GUID уникальным, но есть вероятность ложного указания на столкновение. Альтернативный метод, если вы тестируете пакет за раз, это отсортировать пакет и сравнить каждый последующий элемент.

Answer 4

В общем, да, это безопасно предположить.

Если ваш генератор GUID действительно случайный, вероятность столкновения в пределах 1000 GUID чрезвычайно мала.

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

Answer 5

Обычно это довольно безопасное предположение.

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Является ли GUID уникальным в 100% случаев?

Answer 6

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