четверг, 28 апреля 2011, Александр Краковецкий

Очень зачетный тред увидел на моем любимом сайте для разработчиков - StackOveflow. Некто Кай решил проверить, насколько 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());
}

Просидев долгие часы (дни?) в надежде увидеть долгожданную коллизию, он все таки решил посоветоваться с коллегами по цеху. Коллеги не подкачали :)

Wait several trillion years.

Подождите пару триллионов лет.

А почему бы и нет? Я бы тоже "подождал".

It's only globally unique, so it's only unique on our planet. If you want a truly unique id you need to use a universally unique id (UUID).

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

Согласен, зачем мыслить так узко? Еще нужно написать функцию UUID(int dimension), которая будет возвращать уникальный идентификатор в зависимости от измерения. Но идем дальше.

Один разработчик предложил программу на таких условиях: платить ему $0.0001 за один час за одно ядро процессора. Вот и программа:

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];

            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.
                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?");
        }
    }
}

Обратите внимание на последний Console.WriteLine(). Вместо этого вывода предложили бросать исключение CommonlyAcceptedCosmologicTheoriesWrongException. Хорошая идея ;)

Обратимся к помощи математики: если у вас есть процессор 1 GHz, то процесс обнаружения коллизий займет 10790283070806014188970 лет, что в 83 миллиарда больше возраста Вселенной. Но, правда, можно использовать потоки и тогда на 4-хядерном процессоре это займет "всего" 20 млрд лет!

Теоретически GUID не уникален:

• GUID - это 128-битное число
• получается, что сгенерировать больше, чем 2^128 + 1 GUIDs нельзя :(

Вот так вот. На самом деле мне понравилось то, что никто не назвал автора вопроса придурком (хотя кто-то предположил, что он тролль) и даже не послал в google. А еще меня мучает зависть - почему я не умею задавать такие классные вопросы, а вечно задаю какую-то фигню?

---