Возможны ли коллизии GUID?
https://stackoverflow.com/questions/184869
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я работаю над базой данных в SQL Server 2000, которая использует GUID для каждого пользователя, который использует приложение, к которому он привязан. Каким-то образом два пользователя оказались с одинаковым GUID. Я знаю, что Microsoft использует алгоритм для генерации случайного идентификатора GUID, который имеет крайне низкую вероятность возникновения коллизий, но возможна ли коллизия?
Решение
В основном нет. Я думаю, что кто-то испортил вашу базу данных. В зависимости от GUID версии, которую вы используете, значение может быть либо уникальным (для таких вещей, как GUID версии 1), либо одновременно уникальным и непредсказуемым (для таких вещей, как GUID версии 4). Реализация SQL Server для их функции NEWID (), похоже, использует 128-битное случайное число, поэтому вы не столкнетесь с коллизией.
Чтобы с вероятностью 1% столкнуться, вам нужно сгенерировать около 2 600 000 000 000 000 000 GUID.
Другие советы
В основном они невозможны! , шансы астрономически низкие .
Но ... Я единственный человек в мире, о котором я знаю, у которого было когда-то столкновение с GUID (да!).
И я в этом уверен, и это не было ошибкой.
Как это произошло, в небольшом приложении, которое работало на Pocket PC, в конце операции должна быть выдана команда с сгенерированным GUID. Команда после того, как она была выполнена на сервере, была сохранена в таблице команд на сервере вместе с датой выполнения. Однажды, когда я отлаживал, я выполнил команду модуля (с присоединенным вновь сгенерированным GUID), и ничего не произошло. Я сделал это снова (с тем же guid, потому что guid был сгенерирован только один раз в начале операции), и снова, и ничего, наконец, пытаясь выяснить, почему команда не выполняется, я проверил таблицу команд, и тот же GUID, что и текущий, был вставлен 3 недели назад. Не веря этому, я восстановил базу данных из резервной копии за 2 недели, и гид был там. Проверив код, новый guid был сгенерирован заново, без сомнения. Пау, столкновение с гидом, произошло только один раз, но я действительно хотел бы выиграть в лотерею, шанс больше :).
Изменить: есть некоторые факторы, которые могли бы значительно увеличить вероятность этого, приложение работало на эмуляторе PocketPC, а эмулятор имеет функцию сохранения состояния, которая означает, что каждый раз, когда состояние восстанавливается по местному времени также восстанавливается, и guid основан на внутреннем таймере .... также алгоритм генерации guid для компактной среды может быть менее полным, чем, например, COM ...
Теоретически они возможны, но с возможными числами 3.4E38, если вы создаете десятки триллионов GUID в год, вероятность наличия одного дубликата составляет 0,00000000006 ( Source ).
Если бы два пользователя получили один и тот же GUID, я бы поспорил, что в программе есть ошибка, которая приводит к копированию или обмену данными.
Сначала давайте рассмотрим вероятность столкновения двух GUID. Это не так, как утверждали другие ответы, 1 к 2 ^ 128 (10 ^ 38) из-за дня рождения парадокса , что означает, что для 50% вероятности столкновения двух GUID вероятность на самом деле равна 1 к 2 ^ 64 (10 ^ 19), что намного меньше. Однако это все еще очень большое число, и поэтому вероятность столкновения при условии использования разумного количества идентификаторов GUID невелика.
Также обратите внимание, что GUID не содержат метки времени или MAC-адреса, как многие, похоже, считают. Это было верно для vID GUID, но теперь используются v4 GUID, которые просто являются псевдослучайным числом что означает, что вероятность столкновения, возможно, выше, потому что они больше не являются уникальными для времени и машины.
Поэтому, по сути, ответ - да, возможны столкновения. Но они крайне маловероятны.
Изменить: исправлено: 2 ^ 64
Вероятность столкновения двух случайных идентификаторов GUID (~ 1 из 10 ^ 38) ниже, чем вероятность не обнаружить поврежденный пакет TCP / IP (~ 1 из 10 ^ 10). http: //wwwse.inf.tu-dresden .de / data / courses / SE1 / SE1-2004-lec12.pdf , стр. 11. Это также относится к дисководам, дисководам для компакт-дисков и т. д. ...
GUID являются статистически уникальными, а данные, которые вы читаете из БД, являются только статистически правильными.
Я бы посоветовал бритва Оккама в этом случае. Это невероятно маловероятно, что у вас есть коллизия GUID. Скорее всего, у вас ошибка или кто-то вмешивается в ваши данные.
См. глобально уникальный идентификатор Википедии. Есть несколько способов создания GUID. Очевидно старый (?) Способ использовал адрес Mac, временную метку до очень короткого устройства и уникальный счетчик (для управления быстрыми поколениями на одном компьютере), поэтому дублирование их практически невозможно. Но эти GUID были отброшены, потому что их можно было использовать для отслеживания пользователей ...
Я не уверен в новом алгоритме, используемом Microsoft (статья говорит, что последовательность GUID может быть предсказана, похоже, они больше не используют временную метку? В статье Microsoft, указанной выше, говорится что-то еще ...).
Теперь GUID тщательно спроектированы, чтобы быть по имени уникальными для всего мира, поэтому я рискну, что это невозможно или очень очень маловероятно. Я бы посмотрел в другом месте.
Две машины Win95, имеющие карты Ethernet с дублирующимися MAC-адресами, будут выдавать дубликаты GUIDS в строго контролируемых условиях, особенно если, например, в здании отключается питание, и они обе загружаются в одно и то же время.
Я знаю, что людям нравится приятный ответ, что GUID являются волшебными и гарантированно уникальными, но в действительности большинство GUID являются просто 121-битными случайными числами (семь битов теряются при форматировании). Если вам неудобно использовать большое случайное число, тогда вам неудобно использовать GUID.
Может ли код, используемый для генерации GUID, содержать ошибку? Да, конечно, это возможно. Но ответ такой же, как и в случае ошибки компилятора - ваш собственный код на несколько порядков более вероятен с ошибкой, поэтому посмотрите сначала.
Конечно, это возможно .... Возможно? Вряд ли, но это возможно.
Помните, что один и тот же компьютер генерирует каждый GUID (сервер), поэтому большая часть "случайности" это основано на машинной информации, потеряно.
Просто ради ухмылки попробуйте следующий скрипт ... (работает на SQL 2005, не уверен насчет 2000)
declare @table table
(
column1 uniqueidentifier default (newid()),
column2 int,
column3 datetime default (getdate())
)
declare @counter int
set @counter = 1
while @counter <= 10000
begin
insert into @table (column2) values (@counter)
set @counter = @counter + 1
end
select * from @table
select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2
Повторное выполнение (занимает менее секунды) приводит к довольно широкому диапазону от первого выбора, даже с ОЧЕНЬ коротким промежутком времени. Пока что второй выбор ничего не дал.
Невозможно, если у пользователей разные машины с сетевыми картами, и даже если нет, это все еще крайне незначительный, почти теоретический риск.
Лично я бы посмотрел в другом месте, так как это скорее ошибка, чем конфликт GUID ...
Если, конечно, вы не отрежете биты от GUID, чтобы сделать его короче.
Конечно, это возможно, и, возможно, даже вероятно. Это не так, как каждый GUID находится в случайной части возможного пространства номеров. В случае, если два потока попытались сгенерировать один одновременно, за исключением некоторой централизованной функции GUID с семафором вокруг них, они могли бы получить одно и то же значение.
Я предвожу это словами "Я не сетевой человек, поэтому я могу сделать совершенно несогласованные предложения после".
Когда я работал в Университете штата Иллинойс, у нас было два настольных компьютера Dell, заказанных в разное время. Мы поместили первый в сеть, но когда мы попытались поместить второй в сеть, мы начали получать сумасшедшие ошибки. После долгих поисков и устранения проблем было установлено, что обе машины производили один и тот же GUID (я точно не знаю, зачем, но это сделало их обе непригодными для использования в сети). Dell фактически заменила обе машины как дефектные.
Маловероятно, что вы столкнетесь с коллизиями GUID, если будете генерировать их с помощью чего-то вроде функции NEWID () в SQL Server (хотя, конечно, это возможно, как подчеркивалось в других ответах) , Одна вещь, на которую они не указали, заключается в том, что на самом деле вполне вероятно, что вы столкнетесь с коллизиями, если будете генерировать GUID в JavaScript в браузерах в дикой природе. Мало того, что иногда возникают проблемы с ГСЧ в разных браузерах, но я также сталкивался с проблемами, когда пауки Google, похоже, кэшировали результаты подобных функций и в итоге неоднократно передавали один и тот же GUID в наши системы.
Для получения более подробной информации смотрите различные ответы здесь:
