The Identifier: Generating Unique IDs Without a Central Authority

The Deceptively Simple Problem

Every database row, every event log entry, every message in a queue needs an identifier. In a single-process system, this is a solved problem. You have one counter. You increment it. You move on.

In a distributed system, you have ten machines, each receiving writes concurrently, none of them coordinating with the others. Now what?

The naive approach is to keep a central ID server. Every node that needs an ID asks the central authority. The central authority hands out the next sequential number. This actually works, and systems have been built this way. The problem is you have just created a single point of failure and a write bottleneck. Every ID request now requires a network round-trip to one machine. Under high load, that machine becomes the ceiling on your throughput. Under failure, it stops everything.

So you need IDs that each node can generate independently, without coordination, while still guaranteeing that no two nodes ever produce the same ID. This is harder than it sounds.

Why Simple Approaches Fail

The first instinct is usually timestamps. Use the current time in milliseconds as your ID. Two events that happen at the same time should have different IDs. But two nodes might generate an ID at the exact same millisecond, giving you a collision. Even on a single machine, if your system is fast enough, you can generate multiple IDs within the same millisecond.

The second instinct is randomness. Generate 128 bits of random data. The birthday problem guarantees that with enough IDs, you will eventually get a collision, but with 128 bits the probability is so low that it is effectively zero for any practical system. This is the logic behind UUID v4.

UUID v4 looks like this: 550e8400-e29b-41d4-a716-446655440000. It is 128 bits of randomness, formatted as five hyphen-separated groups of hexadecimal digits. The version and variant bits are fixed, leaving 122 bits of entropy. To have a 50% chance of a collision, you would need to generate 2.71 quintillion UUIDs. At a billion UUIDs per second, that takes about 85 years.

UUID v4 is correct. The problem is that it is random. And random IDs cause a specific, serious problem in databases.

Index Locality and Why Random IDs Are Expensive

Most databases use B-tree data structures for indexes. A B-tree keeps data sorted. When you insert a new row with a sequential ID like 1, 2, 3, the new row goes at the end of the index. The leaf page you are writing to is likely already in memory from the previous insert. This is fast.

When you insert a row with a random UUID, the ID could fall anywhere in the sorted order. You are writing into a random location in the index. That leaf page is almost certainly not in memory. The database must do a disk read to find the right page, insert the row, and write it back. This is the classic "random write" performance problem.

Under high write throughput, UUID primary keys cause your database's buffer pool to thrash. Every insert touches a different page. Your cache hit rate for index pages plummets. Databases like MySQL's InnoDB store rows in primary key order, so random UUIDs mean your entire table is fragmented.

This is not theoretical. Engineers at companies with heavy write workloads have benchmarked the difference between sequential and random primary keys and found order-of-magnitude differences in write throughput at scale.

The practical lesson: random IDs are convenient, but they carry a hidden performance tax that only shows up at scale.

Twitter's Snowflake

In 2010, Twitter was growing fast. They needed to generate unique IDs for tweets. The requirements were clear: IDs must be unique across all machines, they must be roughly sortable by time (so you can paginate through recent tweets efficiently), and the system must be available even if some machines are down or unreachable.

Their solution, published as Snowflake, packs a 64-bit integer with three components:

| 41 bits timestamp | 10 bits machine ID | 12 bits sequence |

The timestamp is milliseconds since a custom epoch (January 1, 2010 in Twitter's case). 41 bits gives you 69 years before overflow. The 10 bits of machine ID encode which node generated the ID, split into 5 bits for datacenter ID and 5 bits for machine ID within that datacenter. This supports 32 datacenters each with 32 machines. The 12-bit sequence counter allows 4096 unique IDs per millisecond per machine.

The bit packing means IDs are monotonically increasing within a machine (barring clock drift, which we will get to). Two IDs from different machines generated at the same millisecond will differ in the machine ID bits. The result is that the IDs are roughly time-ordered even when generated across many machines, which preserves the index locality property of sequential IDs.

Generating a Snowflake ID looks like this:

def generate_id(self):
    timestamp = int(time.time() * 1000) - EPOCH

    if timestamp == self.last_timestamp:
        self.sequence = (self.sequence + 1) & 0xFFF
        if self.sequence == 0:
            # Sequence overflow: wait for next millisecond
            while timestamp <= self.last_timestamp:
                timestamp = int(time.time() * 1000) - EPOCH
    else:
        self.sequence = 0

    self.last_timestamp = timestamp

    return (timestamp << 22) | (self.datacenter_id << 17) | (self.machine_id << 12) | self.sequence

The bit shifts pack each component into the correct position in the 64-bit integer. The sequence overflow handling shows what to do when you exhaust the 4096 IDs available in a millisecond: you wait. In practice, the microsecond-level pause before the next millisecond ticks over is acceptable for most workloads.

The Clock Problem

Snowflake has a subtle dependency: it assumes clocks only move forward. This is not always true.

Network Time Protocol (NTP) occasionally adjusts clocks backward to correct drift. If your machine's clock jumps backward 100 milliseconds, and your ID generator then produces IDs with a timestamp that is 100 milliseconds in the past, you might generate an ID that is identical to one you already produced. The same timestamp, same machine ID, and if the sequence counter happened to be at the same value, the same sequence number. Collision.

Production Snowflake implementations handle this by refusing to generate IDs when clock drift is detected. If now < last_timestamp, the generator waits until the clock catches up. This means that after an NTP adjustment, there is a brief pause in ID generation equal to the amount the clock moved backward.

In the worst case, if a machine restarts with a clock that is in the past (perhaps the system clock was wrong), you could generate IDs that duplicate IDs generated by a previous run of the same machine. This is why Snowflake requires each machine ID to be unique and persistent across restarts, and why it is worth persisting the last-used timestamp to disk so you can detect problematic clock scenarios on startup.

ULID: A Better Default

UUID v4's random distribution is its weakness. Snowflake's 64-bit integer requires coordination to assign machine IDs. For many use cases, there is a middle ground: the Universally Unique Lexicographically Sortable Identifier, or ULID.

A ULID is 128 bits: 48 bits of millisecond timestamp followed by 80 bits of randomness. It is encoded in Crockford's Base32 to produce a 26-character string like 01ARZ3NDEKTSV4RRFFQ69G5FAV.

The key properties:

• Lexicographic sort order matches time order. 01ARZ3... comes before 01ARZ4... in string comparison, and the later ID was generated later. Your database index stays mostly sequential.
• No coordination required. The 80 bits of randomness per millisecond make collisions essentially impossible without needing to know anything about other generators.
• Monotonic within a millisecond. The spec includes an optional monotonic mode where if two ULIDs are generated within the same millisecond, the second one increments the random component rather than generating a new random value, preserving sort order even at sub-millisecond granularity.

The practical tradeoff compared to Snowflake is that ULIDs are not perfectly sequential within a millisecond (unless using monotonic mode), and they are 128 bits instead of 64. Most modern databases handle 128-bit primary keys fine, but a 64-bit integer is somewhat more compact.

For new projects where you do not need Snowflake's specific machine-ID-embedded structure, a ULID is often the right default. It is sortable, it requires no coordination, and it avoids the index fragmentation problem of UUID v4.

The Birthday Problem in Practice

The birthday problem is the counterintuitive probability calculation that in a group of 23 people, there is a better-than-50% chance that two people share a birthday. The same math applies to ID generation.

For UUID v4 with 122 bits of entropy, the probability of a collision after generating n IDs is approximately n^2 / 2^123. To get to a 1-in-a-billion chance of collision, you need to generate about 1.2 trillion UUIDs. That is a lot. At a million UUIDs per second, you would generate 1.2 trillion in about 13 days. At that rate, you probably want Snowflake or ULID rather than UUID v4 anyway.

For an 80-bit random component (like ULID), the collision probability is higher but still extremely low for practical systems. You would need to generate about 1.2 billion IDs in the same millisecond to have a 1-in-a-trillion chance of collision within that millisecond.

The risk of birthday-problem collisions is much lower than the risk of implementation bugs in your ID generator. UUID v4 is safe for all but the most extreme-scale systems. The real reason to choose ULID or Snowflake over UUID v4 is database performance and sortability, not collision probability.

Partition Tolerance

One of the requirements in this track is that your ID generator must work during a network partition. A node that cannot reach any other node must still be able to generate IDs.

This is where centralized approaches fail. If your ID server is unreachable, you cannot generate IDs. If you use a consensus protocol to coordinate ID generation, a partition that isolates a node from the majority means that node cannot generate IDs.

Snowflake's design is explicitly partition-tolerant in this sense. Each node generates IDs using only its local clock and its locally-assigned machine ID. No network communication is required. A fully isolated node continues generating unique IDs indefinitely.

This is the correct design choice. IDs should be generated from local state. The uniqueness guarantee comes from the combination of machine identity (assigned at startup, not at generation time) and local time. The only coordination required is the initial assignment of machine IDs, which can happen at node startup and does not need to repeat for each ID generated.

This fits a broader principle: move coordination out of the hot path. The expensive work of ensuring uniqueness (assigning machine IDs, handling time synchronization) happens rarely. The common case, generating an ID, is entirely local.

Choosing the Right Scheme

For most applications, the decision tree looks like this.

If you need a 64-bit integer for storage efficiency, database index performance, and you have a bounded number of machines, use Snowflake or a Snowflake variant. Assign machine IDs at startup using a coordination service like ZooKeeper or etcd. Generate IDs locally thereafter.

If you need a string identifier (for API responses, URLs), want simplicity, and are not at Snowflake-scale, use ULID. You get good sort behavior, no coordination, and reasonable storage size.

If you are working with external systems that already use UUID v4, or storage size does not matter and sort order is irrelevant, UUID v4 is fine. Its collision probability is genuinely negligible for almost every real application.

The one scheme you should avoid for new code is sequential integers from a central counter. Not because it is wrong, but because it creates operational complexity: you need the counter to be highly available, you need it to be fast, and any failure in the counter service stops all writes to your system. The local generation schemes give you the same uniqueness guarantee with far better fault tolerance properties.

MongoDB's ObjectId is worth knowing as a real-world example that predates Snowflake but makes similar choices: 4 bytes of timestamp, 5 bytes of random machine identifier, and 3 bytes of incrementing counter. It is 96 bits, sortable by time, and requires no coordination. The machine identifier in ObjectId is not pre-assigned but generated randomly at startup, which means there is a small but non-zero collision probability in the machine ID space. For MongoDB's use case, this tradeoff is acceptable.

The deeper lesson from all of these schemes is that uniqueness in distributed systems comes from combining locality (each node has unique identity) with time (things that happen at different times are distinguishable) and optionally randomness (to handle the same-millisecond case). These three ingredients, mixed in different proportions, give you the full design space of distributed ID generation.