Unique ID Generator: High-Level Design

Step 5: High-Level System Design

First, a decision: a library or a service?

Step 4 left us with one endpoint. This step decides what sits behind it.

Snowflake needs no coordination to make an ID. A node that knows its own machine number can produce IDs forever without talking to anything. So the obvious question is why there is a service here at all.

There are two ways to ship this.

As a library, running inside each client. The application imports a package, gets a machine number at startup, and makes IDs in its own process. This is what Twitter, Instagram and Discord actually do. An ID costs a few processor instructions and no network at all.

As a service, called over the network. Clients ask for IDs over HTTP or gRPC. This is what the rest of this chapter builds.

On these measures, the library is clearly better.

A service puts a network hop in front of every row a client inserts. It also makes ID generation a shared dependency, so an outage there stops writes everywhere. Those are real costs. Any proposal for a service has to name them, because they are the interesting part of this problem.

So why build one anyway? There are three reasons, and all of them are about organizations rather than machines.

The first is the machine numbers themselves. Ten bits give 1024 of them, and every generating process needs one of its own. Handing them out across deploys and autoscaling is a coordination problem that grows with the fleet. A service turns that problem into a few dozen long-lived nodes.

The second is languages. A library has to be built and kept correct in each language its clients use. A subtle bug in clock handling then exists in several places at once.

The third is change. Suppose the time field grows from 41 bits to 42, or the epoch changes. The epoch is the date the time count starts from. Every client that carries the library then has to be redeployed. Behind a service it is one rollout.

The best answer is a hybrid. Ship a library for the services that generate IDs in bulk and can be trusted with a machine number. Run the service for everything else, and for clients in languages the library does not cover. The count parameter from Step 4 is what makes the service tolerable. A client that fetches a thousand IDs at a time makes one network call per thousand rows rather than one per row.

The rest of this step designs the service. It is the harder of the two, and it contains the library as a part.

The service itself

We build a dedicated ID Generation Service. It runs in many regions, with many instances in each. The parts are ordinary. What is unusual is how little they need from each other.

Start with the callers. Client services are the microservices and applications that need unique IDs, for new database records, objects, and so on. Instead of making IDs themselves, they call the ID service whenever they need one.

They all call one well-known endpoint. A global load balancer or API gateway routes each request to a generator instance. That can be DNS pointing at a regional endpoint, or an anycast IP or cloud load balancer that finds a nearby healthy instance. The gateway spreads load evenly and sends traffic to the closest datacenter, which keeps latency low. Any node can answer any request, so distance is the only thing left to choose on.

Behind the gateway sit the ID generation service nodes. These are the worker servers or containers that actually make IDs. They run the generation algorithm, detailed in the next step. There are multiple instances per region, and each knows its own unique node ID, so no two nodes produce the same IDs.

The nodes are stateless in the sense that any node can handle any request. Nothing about a request is kept after it is answered. Each node does hold a little configuration: its node ID and its algorithm state. That state matters to nobody but the node itself, so losing a node costs only its capacity.

The service is a lightweight program in a fast language like Java, Go or C++. It is tuned for fast atomic operations, meaning steps that cannot be interrupted halfway, and for fast time reads.

One part is shared, and only one. To guarantee uniqueness across nodes and datacenters, we use a small coordination service. Apache ZooKeeper, etcd, or a lightweight consensus service will do. It gives each generator node a unique identifier, made of region ID bits and machine ID bits. When a node starts, it contacts the coordinator and gets a free worker ID. The coordinator tracks which IDs are in use, so no two live nodes ever share one.

Notice when a node talks to it: at startup, and never again. So if the coordinator goes down for a while, existing nodes keep their IDs and keep serving. What stops is growth, because no new node can join until it is back. We run the coordinator as a resilient cluster to keep that downtime short.

One more part is worth naming, though we do not use it. Our final design favors the Snowflake approach with no central database. But an alternative mode hands out blocks (segments) of IDs. In that mode a relational database or key-value store holds and increments counters. Each database call returns a range of IDs for the service to hand out. That database would be critical, and a potential bottleneck. So in the chosen approach we avoid it, except as a backup or hybrid.

Now follow one request through those parts.

1. A client needing an ID calls the API, for example POST /v1/ids with type set to sortable or opaque. The request reaches the load balancer or API gateway.
2. The load balancer forwards it to a healthy generator node in the nearest region, using health checks and possibly client location. For global clients, DNS may resolve to the local region's endpoint. If one region is overloaded, a cross-region call is allowed, though normally each region serves its own traffic.
3. The chosen node checks the request type. For a time-sortable ID it runs the Snowflake-like algorithm. It reads the current time in milliseconds. It combines that with its region and machine ID and an internal sequence counter. For an opaque ID it asks a secure random generator for 128 bits, or calls a UUIDv4 library. Each such call is independent and needs no shared state. Either way the work is local and very fast, a few arithmetic and bit operations or a few random bytes. There is no extra network call on this path. The node never asks another node for anything.
4. The node returns the ID, usually as a numeric string for time-sortable or a UUID-formatted string for opaque. For example, {"ids": ["1541757210912000000"]} or {"ids": ["c2f3a8d0-7e5b-4efb-b1a2-5d91c1e315b8"]}. The client uses the ID, for example as a key in a database insert. The round trip is quick, often a few milliseconds within one region, well under the latency target from Step 2.
5. If a request fails, say because the node was unresponsive, the client or gateway retries, possibly on a different node. A retried request just produces a new ID. An ID that was made but never used is simply lost, and that causes no conflict. So retries are safe. A client can also request a batch in advance, so spare IDs are ready if a call fails. That is an optional client-side optimization.

One question is still open. Every region runs its own nodes, and they never ask each other anything. So what stops two of them making the same ID?

Each region's cluster of nodes gets a distinct region identifier. For time-sortable IDs, that region ID is part of the ID itself. For opaque IDs we do not include it, because randomness alone gives global uniqueness there.

In the Snowflake layout, some of the machine ID bits encode the region. For example, a 10-bit machine ID can be split into a 5-bit datacenter ID and a 5-bit host ID. Region A might be datacenter 5 and Region B datacenter 6. Two machines in different regions can then make an ID in the same millisecond, with the same sequence number. The datacenter bits still differ, so the two 64-bit IDs are distinct.

The coordinator manages this by pre-allocating a range of machine IDs to each region. With 5 region bits, region 1 gets IDs 0 to 31, region 2 gets 32 to 63, and so on. Or the region ID can be an explicit field in the ID. Either way, no coordination between regions is needed per request. The layout does the work that coordination would otherwise have to do.

An example makes that concrete. Service X in the US-East region needs an ID for a new user profile. It calls the ID API. The US-East load balancer routes the call to a node with, say, region 1, node 3. The node's Snowflake algorithm reads the wall-clock time. It turns that into a 41-bit value counted from the epoch. It combines that with datacenter=1, worker=3, and the sequence, say 5 if it has already made 5 IDs this millisecond. The result is a 64-bit ID like 0x1E2C..., returned in decimal form.

Meanwhile a client in the EU region calls at nearly the same moment. Its node has datacenter=2 and maybe sequence 1, so it yields a different 64-bit number. Even if the timestamp bits are identical, the datacenter bits differ, so the IDs are unique.

Later, when both IDs sit in a database, sorting them puts the US-East one before or after the EU one by timestamp. If the timestamps are equal to the millisecond, the datacenter bits decide the order. That is not strictly true time order, but such ties are rare and only happen within one millisecond.

The whole design is a set of generator nodes that work almost independently. A lightweight coordinator only assigns node IDs. Clients reach the service through a simple network API. The request path holds no shared state, so load balancing and horizontal scaling are easy.

Next: Step 6, which compares the ways to actually make an ID.