System Design Interview Questions: ID Generation

True. UUID v4 IDs can be generated independently on separate servers with no coordination. Each ID carries 122 random bits, so the chance of a collision stays negligible even across millions of generated IDs.

UUID v4 keys can be generated independently on many servers with no central counter, lock, or coordination round-trip, which is their main advantage over sequential auto-increment keys in distributed systems. The trade-offs are a larger 128-bit size and random insertion order that can fragment B-tree indexes.

It generates 64-bit IDs laid out as: a 1-bit sign/unused bit (always 0, ensuring the ID is a positive integer), a 41-bit timestamp (milliseconds since a custom epoch), a 10-bit worker/machine ID, and a 12-bit per-millisecond sequence number. The timestamp prefix makes Snowflake IDs roughly sortable by creation time, the worker ID enables distributed generation without a central coordinator, and the sequence number disambiguates multiple IDs produced on the same node within the same millisecond.

Twitter Snowflake-style IDs satisfy all three requirements. They pack a millisecond timestamp, a worker ID, and a per-millisecond sequence into one 64-bit integer, so IDs sort roughly by creation time and each node generates them locally without a coordinator, provided every node has a distinct worker ID.

UUID v4 generates 122 random bits, so each new key lands at an arbitrary position in the clustered B-tree instead of appending at the end. This forces frequent page splits, poor buffer-pool locality, and index fragmentation on every insert. Using time-ordered or sequential identifiers, such as a Snowflake ID, ULID, UUID v7, or an auto-increment column, appends new rows near the existing leaf pages, keeping the B-tree compact and writes fast.

Twitter Snowflake divides its 64-bit ID into four fields: 1 sign bit, 41 bits for the timestamp, 10 bits for the worker ID, and 12 bits for the sequence number.

Database auto-increment's primary trade-off is a single point of failure, because all writes funnel through one primary. Snowflake requires each node to have a unique worker ID, and UUID v4 is not time-sortable, which scatters B-tree index inserts.

The lifecycle of a Snowflake ID generation call runs: read the current millisecond timestamp, compare it with the last timestamp used, increment or reset the sequence, pack the timestamp, worker ID, and sequence into a 64-bit integer, then return the ID. Each step needs the result of the one before it, so the order is fixed.

No, the 41-bit millisecond timestamp in Twitter Snowflake covers only about 69.7 years. 2^41 milliseconds is roughly 2.2 trillion ms, which works out to about 69.7 years. Snowflake deployments set a custom epoch, such as Twitter's November 4, 2010, so the range extends well into the future.

Snowflake is the ID-generation scheme that packs a timestamp, a worker ID, and a sequence number into a 64-bit integer, so many machines can generate IDs independently. ULID and UUID v7 are 128-bit identifiers, and auto-increment is issued by a single database rather than generated in a distributed way.

True. Two Snowflake-style nodes that share a worker ID and emit IDs in the same millisecond can produce identical (timestamp, worker_id, sequence) tuples. Each node keeps its own sequence counter starting at 0, so nothing prevents the collision. Unique worker IDs are required for uniqueness.

In Twitter's original Snowflake ID generation algorithm, the 10-bit field that identifies the generating node is called the worker ID, and the 12-bit field that disambiguates multiple IDs generated within the same millisecond on the same node is called the sequence number.

Snowflake: suitable, because each ID starts with a millisecond timestamp, so IDs sort by creation time. ULID: suitable, because it also starts with a timestamp and is lexicographically sortable. UUID v4: not suitable, because it is random and carries no creation-time information. Auto-increment: suitable, because values are sequential and roughly track insertion order, though it requires a single coordinating database to issue them.

False: UUID version 4 does not require coordination between nodes. Each node fills 122 bits with random values independently, so collisions are astronomically unlikely without shared state. Uniqueness is probabilistic rather than a strict mathematical guarantee.

Snowflake-style IDs are preferable to UUID v4 in a clustered index because they are 64-bit instead of 128-bit, which shrinks storage and index size. Their roughly time-ordered prefix also makes new rows append near the end of the index rather than causing random page splits and fragmentation.

I would use a Snowflake-style 64-bit id: a millisecond timestamp, a worker/shard id (for example 10 bits, about 1024 workers), and a per-millisecond sequence counter (for example 12 bits, 4096 ids per ms per worker). Each worker generates ids locally with no per-id coordination, and the capacity per shard (roughly 4 million ids per second) far exceeds the 50k/s total requirement. Ids from one shard increase because the timestamp dominates the ordering and the sequence orders ids within the same millisecond. The shard id is assigned at startup from a config service such as ZooKeeper and persisted, so a restarted worker does not reuse an id space it used before. For clock drift, the worker stores the last timestamp it issued and never issues an id with an earlier timestamp; if the clock jumps backward, it waits until the clock catches up (or refuses to issue ids and alerts) instead of generating stale or duplicate values. For shard failover, a standby may take over a shard id only after the original is confirmed dead, using a lease or heartbeat with a fencing token so two live workers never share the same worker id. I considered random UUIDv4 (coordination-free but not sortable and 128 bits) and a centralized database sequence (ordered but a single point of failure and a throughput bottleneck). Snowflake balances monotonicity, throughput, and operational simplicity.

Snowflake-style IDs are 64-bit integers with a 41-bit millisecond timestamp in the high bits, a 10-bit worker ID, and a 12-bit sequence. Each worker generates IDs locally without a central database per ID. Ordering is only rough, not strict, and a backward clock jump left unhandled can produce duplicate IDs.

I would implement a Snowflake-style ID generator. The 64-bit ID is split into three fields: 41 bits for a millisecond timestamp (giving ~69 years of range from a custom epoch), 10 bits for a worker ID (up to 1,024 workers), and 12 bits for a per-millisecond sequence number (4,096 IDs/ms per worker, ~4M IDs/sec per worker). The timestamp occupies the high-order bits so sorting IDs numerically approximates sorting by creation time. Worker ID assignment: each worker acquires one of the 1,024 available worker-ID slots (0–1,023) through a coordination service (e.g., ZooKeeper) at startup. Specifically, the worker attempts to create an ephemeral node at a well-known path for each slot it tries (e.g., /workers/worker-<id>), starting from slot 0 and incrementing until it succeeds at creating a node that does not already exist. Because a slot node is only held while the worker's ZooKeeper session is alive, a crashed worker's ephemeral node disappears, freeing that exact slot for a replacement. The worker caches its assigned slot ID in memory during its session. If ZooKeeper is unavailable at startup, the worker refuses to serve IDs until it obtains a valid, non-conflicting worker ID—using a stale cached ID risks collision if the original holder is still alive. This slot-based scheme never reuses a slot that is still held, so the monotonic ZooKeeper sequential counter cannot cause two live workers to collide on the same ID. Clock drift handling: the worker tracks the last timestamp for which it generated IDs. Before generating a new ID, it reads the system clock; if the clock has moved backward (e.g., NTP step), the worker refuses to generate IDs with a timestamp earlier than the last-used timestamp, returning an error or sleeping until the clock catches up. This prevents duplicates from reusing a previous (timestamp, sequence) pair. Sequence exhaustion: if a worker generates 4,096 IDs in one millisecond, it does not wrap around—instead it busy-waits until the next millisecond. This bounds per-worker throughput at ~4M IDs/sec, well above the 100k/sec target. Failure degradation: if ZooKeeper goes down after a worker has its ID, the worker continues using its cached worker ID (the slot remains valid until its session expires). If ZooKeeper is down for a long period and workers restart, there is a collision risk if a session expires while the worker is still alive; a mitigation is to also encode a datacenter ID or use a persistent worker-ID registry (e.g., a database table with a unique constraint) alongside the ephemeral slot approach.

Use a Snowflake-style approach: each ID is a 64-bit integer composed of a 41-bit millisecond timestamp (custom epoch), a 10-bit worker/machine identifier, and a 12-bit per-millisecond sequence number. Worker IDs are assigned by a lightweight coordination service (e.g., ZooKeeper or a database table with a unique constraint) so each of the 1,000 nodes gets a distinct 10-bit ID (up to 1,024 workers). Within a single millisecond on a single node, the 12-bit sequence number disambiguates concurrent requests (up to 4,096 per ms per node, well above the 10 writes/sec/node average). Uniqueness holds because no two nodes share a worker ID and the sequence resets each millisecond, so the (timestamp, worker, sequence) triple is unique. Time-ordering holds because the high-order bits are the timestamp, so IDs sort numerically by creation time at roughly millisecond granularity. There is no single point of failure for ID generation itself: each node generates IDs locally, needing only clock synchronization (NTP). The coordination service is used only at startup to obtain a worker ID; if it is unavailable, a node can reuse a cached or range-based assignment. Compared to UUID v4 (122 random bits, 16 bytes, not sortable, but zero coordination and negligible collision risk), Snowflake yields compact 8-byte sortable IDs at the cost of worker-ID allocation and roughly synchronized clocks. Compared to database auto-increment (simple and strictly monotonic, but a write bottleneck and single point of failure at 10k/s), Snowflake avoids centralized writes. Edge cases: clock skew (a node whose clock moves backward should pause generation until it catches up), worker-ID exhaustion (2^10 = 1,024 workers is enough here), and timestamp rollover (41 bits ≈ 69 years from the epoch).

Use Snowflake-style ids that pack a timestamp, a node id, and a per-node sequence counter — coordination-free, unique, and naturally time-ordered. Every node mints ids locally with no round-trip, and the timestamp prefix gives the index locality you want. A central sequence reintroduces the coordination and single point of failure; UUIDv4 is coordination-free but fully random, so it scatters B-tree inserts; and hashing row contents lets identical rows collide.

Requirements. Two operations dominate: create (write a mapping, optionally with a custom alias and expiry) and redirect (look up a code and 30x to the long URL). The system is overwhelmingly read-heavy (100:1), so the redirect path is what we optimise. I'd confirm: are custom aliases required (yes), do links expire (optional TTL), and how precise must click counts be (approximate/eventually-consistent is fine). I'd use a 302 (temporary) redirect so we keep serving redirects through our system and can still count clicks; a 301 would let browsers cache and bypass us.

Capacity. ~40 writes/sec average, ~200/sec peak; ~4K reads/sec average, ~20K peak. Storage: ~6B links over 5 years; at ~500 bytes/row (code, URL, metadata) that's ~3 TB — comfortably shardable. Keyspace: base62 with 7 characters gives 62⁷ ≈ 3.5×10¹² codes, far more than 6B, so 7 chars (often padded to a fixed length) is plenty. The hot working set (recently/ popularly accessed links) is a small fraction of 6B, so a cache of tens of GB covers the bulk of redirect traffic.

Data model. A single mapping table/collection keyed by the short code: code (PK) → long_url, created_at, expires_at, owner_id. Point lookups by primary key suit a key-value store (DynamoDB/Redis-backed) or a sharded relational table sharded by code. Click counts live separately — incrementing a counter on every redirect would put write load on the read path — so clicks are emitted as events and aggregated asynchronously.

Short-code generation. Generate a unique 64-bit id (a distributed counter handed out in ranges per server, or a Snowflake-style id) and base62-encode it to get the short code; this guarantees uniqueness with no collision checks and no hotspot from a single shared counter. Custom aliases are written directly with a uniqueness check and stored in the same table, reserving that code. (A hash-of-URL scheme is the alternative but needs collision handling and breaks idempotency for duplicate URLs.)

Read/write paths. Write: allocate id → base62 → insert mapping → return the short URL. Redirect: a load balancer / CDN fronts stateless app servers; the server does a cache-aside lookup (code → long_url) in Redis, falling back to the store on a miss and populating the cache, then returns a 302. This keeps p99 well under 100 ms for cache hits. Expiry is enforced by TTL on both the row and the cache entry. Each redirect fires a lightweight click event onto a queue (Kafka) that a consumer aggregates into per-link counts.

Bottleneck & scaling. The bottleneck is the redirect read path at peak. We scale it with cache layers (most reads never touch the store), read replicas, and sharding the mapping store by code so lookups stay single-shard. Id generation scales by handing each server an independent id range (or using Snowflake), avoiding a single global counter as a SPOF. At 10× traffic, the cache absorbs most of it; we add cache nodes and replicas and, if needed, push redirects further to the edge.

Use a Snowflake-style 64-bit integer layout: 1 unused sign bit (kept 0), 41 bits of millisecond timestamp (about 69 years from a chosen custom epoch), 10 bits of worker ID (1,024 generators), and 12 bits of per-millisecond sequence (4,096 IDs per ms per generator, roughly 4 million IDs/sec per generator). Generation is fully local: each application node calls its own in-process generator, so there is no central ID server on the hot path. Worker IDs must be unique across the whole fleet, including all data centers, so they are leased from a coordination service such as ZooKeeper or etcd (or allocated from a database table with a UNIQUE constraint on worker_id) at startup and renewed as leases; a common split is a 5-bit datacenter ID plus a 5-bit worker ID within it. Each generator keeps a last-issued timestamp and sequence: within the same millisecond it increments the sequence, and if the sequence overflows it waits for the next millisecond instead of wrapping. For clock drift, the generator keeps a watermark of the last timestamp it used; if the wall clock (for example after an NTP correction) reads earlier than the watermark, it refuses to issue IDs (or waits) until the clock passes the watermark, so its IDs never decrease. Because worker IDs are unique, two generators that share a millisecond still produce different IDs. Note that the IDs are strictly increasing per generator and time-ordered at millisecond granularity across generators, not a strict global sequence.

Snowflake-style 64-bit IDs put a timestamp in their high-order bits, so numeric order follows creation time, and each generator needs a distinct worker ID assigned out of band. A UUID v4 has 122 random bits, since 6 of its 128 bits are fixed version and variant markers. A UUID v4 does not fit in a 64-bit BIGINT.

I would use a Snowflake-style 64-bit layout: 1 sign bit (always 0), 41 bits of millisecond timestamp since a custom epoch (2^41 ms is about 69 years), 10 bits of worker/machine ID (1,024 workers), and 12 bits of per-millisecond sequence (4,096 IDs per ms per worker). Each application process generates IDs locally in memory, so there is no network call per ID and latency is well under a microsecond to a few microseconds. Throughput is far above the requirement: one worker produces about 4.1 million IDs/s, and the 10,000 IDs/s target needs only a tiny fraction of one worker. Worker IDs are leased at process startup from a coordination service (ZooKeeper, etcd, or a database row) and cached locally; if the coordinator is down, workers that already hold a lease keep generating IDs, so the coordinator is not on the hot path. For sequence exhaustion, if a worker has issued 4,096 IDs in the current millisecond it spins or waits until the next millisecond before issuing more. For clock skew, the worker records the last timestamp it used; if the wall clock moves backward by a small amount, it refuses to generate (or waits) until the clock catches up to the last timestamp, and for larger regressions it raises an alert and stops issuing IDs rather than risk duplicates. Trade-offs: IDs are only roughly time-ordered across machines because of clock skew and per-worker sequences; the design depends on NTP-disciplined clocks; the 10-bit worker field caps the fleet at 1,024 concurrent worker IDs, so worker-ID reuse and lease expiry must be managed; and the IDs leak approximate creation time and worker identity. Alternatives such as UUIDv7 or ULID avoid worker assignment but are 128-bit, and a centralized sequence (ticket server or database ranges) is simpler but reintroduces a single point of failure and a throughput bottleneck.

It blocks (waits or spins) until the clock advances to the next millisecond, then resets the sequence to 0 and resumes generating IDs. Wrapping the sequence within the same millisecond would reproduce an existing (timestamp, machine, sequence) tuple and cause ID collisions, so the generator waits for a new timestamp instead.