SYSTEM DESIGN:Lesson 13: Counting Without Collisions

Three servers, one counter, zero unique IDs

"We deployed three API servers behind a load balancer and used Postgres auto-increment for order IDs. Two orders got ID 847291 on the same millisecond. Finance reconciled duplicates for a week."

Generating unique IDs sounds trivial until you have multiple machines creating records at the same time. A single SERIAL column works on one database. It breaks the moment you shard, replicate with lag, or run ID generation on app servers without coordination.

This chapter covers the core ID generation problem: why auto-increment fails in distributed systems, UUID trade-offs, database sequences, collision math, and the sortable-vs-random debate. Snowflake and datacenter-scale IDs come in the next lesson.

If you built a URL shortener in the earlier chapters, you already touched base62 encoding and counters. This chapter explains why those choices matter when you leave single-server territory.

A UUID so long it needs its own zip code

Unique? Yes. Fits in a WhatsApp message? Absolutely not.

Why auto-increment breaks at scale

Auto-increment is the default in every ORM: id BIGSERIAL PRIMARY KEY. One database, one sequence, guaranteed order. Simple.

It breaks in four common scenarios:

Problem 1 — Multiple app servers, local counters
  Server A: id = 1001, 1002, 1003
  Server B: id = 1001, 1002, 1003   ← collision

Problem 2 — Sharded databases
  Shard 0 sequence: 1, 2, 3...
  Shard 1 sequence: 1, 2, 3...       ← same IDs, different shards

Problem 3 — Write bottleneck
  Every INSERT hits the single sequence row → hot spot

Problem 4 — Predictable IDs
  order/100001, order/100002 → competitor scrapes your volume

Range allocation is a middle ground: a central service hands Server A IDs 1–1000, Server B 1001–2000. Each server increments locally. Works until a server crashes with unused IDs or you run out of range mid-traffic. Acceptable for batch jobs, fragile for real-time APIs.

The four approaches — compared

Comparison of unique ID generation approaches

Interviewers want you to compare at least two. My default answer: "Single-server MVP uses DB auto-increment. Distributed system uses Snowflake-style IDs or UUID v4 depending on whether sort order matters."

UUID v4: random and everywhere

UUID v4 is 128 bits of randomness: 550e8400-e29b-41d4-a716-446655440000. No coordination. Any server generates one independently. Collision probability is astronomically low.

import uuid

def new_order_id() -> str:
    return str(uuid.uuid4())

# "f47ac10b-58cc-4372-a567-0e02b2c3d479"

Pros:

• Zero coordination — perfect for offline-first mobile apps
• Built into every language standard library
• No single point of failure for ID generation
• Works across datacenters without network calls

Cons:

• Not sortable by creation time — bad for database indexes (random inserts fragment B-tree pages)
• 36 characters as string — wide primary keys bloat indexes and JOINs
• Ugly in URLs — schoolabe.com/order/f47ac10b-58cc-4372-a567-0e02b2c3d479 vs schoolabe.com/order/kF3xP
• No embedded metadata — cannot tell which datacenter or service created it

Flipkart-scale order tables with UUID primary keys often switch to UUID v7 (time-ordered) or Snowflake IDs specifically because random UUID inserts kill Postgres write throughput on large indexes.

Database sequences: still useful, with rules

A Postgres sequence is atomic: nextval('order_id_seq') returns a unique increasing number even with concurrent connections.

CREATE SEQUENCE order_id_seq START 1000000;

INSERT INTO orders (id, user_id, total)
VALUES (nextval('order_id_seq'), 4821, 1299.00);

This works with multiple app servers as long as every server asks the database for the next ID. The database is the single coordinator.

Sharding with sequence offsets:

Shard 0: IDs = 0, 4, 8, 12...   (id % 4 == 0)
Shard 1: IDs = 1, 5, 9, 13...   (id % 4 == 1)
Each shard runs its own sequence with INCREMENT BY 4

Each shard's sequence increments by the shard count. IDs are globally unique and sortable. Resharding (4 → 8 shards) is painful — every sequence must be reconfigured. This is why embedded-bit IDs (Snowflake) replaced offset sequences at most large companies.

Throughput ceiling: a single Postgres sequence handles roughly 10,000–30,000 IDs/sec depending on hardware. Enough for most Indian startups. Not enough for Twitter-scale tweet creation.

Collision math — when "unique enough" fails

Collisions are a birthday problem. With random IDs of b bits, collision probability crosses 50% around √(2^b) IDs generated (rough approximation).

UUID v4: 122 random bits
  √(2^122) ≈ 2^61 IDs before ~50% collision chance
  You will never generate 2^61 IDs. UUID v4 is safe.

Truncated hash (7 chars base62 ≈ 42 bits):
  √(2^42) ≈ 2^21 ≈ 2 million IDs
  Collision risk becomes real at scale → need retry or counter fallback

When an interviewer asks "what if two servers generate the same ID?", quantify it. "With UUID v4, collision is negligible. With a truncated hash, I add a DB unique constraint and retry on conflict."

Sortable vs random: pick based on access pattern

This decision affects database performance, API design, and debugging — not just aesthetics.

When to choose sortable:

• High write throughput to indexed tables (orders, tweets, logs)
• URL shortener codes where you base62-encode a numeric ID
• Time-range queries without a separate timestamp column

When to choose random:

• Client-side ID generation (offline mobile, PWA)
• IDs exposed publicly where predictability is a security risk
• Simple systems where index fragmentation does not matter yet

For the URL shortener from earlier chapters: sortable ID + base62 encode gives you short, unique, roughly time-ordered codes. That is why auto-increment or Snowflake beats UUID v4 for short links.

Common mistakes in ID design interviews

Mistake 1 — using UUID v4 everywhere by default.

It is the lazy answer. Fine for a config table with 500 rows. Wrong for a 500-million-row orders table where insert performance and "show latest 20" queries matter.

Mistake 2 — app-server local counters.

Never id = Math.floor(Math.random() * 1e9) or a process-local incrementing counter. Collisions are guaranteed under load.

Mistake 3 — ignoring index width.

A UUID primary key on a table with 4 foreign keys means every index stores 16 bytes per reference instead of 8. At 100M rows, that is gigabytes of wasted RAM.

Mistake 4 — no DB unique constraint.

Even with a perfect ID generator, add UNIQUE on the ID column. Generators have bugs. Constraints are your last line of defence.

Mistake 5 — predictable IDs for sensitive resources.

Invoice IDs INV-2026-00001 through INV-2026-00847 tell competitors your sales volume. Use opaque IDs for anything a user can guess and enumerate.

Interview talking points

When asked "design a unique ID generator":

1. Clarify — sortable? URL-safe? Offline generation? QPS? ID length?
2. Single vs distributed — one DB sequence may be enough below 5k IDs/sec
3. Compare UUID v4 vs Snowflake — random/coordination-free vs sortable/coordinated
4. Collision handling — unique DB constraint + retry for hash-based; impossible for counter-based
5. Failure modes — clock skew (Snowflake), sequence exhaustion, hot-spot on single coordinator

Say "I would start with DB auto-increment for an MVP, move to Snowflake when we shard or exceed sequence throughput" — it shows progression, not premature complexity.

What comes next: Snowflake at scale

When 10,000 IDs per second from one Postgres sequence is not enough, and you need sortable, datacenter-aware, 64-bit integers — that is when Twitter's Snowflake pattern enters the room.

The next chapter breaks down the bit layout, clock skew handling, throughput math, and alternatives like Sonyflake and ULID.

Continue here: Snowflake IDs at Scale.