Cómo crear guías deterministas

103

En nuestra aplicación estamos creando archivos Xml con un atributo que tiene un valor Guid. Este valor debía ser coherente entre las actualizaciones de archivos. Entonces, incluso si todo lo demás en el archivo cambia, el valor de guid para el atributo debería permanecer igual.

Una solución obvia fue crear un diccionario estático con el nombre del archivo y las guías que se utilizarían para ellos. Luego, cada vez que generamos el archivo, buscamos en el diccionario el nombre del archivo y usamos el guid correspondiente. Pero esto no es factible porque podríamos escalar a cientos de archivos y no queríamos mantener una gran lista de guías.

Entonces, otro enfoque fue hacer que el Guid fuera el mismo en función de la ruta del archivo. Dado que nuestras rutas de archivo y la estructura del directorio de la aplicación son únicas, el Guid debe ser único para esa ruta. Entonces, cada vez que ejecutamos una actualización, el archivo obtiene la misma guía en función de su ruta. Encontré una manera genial de generar tales ' Guías deterministas ' (Gracias Elton Stoneman). Básicamente hace esto:

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; 

} 

Entonces, dada una cadena, el Guid siempre será el mismo.

¿Existen otros enfoques o formas recomendadas para hacer esto? ¿Cuáles son los pros o los contras de ese método?

Punit Vora
fuente

Respuestas:

151

Como lo menciona @bacar, RFC 4122 §4.3 define una forma de crear un UUID basado en nombre. La ventaja de hacer esto (en lugar de usar un hash MD5) es que se garantiza que no colisionarán con los UUID basados ​​en nombres y tienen una posibilidad muy (muy) pequeña de colisión con otros UUID basados ​​en nombres.

No hay soporte nativo en .NET Framework para crearlos, pero publiqué código en GitHub que implementa el algoritmo. Se puede utilizar de la siguiente manera:

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

Para reducir aún más el riesgo de colisiones con otros GUID, puede crear un GUID privado para usarlo como ID de espacio de nombres (en lugar de usar el ID de espacio de nombres URL definido en el RFC).

Bradley Grainger
fuente
5
@Porges: RFC4122 es incorrecto y tiene erratas que corrigen el código C ( rfc-editor.org/errata_search.php?rfc=4122&eid=1352 ). Si esta implementación no cumple completamente con RFC4122 y sus erratas, proporcione más detalles; Me gustaría que siguiera el estándar.
Bradley Grainger
1
@BradleyGrainger: No me di cuenta de eso, ¡gracias / lo siento! Siempre debería recordar comprobar la errata al leer un RFC ... :)
porges
3
@Porges: De nada, no hay problema. Es sorprendente que no actualicen el RFC en el lugar con las correcciones de la errata. Incluso un enlace al final del documento sería mucho más útil que confiar en que el lector recuerde buscar erratas (con suerte antes de escribir una implementación basada en el RFC ...).
Bradley Grainger
1
@BradleyGrainger: si usa la versión HTML, tiene un enlace a la errata desde el encabezado, por ejemplo, tools.ietf.org/html/rfc4122 . Me pregunto si hay una extensión de navegador para redirigir siempre a la versión HTML ...
porges
2
Debería considerar contribuir con esto al repositorio .NET .NET está aquí: github.com/dotnet/coreclr/tree/master/src/mscorlib/src/System
sapphiremirage
29

Esto convertirá cualquier cadena en un Guid sin tener que importar un ensamblaje externo.

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

Hay formas mucho mejores de generar un Guid único, pero esta es una forma de actualizar constantemente una clave de datos de cadena a una clave de datos de Guid.

Ben Gripka
fuente
Encontré que este fragmento es útil cuando se usa un identificador único en una base de datos para distribución federada.
Gleno
6
¡Advertencia! Este código no genera Guids / UUID válidos (como bacar también se menciona a continuación). Ni la versión ni el campo de tipo están configurados correctamente.
MarkusSchaber
3
¿No sería tan efectivo usar MD5CryptoServiceProvider en lugar de SHA1, ya que MD5 ya tiene 16 bytes de longitud?
Brain2000
20

Como menciona Rob, su método no genera un UUID, genera un hash que parece un UUID.

El RFC 4122 en UUID permite específicamente UUID deterministas (basados ​​en nombres): las versiones 3 y 5 usan md5 y SHA1 (respectivamente). La mayoría de las personas probablemente estén familiarizadas con la versión 4, que es aleatoria. Wikipedia ofrece una buena descripción general de las versiones. (Tenga en cuenta que el uso de la palabra 'versión' aquí parece describir un 'tipo' de UUID; la versión 5 no reemplaza a la versión 4).

Parece que existen algunas bibliotecas para generar UUID de la versión 3/5, incluido el módulo uuid de python , boost.uuid (C ++) y UUID OSSP . (No he buscado ninguno .net)

bacar
fuente
1
Esto es exactamente lo que busca el póster original. UUID ya tiene un algoritmo para que comiences con una cadena y la conviertas en un GUID. UUID versión 3 hash la cadena con MD5, mientras que la versión 5 la hash con SHA1. El punto importante en la creación de un "guid" es hacerlo "único" frente a otros GUID. El algoritmo define dos bits que deben establecerse, así como un nibble se establece en 3 o 5, dependiendo de si es la versión 3 o 5.
Ian Boyd
2
Con respecto al uso de la palabra "versión", RFC 4122 §4.1.3 establece: "La versión es más exactamente un subtipo; nuevamente, retenemos el término para compatibilidad".
Bradley Grainger
11
Publiqué
Bradley Grainger
@BradleyGrainger, recibo una advertencia Bitwise-or operador usado en un operando extendido de signo; considere enviar primero a un tipo sin firmar más pequeño
Sebastian
1
¡Esto se está saliendo del tema! Sugiera mover informes de errores de lib individuales a GitHub.
bacar
3

Debe hacer una distinción entre las instancias de la clase Guidy los identificadores que son únicos globalmente. Una "guía determinista" es en realidad un hash (como lo demuestra su llamada a provider.ComputeHash). Los hash tienen una probabilidad mucho mayor de colisiones (dos cadenas diferentes producen el mismo hash) que Guid creado a través de Guid.NewGuid.

Entonces, el problema con su enfoque es que tendrá que estar de acuerdo con la posibilidad de que dos rutas diferentes produzcan el mismo GUID. Si necesita un identificador que sea único para cualquier cadena de ruta determinada, entonces lo más fácil de hacer es usar la cadena . Si necesita que sus usuarios no vean la cadena, encriptarla ; puede usar ROT13 o algo más poderoso ...

Intentar calzar algo que no sea un GUID puro en el tipo de datos GUID podría generar problemas de mantenimiento en el futuro ...

Rob Fonseca-Ensor
fuente
2
Afirmas que "los hash tienen una probabilidad mucho mayor de colisiones ... que las que creó Guid a través de Guid.NewGuid". Puedes profundizar sobre eso? Desde un punto de vista matemático, el número de bits que se puede establecer es el mismo, y tanto MD5 como SHA1 son hashes criptográficos, diseñados específicamente para reducir la probabilidad de colisiones hash (accidentales e intencionales).
MarkusSchaber
Yo diría que la principal diferencia es el mapa de hashes criptográficos de un espacio infinito a otro espacio fijo usando una función. Generación de imágenes de un hash que asigna cadenas de longitud variable a 128 bits, mientras que Guid genera 128 bits pseudoaleatorios. La generación pseudoaleatoria no se basa en una entrada inicial, sino que genera la salida de manera uniforme en el espacio de salida utilizando la aleatoriedad sembrada desde el hardware u otros medios.
Thai Bui
2

MD5 es débil, creo que puede hacer lo mismo con SHA-1 y obtener mejores resultados.

Por cierto, solo una opinión personal, disfrazar un hash md5 como un GUID no lo convierte en un buen GUID. Los GUID por su propia naturaleza no son deterministas. esto se siente como una trampa. ¿Por qué no llamar a una espada espada y decir que es una cadena representada como hash de la entrada? podría hacerlo usando esta línea, en lugar de la nueva línea de guía:

string stringHash = BitConverter.ToString(hashBytes)
Ryber
fuente
Gracias por su aporte, pero esto todavía me da una cadena, y estoy buscando un GUID ...
Punit Vora
Bien, llame a su hash un "GUID", problema resuelto. ¿O el problema real es que necesitas un Guidobjeto?
user7116
Ojalá fuera así de simple .. :) pero sí, necesito un objeto 'GUID'
Punit Vora
5
"Los GUID por su propia naturaleza no son deterministas"; esto solo es cierto para ciertos tipos ('versiones') de GUID. Sin embargo, estoy de acuerdo en que "vestir un hash md5 como un GUID no es un buen GUID" por otras razones, como lo explican @Bradley Grainger y @Rob Fonseca-Ensor, y mi respuesta a esta pregunta.
bacar