Возможны ли коллизии GUID? - PullRequest
108 голосов
/ 09 октября 2008

Я работаю над базой данных в SQL Server 2000, которая использует GUID для каждого пользователя, который использует приложение, к которому он привязан. Каким-то образом два пользователя оказались с одинаковым GUID. Я знаю, что Microsoft использует алгоритм для генерации случайного идентификатора GUID, который имеет крайне низкую вероятность возникновения конфликтов, но возможен ли конфликт еще?

Ответы [ 16 ]

121 голосов
/ 09 октября 2008

В основном нет. Я думаю, что кто-то испортил вашу базу данных. В зависимости от GUID версии, которую вы используете, значение может быть либо уникальным (для таких вещей, как GUID версии 1), либо одновременно уникальным и непредсказуемым (для таких вещей, как GUID версии 4). Реализация SQL Server для их функции NEWID (), по-видимому, использует 128-битное случайное число, поэтому вы не столкнетесь с коллизией.

Для вероятности столкновения в 1% вам потребуется сгенерировать около 2 600 000 000 000 000 000 GUID.

92 голосов
/ 09 октября 2008

В основном они невозможны! , шансы астрономически низкие .

Но ... Я единственный человек в мире, о котором я знаю, у которого когда-то было столкновение с GUID (да!).

И я в этом уверен, и это не было ошибкой.

Как это произошло, в небольшом приложении, которое работало на Pocket PC, в конце операции должна быть выдана команда с сгенерированным GUID. Команда после того, как она была выполнена на сервере, была сохранена в таблице команд на сервере вместе с датой выполнения. Однажды, когда я отлаживал, я выполнил команду модуля (с присоединенным вновь сгенерированным GUID), и ничего не произошло. Я сделал это снова (с тем же guid, потому что guid был сгенерирован только один раз в начале операции), и снова, и ничего, наконец, пытаясь выяснить, почему команда не выполняется, я проверил таблицу команд, и тот же GUID, что и текущий, был вставлен 3 недели назад. Не веря этому, я восстановил базу данных из резервной копии за 2 недели, и гид был там. Проверив код, новый guid был сгенерирован заново, без сомнения. Пау, столкновение с гидом, произошло только один раз, но я действительно хотел бы выиграть в лотерею, шанс больше :).

Изменить: есть некоторые факторы, которые могли бы значительно увеличить вероятность этого, приложение работало на эмуляторе PocketPC, и эмулятор имеет функцию сохранения состояния, что означает, что каждый раз, когда состояние восстанавливается по местному времени также восстанавливается, и guid основан на внутреннем таймере .... также алгоритм генерации guid для компактной среды может быть менее полным, чем, например, COM ...

28 голосов
/ 09 октября 2008

Они теоретически возможны, но с возможными числами 3.4E38, если вы создаете десятки триллионов идентификаторов GUID в год, вероятность иметь один дубликат составляет 0,00000000006 ( Источник ).

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

19 голосов
/ 09 октября 2008

Сначала давайте посмотрим на вероятность столкновения двух GUID. Это не так, как утверждали другие ответы, 1 из 2 ^ 128 (10 ^ 38) из-за парадокса дня рождения , что означает, что для 50% вероятности столкновения двух GUID вероятность фактически равна 1 в 2 ^ 64 (10 ^ 19), что намного меньше. Однако это все еще очень большое число, и поэтому вероятность столкновения при условии использования разумного количества идентификаторов GUID невелика.

Также обратите внимание, что GUID не содержат метки времени или MAC-адреса, как многие, похоже, считают. Это было верно для vID GUID, но теперь используются v4 GUID, которые являются просто псевдослучайным числом , что означает, что вероятность столкновения, возможно, выше, потому что они больше не уникальны для времени и машины.

Так что, по сути, ответ - да, возможны столкновения. Но они крайне маловероятны.

Редактировать: исправлено: 2 ^ 64

17 голосов
/ 09 октября 2008

Вероятность столкновения двух случайных идентификаторов GUID (~ 1 из 10 ^ 38) ниже, чем вероятность не обнаружить поврежденный пакет TCP / IP (~ 1 из 10 ^ 10). http://wwwse.inf.tu -dresden.de / data / courses / SE1 / SE1-2004-lec12.pdf , стр. 11. Это также относится к дискам, дискам для компакт-дисков и т. Д. ...

GUID являются статистически уникальными, а данные, которые вы читаете из БД, являются только статистически правильными.

13 голосов
/ 09 октября 2008

Я бы посчитал бритвой Оккама хорошим руководством в этом случае. Это невероятно маловероятно, что у вас есть коллизия GUID. Скорее всего, у вас есть ошибка или кто-то вмешивается в ваши данные.

11 голосов
/ 09 октября 2008

См. Статью Глобального уникального идентификатора * Википедии . Есть несколько способов создания GUID. Очевидно старый (?) Способ использовал адрес Mac, временную метку до очень короткого устройства и уникальный счетчик (для управления быстрыми поколениями на одном компьютере), поэтому дублирование их практически невозможно. Но эти GUID были отброшены, потому что они могли использоваться для отслеживания пользователей ...

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

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

9 голосов
/ 16 октября 2008

Две машины Win95, имеющие карты Ethernet с дублирующимися MAC-адресами, будут выдавать дубликаты GUIDS в строго контролируемых условиях, особенно если, например, в здании отключается питание, и они обе загружаются в одно и то же время.

4 голосов
/ 27 октября 2010

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

3 голосов
/ 09 октября 2008

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

...