对 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：这里还有一些我生成的顺序 guid，似乎它们没有按照十六进制字符串

的升序排序

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

Answer 1

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

Guid 将按其在数据库中的字节值编制索引。这是一个控制台应用程序，用于证明您的 Guids 是按数字顺序排列的：

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();
    }
}

Answer 2

首先，让我们重申观察结果：当创建具有巨大时间延迟的顺序 GUID 时——60 十亿纳秒——在创建之间，生成的 GUID 不是顺序的.

am I missing something?

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

您有一项服务可以提供连续并且 在全宇宙 的所有计算机中唯一的号码。想一想这怎么可能。这不是一个魔术盒；必须有人编写该代码。

想象一下，如果您不必使用计算机来完成，而是必须手工完成。您为一项服务做广告：您向任何人提供连续的全球唯一编号随时。

现在，假设我问你三个这样的数字，你给出了 20、21 和 22。然后 六十年后我再问你三个，让你吃惊的是给我 13510985、13510986 和 13510987。"Wait just a minute here"，我说，"I wanted six sequential numbers, but you gave me three sequential numbers and then three more. What gives?"

嗯，你认为在那之后的 60 年里发生了什么？请记住，您随时向任何提出要求的人提供此服务。什么情况下可以给我23、24、25？ 仅当在那 60 年内没有其他人询问时。

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

实际上，顺序 GUID 生成器使用当前时间作为其策略的一部分来强制执行全局唯一属性。当前时间和当前位置是创建唯一号码的合理起点，因为在任何时候您的办公桌上大概只有一台计算机。

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

Answer 3

经过研究，我无法使用默认排序方式对 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!");
}

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

Sort Sequential Guids Generated by UuidCreateSequential

c#

guid