Gerando UUID v5. O que é nome e namespace?

125

Eu li a manpágina, mas eu não undestand o que namee namespacesão para.

Para UUIDs da versão 3 e 5, o namespace e o nome dos argumentos da linha de comando adicionais devem ser fornecidos. O namespace é um UUID em representação de string ou um identificador para UUIDs de namespace predefinidos internamente (atualmente conhecidos são "ns: DNS", "ns: URL", "ns: OID" e "ns: X500"). O nome é uma string de comprimento arbitrário.

O namespace:

O namespace é um UUID em representação de string ou um

Isso significa que preciso armazená-lo (UUID v4) em algum lugar em relação ao UUID v5 gerado? Em ambos os casos, por que isso não é feito automaticamente?

O nome é uma string de comprimento arbitrário.

nameuma string completamente aleatória? Qual é o propósito disso então? Ele pode ser decodificado do UUID v5?

Gajus
fonte

Respostas:

106

O nome e o namespace podem ser usados ​​para criar uma hierarquia de UUIDs (muito provavelmente) exclusivos.

A grosso modo, um UUID tipo 3 ou 5 é gerado por hash de um identificador de namespace com um nome. UUIDs tipo 3 usam MD5 e UUIDs tipo 5 usam SHA1. Apenas 128 bits estão disponíveis e 5 bits são usados ​​para especificar o tipo, portanto, todos os bits de hash não chegam ao UUID. (Além disso, o MD5 é considerado criptograficamente quebrado e o SHA1 está em seus últimos passos, portanto, não use isso para verificar os dados que precisam ser "muito seguros"). Dito isso, ele oferece uma maneira de criar uma função "hash" repetível / verificável, mapeando um nome possivelmente hierárquico em um valor de 128 bits probabilisticamente exclusivo, potencialmente agindo como um hash hierárquico ou MAC.

Suponha que você tenha um armazenamento (chave, valor), mas ele suporta apenas um namespace. Você pode gerar um grande número de namespaces lógicos distintos usando UUIDs tipo 3 ou 5. Primeiro, crie um UUID raiz para cada namespace. Este pode ser um UUID tipo 1 (host + carimbo de data / hora) ou tipo 4 (aleatório), desde que você o armazene em algum lugar. Como alternativa, você pode criar um UUID aleatório para sua raiz (ou usar o nullUUID: 00000000-0000-0000-0000-000000000000como raiz) e, em seguida, criar um UUID reproduzível para cada namespace usando " uuid -v5 $ROOTUUID $NAMESPACENAME". Agora você pode criar UUIDs exclusivos para chaves em um namespace usando "uuid -v5 $NAMESPACEUUID $KEY". Esses UUIDs podem ser colocados em um único armazenamento de valor-chave com alta probabilidade de evitar a colisão. Este processo pode ser repetido recursivamente para que se, por exemplo, o" valor "associado a uma chave UUID represente algum tipo de namespace lógico "como um balde, contêiner ou diretório, seu UUID pode ser usado para gerar UUIDs mais hierárquicos.

O UUID tipo 3 ou 5 gerado contém um hash (parcial) do id do namespace e do nome dentro do namespace (chave). Ele não contém mais o UUID do espaço de nomes do que um MAC de mensagem contém o conteúdo da mensagem a partir da qual é codificado. O nome é uma string "arbitrária" (octeto) da perspectiva do algoritmo uuid. Seu significado, entretanto, depende de sua aplicação. Pode ser um nome de arquivo dentro de um diretório lógico, id de objeto em um armazenamento de objeto, etc.

Embora isso funcione bem para um número moderadamente grande de namespaces e chaves, ele eventualmente perde força se você deseja um número muito grande de chaves únicas com probabilidade muito alta. A entrada da Wikipedia para o Problema do Aniversário (também conhecido como Paradoxo do Aniversário) inclui uma tabela que fornece as probabilidades de pelo menos uma colisão para vários números de chaves e tamanhos de mesa. Para 128 bits, o hash de 26 bilhões de chaves dessa forma tem uma probabilidade de colisão de p=10^-18(insignificante), mas 26 trilhões de chaves aumentam a probabilidade de pelo menos uma colisão com p=10^-12(um em um trilhão) e o hash de 26*10^15chaves aumenta a probabilidade de pelo menos uma colisão comp=10^-6(um em um milhão). Ajustando para 5 bits que codificam o tipo UUID, ele se esgotará um pouco mais rápido, de modo que um trilhão de chaves tem aproximadamente uma chance de 1 em um trilhão de ter uma única colisão.

Consulte http://en.wikipedia.org/wiki/Birthday_problem#Probability_table para a tabela de probabilidade.

Consulte http://www.ietf.org/rfc/rfc4122.txt para obter mais detalhes sobre as codificações UUID.

Jeff Anderson-Lee
fonte
2
Em um determinado nível na hierarquia, posso usar um UUIDv5 como o namespace e UUIDv4 como a chave aleatória para garantir que as colisões nos próprios dados (que estão sendo identificados por este GUID) não aumentem as chances de UUIDs em colisão? Algum problema de desempenho que eu deva saber?
ermik
Eu sou novo no conceito e fiquei intrigado sobre o que é essa hierarquia de que você está falando. Onde posso vê-lo, etc ... Alguma clareza veio quando eu mantive a explicação de que isso pode ser usado para criar um UUID reproduzível para namespace . Gostaria de saber se há uma maneira de verificar se um determinado UUID (do tipo 3 ou 5) foi gerado usando um determinado namespace (seu UUID)?
msciwoj
213

UUIDs tipo 3 e tipo 5 são apenas uma técnica de inserir um hash em um UUID.

  • Tipo 1: armazena endereço MAC + data e hora em 128 bits
  • Tipo 3 : armazena um hash MD5 em 128 bits
  • Tipo 4: armazena dados aleatórios em 128 bits
  • Tipo 5 : insere um hash SHA1 em 128 bits
  • Tipo 6: ideia não oficial para UUIDs sequenciais

Um hash SHA1 gera 160 bits (20 bytes); o resultado do hash é convertido em um UUID.

Com o hash de 20 bytes de SHA1:

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

(Observe que os primeiros dois bits de '9' já são 1 e 0, respectivamente, portanto, isso não tem efeito).

O que eu hash?

Você provavelmente está se perguntando o que é isso que devo fazer hash. Basicamente, você faz hash da concatenação de:

sha1([NamespaceUUID]+[AnyString]);

Você prefixa sua string com um denominado namespace para evitar conflitos de nome.

O UUID RFC pré-define quatro namespaces para você:

  • 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}

Então, você pode misturar:

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

A RFC então define como:

  • pegue os 160 bits de SHA1
  • e convertê-lo em 128 bits de um UUID

A essência básica é pegar apenas os primeiros 128 bits, inserir um 5no registro de tipo e definir os dois primeiros bits da clock_seq_hi_and_reservedseção como 1 e 0, respectivamente.

Mais exemplos

Agora que você tem uma função que gera um denominado Nome , pode ter a função (em pseudo-código):

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

(Observe que o endian-ness do seu sistema pode afetar os índices dos bytes acima)

Você pode receber chamadas:

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');

Agora de volta à sua pergunta

Para UUIDs da versão 3 e 5, o namespace e o nome dos argumentos da linha de comando adicionais devem ser fornecidos. O namespace é um UUID em representação de string ou um identificador para UUIDs de namespace predefinidos internamente (atualmente conhecidos são "ns: DNS", "ns: URL", "ns: OID" e "ns: X500"). O nome é uma string de comprimento arbitrário.

O namespace é o UUID que você quiser. Pode ser um dos pré-definidos, ou você pode criar o seu próprio, por exemplo:

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

O nome é uma string de comprimento arbitrário.

O nome é apenas o texto que você deseja anexar ao namespace, fazer o hash e colocá-lo em um 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');

Nota : Qualquer código lançado em domínio público. Nenhuma atribuição necessária.

Ian Boyd
fonte
45
Obrigado pela explicação completa. Se eu pudesse dar pontos de bônus, Namespace_RectalForeignExtractedObjecteu o faria.
boodle
É possível decodificar o nome ou o namespace decodificado do UUID?
Sathesh
3
@Sathesh Não, não é possível decodificar um hash; hashes são funções unilaterais. Por exemplo, a coleção inteira de Star Trek TNG Blu-Ray tem 81 GB e um hash de C5740BBBF2429115276D4AB60A020ED3ADE01192 . Não há como decodificar aquele hash de 20 bytes de volta para 81 GB. Se você realmente precisar, tente fazer o hash de todos os GUIDs e strings possíveis até encontrar a combinação que fornece o mesmo resultado. Com qualquer lanche, você o encontrará em algum lugar entre a eternidade e a eternidade.
Ian Boyd
22

Um nome nada mais é do que um identificador exclusivo em algum namespace. O problema é que os namespaces costumam ser bem pequenos e os nomes de um geralmente colidem com os nomes de outros. Por exemplo, o número da placa do meu carro (nome) é exclusivo no namespace do meu departamento de trânsito, mas provavelmente não é único no mundo; outros DMVs estaduais podem ter usado o mesmo nome em seus próprios namespaces. Caramba, outra pessoa pode ter um número de telefone (nome) que também corresponda porque esse é outro namespace, etc.

UUIDs podem ser vistos como habitando um único namespace tão vasto que pode fornecer um nome único para tudo ; isso é o que significa "universal". Mas como você mapeia nomes existentes em outros namespaces para um UUID?

Uma solução óbvia é gerar um UUID (V1 ou V4) para cada item para substituir os nomes antigos em seus namespaces separados. A desvantagem é que eles são muito maiores, você tem que comunicar todos os novos nomes a todos que têm uma cópia do seu conjunto de dados, atualizar todas as suas APIs, etc. Provavelmente, você não consegue se livrar totalmente dos nomes antigos de qualquer maneira, o que significa que agora cada item tem dois nomes, então você melhorou ou piorou as coisas?

É aqui que entra o V3 / V5. Os UUIDs parecem tão aleatórios quanto o V4, mas na verdade são determinísticos; qualquer pessoa que tenha o UUID certo para um namespace pode, então, de forma independente gerar o mesmo UUID para qualquer nome dentro desse namespace. Você não precisa publicá-los de forma alguma, nem mesmo pré-gerá-los, pois qualquer pessoa pode criá-los imediatamente, conforme necessário!

Nomes de DNS e URLs são namespaces usados ​​com muita freqüência, então UUIDs padrão foram publicados para eles; Os nomes ASN.1 OIDs e X.500 não são tão comuns, mas os órgãos de padrões os adoram, então eles publicaram UUIDs de namespace padrão para eles também.

Para todos os outros namespaces, você deve gerar seu próprio UUID de namespace (V1 ou V4) e comunicá-lo a quem precisar. Se você tiver vários namespaces, ter que publicar o UUID para cada um claramente não é o ideal.

É aqui que entra a hierarquia: você cria um UUID "base" (de qualquer tipo) e, em seguida, usa-o como um namespace para nomear seus outros namespaces! Assim, basta publicar o UUID base (ou usar um óbvio), e todos podem calcular o resto.

Por exemplo, vamos continuar, queríamos criar alguns UUIDs para StackOverflow; que tem um nome óbvio dentro do namespace DNS, então a base é óbvia:

uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

O próprio StackOverflow tem namespaces separados para usuários, perguntas, respostas, comentários, etc., mas esses também são bastante óbvios:

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');

Esta pergunta em particular é # 10867405, então seu UUID seria:

uuid here = uuidv5(ns_question, '10867405');

Observe que não há nada aleatório neste processo, então qualquer pessoa que siga a mesma lógica obterá a mesma resposta, mas o namespace UUID é tão vasto que (efetivamente, dada a segurança de um hash criptográfico de 122 bits) nunca colidirá com um UUID gerado a partir de qualquer outro par de namespace / nome.

StephenS
fonte
Estou me perguntando por que stackoverflow precisa mapear um grande inteiro gerado exclusivamente para um UUID, dado que suas APIs aparentemente retornam apenas o grande inteiro como uma string. Onde o UUID seria usado se não na API. Parece que devemos selecionar um UUID ou BIGINT? Por que fazer essa estratégia híbrida. Mesmo assim, +1 pela explicação clara em sua resposta.
nishant
4
O UUID V3 / V5 foi projetado para quando você precisa converter de forma determinística os namespaces existentes (e provavelmente em conflito) em um namespace UUID, que geralmente é útil ao mesclar conjuntos de dados. Se isso não se aplica ao que você está fazendo, vá com V1 / V4.
StephenS