Generando v5 UUID. ¿Qué es el nombre y el espacio de nombres?

He leído la página del man , pero no entiendo para qué sirven el name y el namespace .

Para los UUID de la versión 3 y la versión 5, debe darse el nombre de espacio y el nombre de los argumentos de la línea de comando adicionales. El espacio de nombres es un UUID en representación de cadena o un identificador para UUID de espacio de nombre predefinidos internamente (actualmente conocidos son “ns: DNS”, “ns: URL”, “ns: OID” y “ns: X500”). El nombre es una cadena de longitud arbitraria.

El espacio de nombres:

El espacio de nombre es un UUID en la representación de cadena o un

¿Significa que necesito almacenarlo (UUID v4) en algún lugar en relación con el UUID v5 generado? En cualquier caso, ¿por qué no se hace esto automáticamente?

El nombre es una cadena de longitud arbitraria.

name una cadena completamente al azar? ¿Cuál es el propósito de eso entonces? ¿Se puede decodificar desde el UUID v5?

El nombre y el espacio de nombres se pueden usar para crear una jerarquía de (muy probablemente) UUID únicos.

En términos generales, un UUID de tipo 3 o tipo 5 se genera mezclando un identificador de espacio de nombres con un nombre. Los UUID de tipo 3 usan MD5 y los UUID de tipo 5 usan SHA1. Solo están disponibles 128 bits y se usan 5 bits para especificar el tipo, por lo que todos los bits hash no entran en el UUID. (También MD5 se considera roto criptográficamente, y SHA1 está en sus últimas patas, por lo tanto, no lo use para verificar los datos que deben ser “muy seguros”). Dicho esto, le ofrece una forma de crear una función “hash” repetible / verificable mapeando un nombre posiblemente jerárquico en un valor de 128 bits probabilísticamente único, que potencialmente actúa como un hash jerárquico o MAC.

Supongamos que tiene un almacén (clave, valor), pero solo admite un espacio de nombre. Puede generar una gran cantidad de espacios de nombres lógicos distintos utilizando UUID de tipo 3 o tipo 5. Primero, cree un UUID raíz para cada espacio de nombres. Esto podría ser un UUID de tipo 1 (host + timestamp) o tipo 4 (aleatorio) siempre que lo almacene en algún lugar. De forma alternativa, podría crear un UUID aleatorio para su raíz (o usar el UUID null : 00000000-0000-0000-0000-000000000000 como raíz) y luego crear un UUID reproducible para cada espacio de nombres usando ” uuid -v5 $ROOTUUID $NAMESPACENAME “. Ahora puede crear UUID únicos para claves dentro de un espacio de nombres usando ” uuid -v5 $NAMESPACEUUID $KEY “. Estos UUID se pueden arrojar a un único almacén de clave-valor con alta probabilidad de evitar una colisión. Este proceso puede repetirse recursivamente, de modo que si, por ejemplo, el “valor” asociado con una clave UUID a su vez representa algún tipo de “espacio de nombre” lógico como un contenedor, contenedor o directorio, entonces su UUID puede usarse para generar más jerarquías UUID.

El UUID tipo 3 o tipo 5 generado contiene un hash (parcial) del id del espacio de nombres y el nombre dentro del espacio de nombres (clave). Ya no contiene el UUID de espacio de nombres que un mensaje MAC contiene el contenido del mensaje desde el que está codificado. El nombre es una cadena “arbitraria” (octeto) desde la perspectiva del algoritmo uuid. Sin embargo, su significado depende de su aplicación. Podría ser un nombre de archivo dentro de un directorio lógico, id de objeto dentro de un almacén de objetos, etcétera.

Si bien esto funciona bien para una cantidad moderadamente grande de espacios de nombres y claves, con el tiempo se queda sin fuerza si se apunta a un gran número de claves que son únicas con una probabilidad muy alta. La entrada de Wikipedia para el Problema del cumpleaños (también conocida como Paradoja del cumpleaños) incluye una tabla que da la probabilidad de al menos una colisión para varios números de teclas y tamaños de tabla. Para 128 bits, hash 26 mil millones de claves de esta manera tiene una probabilidad de colisión de p=10^-18 (insignificante), pero 26 billones de claves, aumenta la probabilidad de al menos una colisión para p=10^-12 (uno en un trillón), y hash 26*10^15 teclas, aumenta la probabilidad de al menos una colisión a p=10^-6 (uno en un millón). Ajustando para 5 bits que codifican el tipo de UUID, se agotará un poco más rápido, por lo que un billón de teclas tienen aproximadamente 1 en un trillón de posibilidades de tener una sola colisión.

Ver http://en.wikipedia.org/wiki/Birthday_problem#Probability_table para la tabla de probabilidades.

Consulte http://www.ietf.org/rfc/rfc4122.txt para obtener más detalles sobre las codificaciones de UUID.

Los UUID de Tipo 3 y Tipo 5 son solo una técnica de relleno de un hash en un UUID.

  • Tipo 1: carga la dirección MAC, datetime en 128 bits
  • Tipo 3 : rellena un hash MD5 en 128 bits
  • Tipo 4: carga datos aleatorios en 128 bits
  • Tipo 5 : rellena un hash SHA1 en 128 bits

Un hash SHA1 genera 160 bits (20 bytes). El resultado del hash se convierte en un UUID. De los 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 

(Tenga en cuenta que los primeros dos bits de ‘9’ ya son 1 y 0, respectivamente, por lo que esto no tiene ningún efecto).

¿Qué tengo?

Probablemente te estés preguntando qué es lo que se supone que tengo que hacer. Básicamente has hash la concatenación de:

 sha1([NamespaceUUID]+[AnyString]); 

Prefija su cadena con un espacio de nombres llamado para evitar conflictos de nombres.

El UUID RFC define previamente cuatro espacios de nombres para usted:

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

Por lo tanto, podría hash juntos:

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

El RFC luego define cómo:

  • tomar los 160 bits de SHA1
  • y convertirlo en 128 bits de un UUID

La idea básica es solo tomar los primeros 128 bits, rellenar un 5 en el registro de tipo y luego establecer los primeros dos bits de la sección clock_seq_hi_and_reserved en 1 y 0, respectivamente.

Más ejemplos

Ahora que tiene una función que genera un llamado Nombre , puede tener la función (en 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; } 

(Tenga en cuenta que la endianidad de su sistema puede afectar los índices de los bytes anteriores)

Puedes tener llamadas:

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

Ahora volvamos a tu pregunta

Para los UUID de la versión 3 y la versión 5, debe darse el nombre de espacio y el nombre de los argumentos de la línea de comando adicionales. El espacio de nombres es un UUID en representación de cadena o un identificador para UUID de espacio de nombre predefinidos internamente (actualmente conocidos son “ns: DNS”, “ns: URL”, “ns: OID” y “ns: X500”). El nombre es una cadena de longitud arbitraria.

El espacio de nombres es el UUID que desee. Puede ser uno de los predefinidos, o puede hacer uno propio, por ejemplo:

 UUID Namespace_RectalForeignExtractedObject = '4d79546f-6e67-7565-496e-486572417373' 

El nombre es una cadena de longitud arbitraria.

El nombre es simplemente el texto que desea anexar al espacio de nombres, luego hash y rellenado en 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'); 

Nota : Cualquier código lanzado al dominio público. No se requiere atribución.

Un nombre no es más que un identificador que es único dentro de un espacio de nombres. El problema es que los espacios de nombres son a menudo bastante pequeños y los nombres en uno a menudo chocan con nombres en otros. Por ejemplo, el número (nombre) de matrícula de mi automóvil es único dentro del espacio de nombre de mi estado en el DMV, pero probablemente no sea único en el mundo; otros DMV estatales pueden haber usado el mismo nombre en sus propios espacios de nombres. Diablos, alguien más puede tener un número de teléfono (nombre) que también coincida porque ese es otro espacio de nombres, etc.

Se puede considerar que los UUID habitan un único espacio de nombre tan vasto que puede proporcionar un nombre único para todo ; eso es lo que significa “universal”. ¿Pero cómo mapea nombres existentes en otros espacios de nombres a un UUID?

Una solución obvia es generar un UUID (V1 o V4) para cada elemento para reemplazar los nombres antiguos en sus espacios de nombres disjuntos. La desventaja es que son mucho más grandes, tienes que comunicar todos los nombres nuevos a todos los que tienen una copia de tu conjunto de datos, actualizar todas tus API, etc. Las probabilidades son que no puedes deshacerte de los nombres antiguos por completo de todos modos, lo que significa que ahora cada artículo tiene dos nombres, ¿lo hizo mejor o peor?

Aquí es donde entran V3 / V5. Los UUID se ven tan aleatorios como V4, pero en realidad son deterministas; cualquiera que tenga el UUID correcto para un espacio de nombre puede generar de forma independiente el mismo UUID para cualquier nombre dentro de ese espacio de nombres. No es necesario que los publiques en absoluto ni los pregeneres, ¡ya que cualquiera puede crearlos sobre la marcha si es necesario!

Los nombres DNS y las URL son espacios de nombres muy utilizados, por lo que se publicaron UUID estándar para ellos; Los OID ASN.1 y los nombres X.500 no son tan comunes, pero los organismos de estándares los adoran, por lo que también publicaron UUID de espacio de nombres estándar para ellos.

Para todos los demás espacios de nombres, debe generar su propio UUID de espacio de nombre (V1 o V4) y comunicarlo a cualquier persona que lo necesite. Si tiene varios espacios de nombres, tener que publicar el UUID para cada uno claramente no es ideal.

Aquí es donde entra la jerarquía: creas un UUID “base” (de cualquier tipo), y luego lo usas como un espacio de nombres para nombrar tus otros espacios de nombres. De esta forma, solo tiene que publicar el UUID base (o usar uno obvio), y todos pueden calcular el rest.

Por ejemplo, quedémonos queríamos crear algunos UUID para StackOverflow; que tiene un nombre obvio dentro del espacio de nombres DNS, por lo que la base es obvia:

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

StackOverflow tiene espacios de nombres separados para los usuarios, preguntas, respuestas, comentarios, etc., pero también son bastante obvios:

 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 pregunta en particular es # 10867405, por lo que su UUID sería:

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

Observe que no hay nada aleatorio en este proceso, por lo que cualquiera que siga la misma lógica obtendrá la misma respuesta, sin embargo, el espacio de nombres UUID es tan vasto que (en efecto, dada la seguridad de un hash criptográfico de 122 bits) nunca colisionará con un UUID generado a partir de cualquier otro par espacio de nombre / nombre.