171

我已经阅读了该man页面,但我不明白它的用途namenamespace用途。

对于版本 3 和版本 5 UUID,必须提供额外的命令行参数命名空间和名称。命名空间是字符串表示形式的 UUID 或内部预定义命名空间 UUID 的标识符(目前已知为“ns:DNS”、“ns:URL”、“ns:OID”和“ns:X500”)。名称是任意长度的字符串。

命名空间:

命名空间是字符串表示形式的 UUID 或

这是否意味着我需要将它(UUID v4)存储在与生成的 UUID v5 相关的某个地方?在任何一种情况下,为什么这不会自动完成?

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

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

4

3 回答 3

282

Type 3 和 Type 5 UUID 只是一种将哈希填充到 UUID 中的技术:

  • 类型 1:填充MAC address+datetime成 128 位
  • 类型 3:将 anMD5 hash塞入 128 位
  • 类型 4:填充random data128 位
  • 类型 5:将SHA1散列塞入 128 位
  • 类型 6顺序 UUID 的非官方想法

编辑:非官方类型 6 现在有官方rfc

SHA1 哈希输出 160 位(20 字节);哈希的结果被转换为 UUID。

使用来自 SHA1 的 20 字节摘要:

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 位
  • 并将其转换为 128 位的 UUID

基本要点是只取前 128 位,将 a 填充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;
}

(注意:系统的字节序会影响上述字节的索引)

现在你可以打电话了:

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, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm');

现在回到你的问题

对于版本 3 和版本 5 UUID,必须提供额外的命令行参数命名空间和名称。命名空间是字符串表示形式的 UUID 或内部预定义命名空间 UUID 的标识符(目前已知为“ns:DNS”、“ns:URL”、“ns:OID”和“ns:X500”)。名称是任意长度的字符串。

命名空间是您喜欢的任何 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');
于 2015-02-28T01:04:47.450 回答
133

名称和命名空间可用于创建(很可能)唯一 UUID 的层次结构。

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

假设您有一个 (key,value) 存储,但它只支持一个命名空间。您可以使用类型 3 或类型 5 UUID 生成大量不同的逻辑命名空间。首先,为每个命名空间创建一个根 UUID。这可以是类型 1(主机+时间戳)或类型 4(随机)UUID,只要您将它存储在某处即可。或者,您可以为您的根创建一个随机 UUID(或使用nullUUID:00000000-0000-0000-0000-000000000000作为根),然后使用“ uuid -v5 $ROOTUUID $NAMESPACENAME”为每个命名空间创建一个可重现的 UUID。现在,您可以使用 "uuid -v5 $NAMESPACEUUID $KEY”。这些 UUID 可以被扔到单个键值存储中,避免冲突的可能性很高。这个过程可以递归地重复,例如,如果与 UUID 键关联的“值”反过来代表某种逻辑“命名空间” " 就像一个桶、容器或目录,那么它的 UUID 可以反过来用来生成更多层次的 UUID。

生成的类型 3 或类型 5 UUID 包含命名空间 id 和命名空间内名称(键)的(部分)散列。它不再保存命名空间 UUID,就像消息 MAC 保存对其进行编码的消息的内容一样。从 uuid 算法的角度来看,名称是一个“任意”(八位字节)字符串。但是,它的含义取决于您的应用程序。它可以是逻辑目录中的文件名、对象存储中的对象 ID 等等。

虽然这适用于中等数量的命名空间和键,但如果您的目标是大量唯一且概率非常高的键,它最终会失去动力。生日问题(又名生日悖论)的 Wikipedia 条目包括一个表格,该表格给出了不同数量的键和表格大小的至少一次冲突的概率。对于 128 位,以这种方式散列 260 亿个密钥的概率为p=10^-18(可忽略不计),但是 26 万亿个密钥,将至少发生一次冲突的概率增加到p=10^-12(万亿分之一),而散列26*10^15密钥,则增加了至少发生一次碰撞p=10^-6(百万分之一)。调整编码 UUID 类型的 5 位,它会更快地用完,因此一万亿个密钥大约有万亿分之一的机会发生一次碰撞。

有关概率表,请参见http://en.wikipedia.org/wiki/Birthday_problem#Probability_table

有关 UUID 编码的更多详细信息,请参阅http://www.ietf.org/rfc/rfc4122.txt

于 2013-03-13T19:55:55.677 回答
44

名称只不过是某个名称空间中唯一的标识符。问题是命名空间通常非常小,并且其中一个名称经常与其他名称冲突。例如,我的车牌号(名称)在我所在州 DMV 的命名空间中是唯一的,但它可能在世界上不是唯一的;其他州 DMV 可能在自己的命名空间中使用了相同的名称。哎呀,其他人可能有一个电话号码(姓名)也匹配,因为那是另一个命名空间等。

UUID 可以被看作是存在于一个单一的命名空间中,如此庞大以至于它可以为所有事物提供一个唯一的名称;这就是“普遍”的意思。但是如何将其他命名空间中的现有名称映射到 UUID?

一个明显的解决方案是为每个项目生成一个 UUID(V1 或 V4),以替换其不相交名称空间中的旧名称。缺点是它们要大得多,您必须将所有新名称传达给拥有数据集副本的每个人,更新所有 API 等。很可能您实际上无法完全摆脱旧名称无论如何,这意味着现在每个项目都有两个名称,那么你让事情变得更好还是更糟?

这就是 V3/V5 的用武之地。UUID看起来和 V4 一样随机,但实际上是确定性的;任何拥有命名空间正确 UUID 的人都可以独立地为该命名空间内的任何给定名称生成相同的 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 本身为用户、问题、答案、评论等提供了单独的命名空间,但这些也相当明显:

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。

于 2018-07-27T03:07:14.147 回答