Является ли GUID уникальным в 100% случаев?
Является ли GUID уникальным в 100% случаев?
Он останется уникальным для нескольких потоков?
25 ответов
Хотя каждый сгенерированный GUID не гарантированно является уникальным, общее количество уникальных ключей (2128 или 3,4 × 1038) настолько велико, что вероятность того, что одно и то же число будет сгенерировано дважды, очень мала. Например, рассмотрим наблюдаемую вселенную, которая содержит около 5 × 1022 звезд; тогда каждая звезда может иметь 6,8 × 1015 универсально уникальных GUID.
Из Википедии.
Это несколько хороших статей о том, как создается GUID (для.NET) и как вы можете получить такое же руководство в правильной ситуации.
https://ericlippert.com/2012/04/24/guid-guide-part-one/
Если вы боитесь одинаковых значений GUID, поместите два из них рядом друг с другом.
Guid.NewGuid().ToString() + Guid.NewGuid().ToString();
Если вы слишком параноик, тогда поставьте три.
Простой ответ - да.
Раймонд Чен (Raymond Chen) написал отличную статью о GUID и о том, почему подстроки GUID не гарантируются уникальными. В этой статье подробно рассказывается о том, как генерируются идентификаторы GUID и данные, которые они используют для обеспечения уникальности, что должно объяснить, почему они таковы:-)
Как примечание, я играл с томами GUID в Windows XP. Это очень непонятная структура разделов с тремя дисками и четырнадцатью томами.
\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
| | | | |
| | | | +-- 6f = o
| | | +---- 69 = i
| | +------ 72 = r
| +-------- 61 = a
+---------- 6d = m
Дело не в том, что GUID очень похожи, а в том, что во всех GUID есть строка "mario". Это совпадение или есть объяснение этому?
Теперь при поиске в части 4 в GUID я обнаружил около 125 000 совпадений с GUID тома.
Вывод: когда речь идет о томе GUID, они не так уникальны, как другие GUID.
Этого не должно быть. Однако, когда.NET находится под большой нагрузкой, возможно получить дубликаты руководств. У меня есть два разных веб-сервера, использующие два разных сервера SQL. Я пошел, чтобы объединить данные и обнаружил, что у меня было 15 миллионов направляющих и 7 дубликатов.
Да, GUID всегда должен быть уникальным. Он основан как на аппаратном обеспечении, так и на времени, плюс несколько дополнительных битов, чтобы убедиться, что он уникален. Я уверен, что теоретически возможно получить два одинаковых, но крайне маловероятно в реальном сценарии.
Вот отличная статья Раймонда Чена о гидах:
https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx
Направляющие статистически уникальны. Шансы двух разных клиентов, генерирующих один и тот же Guid, бесконечно малы (при условии отсутствия ошибок в коде, генерирующем Guid). Вы можете также беспокоиться о сбое вашего процессора из-за космического луча и принятия решения, что 2+2=5 сегодня.
Несколько потоков, выделяющих новые направляющие, получат уникальные значения, но вы должны понимать, что вызываемая вами функция является поточно-ориентированной. В какой среде это?
Эрик Липперт написал очень интересную серию статей о GUID.
В мире насчитывается порядка 230 персональных компьютеров (и, конечно, множество портативных устройств или вычислительных устройств, не относящихся к ПК, которые имеют более или менее одинаковые уровни вычислительной мощности, но давайте их игнорируем). Давайте предположим, что мы поставили все эти компьютеры в мире на задачу генерации GUID; если каждый из них может генерировать, скажем, 220 GUID в секунду, то примерно через 272 секунды - сто пятьдесят триллионов лет - у вас будет очень высокая вероятность возникновения коллизии с вашим конкретным GUID. И шансы столкновения становятся довольно хорошими уже через тридцать триллионов лет.
Теоретически нет, они не уникальны. Можно генерировать идентичный гид снова и снова. Однако вероятность того, что это произойдет, настолько мала, что можно предположить, что они уникальны.
Я читал ранее, что шансы настолько малы, что вам действительно нужно беспокоиться о чем-то другом - например, о том, что ваш сервер самопроизвольно сгорает, или других ошибках в вашем коде. То есть, предположите, что он уникален и не встраивайте какой-либо код для "отлова" дубликатов - тратьте свое время на что-то более вероятное (то есть на что - то еще).
Я попытался описать полезность GUID для аудитории моего блога (нетехнических членов семьи). Оттуда (через Википедию) вероятность создания дубликата GUID:
- 1 в 2 ^ 128
- 1 на 340 ундециллионов (не волнуйтесь, ундециллион нет в викторине)
- 1 в 3,4 × 10 ^ 38
- 1 из 340 000 000 000 000 000 000 000 000 000 000 000 000
Никто, кажется, не упоминает фактическую математику вероятности того, что это произойдет.
Во-первых, давайте предположим, что мы можем использовать все 128-битное пространство (Guid v4 использует только 122-битные).
Мы знаем, что общая вероятность НЕ получить дубликат в n выбирает это:
(1-1 / 2128) (1-2 / 2128)... (1- (n-1) / 2128)
Потому что 2128 намного больше, чем nмы можем приблизить это к:
(1-1 / 2128)n (n-1) / 2
И потому что мы можем предположить, n намного больше, чем 0, мы можем приблизить это к:
(1-1 / 2128)n ^ 2/2
Теперь мы можем приравнять это к "приемлемой" вероятности, скажем, 1%:
(1-1 / 2128)n ^ 2/2 = 0,01
Для чего мы решаем n и получить:
n = sqrt (2 * log 0,01 / log (1-1 / 2128))
Какой Wolfram Alpha получит 5,598318 × 1019
Чтобы представить это число в перспективе, давайте возьмем 10000 машин, каждая из которых имеет 4-ядерный процессор, работает на частоте 4 ГГц и тратит 10000 циклов на генерацию Guid и больше ничего не делает. Затем потребуется около 111 лет, прежде чем они создадут дубликат.
С http://www.guidgenerator.com/online-guid-generator.aspx
Что такое GUID?
GUID (или UUID) является аббревиатурой от "Глобально уникальный идентификатор" (или "Универсально уникальный идентификатор"). Это 128-битное целое число, используемое для идентификации ресурсов. Термин GUID обычно используется разработчиками, работающими с технологиями Microsoft, а UUID используется везде.
Насколько уникален GUID?
128-бит достаточно велик, а алгоритм генерации настолько уникален, что, если в течение 1 года генерируется 1 000 000 000 идентификаторов GUID в секунду, вероятность дублирования составит всего 50%. Или если бы каждый человек на Земле генерировал 600 000 000 GUID, вероятность дубликата была бы только 50%.
Является ли GUID уникальным в 100% случаев?
Не гарантируется, так как существует несколько способов создания одного. Однако вы можете попытаться рассчитать вероятность создания двух идентичных идентификаторов GUID, и вы поймете, что идея: идентификатор GUID имеет 128 бит, следовательно, имеется 2 128 различных идентификаторов GUID - намного больше, чем звезд в известной вселенной. Прочитайте статью в Википедии для более подробной информации.
Я испытал дубликат GUID.
Я использую настольный сканер Neat Receipts, и он поставляется с проприетарным программным обеспечением для баз данных. В программном обеспечении есть функция синхронизации с облаком, и я получал сообщение об ошибке при синхронизации. Гусак на бревнах показал удивительную черту:
"errors": [{"code": 1, "message": "creator_guid: уже занят","guid":"C83E5734-D77A-4B09-B8C1-9623CAC7B167"}]}
Я немного не поверил, но, конечно же, когда я нашел путь к своей локальной базе данных neatworks и удалил запись, содержащую этот GUID, ошибка перестала возникать.
Таким образом, чтобы ответить на ваш вопрос с неподтвержденными данными, нет. Дубликат возможен. Но вполне вероятно, что причина, по которой это произошло, была не случайностью, а из-за несоблюдения какой-либо стандартной практики. (Мне просто не так повезло) Однако точно сказать не могу. Это не мое программное обеспечение.
Их служба поддержки была ОЧЕНЬ вежливой и услужливой, но они никогда не сталкивались с этой проблемой раньше, потому что после трех с лишним часов разговора по телефону они не нашли решения. (FWIW, Я очень впечатлен Neat, и этот глюк, хотя и расстраивающий, не изменил мое мнение об их продукте.)
MSDN:
Существует очень низкая вероятность того, что значение нового Guid равно нулю или равно любому другому Guid.
Если ваши системные часы настроены правильно и не были обернуты, и если у вашей сетевой карты есть собственный MAC (т.е. вы не установили пользовательский MAC), и ваш поставщик сетевой карты не перерабатывал MAC (что они не должны делать) но это, как известно, происходило), и если функция генерации GUID вашей системы правильно реализована, то ваша система никогда не будет генерировать дубликаты GUID.
Если каждый на земле, кто генерирует GUID, следует этим правилам, тогда ваши GUID будут глобально уникальными.
На практике количество людей, нарушающих правила, невелико, и их GUID вряд ли "сбегут". Конфликты статистически маловероятны.
For more better result the best way is to append the GUID with the timestamp (Just to make sure that it stays unique)
Guid.NewGuid().ToString() + DateTime.Now.ToString();
Я видел, что GUID не были уникальными во время многопоточного / многопроцессорного юнит-тестирования (тоже?). Я предполагаю, что это связано с тем, что при прочих равных условиях происходит одинаковое заполнение (или отсутствие заполнения) псевдослучайных генераторов. Я использовал его для генерации уникальных имен файлов. Я обнаружил, что ОС намного лучше делает это:)
Троллинг оповещения
Вы спрашиваете, являются ли GUID уникальными на 100%. Это зависит от количества идентификаторов GUID, среди которых оно должно быть уникальным. Поскольку количество идентификаторов GUID приближается к бесконечности, вероятность дублирования идентификаторов GUID приближается к 100%.
Я думаю, что когда люди закапывают свои мысли и страхи в статистику, они склонны забывать очевидное. Если система действительно случайна, то результат, которого вы меньше всего ожидаете (скажем, все единицы), столь же вероятен, как и любое другое неожиданное значение (скажем, все нули). Ни один из фактов не препятствует тому, чтобы они происходили последовательно или в первой паре выборок (хотя это было бы статистически «поистине шокирующим»). И в этом проблема измерения шанса: он полностью игнорирует критичность (и гнилую удачу).
ЕСЛИ это когда-либо произошло, каков результат? Ваше программное обеспечение перестает работать? Кто-то получает травму? Кто-то умирает? Мир взрывается?
Чем крайняя критичность, тем хуже слово «вероятность» сидит во рту. В конце концов, объединение GUID в цепочку (или их XOR или что-то еще) — это то, что вы делаете, когда считаете (субъективно) свою особую критичность (и свое чувство «везения») неприемлемым. И если это может положить конец миру, то, пожалуйста, от имени всех нас, не участвовавших в ядерных экспериментах на Большом адронном коллайдере, не используйте GUID или что-либо еще недетерминированное!
Алгоритмы GUID обычно реализуются в соответствии со спецификацией GUID v4, которая, по сути, является псевдослучайной строкой. К сожалению, они попадают в категорию "вероятно, не уникальных", из Википедии (я не знаю, почему так много людей игнорируют этот бит): "... другие версии GUID имеют разные свойства уникальности и вероятности, начиная от гарантированной уникальности скорее всего, не уникальность."
Псевдослучайные свойства JavaScript V8 Math.random() УЖАСНЫ в уникальности, с коллизиями, часто возникающими после нескольких тысяч итераций, но V8 не единственный виновник. Я видел реальные коллизии GUID с использованием реализаций GUID v4 как в PHP, так и в Ruby.
Поскольку масштабирование генерации идентификаторов на нескольких клиентах и кластерах серверов становится все более распространенным явлением, энтропия имеет большой успех - вероятность того, что одно и то же случайное начальное число используется для генерации повышенного идентификатора (время часто используется в качестве случайного начального числа). в псевдослучайных генераторах), и коллизии GUID увеличиваются от "вероятно неуникального" до "очень вероятно, вызовет много проблем".
Чтобы решить эту проблему, я решил создать алгоритм идентификации, который мог бы безопасно масштабироваться и обеспечивать более надежные гарантии от столкновений. Для этого используются временная метка, счетчик клиента в памяти, отпечаток клиента и случайные символы. Сочетание факторов создает аддитивную сложность, которая особенно устойчива к коллизиям, даже если вы масштабируете ее на нескольких хостах:
Ответ "Является ли GUID уникальным на 100%?" это просто "Нет".
Если вы хотите 100% уникальность GUID, сделайте следующее.
- генерировать GUID
- проверьте, существует ли этот GUID в столбце таблицы, где вы ищете уникальность
- если существует, то перейдите к шагу 1 или к шагу 4
- используйте этот GUID как уникальный.
В более общем смысле это известно как "проблема дня рождения" или "парадокс дня рождения". Википедия имеет довольно хороший обзор по адресу: Википедия - день рождения проблема
В очень грубых выражениях, квадратный корень из размера пула является приблизительным приближением, когда можно ожидать 50% вероятности дублирования. Статья включает в себя таблицу вероятностей размера пула и различных вероятностей, в том числе строку для 2^128. Таким образом, для вероятности коллизии в 1% вы можете случайно выбрать 2,6*10^18 128-битных чисел. Вероятность 50% требует 2,2*10^19 пиков, в то время как SQRT(2^128) составляет 1,8*10^19.
Конечно, это просто идеальный случай действительно случайного процесса. Как уже упоминалось, многое зависит от этого случайного аспекта - насколько хороши генератор и семена? Было бы неплохо, если бы была некоторая аппаратная поддержка для помощи в этом процессе, которая была бы более пуленепробиваемой, за исключением того, что все можно было подделать или виртуализировать. Я подозреваю, что это может быть причиной того, что MAC-адреса / временные метки больше не включены.
Самое сложное не в создании дублирующегося Guid.
Самая сложная часть - это база данных, в которой хранятся все сгенерированные, чтобы проверить, действительно ли она дублирована.
Из Вики:
Например, число случайных UUID версии 4, которые должны быть сгенерированы для того, чтобы иметь вероятность 50%, по крайней мере, одного столкновения, составляет 2,71 квинтиллиона, вычисляемое следующим образом:
введите описание изображения здесь
Это число эквивалентно генерации 1 миллиарда UUID в секунду в течение примерно 85 лет, и файл, содержащий такое количество UUID, по 16 байт на UUID, будет примерно 45 эксабайт, во много раз больше, чем самые большие базы данных, которые в настоящее время существуют, порядка сотен петабайт
GUID расшифровывается как глобальный уникальный идентификатор
Вкратце: (ключ в названии)
Подробно: GUID разработаны так, чтобы быть уникальными; они рассчитываются с использованием случайного метода на основе часов компьютера и самого компьютера. Если вы создаете много идентификаторов GUID в одну и ту же миллисекунду на одной и той же машине, возможно, они могут совпадать, но почти для всех обычных операций их следует считать уникальными.
Достаточно GUID, чтобы назначить по одному каждой гипотетической песчинке на каждой гипотетической планете вокруг каждой звезды в видимой Вселенной.
Достаточно, чтобы, если каждый компьютер в мире генерирует 1000 GUID в секунду в течение 200 лет, может (МОЖНО) произойти коллизия.
Учитывая количество текущих локальных применений GUID (например, одна последовательность на таблицу для каждой базы данных), это чрезвычайно маловероятно, что когда-либо станет проблемой для нас, ограниченных существ (и машин со сроком службы, который обычно составляет менее десяти лет, если не год или два. для мобильных телефонов).
... Можем ли мы закрыть эту тему сейчас?
Настолько невероятно мало, что почти 0, но никогда не 0. Спросите меня, откуда я знаю... На самом деле я пришел сюда, чтобы узнать, насколько это на самом деле невероятно, потому что я только что обнаружил, что есть два фрагмента данных, которые имеют один и тот же GUID в один из моих БД...