Возможны ли конфликты GUID?

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

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

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

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

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

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

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

Изменить: исправлено, чтобы сказать 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-адресами, будут выдавать дублированные GUID в строго контролируемых условиях, особенно если, например, в здании отключается питание и они обе загружаются в одно и то же время.

Я предваряю это словами: «Я не занимаюсь сетями, поэтому я могу сделать после него совершенно бессвязные предложения».

Когда я работал в Университете штата Иллинойс, у нас было два настольных компьютера Dell, заказанных в разное время. Мы поместили первый в сеть, но когда мы попытались подключить вторую, мы начали получать сумасшедшие ошибки. После долгого устранения неполадок было определено, что обе машины выдавали один и тот же GUID (я не уверен, зачем, но это сделало их непригодными для использования в сети). Dell фактически заменила обе машины как неисправные.

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

Маловероятно, что вы столкнетесь с конфликтами GUID, если вы создаете их с помощью чего-то вроде NEWID()функции в SQL Server (хотя, конечно, возможно, как подчеркивали другие ответы). Одна вещь, на которую они не указали, - это то, что на самом деле весьма вероятно, что вы столкнетесь с коллизиями, если вы создаете GUID в JavaScript в браузерах в дикой природе. Мало того, что иногда возникают проблемы с RNG в разных браузерах, но я также сталкиваюсь с проблемами, когда пауки Google, кажется, кэшируют результаты таких функций, и в итоге неоднократно передавали один и тот же GUID нашим системам.

См. Различные ответы здесь для получения более подробной информации:

Коллизии при генерации UUID в JavaScript?