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.