Design a distributed unique ID generator (like Twitter Snowflake) — how do you guarantee uniqueness without coordination?

#Why an auto-increment column stops working

A single database's AUTO_INCREMENT or SERIAL column guarantees uniqueness by forcing every insert through one sequence, which is exactly what breaks once you shard the database or run multiple write-capable nodes: two shards handing out id = 4501 independently is a collision waiting to happen. The requirement, restated precisely, is: generate a 64-bit integer ID, from any of many independent machines, with no coordination between them at request time, such that IDs are (a) guaranteed unique across the whole fleet and (b) roughly sortable by creation time, because "sort by ID" is a surprisingly common substitute for "sort by created_at" and a much cheaper index to scan.

Twitter's Snowflake algorithm (and its many descendants — Sony's Sonyflake, Instagram's ID scheme, Discord's snowflakes) solves this by encoding time, machine identity, and a per-machine counter into one integer, so that uniqueness comes from the combination rather than from asking anyone else what ID they just used.

#The bit layout

A 64-bit signed integer is split into fixed-width fields:

41 bits of milliseconds is roughly 69.7 years — which is why implementations pick a custom epoch (e.g. "midnight, January 1st 2024") instead of the Unix epoch: it pushes the wraparound 69 years further into the future than starting from 1970 would. 10 bits of machine ID allows 1,024 concurrently running generators. 12 bits of sequence allows 4,096 IDs per machine per millisecond — over 4 million IDs per millisecond across the full fleet, with zero network calls per ID.

#A real implementation

Wrap long lines
class SnowflakeIdGenerator(private val workerId: Long, private val datacenterId: Long) {

    companion object {
        private const val EPOCH = 1704067200000L // 2024-01-01T00:00:00Z, custom epoch
        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 must be between 0 and $MAX_WORKER_ID" }
        require(datacenterId in 0..MAX_DATACENTER_ID) { "datacenterId must be between 0 and $MAX_DATACENTER_ID" }
    }

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

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

        if (timestamp < lastTimestamp) {
            // Clock moved backwards (NTP correction, VM pause). Refuse rather than
            // risk minting an id that collides with one already issued.
            throw IllegalStateException(
                "Clock moved backwards by ${lastTimestamp - timestamp}ms. Refusing to generate id."
            )
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) and MAX_SEQUENCE
            if (sequence == 0L) {
                // Exhausted 4096 ids in this millisecond; spin until the clock ticks over.
                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 worker/datacenter slots x 4,096 ids/ms each
// = up to ~4.19M unique, roughly time-sortable ids per millisecond, fleet-wide.
val generator = SnowflakeIdGenerator(workerId = 3, datacenterId = 1)
val id = generator.nextId()

Notice what makes this coordination-free: nextId() never calls another service, another machine, or even the database. It only needs to know its own workerId/datacenterId (assigned once, at startup) and the local clock. Two calls on two different machines can literally never collide, because the machine-id bits differ; two calls on the same machine can't collide, because either the timestamp differs or the sequence counter does.

#The failure modes worth naming

Clock drift and NTP corrections. If the system clock jumps backward — an NTP correction, a VM pause-and-resume, a misconfigured time sync — nextId() above throws rather than risk generating a timestamp-based ID that could collide with, or sort before, one already issued from an earlier "now." Production systems either tolerate a small backward jump by borrowing from the sequence bits, or simply alert and refuse, treating it as an operational incident rather than something to paper over silently.

Worker ID assignment and reuse. If two pods are misconfigured with the same workerId (a redeploy that reused an ID before the old pod finished draining, for instance), uniqueness silently breaks. Systems at scale usually solve this with a coordination service that hands out leases (Zookeeper znodes, etcd keys with TTLs) rather than static config files that a human can duplicate by mistake.

Sequence exhaustion under extreme load. 4,096 IDs per millisecond per machine is 4.096 million per second per machine — enormous for almost any workload, but the waitForNextMillis spin-wait above is a real (if rare) latency spike if you ever do hit it. Widening the sequence field (at the cost of the timestamp or machine-id field) is the fix if a specific workload genuinely needs more.

#Snowflake vs. the alternatives

🧠 Check your understanding
0/2 · 0/2 answered
1. Why does a Snowflake-style generator not need to contact any other machine to guarantee a unique ID?
It relies on the database to reject duplicate insertsIt uses a checksum that detects collisions after the factUniqueness comes from combining a local timestamp, a pre-assigned machine ID, and a per-machine sequence counter, each of which is only ever touched by one machineIt queries a central counter service over the network for every ID
2. What is the actual one-time coordination cost in a Snowflake-style scheme?
Every ID must be validated against a central registry before useEvery ID generation must acquire a distributed lockAssigning each running instance a unique worker ID at startupThe database must approve each batch of IDs in advance