Génération de l'UUID v5. Qu'est-ce qu'un nom et un espace de noms ?

Question

J'ai lu le man page, mais je ne comprends pas ce que name y namespace sont destinés à.

Pour les UUID de la version 3 et de la version 5, les arguments supplémentaires de la ligne de commande doivent être fournis. L'espace de noms est soit un UUID sous forme de chaîne de caractères ou un pour les espaces de noms prédéfinis en interne (actuellement connus sous les noms de "ns:DNS", "ns:URL", "ns:OID" et "ns:X500"). Les est une chaîne de caractères de longueur arbitraire.

L'espace de noms :

L'espace de noms est soit un UUID sous la forme d'une chaîne de caractères, soit un

Cela signifie-t-il que je dois le stocker (UUID v4) quelque part par rapport à l'UUID v5 généré ? Dans un cas comme dans l'autre, pourquoi cela ne se fait-il pas automatiquement ?

Le nom est une chaîne de caractères de longueur arbitraire.

name une chaîne de caractères totalement aléatoire ? À quoi sert-elle alors ? Peut-on la décoder à partir de l'UUID v5 ?

Answer 1

Les UUID de type 3 et de type 5 ne sont qu'une technique d'insertion d'un hachage en un UUID :

• Type 1 : trucs et astuces MAC address + datetime en 128 bits
• Type 3 Le projet de loi sur l'emploi et l'égalité des chances est en cours d'élaboration. MD5 hash en 128 bits
• Type 4 : trucs et astuces random data en 128 bits
• Type 5 Le projet de loi sur l'emploi et l'égalité des chances est en cours d'élaboration. SHA1 hachage en 128 bits
• Type 6 : idée non officielle pour les UUID séquentiels

Editer : Le type 6 non officiel a maintenant un type officiel rfc

Un hachage SHA1 produit 160 bits (20 octets) ; le résultat du hachage est converti en UUID.

Avec un condensé de 20 octets de 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

Qu'est-ce que je hache ?

Vous vous demandez probablement ce que je suis censé hacher. En fait, il s'agit de hacher la concaténation de :

sha1( NamespaceUUID + AnyString ) ;

Vous préfixez votre chaîne de caractères par ce que l'on appelle un espace de noms pour éviter les conflits de noms.

En UUID RFC prédéfinit quatre espaces de noms pour vous :

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

Ainsi, vous pourriez hacher ensemble :

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

Le RFC définit ensuite comment :

• prendre les 160 bits de SHA1
• et le convertir en 128 bits d'un UUID

L'idée de base est de ne prendre que les 128 premiers bits, de mettre un 5 dans le type puis de définir les deux premiers bits de l'enregistrement clock_seq_hi_and_reserved à 1 et 0, respectivement.

Plus d'exemples

Maintenant que vous disposez d'une fonction qui génère un fichier appelé Nom vous pouvez avoir la fonction (en pseudo-code) :

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 : l'endianité de votre système peut affecter les indices des octets ci-dessus)

Vous pouvez désormais passer des appels :

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

Revenons à votre question

Pour les UUID de la version 3 et de la version 5, les arguments supplémentaires de la ligne de commande namespace et name doivent être fournis. L'espace de noms est soit un UUID sous forme de chaîne de caractères, soit un identifiant pour des UUID d'espaces de noms prédéfinis en interne (actuellement connus sous les noms de "ns:DNS", "ns:URL", "ns:OID" et "ns:X500"). Le nom est une chaîne de longueur arbitraire.

En espace de noms est l'UUID de votre choix. Il peut s'agir d'un des UUID prédéfinis, ou vous pouvez créer le vôtre, par exemple 1 :

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

Le nom est une chaîne de caractères de longueur arbitraire.

Le nom est simplement le texte que vous souhaitez voir ajouté à l'espace de noms, puis haché et inséré dans un 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

Le nom et l'espace de noms peuvent être utilisés pour créer une hiérarchie d'UUID (très probablement) uniques.

En gros, un UUID de type 3 ou de type 5 est généré par le hachage d'un identifiant d'espace de noms et d'un nom. Les UUID de type 3 utilisent MD5 et les UUID de type 5 utilisent SHA1. Seuls 128 bits sont disponibles et 5 bits sont utilisés pour spécifier le type, de sorte que tous les bits de hachage ne sont pas inclus dans l'UUID. (De plus, MD5 est considéré comme cryptographiquement cassé, et SHA1 est sur ses dernières jambes, donc ne l'utilisez pas pour vérifier des données qui ont besoin d'être "très sécurisées"). Cela dit, cette méthode permet de créer une fonction de "hachage" répétable/vérifiable qui met en correspondance un nom éventuellement hiérarchique avec une valeur unique probabiliste de 128 bits, ce qui peut agir comme un hachage hiérarchique ou un MAC.

Supposons que vous disposiez d'un magasin (clé, valeur), mais qu'il ne prenne en charge qu'un seul espace de noms. Vous pouvez générer un grand nombre d'espaces de noms logiques distincts en utilisant des UUID de type 3 ou de type 5. Commencez par créer un UUID racine pour chaque espace de noms. Il peut s'agir d'un UUID de type 1 (hôte + horodatage) ou de type 4 (aléatoire), à condition que vous le conserviez quelque part. Vous pouvez également créer un UUID aléatoire pour votre racine (ou utilisez la fonction null UUID : 00000000-0000-0000-0000-000000000000 en tant que Root), puis créer un UUID reproductible pour chaque espace de noms en utilisant " uuid -v5 $ROOTUUID $NAMESPACENAME ". Vous pouvez maintenant créer des UUID uniques pour les clés d'un espace de noms en utilisant " uuid -v5 $NAMESPACEUUID $KEY ". Ces UUID peuvent être jetés dans un seul magasin de valeurs clés avec une forte probabilité d'éviter les collisions. Ce processus peut être répété de manière récursive, de sorte que si, par exemple, la "valeur" associée à une clé UUID représente à son tour une sorte d'"espace de noms" logique tel qu'un seau, un conteneur ou un répertoire, son UUID peut être utilisé à son tour pour générer d'autres UUID hiérarchiques.

L'UUID de type 3 ou de type 5 généré contient un hachage (partiel) de l'identifiant de l'espace de nommage et du nom au sein de l'espace de nommage (clé). Il ne contient pas plus l'UUID de l'espace de nommage qu'un MAC de message ne contient le contenu du message à partir duquel il est encodé. Le nom est une chaîne "arbitraire" (octet) du point de vue de l'algorithme uuid. Sa signification dépend toutefois de votre application. Il peut s'agir d'un nom de fichier dans un répertoire logique, d'un identifiant d'objet dans un magasin d'objets, etc.

Si cette méthode fonctionne bien pour un nombre modérément élevé d'espaces de noms et de clés, elle finit par s'essouffler si l'on vise un très grand nombre de clés uniques avec une très forte probabilité. L'entrée de Wikipédia consacrée au problème de l'anniversaire (ou paradoxe de l'anniversaire) comprend un tableau qui donne les probabilités d'au moins une collision pour différents nombres de clés et différentes tailles de tables. Pour 128 bits, le hachage de 26 milliards de clés de cette manière a une probabilité de collision de p=10^-18 (négligeable), mais 26 billions de clés, fait passer la probabilité d'au moins une collision à p=10^-12 (un sur mille milliards), et le hachage 26*10^15 augmente la probabilité d'au moins une collision à p=10^-6 (un sur un million). Si l'on tient compte des 5 bits qui codent le type d'UUID, l'épuisement est un peu plus rapide, de sorte qu'un billion de clés ont environ une chance sur un billion d'avoir une seule collision.

Véase http://en.wikipedia.org/wiki/Birthday_problem#Probability_table pour la table de probabilité.

Véase http://www.ietf.org/rfc/rfc4122.txt pour plus de détails sur les encodages UUID.

Answer 3

Un nom n'est rien d'autre qu'un identifiant unique au sein d'un espace de noms. Le problème est que les espaces de noms sont souvent très petits et que les noms d'un espace entrent souvent en collision avec des noms d'autres espaces. Par exemple, le numéro de plaque d'immatriculation de ma voiture (nom) est unique dans l'espace de noms du service des immatriculations de mon État, mais il n'est probablement pas unique au monde ; d'autres services des immatriculations d'États peuvent avoir utilisé le même nom dans leurs propres espaces de noms. Il se peut aussi que quelqu'un d'autre ait un numéro de téléphone (nom) qui corresponde également, parce qu'il s'agit d'un autre espace de noms, etc.

Les UUID peuvent être considérés comme appartenant à un espace de noms unique, si vaste qu'il peut fournir un nom unique pour les tout c'est ce que signifie le terme "universel". Mais comment faire correspondre des noms existants dans d'autres espaces de noms à un UUID ?

Une solution évidente consiste à générer un UUID (V1 ou V4) pour chaque élément afin de remplacer les anciens noms dans leurs espaces de noms disjoints. L'inconvénient est qu'ils sont beaucoup plus grands, vous devez communiquer tous les nouveaux noms à tous ceux qui ont une copie de votre jeu de données, mettre à jour toutes vos API, etc. Il est probable que vous ne puissiez pas vous débarrasser complètement des anciens noms, ce qui signifie que chaque élément a désormais un nom deux noms, avez-vous amélioré ou aggravé la situation ?

C'est là qu'interviennent les V3/V5. Les UUID regarder aussi aléatoire que la V4, mais sont en fait déterministes ; quiconque possède le bon UUID pour un espace de noms peut alors de manière indépendante générer le même UUID pour tout nom donné dans cet espace de noms. Il n'est pas nécessaire de les publier, ni même de les pré-générer, puisque tout le monde peut les créer à la volée, en fonction des besoins !

Les noms DNS et les URL sont des espaces de noms très couramment utilisés, et des UUID standard ont donc été publiés pour ceux-ci ; les OID ASN.1 et les noms X.500 ne sont pas aussi courants, mais les organismes de normalisation les adorent, et ils ont donc publié des UUID standard pour ces espaces de noms également.

Pour tous les autres espaces de noms, vous devez générer votre propre UUID d'espace de noms (V1 ou V4) et le communiquer à toute personne qui en a besoin. Si vous avez plusieurs espaces de noms, le fait de devoir publier l'UUID pour chacun d'entre eux n'est évidemment pas la solution idéale.

C'est là qu'intervient la hiérarchie : vous créez un UUID "de base" (quel que soit le type), puis vous l'utilisez comme espace de noms pour nommer vos autres espaces de noms ! Ainsi, vous n'avez qu'à publier l'UUID de base (ou utiliser un UUID évident), et tout le monde peut calculer le reste.

Par exemple, disons que nous voulions créer des UUID pour StackOverflow, dont le nom est évident dans l'espace de noms DNS, et dont la base est donc évidente :

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

StackOverflow lui-même a des espaces de noms séparés pour les utilisateurs, les questions, les réponses, les commentaires, etc :

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

Cette question particulière est #10867405, son UUID serait donc :

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

Remarquez qu'il y a rien Pourtant, l'espace de noms UUID est si vaste qu'il n'entrera jamais en collision (compte tenu de la sécurité d'un hachage cryptographique de 122 bits) avec un UUID généré à partir d'une autre paire nom/espace de noms.