Простое доказательство того, что GUID не уникален [закрыто]

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

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

Я использую C #.

Кай, я предоставил программу, которая будет делать то, что вы хотите, используя потоки. Он лицензируется на следующих условиях: вы должны платить мне 0,0001 доллара в час за ядро ​​процессора, на котором вы его запускаете. Сборы уплачиваются в конце каждого календарного месяца. Пожалуйста, свяжитесь со мной для получения подробной информации о моем счете PayPal при первой возможности.

using System;
using System.Collections.Generic;
using System.Linq;

namespace GuidCollisionDetector
{
    class Program
    {
        static void Main(string[] args)
        {
            //var reserveSomeRam = new byte[1024 * 1024 * 100];     // This indeed has no effect.

            Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
            // Fill up memory with guids.
            var bigHeapOGuids = new HashSet<Guid>();
            try
            {
                do
                {
                    bigHeapOGuids.Add(Guid.NewGuid());
                } while (true);
            }
            catch (OutOfMemoryException)
            {
                // Release the ram we allocated up front.
                // Actually, these are pointless too.
                //GC.KeepAlive(reserveSomeRam);
                //GC.Collect();
            }
            Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());


            // Spool up some threads to keep checking if there's a match.
            // Keep running until the heat death of the universe.
            for (long k = 0; k < Int64.MaxValue; k++)
            {
                for (long j = 0; j < Int64.MaxValue; j++)
                {
                    Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
                    System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
                    {
                        if (bigHeapOGuids.Contains(Guid.NewGuid()))
                            throw new ApplicationException("Guids collided! Oh my gosh!");
                    }
                    );
                    Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
                }
            }
            Console.WriteLine("Umm... why hasn't the universe ended yet?");
        }
    }
}

PS: я хотел попробовать библиотеку параллельных расширений. Это было легко.

И использование OutOfMemoryException в качестве потока управления кажется неправильным.

РЕДАКТИРОВАТЬ

Ну, кажется, это все еще привлекает голоса. Итак, я исправил проблему с GC.KeepAlive (). И изменил его для запуска с C # 4.

И чтобы уточнить мои условия поддержки: поддержка доступна только 28 февраля 2010 года. Пожалуйста, используйте машину времени, чтобы делать запросы поддержки только в этот день.

РЕДАКТИРОВАТЬ 2 Как всегда, GC делает лучшую работу, чем я в управлении памятью; любые предыдущие попытки сделать это самостоятельно были обречены на провал.

Это будет длиться намного дольше, чем часами. Предполагая, что он работает на частоте 1 ГГц (чего не будет - будет намного медленнее), он будет работать в течение 10790283070806014188970 лет. Что примерно в 83 миллиарда раз больше, чем возраст Вселенной.

Предполагая, что закон Мура действует, было бы намного быстрее не запускать эту программу, подождать несколько сотен лет и запустить ее на компьютере, который в миллиарды раз быстрее. Фактически, любая программа, выполнение которой занимает больше времени, чем удвоение скорости процессора (около 18 месяцев), завершится раньше, если вы дождетесь увеличения скорости процессора и купите новый процессор перед его запуском (если вы не напишете его так, чтобы он может быть приостановлено и возобновлено на новом оборудовании).

GUID теоретически не уникален. Вот ваше доказательство:

• GUID - это 128-битное число
• Вы не можете сгенерировать 2 ^ 128 + 1 или более GUID без повторного использования старых GUID

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

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

Конечно, GUID может столкнуться. Поскольку GUID являются 128-битными, просто сгенерируйте 2^128 + 1их, и по принципу почтового ящика должно происходить столкновение.

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

Если вы генерируете последовательность nидентификаторов GUID случайным образом, то вероятность, по крайней мере, одного столкновения составляет приблизительно p(n) = 1 - exp(-n^2 / 2 * 2^128)(это проблема дня рождения с количеством возможных дней рождения 2^128).

   n     p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03

Для того, чтобы эти цифры бетона, 2^60 = 1.15e+18. Таким образом, если вы генерируете один миллиард идентификаторов GUID в секунду, вам потребуется 36 лет, чтобы сгенерировать 2^60случайные идентификаторы GUID, и даже тогда вероятность того, что у вас возникла коллизия, все еще остается 1.95e-03. Скорее всего, вы будете убиты в какой-то момент вашей жизни ( 4.76e-03), чем столкновение в течение следующих 36 лет. Удачи.

Если вы беспокоитесь об уникальности, вы всегда можете приобрести новые GUID, чтобы вы могли выбросить свои старые. Я положу некоторые на eBay, если хотите.

Лично я думаю, что "Большой взрыв" был вызван, когда столкнулись два GUID.

Вы можете показать, что за O (1) время с помощью варианта алгоритма квантовой Bogosort .

Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();

Любые два GUID, скорее всего, уникальны (не равны).

Смотрите эту SO запись и из Википедии

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

Поэтому, вероятно, вам придется ждать еще много миллиардов лет и надеяться, что вы достигнете одного перед Вселенной, поскольку мы знаем, что он подходит к концу.

[Обновление:] Как отмечают комментарии ниже, новые GUID MS являются V4 и не используют MAC-адрес как часть генерации GUID (хотя я не видел никаких признаков реализации V5 от MS, поэтому, если у кого-то есть ссылка, подтверждающая, что дайте мне знать). Однако с V4 время все еще является фактором, и шансы против дублирования GUID остаются настолько малыми, что не имеют значения для любого практического использования. Вы, безусловно, вряд ли когда-либо сгенерируете двойной GUID из одного теста системы, такого как пытался выполнить OP.

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

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

Для всех практических целей GUID универсально уникальны.

В блоге "The Old New Thing" есть довольно хорошее описание MS GUID

Вот отличный метод расширения, который вы можете использовать, если хотите проверить уникальность guid во многих местах вашего кода.

internal static class GuidExt
{
    public static bool IsUnique(this Guid guid)
    {
        while (guid != Guid.NewGuid())
        { }
        return false;
    }
}

Чтобы вызвать его, просто вызовите Guid.IsUnique всякий раз, когда вы генерируете новый guid ...

Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
    throw new GuidIsNotUniqueException();
}

... чёрт, я бы даже посоветовал позвонить дважды, чтобы убедиться, что все получилось правильно в первом раунде.

Считать до 2 ^ 128 - амбициозно.

Давайте представим , что мы можем рассчитывать 2 ^ 32 идентификаторы в секунду на машине - не что амбициозные, так как это даже не 4,3 миллиарда долларов в секунду. Давайте посвятим 2 ^ 32 машины для этой задачи. Кроме того, давайте получим 2 ^ 32 цивилизации, чтобы каждая из них выделяла одни и те же ресурсы для выполнения задачи.

Пока что мы можем считать 2 ^ 96 идентификаторов в секунду, то есть мы будем считать 2 ^ 32 секунды (чуть более 136 лет).

Теперь все, что нам нужно, - это получить 4 294 967 296 цивилизаций, чтобы каждая из них выделяла 4 294 967 296 машин, каждая машина способна считать 4 294 967 296 идентификаторов в секунду, чисто для выполнения этой задачи в течение следующих 136 лет или около того - я предлагаю начать работу с этой важной задачей прямо сейчас; -)

Хорошо, если время работы в 83 миллиарда лет вас не пугает, подумайте, что вам также нужно где-то хранить сгенерированные GUID, чтобы проверить, есть ли у вас дубликат; Хранение 2 ^ 128 16-байтовых чисел потребует от вас только 4951760157141521099596496896 терабайт оперативной памяти, так что представьте, что у вас есть компьютер, который может вместить все это, и что вы каким-то образом найдете место, где можно купить терабайтные модули DIMM по 10 грамм каждый, в сочетании они будут весят более 8 масс Земли, поэтому вы можете серьезно сдвинуть ее с текущей орбиты, прежде чем даже нажать «Выполнить». Подумать дважды!

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

Вы не увеличиваете, beginпоэтому условие begin < endвсегда выполняется.

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

Предположительно у вас есть основания полагать, что алгоритм создания Guids не производит действительно случайные числа, а фактически цикличен с периодом << 2 ^ 128.

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

Доказательство езды на велосипеде будет зависеть от возможного размера периода.

Для небольших периодов подходом может быть хеш-таблица хеш-кода (GUID) -> GUID с заменой при столкновении, если GUID не совпадают (завершаются, если они есть). Также рассмотрите возможность выполнения замены только случайную долю времени.

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

Обратите внимание, что если метод генерации Guids основан на часах (см. RFC), то, возможно, не удастся определить, существуют ли коллизии, потому что (а) вы не сможете ждать достаточно долго, чтобы часы развернулись, или (b) вы не можете запросить достаточное количество гидов в течение такта, чтобы вызвать столкновение.

В качестве альтернативы вы можете показать статистическую взаимосвязь между битами в Guid или корреляцию битов между Guid. Такое отношение может сделать весьма вероятным, что алгоритм имеет недостатки, не обязательно в состоянии найти фактическое столкновение.

Конечно, если вы просто хотите доказать, что Guids может столкнуться, то вам нужно математическое доказательство, а не программа.

Я не понимаю, почему никто не упомянул обновление вашей видеокарты ... Конечно, если у вас есть высокопроизводительный NVIDIA Quadro FX 4800 или что-то еще (192 ядра CUDA), это будет идти быстрее ...

Конечно, если бы вы могли позволить себе несколько NVIDIA Qadro Plex 2200 S4 (по 960 ядер CUDA каждый), этот расчет был бы действительно ошеломляющим. Возможно, NVIDIA захочет одолжить вам несколько на «демонстрацию технологии» в качестве пиар-трюка?

Конечно, они хотели бы быть частью этого исторического расчета ...

Но нужно ли вам быть уверенным, что у вас есть дубликат, или вас волнует только то, что он может быть. Чтобы быть уверенным, что у вас два человека с одинаковым днем ​​рождения, вам нужно 366 человек (не считая високосного года). Для того, чтобы иметь двух человек с одинаковым днем ​​рождения более чем на 50%, нужно всего 23 человека. Это проблема дня рождения .

Если у вас 32 бита, вам нужно всего лишь 77 163 значения, чтобы вероятность дублирования превышала 50%. Попробуйте это:

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

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

• 0,8 миллиарда для вероятности 1/1000 столкновения
• 21,7 миллиарда на 50% вероятности столкновения
• 39,6 миллиарда долларов с вероятностью столкновения 90%

В год отправляется около 1E14 электронных писем, поэтому на этом уровне пройдет около 400 000 лет, прежде чем у вас будет 90% шанс получить два с одинаковым GUID, но это сильно отличается от того, что вам нужно запустить компьютер 83 миллиарда раз возраст вселенной или то, что солнце остынет, прежде чем найти дубликат.

Разве вы не пропустили главную мысль?

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

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

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

Тони

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

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

GUID - 124 бита, потому что 4 бита содержат номер версии.

1. Отправляйтесь в криогенную лабораторию в Нью-Йорке.
2. Заморозить себя (примерно) на 1990 год.
3. Получить работу в Planet Express.
4. Купите новый процессор. Соберите компьютер, запустите программу и поместите его в безопасное место с помощью псевдо-вечного двигателя, такого как машина судного дня.
5. Подождите, пока машина времени не изобретена.
6. Прыгай в будущее, используя машину времени. Если вы купили 128-битный процессор с частотой 1 ГГц, переходите к тому, 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 psкогда вы начали запускать программу.
7. ...?
8. PROFIT !!!

... Это займет как минимум 10,783,127годы, даже если у вас был процессор с частотой 1 ГГц, который 1,000,000,000,000,000(или 1,125,899,906,842,624если вы предпочитаете использовать двоичный префикс) в разы быстрее, чем процессор с частотой 1 ГГц.

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

Или вы можете подождать, пока не будет изобретен 128-битный квантовый компьютер. Затем вы можете доказать, что GUID не является уникальным, используя вашу программу в разумные сроки (возможно).

Вы пробовали begin = begin + new BigInteger((long)1)вместо начала ++?

Если число генерируемых UUID соответствует закону Мура, впечатление, что GUID в обозримом будущем никогда не иссякнет, является ложным.

При 2 ^ 128 UUID потребуется всего 18 месяцев * Log2 (2 ^ 128) ~ = 192 года, прежде чем мы исчерпаем все UUID.

И я считаю (без каких-либо статистических доказательств) в последние несколько лет после массового принятия UUID скорость, с которой мы генерируем UUID, растет намного быстрее, чем диктует закон Мура. Другими словами, у нас, вероятно, осталось меньше 192 лет, чтобы справиться с кризисом UUID, это намного раньше, чем конец вселенной.

Но так как мы определенно не исчерпаем их к концу 2012 года, мы предоставим другим видам возможность беспокоиться о проблеме.

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

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

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

Вы можете сократить свою 128-битную таблицу, чтобы доказать свою точку зрения. Лучшее решение - использовать формулу хеширования, чтобы сократить таблицу с дубликатами, а затем использовать полное значение, когда хэш сталкивается, и на основе этого повторно генерировать GUID. Если вы работаете из разных мест, вы должны хранить ваши пары хэш / полный ключ в центральном месте.

Ps: Если цель состоит в том, чтобы просто сгенерировать х количество различных значений, создайте хеш-таблицу этой ширины и просто проверьте значение хеш-функции.

Не пушить на костер здесь, но это действительно происходит, и да, я понимаю, что вы пошутили над этим парнем, но GUID уникален только в принципе, я наткнулся на эту тему, потому что есть ошибка в эмуляторе WP7, что означает, что каждый раз, когда он загружается, он выдает тот же GUID при первом вызове! Таким образом, если в теории у вас не может быть конфликта, если есть проблема с генерацией указанного GUI, тогда вы можете получить дубликаты

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310

Так как часть генерации Guid основана на времени текущей машины, моя теория получить дубликат Guid:

1. Выполните чистую установку Windows
2. Создайте сценарий запуска, который сбрасывает время до 2010-01-01 12:00:00, как только загружается Windows.
3. Сразу после запуска скрипт запускает ваше приложение для генерации Guid.
4. Клонируйте эту установку Windows, чтобы исключить тонкие различия, которые могут возникнуть при последующих загрузках.
5. Измените образ жесткого диска с этим образом и загрузите компьютер несколько раз.

Для меня ... время, которое требуется одному ядру для генерации UUIDv1, гарантирует, что оно будет уникальным. Даже в ситуации с несколькими ядрами, если генератор UUID позволяет одновременно генерировать только один UUID для вашего конкретного ресурса (имейте в виду, что несколько ресурсов могут полностью использовать одни и те же идентификаторы UUID, что маловероятно, поскольку ресурс является неотъемлемой частью адреса), тогда вы будет иметь более чем достаточно UUID для вас, пока не сгорит метка времени. В этот момент я действительно сомневаюсь, что тебя это волнует.

Вот решение тоже:

int main()
{
  QUuid uuid;
  while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
  std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

Примечание: требуется Qt, но я гарантирую, что если вы позволите ему работать достаточно долго, он может найти его.

(Обратите внимание: на самом деле, теперь, когда я смотрю на это, в алгоритме генерации может быть что-то, что предотвращает столкновение двух последовательно генерируемых uuids - но я в этом немного сомневаюсь).

Единственное решение доказать, что идентификаторы GUID не являются уникальными, это наличие World GUID Pool. Каждый раз, когда GUID генерируется где-то, он должен быть зарегистрирован в организации. Или, черт возьми, мы можем включить стандартизацию, которая нужна всем генераторам GUID для автоматической регистрации и для этого требуется активное подключение к Интернету!