生成v5 UUID.什么是名称和名称空间？

Question

我读过的man页面,但我不已了解了name和namespace是.

对于版本3和版本5 UUID,必须提供附加命令行参数命名空间和名称.命名空间是字符串表示形式的UUID或内部预定义命名空间UUID的标识符(当前已知为"ns:DNS","ns:URL","ns:OID"和"ns:X500").名称是一个任意长度的字符串.

命名空间:

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

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

名称是一个任意长度的字符串.

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

Answer 1

类型3和类型5 UUID只是将哈希填充到UUID中的技术.

• 类型1:填充MAC地址,日期时间为128位
• 类型3:将MD5哈希填充到128位
• 类型4:将随机数据填充到128位
• 类型5:将SHA1哈希填充到128位

SHA1哈希输出160位(20字节).哈希的结果被转换为UUID.来自SHA1的20个字节:

SHA1 Digest:   74738ff5 5367 e958 9aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ^_low nibble is set to 5 to indicate type 5
                                  ^_first two bits set to 1 and 0, respectively

(注意,'9'的前两位分别是1和0,所以这没有效果).

哈哈什么？

你可能想知道我应该散列什么.基本上你哈希连接:

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位,5在类型记录中填充a ,然后将该clock_seq_hi_and_reserved部分的前两位分别设置为1和0.

更多例子

现在您有一个生成所谓Name的函数,您可以使用该函数(伪代码):

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    UUID result;
    Copy(hash, result, 16);
    result[6] &= 0x0F; 
    result[6] |= 0x50;
    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.它可以是预定义的一个,也可以自己组成,例如:

UUID Namespace_RectalForeignExtractedObject = '4d79546f-6e67-7565-496e-486572417373'

名称是一个任意长度的字符串.

该名称只是您要附加到命名空间的文本,然后散列并填充到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');

注意:任何代码都会发布到公共领域.无需归属.

Answer 2

名称和命名空间可用于创建(很可能)唯一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以root身份),然后使用" uuid -v5 $ROOTUUID $NAMESPACENAME" 为每个命名空间创建可重现的UUID .现在,您可以使用" uuid -v5 $NAMESPACEUUID $KEY" 为命名空间内的键创建唯一的UUID .这些UUID可以被抛入单个键值存储中,很可能避免冲突.可以递归地重复该过程,以便例如如果与UUID密钥相关联的"值"依次表示某种逻辑"命名空间"(如桶,容器或目录),则可以依次使用其UUID来生成更多层次结构.的UUID.

生成的类型3或类型5 UUID保存命名空间标识和名称空间(标识)内的(部分)哈希.它不再保留命名空间UUID,而不是消息MAC保存它所编码的消息的内容.从uuid算法的角度来看,该名称是"任意"(八位字节)字符串.但其含义取决于您的应用.它可以是逻辑目录中的文件名,对象存储中的object-id等.

虽然这适用于大量的名称空间和密钥,但如果您的目标是非常大的密钥以非常高的概率存在,它最终会失去动力.生日问题(又名生日悖论)的维基百科条目包括一个表格,该表格给出了针对不同数量的键和表格大小的至少一次碰撞的概率.对于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.

Answer 3

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

UUID可以被视为居住在一个如此庞大的名称空间中,它可以为所有内容提供唯一的名称; 这就是"普遍"的含义.但是,如何将其他命名空间中的现有名称映射到UUID？

一个显而易见的解决方案是为每个项生成UUID(V1或V4)以替换其不相交的命名空间中的旧名称.缺点是它们要大得多,你必须将所有新名称传达给拥有数据集副本的所有人,更新所有API等等.你可能无法完全摆脱旧名称无论如何,这意味着现在每个项目都有两个名字,所以你做得更好还是更糟？

这就是V3/V5的用武之地.UUID 看起来和V4一样随机,但实际上是确定性的; 任何拥有命名空间的正确UUID的人都可以为该命名空间中的任何给定名称独立生成相同的UUID.您根本不需要发布它们,甚至不需要预先生成它们,因为任何人都可以根据需要动态创建它们!

DNS名称和URL是非常常用的名称空间,因此为这些名称和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.