GUID 不唯一的简单证明

Question

我想证明 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#。

Answer 1

这也是一个解决方案：

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

注意：需要 Qt，但我保证如果你让它运行足够长的时间，它可能会找到一个。

（注意：实际上，现在我正在查看它，生成算法可能会阻止两个随后生成的 uuid 发生冲突 - 但我有点怀疑）。

Answer 2

证明 GUID 不唯一的唯一解决方案是拥有世界 GUID 池。每次在某处生成 GUID 时，都应将其注册到组织。或者，我们可能会包含一个标准化，所有 GUID 生成器都需要自动注册它，为此它需要有效的互联网连接！

Answer 3

Kai，我提供了一个程序，可以使用线程执行您想要的操作。它是根据以下条款获得许可的：对于运行它的每个 CPU 核心，您必须每小时向我支付 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];     // 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 运行。

并澄清我的支持条款：仅在 2010 年 2 月 28 日提供支持。请仅在当天使用时间机器提出支持请求。

编辑2
一如既往，GC 在管理内存方面比我做得更好；以前我自己做的任何尝试都注定会失败。

Answer 4

这将运行几个小时以上。假设它以 1 GHz 循环（事实并非如此，它会比这个慢很多），它将运行 10790283070806014188970 年。这大约是宇宙年龄的830亿倍。

假设摩尔定律成立，不运行这个程序会快很多，等几百数年，并在速度快数十亿倍的计算机上运行。事实上，任何运行时间超过 CPU 速度加倍所需时间（大约 18 个月）的程序，如果您等到 CPU 速度增加并购买新的 CPU 后再运行它，那么它会更快完成（除非您编写的程序是这样的）可以在新硬件上暂停和恢复）。

Answer 5

GUID 理论上是不唯一的。这是你的证明：

• GUID 是一个 128 位数字
• 如果不重新使用旧的 GUID，则无法生成 2^128 + 1 或更多 GUID

但是，如果太阳的全部功率输出都用于执行此任务，那么它很早就会变冷它完成了。

GUID 可以使用多种不同的策略生成，其中一些策略采取特殊措施来保证给定的计算机不会两次生成相同的 GUID。在特定算法中查找冲突将表明您生成 GUID 的特定方法很糟糕，但通常不会证明有关 GUID 的任何信息。

Answer 6

当然 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。因此，如果每秒生成 10 亿个 GUID，则需要 36 年才能生成 2^60 随机 GUID，即使如此，发生冲突的概率仍然是 1.95e-03。您更有可能在生命中的某个时刻被谋杀 (4.76e-03) 比您在未来 36 年内发现碰撞的时间更长。祝你好运。

Answer 7

如果您担心唯一性，您可以随时购买新的 GUID，这样您就可以扔掉旧的 GUID。如果你愿意的话，我会把一些放在 eBay 上。

Answer 8

就我个人而言，我认为“大爆炸”是由两个 GUID 碰撞引起的。

Answer 9

您可以使用 Quantum bogosort 算法的变体在 O(1) 时间内证明这一点。

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

Answer 10

任何两个 GUID 很可能是唯一的（不相等）。

请参阅此SO条目，以及来自维基百科

虽然每个生成的 GUID 不是
保证是唯一的，总数
唯一键的数量（2^128 或
3.4×10^38) 如此之大以至于相同数字的概率
生成两次的值非常小。为了
例如，考虑可观察的
宇宙，大约包含 5×10^22
星星；每个明星都可以拥有
6.8×10^15 通用唯一 GUID。

因此，你可能还需要等待数十亿年，并希望你能在我们所知的宇宙终结之前到达这一点。

Answer 11

[更新：] 正如下面的评论所指出的，较新的 MS GUID 是 V4，并且不使用 MAC 地址作为 GUID 生成的一部分（我没有看到任何 V5 的迹象）不过，微软的实施，所以如果有人有确认链接，请告诉我）。但对于 V4，时间仍然是一个因素，而且 GUID 重复的可能性仍然很小，与任何实际用途无关。您当然不可能仅通过单个系统测试（例如 OP 尝试执行的操作）生成重复的 GUID。

这些答案中的大多数都缺少有关 Microsoft GUID 实现的一个重要点。 GUID 的第一部分基于时间戳，另一部分基于网卡的 MAC 地址（如果未安装 NIC，则为随机数）。

如果我理解正确的话，这意味着复制 GUID 的唯一可靠方法是在 MAC 地址相同且两个系统上的时钟在生成时处于同一精确时间的多台计算机上同时运行 GUID 生成。发生了（如果我理解正确的话，时间戳是基于毫秒的）……即使如此，数字中还有很多其他位是随机的，所以几率仍然很小。

出于所有实际目的，GUID 都是唯一的。

"对 MS GUID 有很好的描述老新事物”博客

Answer 12

如果您想在代码中的许多地方检查 guid 的唯一性，可以使用以下一个漂亮的小扩展方法。

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

要调用它，只需在生成新的 guid 时调用 Guid.IsUnique...

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

...哎呀，我什至建议调用它两次以确保它在第一轮中正确。

Answer 13

数到 2^128 - 雄心勃勃。

让我们想象一下，每台机器每秒可以计算 2^32 个 ID - 并不是那么雄心勃勃，因为每秒甚至不到 43 亿个。让我们专门使用 2^32 台机器来完成该任务。此外，让 2^32 个文明为每个任务分配相同的资源。

到目前为止，我们每秒可以计算 2^96 个 ID，这意味着我们将计算 2^32 秒（略多于 136 年）。

现在，我们需要的只是让 4,294,967,296 个文明为每个文明提供 4,294,967,296 台机器，每台机器每秒能够计算 4,294,967,296 个 ID，纯粹用于未来 136 年左右的这项任务 - 我建议我们现在就开始这项重要任务； -)

Answer 14

好吧，如果 830 亿年的运行时间没有吓到您，那么您还需要将生成的 GUID 存储在某个地方，以检查是否有重复项；存储 2^128 16 字节的数字只需要您预先分配 4951760157141521099596496896 TB 的 RAM，因此想象一下您有一台可以容纳所有这些的计算机，并且您以某种方式找到一个地方以每个 10 克的价格购买 TB 的 DIMM，将它们组合起来重量超过 8 个地球质量，因此您可以在按下“运行”之前认真地将其移离当前轨道。三思而后行！

Answer 15

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

您没有递增 begin，因此条件 begin begin begin begin begin begin begin begin begin begin begin end 始终为真。

Answer 16

如果 GUID 冲突是一个问题，我建议使用 ScottGuID 代替。

Answer 17

想必您有理由相信生成 Guid 的算法并没有生成真正的随机数，而是实际上以周期 << 循环。 2^128。

例如，用于导出 GUID 的 RFC4122 方法固定了某些位的值。

循环的证明将取决于周期的可能大小。

对于小周期，哈希表的 hash(GUID) -> GUID 碰撞时替换
如果 GUID 不匹配（如果匹配则终止）可能是一种方法。还可以考虑仅在随机的一段时间内进行替换。

最终，如果碰撞之间的最大周期足够大（并且事先不知道），则任何方法都只会产生碰撞存在时被发现的概率。

请注意，如果生成 Guid 的方法是基于时钟的（请参阅 RFC），则可能无法确定是否存在冲突，因为 (a) 您将无法等待足够长的时间让时钟绕回，或者 (b) 您无法在一个时钟周期内请求足够的 Guid 来强制发生碰撞。

或者，您也许能够显示 Guid 中的位之间的统计关系，或者 Guid 之间的位的相关性。这种关系可能会使算法很可能存在缺陷，但不一定能够找到实际的碰撞。

当然，如果你只是想证明Guids可以碰撞，那么答案就是数学证明，而不是程序。

Answer 18

我不明白为什么没有人提到升级你的显卡...当然，如果你有高端 NVIDIA Quadro FX 4800 或其他东西（192 个 CUDA 核心），这会更快...

当然，如果你能买得起几个 NVIDIA Qadro Plex 2200 S4（每个 960 个 CUDA 核心），这个计算会真的尖叫。也许 NVIDIA 愿意借给您一些用于“技术演示”作为公关噱头？

他们肯定想成为这个历史计算的一部分......

Answer 19

但是您是否必须确保您有重复项，或者您是否只关心是否可能有重复项。为了确保有两个人生日相同，需要 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 位已经很多了，所以你仍然在谈论大量的项目，但碰撞的可能性仍然很小。使用近似值，对于给定的赔率，您需要以下数量的记录：

• 8 亿，表示发生碰撞的可能性为 1/1000
• 217 亿，表示发生碰撞的可能性为 50%
• 396 亿，表示发生碰撞的可能性为 90% 每年大约发送 1E14 封电子邮件，因此

在这个水平上大约需要 400,000 年，您才有 90% 的机会收到两封具有相同 GUID 的电子邮件，但这与说您需要运行计算机有很大不同 83宇宙年龄的十亿倍，或者太阳在找到复制品之前会变冷。

Answer 20

你们没有错过一个要点吗？

我认为 GUID 是使用两个东西生成的，这使得它们成为全球唯一的机会非常高。一是它们使用您所在计算机的 MAC 地址作为种子，二是它们使用生成时间加上随机数。

因此，除非您在实际机器上运行它并在机器用于表示 GUID 中的时间的最短时间内运行所有猜测，否则无论您使用系统调用进行多少次猜测，都将永远不会生成相同的数字。

我想如果您知道 GUID 的实际制作方式，实际上会大大缩短猜测时间。

托尼

Answer 21

您可以散列 GUID。这样，您应该可以更快地获得结果。

哦，当然，同时运行多个线程也是一个好主意，这样您就可以增加竞争条件在不同线程上两次生成相同 GUID 的机会。

Answer 22

GUID 为 124 位，因为 4 位保存版本号。

Answer 23

1. 前往纽约市的低温实验室。
2. 将自己冻结（大约）1990 年。
3. 在 Planet Express 找到一份工作。
4. 购买全新的CPU。搭建一台计算机，运行程序，用末日机器之类的伪永动机将其放置在安全的地方。
5. 等到时间机器发明出来。
6. 使用时间机器跳转到未来。如果您购买的是 1YHz 128 位 CPU，则开始运行程序后转到3,938,453,320 天 20 小时 15 分 38 秒 463 ms 463 μs 374 ns 607 ps。
7. ...？
8. 利润！！！

...即使您有 1YHz CPU，即 1,000,000,000,000,000（或 1,125,899,906,842,624，如果您喜欢使用二进制前缀），也至少需要 10,783,127 年比 1GHz CPU 快数倍。

因此，与其等待计算完成，不如去喂养失去家园的鸽子，因为其他n鸽子夺走了它们的家。 :(

或者，你可以等到 128 位量子计算机发明。然后你可以通过在合理的时间（也许）使用你的程序来证明 GUID 不是唯一的。

Answer 24

您是否尝试过 begin = begin + new BigInteger((long)1) 代替 begin++ ？

Answer 25

如果生成的 UUID 数量遵循摩尔定律，那么在可预见的将来 GUID 永远不会耗尽的印象是错误的。

有了 2 ^ 128 个 UUID，只需要 18 个月 * Log2(2^128) ~= 192 年，我们就会用完所有 UUID。

我相信（没有任何统计证据）自从大规模采用 UUID 以来的过去几年中，我们生成 UUID 的速度增长速度比摩尔定律规定的要快得多。换句话说，我们距离应对 UUID 危机的时间可能还不到 192 年，这比宇宙末日要早得多。

但由于到 2012 年底我们肯定不会耗尽它们，因此我们将把这个问题留给其他物种来解决。

Answer 26

GUID 生成代码中出现错误的几率远高于算法生成冲突的几率。测试 GUID 的代码中出现错误的可能性更大。放弃。

Answer 27

该程序尽管有错误，但证明 GUID 不是唯一的。那些试图证明相反观点的人没有抓住要点。这个声明只是证明了一些 GUID 变体的弱实现。

GUID 不一定是唯一的，但它是高度唯一的。您刚刚精炼了高度的含义。根据版本、实现者（MS 或其他）、VM 的使用等，您的定义会发生很大的变化。 （请参阅之前帖子中的链接）

您可以缩短 128 位表来证明您的观点。最好的解决方案是使用哈希公式来缩短包含重复项的表，然后在哈希冲突时使用完整值，并基于此重新生成 GUID。如果从不同的位置运行，您将把哈希/完整密钥对存储在一个中央位置。

Ps：如果目标只是生成 x 个不同的值，则创建一个此宽度的哈希表并仅检查哈希值。

Answer 28

不是在这里的篝火上胡闹，但它确实发生了，是的，我理解你一直在给这个家伙开的玩笑，但 GUID 仅在原则上是唯一的，我遇到这个线程是因为有一个错误在 WP7 模拟器中，这意味着每次启动时，它都会在第一次调用时给出相同的 GUID！因此，理论上不会发生冲突，如果生成所述 GUI 时出现问题，那么您可以获得重复的

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

Answer 29

由于 Guid 生成的一部分基于当前计算机的时间，因此我获取重复 Guid 的理论是：

1. 执行 Windows 的全新安装
2. 创建一个启动脚本，将时间重置为 2010-01-01 12:00:00 就像 Windows 一样启动。
3. 启动脚本之后，它会触发您的应用程序生成 Guid。
4. 克隆此 Windows 安装，以便排除后续启动中可能出现的任何细微差异。
5. 使用此映像重新映像硬盘驱动器并启动计算机几次。

Answer 30

对我来说..单个核心生成 UUIDv1 所需的时间保证它是唯一的。即使在多核情况下，如果 UUID 生成器一次只允许为您的特定资源生成一个 UUID（请记住，多个资源可以完全利用相同的 UUID，但不太可能，因为资源本质上是地址的一部分），那么您将有足够多的 UUID 供您使用，直到时间戳耗尽为止。在这一点上我真的怀疑你会关心。