对UuidCreateSequential生成的顺序Guid进行排序

Question

我试图对UuidCreateSequential生成的Guid进行排序，但我发现结果不正确，我是不是搞错了什么？这是代码

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

第1版：

为了澄清我的问题，为什么guid结构不能使用默认比较器进行排序？

编辑2:这里还有我生成的一些顺序指南，它们似乎没有按照十六进制字符串的方式升序排列

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

Answer 1

首先，让我们重新陈述观察结果：当创建具有巨大时间延迟（创建之间的时间延迟为60亿纳秒）的顺序GUID时，生成的GUID不是顺序的。

我是不是错过了什么？

你知道每一个你需要知道的事实来弄清楚发生了什么。你只是没有把它们放在一起。

您有一项服务，它提供的数字在宇宙中的所有计算机中都是顺序和唯一的。想一想这是怎么可能的。这不是一个魔盒；必须有人写那个代码。

想象一下，如果你不必用电脑，而是必须用手来做。您为一项服务做广告：您向任何在任何时间询问的人提供连续全局唯一编号。

现在，假设我问你三个这样的数字，然后你发20、21和22。60年后，我再问你三个，你给了我13510985、13510986和13510987。"在这里等一分钟"，我说，"我想要六个序列号，但你给了我三个序列号然后又给了三个。是什么？"

好吧，你认为在这中间的60年里发生了什么？请记住，您在任何时候向任何提出要求的人提供此服务。在什么情况下你能给我23、24和25只有在60年内没有其他人提出要求的情况下。

现在清楚了为什么你的程序会按照它应该的方式运行吗？

在实践中，顺序GUID生成器使用当前时间作为其策略的一部分，以强制执行全局唯一属性。当前时间和当前位置是创建唯一号码的合理起点，因为假设在任何时候你的桌子上都只有一台电脑。

现在，我提醒大家，这只是一个起点；假设你有二十个虚拟机都在同一台真实机器中，并且都试图同时生成顺序GUID？在这些情况下，碰撞的可能性会大得多。您可能会想到在这些场景中可以用来减轻碰撞的技术。

Answer 2

经过研究，我无法使用默认排序对guid进行排序，甚至无法使用guid中的默认字符串表示。ToString作为字节顺序不同。

为了对UuidCreateSequential生成的guid进行排序，我需要转换为BigInteger，或者通过将字节按最重要到最不重要的顺序排列来形成我自己的字符串表示（即十六进制字符串32个字符），如下所示：

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

Answer 3

希望我能正确理解你的问题。看起来你正在尝试对你的Guid的HEX表示进行排序。这实际上意味着你是按字母顺序对它们进行排序，而不是按数字。

Guid将根据其在数据库中的字节值进行索引。这里有一个控制台应用程序来证明你的Guid是数字顺序的：

using System;
using System.Linq;
using System.Numerics;
class Program
{
    static void Main(string[] args)
    {
        //These are the sequential guids you provided.
        Guid[] guids = new[]
        {
            "53cd98f2504a11e682838cdcd43024a7",
            "7178df9d504a11e682838cdcd43024a7",
            "800b5b69504a11e682838cdcd43024a7",
            "9796eb73504a11e682838cdcd43024a7",
            "c14c5778504a11e682838cdcd43024a7",
            "c14c5779504a11e682838cdcd43024a7",
            "d2324e9f504a11e682838cdcd43024a7",
            "d2324ea0504a11e682838cdcd43024a7",
            "da3d4460504a11e682838cdcd43024a7",
            "e149ff28504a11e682838cdcd43024a7",
            "f2309d56504a11e682838cdcd43024a7",
            "f2309d57504a11e682838cdcd43024a7",
            "fa901efd504a11e682838cdcd43024a7",
            "fa901efe504a11e682838cdcd43024a7",
            "036340af504b11e682838cdcd43024a7",
            "11768c0b504b11e682838cdcd43024a7",
            "2f57689d504b11e682838cdcd43024a7"
        }.Select(l => Guid.Parse(l)).ToArray();
        //Convert to BigIntegers to get their numeric value from the Guids bytes then sort them.
        BigInteger[] values = guids.Select(l => new BigInteger(l.ToByteArray())).OrderBy(l => l).ToArray();
        for (int i = 0; i < guids.Length; i++)
        {
            //Convert back to a guid.
            Guid sortedGuid = new Guid(values[i].ToByteArray());
            //Compare the guids. The guids array should be sequential.
            if(!sortedGuid.Equals(guids[i]))
                throw new Exception("Not sequential!");
        }
        Console.WriteLine("All good!");
        Console.ReadKey();
    }
}