Las colisiones de marcas de tiempo de nanosegundos son comunes

• En sistemas modernos donde varios núcleos físicos leen el reloj al mismo tiempo, incluso las marcas de tiempo de nanosegundos se superponen fácilmente, y en una medición simultánea con 4 núcleos físicos alrededor del 5% de todas las muestras colisionó
• Es riesgoso diseñar sistemas que usen marcas de tiempo sin procesar como si fueran identificadores únicos, y la frecuencia de colisión varía según el sistema operativo y la forma de ejecución
• time.Now() de Go registra tanto el tiempo absoluto como el tiempo relativo basado en un reloj monótono, lo que permite verificar por separado la diferencia entre llamadas consecutivas y la duplicación de marcas de tiempo absolutas
• En Linux de un solo hilo, el tiempo siempre aumentó y el incremento mínimo fue de 32 ns, pero cuando los hilos se separan se observa el mismo tiempo absoluto
• En Mac OS X, el tiempo absoluto tiene resolución de microsegundos, así que hay muchas más colisiones, y aun en un solo hilo se observa con frecuencia que el reloj monótono no aumenta

---

Frecuencia de colisiones revelada en lecturas concurrentes

• La pregunta clave es con qué frecuencia ocurren en la práctica las colisiones de marcas de tiempo de nanosegundos en sistemas modernos
• Si se lee el reloj al mismo tiempo en 4 núcleos físicos, alrededor del 5% de todas las muestras colisiona
• Incluso usando solo 2 hilos en un sistema de 4 núcleos, cerca del 2% de las marcas de tiempo se superpone
• Por lo tanto, no es seguro asumir que se puede crear un ID único solo con una marca de tiempo de nanosegundos sin procesar

Método de prueba y diferencias por sistema operativo

• El programa de prueba está escrito en Go
• time.Now() de Go registra en cada llamada el tiempo absoluto y el tiempo relativo basado en un reloj monótono
  • La prueba compara la diferencia relativa entre marcas de tiempo consecutivas
  • También verifica la duplicación de la marca de tiempo absoluta en sí

• Linux

  • En un solo hilo, el tiempo absoluto y el tiempo monótono siempre aumentan
  • El incremento mínimo del sistema medido fue de 32 ns
  • Entre hilos, alrededor del 5% de las veces el tiempo absoluto coincide exactamente con el de otro hilo

• Mac OS X

  • Como el tiempo absoluto tiene resolución de microsegundos, en la misma prueba ocurren muchísimas colisiones
  • Incluso en un solo hilo, se observó con frecuencia que el reloj monótono no aumentaba

[GN⁺]

Comentarios de Hacker News

• Usar IDs que incluyan un componente de tiempo y un número de secuencia es una forma de evitar este problema
  Por ejemplo, UUIDv7 tiene un componente temporal con resolución de milisegundos, un campo que incrementa para cada evento dentro del mismo milisegundo y suficientes bits aleatorios como para que la probabilidad de colisión entre IDs generados en distintas máquinas sea astronómicamente baja
  Claro, la cantidad de bits es finita, así que si hay demasiados eventos en el mismo intervalo de tiempo el contador puede desbordarse, las colisiones entre máquinas sí pueden ocurrir en la práctica y la operación de incremento puede requerir sincronización de CPU, limitando la velocidad de generación de eventos
  Aun así, a escala real de trabajo, UUIDv7 funciona muy bien

  • Me siento un poco accidentalmente como un viajero en el tiempo, pero recuerdo una conversación de hace al menos unos 10 años en una reunión técnica donde alguien estaba generando más de 1000 UUID por milisegundo y sufría problemas de unicidad, y en ese momento no estaba satisfecho con las opciones disponibles
    No encuentro bien en internet desde cuándo existe UUIDv7
  • Para empezar, no entiendo por qué hace falta un componente de tiempo
    Solo consume bits dentro del UUID y no aporta mucho a la entropía
  • También encaja bien con el orden de clasificación en bases de datos populares como PostgreSQL
    Todavía no está integrado en el núcleo, pero además de usarlo directamente a nivel de aplicación, hay varias excelentes extensiones de pg que ofrecen uuidv7
  • El problema de los UUID es que son totalmente difíciles de leer
    Más allá de ser difíciles de entender, incluso distinguirlos visualmente entre sí es muy complicado
    Por eso, en algunos casos, un identificador que no incluya absolutamente nada de información o ruido aparte del mínimo necesario puede ser útil
  • Dependiendo del caso de uso, ni siquiera hace falta manejar lo de “el mismo milisegundo”, y así se pueden ahorrar algunos ciclos
    Un contador incremental con desbordamiento, en cualquier forma, y unos pocos bits aleatorios suele ser suficiente, y si se diseña bien, ambos pueden hacerse sin ramas

• Relacionado con eso, hace tiempo fui program manager a cargo del registro de eventos de seguridad de Windows
  En sistemas multinúcleo, cuando las cosas ocurren al mismo tiempo o con muy poca diferencia temporal, la planificación de hilos puede influir mucho en lo que se observa
  Por ejemplo, el quantum de un hilo puede terminar antes de llegar a la llamada al sistema que obtiene la marca de tiempo, o antes de entregar el búfer que pondrá el evento en cola para marcarlo después
  De hecho, en los sistemas multiprocesador de Windows de los 2000 era muy común que las entradas del registro de eventos parecieran fuera de orden, y tampoco se podía confiar demasiado en la precisión de las marcas de tiempo del log
  En la práctica, el límite inferior seguro era de 1 segundo, y recuerdo que algunos componentes truncaban o redondeaban la marca de tiempo

• Si necesitas un identificador único, usa un UUID versión 4, o sea, un UUID aleatorio
  La probabilidad de colisión es parecida a la de que, por fluctuaciones cuánticas, aparezca de repente un dinosaurio adulto en tu dormitorio

  • Yo me arriesgaría
    Hablando más en serio, si se puede usar, probablemente lo mejor sea un valor incremental tradicional
    Es rápido y barato, especialmente en bases de datos, pero tiene problemas de privacidad y seguridad porque permite inferir información a partir del valor del ID
    En esos casos, o cuando trabajas con sistemas distribuidos, UUID es mejor
  • v7 parece mejor porque resuelve el problema de localidad de v4 y, además, es muchísimo más probable ganarse la lotería que provocar una colisión
  • Quisiera ver cómo sería el cálculo de “la probabilidad de que aparezca un dinosaurio en el dormitorio”
  • Entonces eso significaría que la probabilidad de que pase algo malo se duplica más o menos, así que no lo puedo aceptar

• Aunque la resolución sea de nanosegundos, me pregunto cuál será realmente la precisión del reloj de una computadora
  Me cuesta imaginar que de verdad sea a nivel de nanosegundos, y me recuerda a cuando en clases de laboratorio de física les insistía a los estudiantes que el dígito más pequeño que muestra un instrumento de medición no es lo mismo que su exactitud

  • En un dispositivo que funcione a más de 1GHz, es perfectamente posible que el reloj avance cada nanosegundo
    Pero eso no significa que sea exacto a ese nivel, y en sistemas multinúcleo puede que los relojes entre núcleos ni siquiera estén sincronizados con esa precisión
    ARMv8 garantiza que el reloj avance al menos a 1GHz, pero Intel y ARM anteriores son más complicados
  • En realidad sí son nanosegundos

• La BEAM VM de Erlang/Elixir hace esta diferencia muy clara. Es la distinción entre monotónicamente creciente y estrictamente monotónicamente creciente
  https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
  “En una secuencia de valores monotónicamente crecientes, cada valor que tiene un valor anterior es mayor o igual que ese valor anterior”
  Esto se puede usar con la función https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
  https://www.erlang.org/doc/apps/erts/time_correction.html#st...
  “En una secuencia de valores estrictamente monotónicamente crecientes, cada valor que tiene un valor anterior es mayor que ese valor anterior”
  Los valores estrictamente monotónicos implican algún tipo de sincronización o coordinación, y eso conlleva un costo de rendimiento cuando hay muchos procesos concurrentes
  Esta función se ofrece mediante https://www.erlang.org/doc/man/erlang.html#unique_integer-1, y la documentación también advierte que los valores estrictamente monotónicamente crecientes son intrínsecamente costosos de generar y no escalan bien, así que solo se debe pasar el modificador monotonic cuando realmente se necesite

  • Incluso los valores de referencia de Erlang no se crean con un generador global estrictamente monotónico, sino que internamente están compuestos por un identificador monotónico normal y el PID del proceso que lo solicitó
    En otras palabras, se parecen a UUIDv1 o a https://en.wikipedia.org/wiki/Snowflake_ID
    Solo se necesita realmente un identificador global estrictamente monotónico cuando se requiere un ganador inmediato y consistente de primera/última escritura
    En cambio, si se puede usar un ganador de primera/última escritura eventualmente consistente, por ejemplo si los eventos de escritura entran en un event store o una cola donde se linealizan por ID y, entre escrituras “concurrentes”, se conserva solo la de mayor prioridad por ID mientras las demás se descartan durante el procesamiento o en la lectura, yo consideraría primero un par comprimido (nodeID, seq)
    Si hace falta ordenar globalmente los eventos, vale especialmente la pena considerar un formato de Snowflake ID como (timestampMajor, nodeID, timestampMinor, seq)

• En FreeBSD no existe CLOCK_MONOTONIC_RAW, así que al comentarlo parece que quedó bien
  Yo entendía que, si había colisiones, algunos timestamps deberían repetirse, pero no logro provocarlas
  clock_getres(CLOCK_REALTIME, ...)=1 ns, clock_getres(CLOCK_MONOTONIC, ...)=1 ns, y en 30 muestras también fue aumentando de forma continua con diferencias de aproximadamente 29~71ns

  • Importa si se ejecutó simultáneamente en 4 núcleos, como hizo el autor

• Al final, da la impresión de que en algún punto esto baja al nivel de la arquitectura del conjunto de instrucciones
  Un CPU que corre a 3GHz obtiene 3 ciclos de reloj por nanosegundo
  Con las optimizaciones del compilador, parece bastante posible que las llamadas en ensamblador para leer el registro del reloj queden pegadas una tras otra
  Si llamadas consecutivas a time.Now() ocurren dentro de 3 ciclos de reloj, no sé si sea justo esperar una precisión de nanosegundos realmente única

  • Linux en x86_64 usa RDTSC y corrige con el valor leído desde VDSO, así que de verdad puede ocurrir muy rápido
  • Incluso en chips modernos, leer el registro contador de ciclos toma alrededor de 20 ciclos
    Aunque las colisiones sean algo raras, que pasen varias veces al día es mucho peor que “casi nunca pasa”

• Esto me recordó una leyenda sobre Lotus Notes
  Antes supuestamente usaban timestamps con resolución de 1 segundo como IDs únicos
  Si había una colisión, simplemente le sumaban 1 segundo, y al final hubo tantas colisiones que los elementos terminaron con marcas de tiempo del futuro

• El tiempo absolutamente preciso es un problema de seguridad
  Los diseñadores de CPU han estado introduciendo jitter en los relojes de forma intencional desde hace muchísimo tiempo, desde la época del Alpha de DEC, para evitar una predictibilidad total
  Incluso en x86, si se ejecuta 3 o 4 veces, se guarda el valor en un registro y luego se revisa al final, parecería que se puede ver que las diferencias de tiempo no son exactamente iguales

  • Me pregunto si hay alguna fuente
    No logro encontrar mucho buscando, y si eso incluye incluso los primeros x86, me sorprende que el problema de seguridad de los relojes precisos se hubiera reconocido tan temprano
    Personalmente creo que hasta antes de este milenio yo no conocía ese problema, y habría supuesto que el jitter observable del reloj se explicaba por cosas como interrupciones
    No digo que esté mal, solo me gustaría saber más

• He visto a demasiada gente sorprenderse por colisiones de timestamps de milisegundos o microsegundos
  El tipo que más recuerdo y más detesté es el de construir un timestamp con dos llamadas al sistema
  Una llamada para los dígitos altos y otra para los bajos, pero por la expulsión del proceso, si después de leer la parte alta la parte baja pasa de 99x a 00x, se puede terminar creando un timestamp anterior al momento que realmente causó la creación de cierta entidad
  Entonces parte del código se rompe de maneras muy espectaculares, y al menos dos veces vi bucles infinitos
  Si no te grabas esto como algo que siempre hay que evitar, las pruebas pasan el 99.5% de las veces y hace falta alguien con muy buen instinto para detectar patrones y notar que “la misma prueba se puso roja una vez por semana durante mes y medio”
  Es demasiado tiempo para dejar viva una bomba lógica dentro del código de CI/CD antes de corregirla

  • El ejemplo más memorable fue en una conversación de soporte cuando dije “parece que hay una condición de carrera”, y me respondieron “como esos dos eventos ocurrieron en exactamente el mismo momento, no puede ser una condición de carrera”