生成v5 UUID。名称和命名空间是什么?

223

我已经阅读了man页面,但是我不理解什么是namenamespace

对于版本3和版本5的UUID,需要提供附加的命令行参数namespace和name。命名空间可以是UUID字符串表示形式,也可以是内部预定义命名空间UUID的标识符(当前已知的为“ns:DNS”、“ns:URL”、“ns:OID”和“ns:X500”)。名称是任意长度的字符串。

命名空间:

命名空间可以是UUID字符串表示形式,也可以是内部预定义命名空间UUID的标识符。

这是否意味着我需要将它(UUID v4)存储在与生成的UUID v5有关的地方?无论哪种情况,为什么不自动完成此操作?

名称是任意长度的字符串。

name是完全随机的字符串吗?那么它的目的是什么?它可以从UUID v5中解码吗?


2
你能澄清一下这是Unix/Linux系统吗?需要查看哪个man手册? - AncientSwordRage
3个回答

375

第3类和第5类UUID仅是将散列值(hash)嵌入UUID中的一种技术:

  • 第1类:将MAC地址+日期时间填入128位
  • 第3类:将MD5散列值填入128位
  • 第4类:将随机数据填入128位
  • 第5类:将SHA1散列值填入128位
  • 第6类用于生成顺序UUID的非官方想法

编辑:非官方的第6类现在有一个官方rfc文档

SHA1散列值输出160位(20个字节);将散列结果转换为UUID。

以20字节的SHA1摘要为例:

SHA1 Digest:   74738ff5 5367 e958 1aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ⭡    ⬑first two bits set to 1 and 0, respectively
                             ╰─low nibble is set to 5, to indicate type 5

我应该哈希什么?

您可能想知道我应该哈希什么。基本上,您需要哈希以下内容的连接:

sha1(NamespaceUUID+AnyString);

您需要在字符串前加上所谓的命名空间以防止名称冲突。

UUID RFC为您预定义了四个命名空间:

  • NameSpace_DNS: {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_URL: {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_OID: {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_X500:{6ba7b814-9dad-11d1-80b4-00c04fd430c8}

因此,您可以将其组合起来进行哈希:

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com");
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com");

RFC文档随后定义如何:

  • 从SHA1中取出160位
  • 将其转换为UUID的128位

基本思路是只取前128位,在类型记录中插入一个5,然后将clock_seq_hi_and_reserved部分的第一二位分别设置为1和0。

更多示例

现在你有一个生成所谓Name的函数,你可以编写函数(伪代���):

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    //Note: All code on stackoverflow is public domain - no attribution required.

    Byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    Uuid result;

    //Copy first 16-bytes of the hash into our Uuid result
    Copy(hash, result, 16);

    //set high-nibble to 5 to indicate type 5
    result[6] &= 0x0F; 
    result[6] |= 0x50; 

    //set upper two bits to "10"
    result[8] &= 0x3F; 
    result[8] |= 0x80; 

    return result;
}
(Note:您系统的字节序可能会影响上述字节的索引) 现在您可以进行调用:
uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com');
uuid = NameToUUID(Namespace_DNS, 'www.google.com');
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com');
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112');
uuid = NameToUUID(Namespace_URL, 'https://dev59.com/11XTa4cB1Zd3GeqP5M1U');

现在回答你的问题

对于版本3和版本5的UUID,还需要提供额外的命令行参数namespace和name。namespace可以是字符串表示的UUID,也可以是内部预定义命名空间UUID的标识符(目前已知的有“ns:DNS”、“ns:URL”、“ns:OID”和“ns:X500”)。name是任意长度的字符串。

namespace可以是你喜欢的任何UUID。它可以是预定义的其中之一,也可以是您自己定义的,例如:1

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

名称是任意长度的字符串。

名称只是您希望附加到命名空间的文本,然后将其散列化并填充到UUID中:


uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch');

88
谢谢您详细的解释。如果我可以为“Namespace_RectalForeignExtractedObject”给予额外的奖励分数,我会这样做。 - boodle
1
能否从UUID中解码出名称或命名空间? - Sathesh
28
不,无法解码哈希值,因为哈希是单向函数。例如,整个《星际迷航TNG蓝光合集》大小为81 GB,其哈希值为C5740BBBF2429115276D4AB60A020ED3ADE01192。无法将20字节的哈希值还原回81 GB。如果确实需要,可以尝试对所有可能的GUID和可能的字符串进行哈希运算,直到找到产生相同结果的组合为止。但是需要非常幸运才能在永恒之间找到它。 - Ian Boyd
1
将文本转换为字节数组时应使用哪种编码? - sdgfsdh
根据RFC的规定,您可以使用适当的编码方式(将名称转换为八位字节的规范序列(根据其名称空间的标准或约定定义);将名称空间ID按网络字节顺序排列)。如果您正在创建自己的名称空间,可以使用任何您喜欢的编码方式。我喜欢UTF-32大端序。 - undefined

146

名称和命名空间可以用来创建层次结构的(非常可能)唯一的UUID。

粗略地说,类型3或类型5的UUID是通过将命名空间标识符与名称进行哈希生成的。类型3 UUID使用MD5,类型5 UUID使用SHA1。只有128位可用,其中5位用于指定类型,因此并非所有哈希位都能进入UUID。(此外,MD5被认为在密码学上已经破解,SHA1也处于最后时刻,因此不要使用它来验证需要“非常安全”的数据)。尽管如此,它为您提供了一种创建可重复/可验证的“哈希”函数的方法,将可能是分层哈希或MAC的概率唯一的128位值映射到可能具有层次结构的名称。

假设你有一个(key,value)存储,但它只支持一个命名空间。您可以使用类型3或类型5 UUID生成大量不同的逻辑命名空间。首先,为每个命名空间创建一个根UUID。这可以是类型1(主机+时间戳)或类型4(随机)UUID,只要您将其放在某个地方即可。或者,您可以为根创建一个随机UUID(或使用null UUID:00000000-0000-0000-0000-000000000000作为根),然后使用“uuid-v5 $ROOTUUID $NAMESPACENAME”为每个命名空间创建可重现的UUID。现在,您可以使用“uuid-v5 $NAMESPACEUUID $KEY”为命名空间内的键创建唯一的UUID。这些UUID可以投入到单个键值存储中,并有很高的避免冲突的概率。这个过程可以递归地重复,以便如果例如与UUID键相关联的“值”代表某种逻辑上的“命名空间”,如桶、容器或目录,则其UUID可以用于生成更多的分层UUID。

生成的类型 3 或类型 5 UUID 包含了命名空间 ID 和命名空间中名称 (key) 的 (部分) 哈希值。它不仅仅包含了命名空间 UUID,就像消息 MAC 不会包含编码自身的消息内容。从 uuid 算法的角度来看,这个名称是一个“任意”的(八位字节)字符串。然而,它的含义取决于你的应用程序。它可以是逻辑目录中的文件名,对象存储中的对象 ID 等等。
虽然对于中等数量的命名空间和 key,这种方法效果良好,但如果你的目标是想要具有非常高概率的大量唯一键,它最终会失效。维基百科关于生日问题(也称为生日悖论)的条目包括一张表格,列出了不同数量的键和表大小时至少发生一次冲突的概率。对于 128 位哈希和 260亿个键,它的碰撞概率为 p=10^-18(可以忽略不计),但对于 26万亿个键,它的碰撞概率增加到 p=10^-12(千亿分之一),而对于哈希 26*10^15 个键,则将至少发生一次碰撞的概率增加到 p=10^-6(百万分之一)。考虑到编码 UUID 类型的 5 位,它会更快耗尽,所以万亿个键大约有 1/万亿 的机会出现单个冲突。
请参见 http://en.wikipedia.org/wiki/Birthday_problem#Probability_table 了解概率表格。
请参见 http://www.ietf.org/rfc/rfc4122.txt 了解 UUID 编码的更多细节。

2
在某个层次结构下,我可以使用UUIDv5作为命名空间,使用UUIDv4作为随机键来确保数据本身中的碰撞(由此GUID标识)不会增加UUID碰撞的机会吗?我需要了解哪些性能问题? - ermik
1
我对这个概念很陌生,不太明白你所说的“层次结构”是什么。我在哪里可以看到它等等...当我坚持解释时,有些清晰度出现了,这可能用于为命名空间创建可重复的UUID。我想知道是否有一种方法可以验证给定类型为3或5的UUID是否已使用特定命名空间(其UUID)生成。 - msciwoj

64
一个名称只是在某个命名空间内唯一的标识符。问题是,命名空间通常很小,其中的名称经常与其他命名空间中的名称冲突。例如,我的汽车牌照号码(名称)在我所在州的DMV(Department of Motor Vehicles)命名空间内是唯一的,但在全球范围内可能并不唯一;其他州的DMV可能在其自己的命名空间中使用了相同的名称。甚至可能有人拥有一个电话号码(名称)也匹配,因为那是另一个命名空间,等等。
UUID可以被视为居住在单个命名空间中,该命名空间非常广泛,可以为“所有”提供唯一名称;这就是“通用”的含义。但是,如何将其他命名空间中的现有名称映射到UUID呢?
一个明显的解决方案是为每个项目生成一个UUID(V1或V4),以替换它们各自命名空间中的旧名称。缺点是它们更大,必须向所有拥有数据集副本的人传达所有新名称,更新所有API等。你可能无法完全摆脱旧名称,这意味着现在每个项目都有“两个”名称,那么你是否使情况变得更好还是更糟呢?
这就是V3 / V5发挥作用的地方。UUID看起来和V4一样随机,但实际上是确定性的;拥有正确命名空间的任何人都可以独立生成相同名称的UUID。你根本不需要发布它们,甚至不需要预先生成它们,因为任何人都可以在需要时立即创建它们!
DNS名称和URL是非常常用的命名空间,因此为其发布了标准UUID;ASN.1 OID和X.500名称并不常见,但标准机构喜欢它们,因此也为它们发布了标准命名空间UUID。
对于所有其他命名空间,您必须生成自己的命名空间UUID(V1或V4)并将其传达给需要使用它的任何人。如果您有多个命名空间,则必须发布每个命名空间的UUID显然不理想。
这就是层次结构的作用:您创建一个“基本”UUID(无论类型如何),然后将其用作为其他命名空间命名的命名空间!这样,您只需发布基本UUID(或使用明显的UUID),每个人都可以计算出其余部分。
例如,假设我们想为StackOverflow创建一些UUID;它在DNS命名空间中有一个明显的名称,因此基地址很明显:
uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

StackOverflow本身为用户、问题、回答、评论等拥有独立的命名空间,但这些很明显:

StackOverflow为每个类型(用户、问题、回答、评论等)拥有不同的命名空间。

uuid ns_user     =  uuidv5( ns_base, 'user'     );
uuid ns_question =  uuidv5( ns_base, 'question' );
uuid ns_answer   =  uuidv5( ns_base, 'answer'   );
uuid ns_comment  =  uuidv5( ns_base, 'comment'  );

这个特定问题的编号是#10867405,因此它的UUID将是:

uuid here = uuidv5(ns_question, '10867405');
请注意,这个过程中没有任何随机性,因此任何遵循相同逻辑的人将得到相同的答案,但UUID命名空间非常广阔,它(在122位密码哈希的安全性条件下)永远不会与从任何其他命名空间/名称对生成的UUID发生冲突。

我在想为什么stackoverflow需要将一个唯一生成的大整数映射到UUID,因为它的API似乎只返回大整数作为字符串。如果UUID不在API中使用,那么它会用在哪里呢?看起来我们应该选择UUID或BIGINT之一?为什么要采用这种混合策略?但是对于你回答中清晰的解释我还是点个赞。 - nishant
15
UUID V3/V5被设计用于将现有(且可能冲突的)命名空间确定性地转换为一个UUID命名空间,这在合并数据集时经常很有用。如果这不适用于您正在进行的工作,请选择V1/V4。 - StephenS
这是一个非常棒的答案。谢谢你。 - conner.xyz
这个应该是被接受的答案,谢谢。 - rednafi
我认为这应该是接受的答案,谢谢。 - Dannylo Dangel
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接