Sort Sequential Guids Generated by UuidCreateSequential

Question

I tried to sort Guids generated by UuidCreateSequential, but I see the results are not correct, am I mising something? here is the code

    private class NativeMethods
    {
        [DllImport("rpcrt4.dll", SetLastError = true)]
        public static extern int UuidCreateSequential(out Guid guid);
    }

    public static Guid CreateSequentialGuid()
    {
        const int RPC_S_OK = 0;

        Guid guid;
        int result = NativeMethods.UuidCreateSequential(out guid);
        if (result == RPC_S_OK)
            return guid;
        else throw new Exception("could not generate unique sequential guid");
    }

    static void TestSortedSequentialGuid(int length)
    {
        Guid []guids = new Guid[length];
        int[] ids = new int[length];

        for (int i = 0; i < length; i++)
        {
            guids[i] = CreateSequentialGuid();
            ids[i] = i;
            Thread.Sleep(60000);
        }

        Array.Sort(guids, ids);

        for (int i = 0; i < length - 1; i++)
        {
            if (ids[i] > ids[i + 1])
            {
                Console.WriteLine("sorting using guids failed!");
                return;
            }
        }

        Console.WriteLine("sorting using guids succeeded!");
    }

EDIT1:

Just to make my question clear, why the guid struct is not sortable using the default comparer ?

EDIT 2: Also here are some sequential guids I've generated, seems they are not sorted ascending as presented by the hex string

            "53cd98f2504a11e682838cdcd43024a7",
            "7178df9d504a11e682838cdcd43024a7",
            "800b5b69504a11e682838cdcd43024a7",
            "9796eb73504a11e682838cdcd43024a7",
            "c14c5778504a11e682838cdcd43024a7",
            "c14c5779504a11e682838cdcd43024a7",
            "d2324e9f504a11e682838cdcd43024a7",
            "d2324ea0504a11e682838cdcd43024a7",
            "da3d4460504a11e682838cdcd43024a7",
            "e149ff28504a11e682838cdcd43024a7",
            "f2309d56504a11e682838cdcd43024a7",
            "f2309d57504a11e682838cdcd43024a7",
            "fa901efd504a11e682838cdcd43024a7",
            "fa901efe504a11e682838cdcd43024a7",
            "036340af504b11e682838cdcd43024a7",
            "11768c0b504b11e682838cdcd43024a7",
            "2f57689d504b11e682838cdcd43024a7"

Answer 1

First off, let's re-state the observation: when creating sequential GUIDs with a huge time delay -- 60 billion nanoseconds -- between creations, the resulting GUIDs are not sequential.

am I missing something?

You know every fact you need to know to figure out what is going on. You're just not putting them together.

You have a service that provides numbers which are both sequential and unique across all computers in the universe. Think for a moment about how that is possible. It's not a magic box; someone had to write that code.

Imagine if you didn't have to do it using computers, but instead had to do it by hand. You advertise a service: you provide sequential globally unique numbers to anyone who asks at any time.

Now, suppose I ask you for three such numbers and you hand out 20, 21, and 22. Then sixty years later I ask you for three more and surprise, you give me 13510985, 13510986 and 13510987. "Wait just a minute here", I say, "I wanted six sequential numbers, but you gave me three sequential numbers and then three more. What gives?"

Well, what do you suppose happened in that intervening 60 years? Remember, you provide this service to anyone who asks, at any time. Under what circumstances could you give me 23, 24 and 25? Only if no one else asked within that 60 years.

Now is it clear why your program is behaving exactly as it ought to?

In practice, the sequential GUID generator uses the current time as part of its strategy to enforce the globally unique property. Current time and current location is a reasonable starting point for creating a unique number, since presumably there is only one computer on your desk at any one time.

Now, I caution you that this is only a starting point; suppose you have twenty virtual machines all in the same real machine and all trying to generate sequential GUIDs at the same time? In these scenarios collisions become much more likely. You can probably think of techniques you might use to mitigate collisions in these scenarios.

Answer 2

After researching, I can't sort the guid using the default sort or even using the default string representation from guid.ToString as the byte order is different.

to sort the guids generated by UuidCreateSequential I need to convert to either BigInteger or form my own string representation (i.e. hex string 32 characters) by putting bytes in most signification to least significant order as follows:

static void TestSortedSequentialGuid(int length)
{
    Guid []guids = new Guid[length];
    int[] ids = new int[length];

    for (int i = 0; i < length; i++)
    {
        guids[i] = CreateSequentialGuid();
        ids[i] = i;

// this simulates the delay between guids creation
// yes the guids will not be sequential as it interrupts generator 
// (as it used the time internally) 
// but still the guids should be in increasing order and hence they are     
// sortable and that was the goal of the question
        Thread.Sleep(60000);
    }

        var sortedGuidStrings = guids.Select(x =>
        {
            var bytes = x.ToByteArray();

          //reverse high bytes that represents the sequential part (time)            
            string high = BitConverter.ToString(bytes.Take(10).Reverse().ToArray());

             //set last 6 bytes are just the node (MAC address) take it as it is.
                return high + BitConverter.ToString(bytes.Skip(10).ToArray());
        }).ToArray();

    // sort ids using the generated sortedGuidStrings
    Array.Sort(sortedGuidStrings, ids);

    for (int i = 0; i < length - 1; i++)
    {
        if (ids[i] > ids[i + 1])
        {
            Console.WriteLine("sorting using sortedGuidStrings failed!");
            return;
        }
    }

    Console.WriteLine("sorting using sortedGuidStrings succeeded!");
}