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 null
UUID: 00000000-0000-0000-0000-000000000000
como 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^15
chaves 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.
UUIDs tipo 3 e tipo 5 são apenas uma técnica de inserir um hash em um UUID.
Um hash SHA1 gera 160 bits (20 bytes); o resultado do hash é convertido em um UUID.
Com o hash de 20 bytes de SHA1:
(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:
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:
A RFC então define como:
A essência básica é pegar apenas os primeiros 128 bits, inserir um
5
no registro de tipo e definir os dois primeiros bits daclock_seq_hi_and_reserved
seçã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):
(Observe que o endian-ness do seu sistema pode afetar os índices dos bytes acima)
Você pode receber chamadas:
Agora de volta à sua pergunta
O namespace é o UUID que você quiser. Pode ser um dos pré-definidos, ou você pode criar o seu próprio, por exemplo:
O nome é apenas o texto que você deseja anexar ao namespace, fazer o hash e colocá-lo em um UUID:
fonte
Namespace_RectalForeignExtractedObject
eu o faria.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:
O próprio StackOverflow tem namespaces separados para usuários, perguntas, respostas, comentários, etc., mas esses também são bastante óbvios:
Esta pergunta em particular é # 10867405, então seu UUID seria:
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.
fonte