The ID collision

A counter hands out a new number for every link. So how do two links end up with the same code?

Before this: Hash or counter·Next: The stale redirect

In 30 seconds

The problem: Two different long URLs get the same short code, so one of them sends visitors to the wrong page.
Why it happens: The handler reads the counter, then writes counter + 1. Two requests that overlap both read the same number before either one writes.
The fix: Let the database read and bump the counter in one step: nextval() on a sequence, or UPDATE … RETURNING.
In an interview: Never read a counter and write it back in two steps. Let the database hand out the number in one statement, a sequence or UPDATE … RETURNING, and keep a unique index on the code as the safety net.

Why it matters

In the previous step we picked a counter because it can never collide. That promise only holds if each number is handed out exactly once. Written the obvious way, it is not.

It never shows up on your laptop, where you send one request at a time. Do the maths with our own numbers instead: 40 new links a second. If the gap between reading and writing the counter is 5 ms (two trips to the database), the chance that another request reads inside that gap is about 1 in 5 (1 − e^−0.2 ≈ 18%). Not a rare edge case: it happens all day.

Words you need

Race condition: A bug that only appears when two requests overlap in an unlucky order. Each request is correct on its own.
Read, then write: Read a value, change it in your code, write it back. Another request can read the same old value in between.
Atomic: Done as one step that nothing can interrupt. Another request sees it either not started or fully finished.
Sequence (counter): A database counter that hands out the next number, exactly once, every time it is asked.
Unique index: A database rule that rejects a second row with the same value. A safety net: it turns a silent duplicate into an error.

Picture it

The counter is at 1,000. Alice and Bob shorten two different URLs.

One at a time (what your tests do)

Alice reads 1000
writes 1001
Bob reads 1001
writes 1002

Alice gets g8, Bob gets g9. Every test passes.

Overlapping (what production does)

Alice reads 1000
Bob reads 1000
Alice writes 1001
Bob writes 1001

Both encode 1000, so both get g8, and the counter moved by one instead of two. Without a unique index both rows are saved and g8 goes to whichever the lookup finds. With one, Bob's request fails.

Break it yourself

Play: The ID collisionYou decide which request moves next. Find the order that breaks it, then try the fixes below. The game checks every possible order, not just yours.

The fixes people try

A mutex in the API
Fails
await mutex.acquire()
A mutex lives inside one process. Two servers have two mutexes, and their requests never wait for each other.
A unique index on code
Half a fix
code text PRIMARY KEY
Stops the silent duplicate, but the second request now fails with a duplicate-key error. Keep it as the safety net; it is not the fix.
Lock the counter row
Works
SELECT value … FOR UPDATE
Correct, but every new link queues on one row for a whole transaction.
UPDATE … RETURNING
Works
SET value = value + 1 RETURNING value
Reads and bumps in one statement. The row is locked only for that statement.
A sequence
Works
SELECT nextval('link_ids')
Built for exactly this. Never hands out the same number twice, and callers do not wait for each other.

The fix and its cost

Use a Postgres sequence. nextval() is atomic: two requests can call it at the same instant and still get different numbers, without queueing behind each other.

Keep the unique index on code anyway. If a bug ever slips through again, the database refuses the duplicate instead of quietly sending visitors to the wrong page.

What it costs

A sequence never goes backwards, even when a transaction rolls back, so some numbers are skipped. For short codes that is fine: nobody needs them to be gapless.

Interviewers also listen for: many servers

One sequence is still one counter. At higher write rates, create it with INCREMENT BY 1000 so each call reserves a block of 1,000 numbers that a server hands out from memory, as in the previous step.

Check yourself

1Why do the tests pass while production breaks?Show answerHide
Tests usually send one request at a time, so the read and the write never overlap. Production sends many at once, and the gap between them is where two requests read the same number.
2Why doesn't a mutex in the API fix it?Show answerHide
It only blocks requests inside the same process. Two servers have two separate mutexes, so their requests still overlap.
3With a unique index on code, what happens instead?Show answerHide
The second insert is rejected with a duplicate-key error. No visitor goes to the wrong page, but that request fails. Better, still not fixed.

The code

GitHub

create-link.bug.ts

import type { Pool } from "pg";
import { toBase62 } from "./base62";

// Read, then write: two requests can both read the same n.
export async function createLink(db: Pool, longUrl: string) {
  const { rows } = await db.query(
    "SELECT value FROM counters WHERE name = 'links'",
  );
  const n = BigInt(rows[0].value);
  await db.query(
    "UPDATE counters SET value = $1 WHERE name = 'links'",
    [String(n + 1n)],
  );

  const code = toBase62(n);
  await db.query(
    "INSERT INTO links (code, target) VALUES ($1, $2)",
    [code, longUrl],
  );
  return code;
}

Example code. The tested version, with a proof test against real Postgres, lands in the repo.

Star the repo for the runnable version

Each trap in this world ships with the bug, the fix and a proof test that fires concurrent requests at a real database.

Star the repo See the folder

Watch the 60-second version

Open on YouTube Open on Instagram

Remember

If the database does the read and the write in one step, two requests can't get the same number. If your code does them, they can.

NextThe stale redirectThe cache keeps sending visitors to a destination the owner already changed.