Является ли GUID уникальным в 100% случаев?

Является ли GUID уникальным в 100% случаев?

Он останется уникальным для нескольких потоков?

Хотя каждый сгенерированный GUID не гарантированно является уникальным, общее количество уникальных ключей (2 ¹²⁸ или 3,4 × 10 ³⁸ ) настолько велико, что вероятность того, что одно и то же число будет сгенерировано дважды, очень мала. Например, рассмотрим наблюдаемую вселенную, которая содержит около 5 × 10 ²² звезд; тогда каждая звезда может иметь 6,8 × 10 ¹⁵ универсально уникальных GUID.

Из Википедии .

Это несколько хороших статей о том, как создается GUID (для .NET) и как вы можете получить такое же руководство в правильной ситуации.

https://ericlippert.com/2012/04/24/guid-guide-part-one/

https://ericlippert.com/2012/04/30/guid-guide-part-two/

https://ericlippert.com/2012/05/07/guid-guide-part-three/

​​

Если вы боитесь одинаковых значений 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.

В мире насчитывается порядка 2 ³⁰ персональных компьютеров (и, конечно, множество портативных устройств или вычислительных устройств, не относящихся к ПК, которые имеют более или менее одинаковые уровни вычислительной мощности, но давайте их игнорируем). Давайте предположим, что мы поставили все эти компьютеры в мире на задачу генерации GUID; если каждый из них может генерировать, скажем, 2 ²⁰ GUID в секунду, то примерно через 2 ⁷² секунды - сто пятьдесят триллионов лет - у вас будет очень высокая вероятность возникновения коллизии с вашим конкретным GUID. И шансы столкновения становятся довольно хорошими уже через тридцать триллионов лет.

• GUID Guide, часть первая
• GUID Guide, часть вторая
• Путеводитель, часть третья

Теоретически нет, они не уникальны. Можно генерировать идентичный гид снова и снова. Однако шансы на то, что это произойдет, настолько низки, что можно предположить, что они уникальны.

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

Я попытался описать полезность 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 / 2 ¹²⁸ ) (1-2 / 2 ¹²⁸ ) ... (1- (n-1) / 2 ¹²⁸ )

Поскольку 2 ¹²⁸ намного больше, чем n, мы можем приблизить это к:

(1-1 / 2 ¹²⁸ ) ^{n (n-1) / 2}

И поскольку мы можем предположить n, что он намного больше 0, мы можем приблизить его к:

(1-1 / 2 ¹²⁸ ) ^{n ^ 2/2}

Теперь мы можем приравнять это к «приемлемой» вероятности, скажем, 1%:

(1-1 / 2 ¹²⁸ ) ^{n ^ 2/2} = 0,01

За что мы решаем nи получаем:

n = sqrt (2 * log 0,01 / log (1-1 / 2 ¹²⁸ ))

Какой Wolfram Alpha получит 5,598318 × 10 ¹⁹

Чтобы представить это число в перспективе, давайте возьмем 10000 машин, каждая из которых имеет 4-ядерный процессор, работает на частоте 4 ГГц и тратит 10000 циклов на генерацию Guid и больше ничего не делает. Затем потребуется около 111 лет, прежде чем они создадут дубликат.

С http://www.guidgenerator.com/online-guid-generator.aspx

Что такое GUID?

GUID (или UUID) является аббревиатурой от «Глобально уникальный идентификатор» (или «Универсально уникальный идентификатор»). Это 128-битное целое число, используемое для идентификации ресурсов. Термин GUID обычно используется разработчиками, работающими с технологиями Microsoft, в то время как UUID используется везде.

Насколько уникален GUID?

128-бит достаточно велик, а алгоритм генерации настолько уникален, что если в течение одного года генерировать 1 000 000 000 идентификаторов GUID в секунду, вероятность дублирования составит всего 50%. Или, если бы каждый человек на Земле генерировал 600 000 000 GUID, вероятность дубликата была бы только 50%.

Я испытал дубликат 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 вряд ли "сбегут". Конфликты статистически маловероятны.

Является ли GUID уникальным в 100% случаев?

Не гарантируется, так как существует несколько способов создания одного. Однако вы можете попытаться рассчитать вероятность создания двух идентичных идентификаторов GUID, и вы поймете, что идея: идентификатор GUID имеет 128 битов, следовательно, имеется 2 ¹²⁸ различных идентификаторов GUID - намного больше, чем звезд в известной вселенной. Прочитайте статью в Википедии для более подробной информации.

В более общем смысле это известно как «проблема дня рождения» или «парадокс дня рождения». Википедия имеет довольно хороший обзор по адресу: Википедия - день рождения проблема

В очень грубых выражениях, квадратный корень из размера пула является приблизительным приближением, когда можно ожидать 50% вероятности дублирования. Статья включает в себя таблицу вероятностей размера пула и различных вероятностей, включая строку для 2 ^ 128. Таким образом, для вероятности коллизии в 1% вы можете случайно выбрать 2,6 * 10 ^ 18 128-битных чисел. Вероятность 50% требует 2,2 * 10 ^ 19 пиков, в то время как SQRT (2 ^ 128) составляет 1,8 * 10 ^ 19.

Конечно, это просто идеальный случай действительно случайного процесса. Как уже упоминалось, многое зависит от этого случайного аспекта - насколько хороши генератор и семена? Было бы хорошо, если бы была некоторая аппаратная поддержка, чтобы помочь с этим процессом, который был бы более пуленепробиваемым, за исключением того, что все может быть подделано или виртуализировано. Я подозреваю, что это может быть причиной того, что MAC-адреса / временные метки больше не включены.

Для лучшего результата лучше всего добавить GUID с отметкой времени (просто чтобы убедиться, что она остается уникальной)

Guid.NewGuid().ToString() + DateTime.Now.ToString();

Алгоритмы GUID обычно реализуются в соответствии со спецификацией GUID v4, которая по сути является псевдослучайной строкой. К сожалению, они попадают в категорию «вероятно, не уникальных» , из Википедии (я не знаю, почему так много людей игнорируют этот бит): «... другие версии GUID имеют разные свойства уникальности и вероятности, начиная от гарантированной уникальности скорее всего, не уникальность. "

Псевдослучайные свойства JavaScript V8 Math.random() ужасны в своей уникальности, часто возникают коллизии после нескольких тысяч итераций, но V8 не единственный виновник. Я видел реальные коллизии GUID с использованием реализаций GUID v4 как в PHP, так и в Ruby.

Поскольку масштабирование генерации идентификаторов на нескольких клиентах и ​​кластерах серверов становится все более распространенным явлением, энтропия имеет большой успех - вероятность того, что одно и то же случайное начальное число используется для генерации повышенного идентификатора (время часто используется как случайное начальное число в псевдослучайных генераторах), и коллизии GUID увеличиваются от «вероятно, не уникального» до «очень вероятно, вызовет много проблем».

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

http://usecuid.org/

Я видел, что GUID не были уникальными во время многопоточного / многопроцессорного юнит-тестирования (тоже?). Я предполагаю, что это связано с тем, что при прочих равных условиях происходит одинаковое заполнение (или отсутствие заполнения) псевдослучайных генераторов. Я использовал его для генерации уникальных имен файлов. Я обнаружил, что ОС намного лучше делает это :)

Троллинг оповещения

Вы спрашиваете, являются ли GUID уникальными на 100%. Это зависит от количества идентификаторов GUID, среди которых оно должно быть уникальным. Поскольку количество идентификаторов GUID приближается к бесконечности, вероятность дублирования идентификаторов GUID приближается к 100%.

Ответ "Является ли GUID уникальным на 100%?" это просто "Нет" .

• Если вы хотите 100% уникальность GUID, сделайте следующее.

  1. генерировать GUID
  2. проверьте, существует ли этот GUID в столбце таблицы, где вы ищете уникальность
  3. если существует, то перейдите к шагу 1 или к шагу 4
  4. используйте этот GUID как уникальный.

Самое сложное не в создании дублируемого Guid.

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

Из Вики:

Например, число случайных UUID версии 4, которые должны быть сгенерированы для того, чтобы иметь вероятность 50%, по крайней мере, одного столкновения, составляет 2,71 квинтиллиона, вычисляемое следующим образом:

введите описание изображения здесь

Это число эквивалентно генерации 1 миллиарда UUID в секунду в течение примерно 85 лет, и файл, содержащий такое количество UUID, по 16 байт на UUID, будет примерно 45 эксабайт, во много раз больше, чем самые большие базы данных, которые в настоящее время существуют, порядка сотен петабайт

GUID расшифровывается как глобальный уникальный идентификатор

Вкратце: (ключ в названии)

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