Comment créer des guides déterministes

103

Dans notre application, nous créons des fichiers Xml avec un attribut qui a une valeur Guid. Cette valeur devait être cohérente entre les mises à niveau de fichiers. Ainsi, même si tout le reste du fichier change, la valeur guid de l'attribut doit rester la même.

Une solution évidente était de créer un dictionnaire statique avec le nom de fichier et les Guids à utiliser pour eux. Ensuite, chaque fois que nous générons le fichier, nous recherchons dans le dictionnaire le nom de fichier et utilisons le guid correspondant. Mais ce n'est pas faisable car nous pourrions passer à des centaines de fichiers et ne voulions pas maintenir une grande liste de guides.

Une autre approche consistait donc à rendre le Guid identique en fonction du chemin du fichier. Étant donné que nos chemins de fichiers et notre structure de répertoires d'application sont uniques, le Guid doit être unique pour ce chemin. Ainsi, chaque fois que nous exécutons une mise à niveau, le fichier obtient le même GUID en fonction de son chemin. J'ai trouvé un moyen sympa de générer de tels « guides déterministes » (merci Elton Stoneman). Il fait essentiellement ceci:

private Guid GetDeterministicGuid(string input) 

{ 

//use MD5 hash to get a 16-byte hash of the string: 

MD5CryptoServiceProvider provider = new MD5CryptoServiceProvider(); 

byte[] inputBytes = Encoding.Default.GetBytes(input); 

byte[] hashBytes = provider.ComputeHash(inputBytes); 

//generate a guid from the hash: 

Guid hashGuid = new Guid(hashBytes); 

return hashGuid; 

} 

Donc, étant donné une chaîne, le Guid sera toujours le même.

Y a-t-il d'autres approches ou moyens recommandés pour y parvenir? Quels sont les avantages ou les inconvénients de cette méthode?

Punit Vora
la source

Réponses:

151

Comme mentionné par @bacar, RFC 4122 §4.3 définit un moyen de créer un UUID basé sur le nom. L'avantage de faire cela (par rapport à la simple utilisation d'un hachage MD5) est que ceux-ci sont garantis de ne pas entrer en collision avec des UUID non nommés, et ont une très (très) faible possibilité de collision avec d'autres UUID basés sur des noms.

Il n'y a pas de support natif dans le .NET Framework pour les créer, mais j'ai publié du code sur GitHub qui implémente l'algorithme. Il peut être utilisé comme suit:

Guid guid = GuidUtility.Create(GuidUtility.UrlNamespace, filePath);

Pour réduire encore davantage le risque de collisions avec d'autres GUID, vous pouvez créer un GUID privé à utiliser comme ID d'espace de noms (au lieu d'utiliser l'ID d'espace de noms d'URL défini dans la RFC).

Bradley Grainger
la source
5
@Porges: RFC4122 est incorrect et contient des errata qui corrigent le code C ( rfc-editor.org/errata_search.php?rfc=4122&eid=1352 ). Si cette implémentation n'est pas entièrement conforme à la RFC4122 et à ses errata, veuillez fournir plus de détails; Je voudrais le faire suivre la norme.
Bradley Grainger
1
@BradleyGrainger: Je n'ai pas remarqué cela, merci / désolé! Je devrais toujours me rappeler de vérifier les errata lors de la lecture d'une RFC ... :)
porges
3
@Porges: De rien / pas de problème. Il est stupéfiant qu'ils ne mettent pas à jour le RFC en place avec les corrections des errata. Même un lien à la fin du document serait bien plus utile que de compter sur le lecteur pour se rappeler de rechercher des errata (espérons-le avant d' écrire une implémentation basée sur la RFC ...).
Bradley Grainger
1
@BradleyGrainger: si vous utilisez la version HTML, il y a un lien vers l'errata de l'en-tête, par exemple tools.ietf.org/html/rfc4122 . Je me demande s'il existe une extension de navigateur pour toujours rediriger vers la version HTML ...
porges
2
Vous devriez envisager de contribuer à .NET .NET repo est ici: github.com/dotnet/coreclr/tree/master/src/mscorlib/src/System
sapphiremirage
29

Cela convertira n'importe quelle chaîne en Guid sans avoir à importer un assembly extérieur.

public static Guid ToGuid(string src)
{
    byte[] stringbytes = Encoding.UTF8.GetBytes(src);
    byte[] hashedBytes = new System.Security.Cryptography
        .SHA1CryptoServiceProvider()
        .ComputeHash(stringbytes);
    Array.Resize(ref hashedBytes, 16);
    return new Guid(hashedBytes);
}

Il existe de bien meilleures façons de générer un Guid unique, mais c'est un moyen de mettre à niveau de manière cohérente une clé de données de chaîne vers une clé de données Guid.

Ben Gripka
la source
Cet extrait de code a été utile lors de l'utilisation d'un identifiant unique dans une base de données pour une distribution fédérée.
Gleno
6
Avertissement! Ce code ne génère pas de Guids / UUID valides (comme bacar également mentionné ci-dessous). Ni la version ni le champ de type ne sont correctement définis.
MarkusSchaber
3
Ne serait-il pas tout aussi efficace d'utiliser le MD5CryptoServiceProvider au lieu du SHA1, puisque MD5 a déjà une longueur de 16 octets?
Brain2000
20

Comme Rob le mentionne, votre méthode ne génère pas d'UUID, elle génère un hachage qui ressemble à un UUID.

La RFC 4122 sur les UUID autorise spécifiquement les UUID déterministes (basés sur le nom) - Les versions 3 et 5 utilisent md5 et SHA1 (respectivement). La plupart des gens connaissent probablement la version 4, qui est aléatoire. Wikipedia donne un bon aperçu des versions. (Notez que l'utilisation du mot «version» ici semble décrire un «type» d'UUID - la version 5 ne remplace pas la version 4).

Il semble y avoir quelques bibliothèques là-bas pour générer des UUID version 3/5, y compris le module uuid python , boost.uuid (C ++) et OSSP UUID . (Je n'ai pas cherché de .net)

bacar
la source
1
C'est exactement ce que cherche l'affiche originale. UUID a déjà un algorithme vous permettant de commencer par une chaîne et de le convertir en GUID. La version UUID 3 hache la chaîne avec MD5, tandis que la version 5 la hache avec SHA1. Le point important dans la création d'un "guid" est de le rendre "unique" par rapport aux autres GUID. L'algorithme définit deux bits qui doivent être définis, ainsi qu'un quartet est défini sur 3 ou 5, selon qu'il s'agit de la version 3 ou 5.
Ian Boyd
2
Concernant l'utilisation du mot «version», la RFC 4122 §4.1.3 stipule: «La version est plus précisément un sous-type; encore une fois, nous retenons le terme de compatibilité.»
Bradley Grainger
11
J'ai posté du code C # pour créer des GUID v3 et v5 sur GitHub: github.com/LogosBible/Logos.Utility/blob/master/src/…
Bradley Grainger
@BradleyGrainger, j'obtiens un opérateur d'avertissement ou au niveau du bit utilisé sur un opérande étendu par signe; envisager de lancer d'abord un type plus petit non signé
Sebastian
1
Cela devient hors sujet! Suggérer de déplacer les rapports de bogues de lib individuels vers GitHub.
bacar
3

Vous devez faire une distinction entre les instances de la classe Guidet les identificateurs qui sont globalement uniques. Un "guid déterministe" est en fait un hachage (comme en témoigne votre appel à provider.ComputeHash). Les hachages ont un risque beaucoup plus élevé de collisions (deux chaînes différentes produisant le même hachage) que Guid créé via Guid.NewGuid.

Le problème avec votre approche est que vous devrez accepter la possibilité que deux chemins différents produisent le même GUID. Si vous avez besoin d'un identifiant unique pour une chaîne de chemin donnée, la chose la plus simple à faire est simplement d'utiliser la chaîne . Si vous avez besoin que la chaîne soit masquée par vos utilisateurs, cryptez-la - vous pouvez utiliser ROT13 ou quelque chose de plus puissant ...

Tenter d'afficher quelque chose qui n'est pas un GUID pur dans le type de données GUID pourrait entraîner des problèmes de maintenance à l'avenir ...

Rob Fonseca-Ensor
la source
2
Vous affirmez que "les hachages ont un risque de collision beaucoup plus élevé ... que Guid créé via Guid.NewGuid.". Pourriez-vous préciser ceci? D'un point de vue mathématique, le nombre de bits que l'on peut définir est le même, et MD5 et SHA1 sont des hachages cryptographiques, spécifiquement conçus pour réduire la probabilité de collisions de hachage (accidentelles et intentionnelles).
MarkusSchaber
Je dirais que la principale différence est que les hachages cryptographiques mappent d'un espace infini à un autre espace fixe à l'aide d'une fonction. Imagerie d'un hachage qui mappe des chaînes de longueur variable à 128 bits tandis que Guid génère 128 bits pseudo-aléatoires. La génération pseudo-aléatoire ne repose pas sur une entrée initiale, mais plutôt en générant la sortie uniformément dans l'espace de sortie en utilisant le caractère aléatoire amorcé à partir du matériel ou d'autres moyens.
Thai Bui
2

MD5 est faible, je pense que vous pouvez faire la même chose avec SHA-1 et obtenir de meilleurs résultats.

BTW, juste une opinion personnelle, habiller un hachage md5 comme un GUID n'en fait pas un bon GUID. Les GUID de par leur nature même ne sont pas déterministes. cela ressemble à une triche. Pourquoi ne pas simplement appeler un chat un chat et dire simplement que c'est une chaîne rendue hachée de l'entrée. vous pouvez le faire en utilisant cette ligne, plutôt que la nouvelle ligne de guidage:

string stringHash = BitConverter.ToString(hashBytes)
Ryber
la source
Merci pour votre contribution, mais cela me donne quand même une chaîne, et je recherche un GUID ...
Punit Vora
Ok, appelez votre hachage un "GUID", problème résolu. Ou le vrai problème est-il que vous ayez besoin d' un Guidobjet?
user7116
J'aurais aimé que ce soit aussi simple que ça .. :) mais oui, j'ai besoin d'un objet 'GUID'
Punit Vora
5
"Les GUID de par leur nature même ne sont pas déterministes" - cela n'est vrai que pour certains types ('versions') de GUID. Cependant, je conviens que "habiller un hachage md5 comme un GUID ne fait pas un bon GUID" pour d'autres raisons comme indiqué par @Bradley Grainger et @Rob Fonseca-Ensor, et ma réponse à cette question.
bacar