Por qué no se puede codificar un UUID en 20 caracteres url-friendly.

A grandes rasgos

Un UUID se compone de 128 bits o 16 bytes.

Su representación canónica es la hexadecimal, la cual codifica cada byte con dos hexadecimales, dando un total de 12*2=32 caracteres, a los que se suman los cuatro guiones que separan los cinco grupos para un total de 36.

La base 64 codifica 6 bits usando 8 bits, o sea un caracter. Si dividimos 128 /6 = 22 caracteres.

La base 85 (que son los Ascii imprimibles) codifica 4 bytes en 5 bytes. Los 16 bytes del UUID divididos en 4 16/4=4.
Por los 5 bytes necesarios 4*5 = 20 caracteres. Esta es la largo mínimo en que podemos codificar un UUID.

A este respecto, ver este otro post >> con un caso de uso similar.

Sin embargo, no todos los Ascii armor son url-friendly. De los 85, sólo 73 se pueden pasar por una url sin ser escapados.

Vemos que nos encontramos entre los 64 y los 85, y de hecho dicen que en base 73 se podría llegar hasta 21 caracteres >>.
(Falta el cálculo)

Las posibles soluciones pasan por comprimir los 16 bytes iniciales (ver CRC)
o averiguar qué bits del UUID podemos eliminar sin perder tanta unicidad.

Eliminando un byte del UUID

  • Si podemos asegurar que todos los UUIDS son versión 4 (random), ¿podemos utilizar sólo 32 bits de los 128? >>
  • En todo caso de los 128 bits, si podemos reducirlo a 120 podremos codificarlo en base64 ya que 120/6 = 20.
  • Entonces, ¿cuál es el byte menos significante? De acuerdo con la especificación RFC >>, los últimos en orden de importancia son clock_seq_low y node.
  • Node es un integer de 48 bits que indentifica el nodo en UUIDs tipo 1.
  •  Clock_seq_low es usado en caso que cambie la hora del reloj, también en UUIDs tipo 1.
  •  Pero el randomUUID de java es tipo 4 y por ende obvia estas definicioes, utilizando para todo números al azar, por lo que nuestra decisión sólo se basa en que clocl_seq_low representa un solo byte a eliminar.
  • Respecto a la probabilidad de colisión, siguiendo el cálculo estadístico de la paradoja del cumpleaños >> y dado que, como dijimos, todos los bytes son random en un UUID de tipo 4, en vez de 122 bits estaríamos trabajando con 122-8=116 por lo que, para 236 UUIDs generados (68 mil millones), nuestras probabilidades de colisión son de 2.8 * 10 -14, es decir, todavía menos probable que que nos caiga un meteorito encima.
Este sitio utiliza cookies.    Leer más