Diseña un generador de IDs únicos distribuido (como Twitter Snowflake): ¿cómo garantizas unicidad sin coordinación?

#Por qué una columna auto-incremental deja de funcionar

La columna AUTO_INCREMENT o SERIAL de una sola base de datos garantiza unicidad forzando cada inserción a través de una única secuencia, que es exactamente lo que se rompe en el momento en que shardeas la base de datos o corres varios nodos capaces de escribir: dos shards entregando id = 4501 de forma independiente es una colisión esperando a ocurrir. El requisito, expresado con precisión, es: generar un ID entero de 64 bits, desde cualquiera de muchas máquinas independientes, sin coordinación entre ellas en el momento de la solicitud, tal que los IDs sean (a) garantizadamente únicos en toda la flota y (b) aproximadamente ordenables por momento de creación, porque "ordenar por ID" es un sustituto sorprendentemente común de "ordenar por created_at" y un índice mucho más barato de escanear.

El algoritmo Snowflake de Twitter (y sus muchos descendientes: Sonyflake de Sony, el esquema de IDs de Instagram, los snowflakes de Discord) resuelve esto codificando tiempo, identidad de máquina y un contador por máquina en un solo entero, de forma que la unicidad venga de la combinación en lugar de preguntarle a alguien más qué ID acaba de usar.

#La disposición de bits

Un entero con signo de 64 bits se divide en campos de ancho fijo:

41 bits de milisegundos son aproximadamente 69.7 años, que es por qué las implementaciones eligen una época personalizada (p. ej. "medianoche del 1 de enero de 2024") en vez de la época Unix: empuja el desbordamiento 69 años más hacia el futuro de lo que lo haría empezar desde 1970. 10 bits de ID de máquina permiten 1,024 generadores corriendo simultáneamente. 12 bits de secuencia permiten 4,096 IDs por máquina por milisegundo: más de 4 millones de IDs por milisegundo en toda la flota, con cero llamadas de red por ID.

#Una implementación real

Ajustar líneas largas
class SnowflakeIdGenerator(private val workerId: Long, private val datacenterId: Long) {

    companion object {
        private const val EPOCH = 1704067200000L // 2024-01-01T00:00:00Z, época personalizada
        private const val WORKER_ID_BITS = 5L
        private const val DATACENTER_ID_BITS = 5L
        private const val SEQUENCE_BITS = 12L

        private const val MAX_WORKER_ID = (1L shl WORKER_ID_BITS.toInt()) - 1       // 31
        private const val MAX_DATACENTER_ID = (1L shl DATACENTER_ID_BITS.toInt()) - 1 // 31
        private const val MAX_SEQUENCE = (1L shl SEQUENCE_BITS.toInt()) - 1          // 4095

        private const val WORKER_ID_SHIFT = SEQUENCE_BITS
        private const val DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
        private const val TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS
    }

    init {
        require(workerId in 0..MAX_WORKER_ID) { "workerId debe estar entre 0 y $MAX_WORKER_ID" }
        require(datacenterId in 0..MAX_DATACENTER_ID) { "datacenterId debe estar entre 0 y $MAX_DATACENTER_ID" }
    }

    private var lastTimestamp = -1L
    private var sequence = 0L

    @Synchronized
    fun nextId(): Long {
        var timestamp = currentTimeMillis()

        if (timestamp < lastTimestamp) {
            // El reloj retrocedió (corrección de NTP, pausa de una VM). Se rechaza en vez de
            // arriesgarse a acuñar un id que colisione con uno ya emitido.
            throw IllegalStateException(
                "El reloj retrocedió ${lastTimestamp - timestamp}ms. Me niego a generar el id."
            )
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) and MAX_SEQUENCE
            if (sequence == 0L) {
                // Se agotaron los 4096 ids de este milisegundo; se espera a que el reloj avance.
                timestamp = waitForNextMillis(lastTimestamp)
            }
        } else {
            sequence = 0L
        }

        lastTimestamp = timestamp

        return ((timestamp - EPOCH) shl TIMESTAMP_SHIFT.toInt()) or
            (datacenterId shl DATACENTER_ID_SHIFT.toInt()) or
            (workerId shl WORKER_ID_SHIFT.toInt()) or
            sequence
    }

    private fun waitForNextMillis(lastTimestamp: Long): Long {
        var timestamp = currentTimeMillis()
        while (timestamp <= lastTimestamp) {
            timestamp = currentTimeMillis()
        }
        return timestamp
    }

    private fun currentTimeMillis(): Long = System.currentTimeMillis()
}

// 1,024 slots de worker/datacenter x 4,096 ids/ms cada uno
// = hasta ~4.19M ids únicos y aproximadamente ordenables por tiempo, por milisegundo, en toda la flota.
val generator = SnowflakeIdGenerator(workerId = 3, datacenterId = 1)
val id = generator.nextId()

Nota qué es lo que hace esto libre de coordinación: nextId() nunca llama a otro servicio, otra máquina, ni siquiera a la base de datos. Solo necesita conocer su propio workerId/datacenterId (asignado una vez, al iniciar) y el reloj local. Dos llamadas en dos máquinas distintas literalmente nunca pueden colisionar, porque los bits de ID de máquina difieren; dos llamadas en la misma máquina no pueden colisionar, porque o el timestamp difiere o lo hace el contador de secuencia.

#Los modos de falla que vale la pena nombrar

Desfase de reloj y correcciones de NTP. Si el reloj del sistema salta hacia atrás —una corrección de NTP, una pausa y reanudación de una VM, una sincronización de tiempo mal configurada—, el nextId() de arriba lanza una excepción en vez de arriesgarse a generar un ID basado en timestamp que podría colisionar con, u ordenarse antes que, uno ya emitido desde un "ahora" anterior. Los sistemas en producción o toleran un pequeño salto hacia atrás tomando prestado de los bits de secuencia, o simplemente alertan y se niegan, tratándolo como un incidente operativo en vez de algo que se tapa en silencio.

Asignación y reutilización del ID de worker. Si dos pods quedan mal configurados con el mismo workerId (un redeploy que reutilizó un ID antes de que el pod anterior terminara de drenar, por ejemplo), la unicidad se rompe en silencio. Los sistemas a escala suelen resolver esto con un servicio de coordinación que entrega leases (znodes de Zookeeper, claves de etcd con TTL) en vez de archivos de configuración estáticos que un humano puede duplicar por error.

Agotamiento de la secuencia bajo carga extrema. 4,096 IDs por milisegundo por máquina son 4.096 millones por segundo por máquina, enorme para casi cualquier carga de trabajo, pero el spin-wait de waitForNextMillis de arriba es un pico de latencia real (aunque raro) si alguna vez lo alcanzas. Ampliar el campo de secuencia (a costa del campo de timestamp o de ID de máquina) es la solución si una carga de trabajo específica realmente necesita más.

#Snowflake frente a las alternativas

🧠 Check your understanding
0/2 · 0/2 answered
1. ¿Por qué un generador estilo Snowflake no necesita contactar a ninguna otra máquina para garantizar un ID único?
Depende de que la base de datos rechace inserciones duplicadasUsa un checksum que detecta colisiones después de generarlasLa unicidad viene de combinar un timestamp local, un ID de máquina preasignado y un contador de secuencia por máquina, cada uno tocado solo por una máquinaConsulta un servicio de contador central por red para cada ID
2. ¿Cuál es el costo de coordinación real, de una sola vez, en un esquema estilo Snowflake?
La base de datos debe aprobar cada lote de IDs por adelantadoCada generación de ID debe adquirir un lock distribuidoAsignar a cada instancia en ejecución un ID de worker único al arrancarCada ID debe validarse contra un registro central antes de usarse