Generating Unique IDs in a Distributed System

Q: Do these ids fit in JavaScript?

Not reliably. Number.MAX_SAFE_INTEGER is 2⁵³−1, and a 64-bit id exceeds it. Serialise as a string in any JSON a browser will parse.

Why auto-increment stops working across shards, what the 64 bits of a Snowflake id are spent on, a working generator, and the clock-goes-backwards case that must throw rather than issue a duplicate.

A single database gives you unique ids for free. AUTO_INCREMENT is correct, compact, ordered and requires no thought. It also requires exactly one writer, which is the assumption that breaks first when a system grows.

Once inserts happen on several nodes, in several regions, possibly while the coordinator is unreachable, id generation becomes a design decision. This walks through the options, then builds the one most systems end up with.

What the requirement actually is

Not just “unique”. Four properties, and the tension between them is the whole problem:

Unique, with no coordination at generation time
Roughly time-ordered, so ids sort close to insertion order
Compact: 64 bits fits a long, a BIGINT and a JavaScript-unsafe integer boundary worth knowing about
Fast, generated locally without a network round trip

Time ordering is the one people leave out and then need. An id that sorts by creation time means range queries over “recent” rows hit a contiguous part of the index, pagination can use the id as a cursor, and a B-tree receives inserts at the right edge rather than scattered through the leaves. That last point is a real write-throughput difference, not a micro-optimisation.

The options, and what each costs

Database auto-increment. Correct and ordered, but one writer. Multi-master with strides (auto_increment_increment=N, each node a different offset) works and permanently fixes your node count.

A ticket server. One tiny service hands out ranges; clients cache a block and serve locally. Good throughput, and a single point of failure you now have to make highly available.

UUIDv4. 128 bits of randomness. Genuinely coordination-free, and unordered, which is why inserting UUIDv4 primary keys into a clustered index degrades as the table grows: every insert lands in a random leaf. It also doubles your key size everywhere the key is referenced.

UUIDv7. Standardised in RFC 9562 (2024): a millisecond timestamp in the high bits, randomness in the rest. Time-ordered, coordination-free, and still 128 bits. If you do not specifically need 64 bits. This is usually the right answer, a library call with no node-id assignment to operate. Most of what follows is worth reading precisely so you can decide whether you need the harder thing.

ULID. Same idea, lexicographically sortable in its text form. Useful when ids appear in URLs.

Snowflake. 64 bits, time-ordered, no coordination at generation time: at the cost of assigning every node a distinct id and depending on the clock. This is the shape that fits into a long.

Sixty-four bits, spent

Twitter’s scheme, and the one most implementations copy:

 1        41                    10          12
┌─┬─────────────────────────┬──────────┬────────────┐
│0│      timestamp (ms)     │ node id  │  sequence  │
└─┴─────────────────────────┴──────────┴────────────┘

1 bit unused, always zero, so the value is always a positive signed 64-bit integer
41 bits of milliseconds since a custom epoch. 2⁴¹ ms is about 69.7 years: from your own epoch, not 1970, which is why the epoch choice matters
10 bits of node id: 1,024 distinct generators
12 bits of sequence: 4,096 ids per millisecond per node, so ~4.1 million per second per node

Adjust the split for your situation. Fewer nodes and more sequence bits, or the reverse. What you cannot do is change it after ids exist, because the layout is baked into every value already issued.

An implementation

package com.example.ids;

import java.time.Instant;

public final class SnowflakeIdGenerator {

    private static final long EPOCH_MILLIS = 1_704_067_200_000L; // 2024-01-01T00:00:00Z

    private static final long NODE_ID_BITS  = 10L;
    private static final long SEQUENCE_BITS = 12L;

    private static final long MAX_NODE_ID  = (1L << NODE_ID_BITS) - 1;   // 1023
    private static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;  // 4095

    private final long nodeId;

    private long lastTimestamp = -1L;
    private long sequence = 0L;

    public SnowflakeIdGenerator(long nodeId) {
        if (nodeId < 0 || nodeId > MAX_NODE_ID) {
            throw new IllegalArgumentException("nodeId must be 0.." + MAX_NODE_ID);
        }
        this.nodeId = nodeId;
    }

    public synchronized long nextId() {
        long now = currentTime();

        if (now < lastTimestamp) {
            // The clock moved backwards. Issuing anything here risks a duplicate.
            throw new IllegalStateException(
                    "clock moved backwards by " + (lastTimestamp - now) + " ms; refusing to generate");
        }

        if (now == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                now = waitForNextMillis(lastTimestamp);   // 4096 used this millisecond
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = now;

        return (now << (NODE_ID_BITS + SEQUENCE_BITS))
             | (nodeId << SEQUENCE_BITS)
             | sequence;
    }

    private long currentTime() {
        return System.currentTimeMillis() - EPOCH_MILLIS;
    }

    private long waitForNextMillis(long lastTimestamp) {
        long now = currentTime();
        while (now <= lastTimestamp) {
            Thread.onSpinWait();
            now = currentTime();
        }
        return now;
    }

    /** Pull the parts back out — useful in tests and when debugging a stray id. */
    public static Instant timestampOf(long id) {
        long millis = (id >> (NODE_ID_BITS + SEQUENCE_BITS)) + EPOCH_MILLIS;
        return Instant.ofEpochMilli(millis);
    }

    public static long nodeIdOf(long id) {
        return (id >> SEQUENCE_BITS) & MAX_NODE_ID;
    }
}

synchronized on nextId() is not laziness. The method mutates sequence and lastTimestamp together, and the correctness of the whole scheme depends on that pair being consistent. An uncontended lock costs tens of nanoseconds against a budget of 4,096 ids per millisecond, so this is not the bottleneck.

Being able to decode an id matters more than it sounds. When two rows collide in production, the first question is which node issued them and when, and the id itself is the only evidence you have.

Assigning node ids is the hard part

Every generator needs a distinct number, and this is where deployments go wrong. Two generators sharing a node id will eventually produce the same id, same millisecond, same node, same sequence.

What does not work:

Hashing the hostname or MAC address into 10 bits. 1,024 slots and a hash function is the birthday problem: collisions become likely at a few dozen nodes, and nothing detects them.
Configuration by hand. Works until an autoscaler doubles the deployment at 2am.

What does:

A StatefulSet ordinal. notes-api-0, notes-api-1: Kubernetes guarantees uniqueness and reuses the ordinal after a restart. Parse the number off the hostname.
A sequential znode in ZooKeeper, or an etcd lease. The node registers, receives a number, and holds it while its lease is alive. Costs a dependency at startup, not at generation.
A row in the database. A node_registry table with a unique constraint, claimed at boot with a heartbeat. Crude and effective.

Whichever you pick, fail to start if a node id cannot be claimed. Defaulting to 0 turns a configuration problem into silent duplicate ids months later.

The clock

Snowflake’s correctness rests on a monotonically advancing wall clock, and wall clocks do move backwards: NTP corrections, a VM resuming from a snapshot, a hypervisor adjusting.

Note what the implementation above does: it throws. That is deliberate and it is the only safe behaviour. The alternatives are worse:

Wait until the clock catches up. Reasonable for a few milliseconds, unavailable for a leap second, and unbounded for a large correction.
Carry on using the old timestamp. Now lastTimestamp is in the future relative to the clock, and the sequence is the only thing preventing collisions.
Ignore it. Duplicate primary keys, discovered later, in a table you cannot easily repair.

Refusing to issue an id is an outage of one instance. Issuing a duplicate is data corruption. Take the outage, and configure NTP to slew rather than step.

What an id gives away

Two properties are sometimes unacceptable and are worth naming before you commit.

An id is decodable: it reveals its creation time to the millisecond and which node made it. If your ids appear in URLs, the creation time of every object is public.

Ids are enumerable within a node-millisecond. An observer collecting ids over time can estimate your volume, and in some layouts guess neighbouring ids. If ids are also your access-control boundary, a share link that anyone with the id can open, a sequential scheme is the wrong choice. Use a random public identifier alongside the internal one.

Frequently asked questions

Why not just use UUIDv4?

It is coordination-free but unordered, so inserts scatter across a clustered index and range queries on recency cannot use it. It is also 128 bits everywhere the key appears.

Should I use UUIDv7 instead of Snowflake?

Usually yes, if 128 bits is acceptable. UUIDv7 is standardised, time-ordered and needs no node-id assignment, which removes the operationally difficult part. Choose Snowflake when the id must fit in 64 bits.

How long does a 41-bit timestamp last?

About 69.7 years from whatever epoch you choose. Pick a recent one: using 1970 spends decades of range before the system exists.

What happens when 4,096 ids are used in one millisecond?

The generator spins until the next millisecond. That is a hard ceiling of roughly 4.1 million ids per second per node; raise it by taking bits from the node id.

Never, if you want uniqueness. Same millisecond plus same node plus same sequence is the same id. Derive the node id from something that guarantees uniqueness, and refuse to start without one.

Is hashing the hostname good enough for the node id?

No. Ten bits is 1,024 slots and hash collisions become likely at a few dozen hosts, with nothing to detect them.

What should happen if the clock moves backwards?

Throw. Waiting is acceptable for a few milliseconds and unbounded for a real correction; reusing the previous timestamp risks duplicates. An instance refusing to serve is recoverable, duplicate keys are not.

Is the synchronized block a bottleneck?

No. An uncontended intrinsic lock is tens of nanoseconds, far below the millisecond-scale budget the algorithm works in.

Are Snowflake ids safe to expose publicly?

They reveal creation time and node identity, and they are guessable within a node-millisecond. If an id doubles as an access token, use a separate random public identifier.

Do these ids fit in JavaScript?

Not reliably. Number.MAX_SAFE_INTEGER is 2⁵³−1, and a 64-bit id exceeds it. Serialise as a string in any JSON a browser will parse.

Where should I go next?

The system design guides cover the surrounding decisions, and Spring Boot REST API is where a generator like this gets wired into an entity.