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

124

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

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

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

Том Сэвидж
источник
30
Нет, если мы все продолжим нажимать кнопку перезагрузки на этом сайте: Wastaguid.info
mipadi
12
Я виню все свои ошибки в конфликтах GUID. Когда-нибудь это должно произойти, верно?
Майкл
8
Гораздо более вероятно, что акула с красивым рисунком в виде пледа упадет с неба и разнесет ваш компьютер на куски, поэтому я хотел бы заявить, что принятие мер предосторожности является более подходящим распределением ресурсов в рамках вашего общего снижения риска. план.
Дэвид Гладфельтер
4
@mipadi: отличная ссылка! Я могу просто представить себе, как какой-то разработчик где-то скулит: «Ууууис! Хватит тратить GUID! Мне они нужны
FrustratedWithFormsDesigner

Ответы:

362

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

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

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

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

А поскольку во Вселенной около 7 × 10 22 звезд и чуть менее 2 128 идентификаторов GUID, то на каждую звезду приходится примерно 4,86 ​​× 10 15 - почти пять квадриллионов - идентификаторов GUID. Если бы у каждой из этих звезд был мир с таким процветающим населением, как наш, то вокруг каждой звезды каждый человек или инопланетянин, который когда-либо жил, имел бы право на более сорока пяти тысяч GUID. Для каждого человека в истории на каждой звезде во Вселенной. Пространство GUID находится на том же уровне размеров, что и размер всей вселенной. Вам не о чем беспокоиться.

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

Антал Спектор-Забуски
источник
1
Кроме того, WolframAlpha сообщает, что на каждую ячейку каждого человека, который когда-либо жил, приходится 36 триллионов UUID. 10^14В вашем теле около клеток, а когда-либо жили 106,5 миллиарда человек. Или 2.385 * 10^23UUID за каждый цент государственного долга США.
new123456
5
Хотя цифры по-прежнему высоки, вероятность конфликта GUID превышает 50% при 2 ^ 64 GUID.
NullUserException
1
При 2 ^ 64 GUID это сократит числа до менее одной (0,00026) на звезду во Вселенной и 2 * 10 ^ (- 15) для каждого человека или пришельца, который когда-либо жил. Это все равно позволит получить более 170 миллионов GUID для каждого человека, который когда-либо жил, так что я думаю, что мы все еще в порядке.
NullUserException
12
Стоит отметить, что конфликт GUID также является проблемой, только если он находится в том же бизнес-пространстве. GUID, который я использую для идентификации компонента в программном обеспечении, может быть таким же, как GUID, который вы используете в строке базы данных в вашем собственном приложении, не вызывая никаких проблем,
Джеймс Торп,
1
Тот факт, что имеется 2 ^ 128 GUIDS, не имеет значения, и вы не «все еще хороши» при 50% вероятности столкновения, вы даже не хороши при 0,0000001%
BlackTigerX
40

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

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

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

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

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

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

Механическая улитка
источник
14
Так заканчивается вселенная ... Некоторые программисты просто предполагают, что их GUID всегда будут уникальными для их мега Звезды Смерти ...
pkr298
Поскольку UUID основаны на неслучайных данных, 36 лет - вам нужно беспокоиться только о каждой миллисекунде отдельно.
mjaggard
UUID @mjaggard основаны на случайных данных. Во всяком случае, любого современного вида.
Trejkaz 05
8

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

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

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

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

Марк Рэнсом
источник
5

В общем, да, можно с уверенностью предположить.

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

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

Haacked
источник
0

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

VeeArr
источник