mufassall

Cheat sheet · Whole systems

Design a URL shortener

13 min · Intermediate · mufassall.dtwin.uz/en/l/design-url-shortener/

← Open the lesson

The problem

A long link goes in, a short code comes out, and every click is a redirect. We build the whole service step by step: estimates, short codes, the redirect, cache, replicas, click analytics, aliases and expiry.

What you learn

  • How to size a read-heavy service from a few numbers
  • Why a counter plus base62 beats hashing the URL
  • 301 or 302: what you give up with each
  • Where cache, replicas and a queue each take load off the database
Final scene
45%35%15%30%20%40%20%

Diagram as code

The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.

Mermaid: flowchart

flowchart LR
  n_user(["Browser"])
  n_api["Link API"]
  n_db[("Links DB (primary)")]
  n_cache{{"Link cache"}}
  n_replica[("Read replica")]
  n_queue[["Click queue"]]
  n_worker("Click worker")
  n_stats[("Stats DB")]
  n_user --> n_api
  n_api --> n_db
  n_user --> n_api
  n_api -.-> n_user
  n_api --> n_cache
  n_api --> n_replica
  n_db --> n_replica
  n_api --> n_queue
  n_queue --> n_worker
  n_worker --> n_stats
  n_worker --> n_db

Mermaid: request sequence

sequenceDiagram
  participant n_user as Browser
  participant n_api as Link API
  participant n_db as Links DB (primary)
  participant n_cache as Link cache
  participant n_replica as Read replica
  participant n_queue as Click queue
  Note over n_user,n_api: What we are building, and how big
  n_user->>n_api: POST /api/links HTTP/1.1
  n_api-->>n_user: HTTP/1.1 201 Created
  Note over n_api,n_db: Hashing the URL collides
  n_api->>n_db: INSERT INTO links (code, long_url)
  n_db-->>n_api: ERROR: duplicate key value
  Note over n_api,n_db: A counter plus base62: no collisions by construction
  n_api->>n_db: UPDATE id_blocks SET next_id = next_id + 1000
  n_db-->>n_api: next_id = 125001000
  Note over n_user,n_api: The redirect: 302, not 301
  n_user->>n_api: GET /8sujL HTTP/1.1
  n_api-->>n_user: HTTP/1.1 302 Found
  Note over n_api,n_db: Every click is a database read
  n_api->>n_db: SELECT long_url, expires_at FROM links
  n_db-->>n_api: (1 row)
  Note over n_api,n_cache: A cache in front of the database
  n_api->>n_cache: GET link:8sujL
  n_cache-->>n_api: #34;https://shop.example.com/sale/42#34;
  Note over n_db,n_replica: Cache misses go to a read replica
  n_db->>n_replica: SELECT now() - pg_last_xact_replay_timestamp()
  n_replica-->>n_db: lag = 00:00:00.180
  Note over n_api,n_db: Counting clicks in the links table
  n_api->>n_db: UPDATE links SET clicks = clicks + 1
  n_db-->>n_api: UPDATE 1
  Note over n_api,n_queue: Clicks go to a queue, a worker counts them
  n_api->>n_queue: PRODUCE clicks key=8sujL partition=7
  n_queue-->>n_api: ack offset=88341201
  Note over n_api,n_db: Custom aliases: one namespace, two sources
  n_api->>n_db: INSERT INTO links (code, long_url, expires_at)
  n_db-->>n_api: (0 rows)
  Note over n_api,n_cache: Links that expire
  n_api->>n_cache: SET link:spring-sale https://shop.example.com/s EX 3600
  n_cache-->>n_api: OK

D2

direction: right

n_user: "Browser" {
  shape: rectangle
}
n_api: "Link API" {
  shape: rectangle
}
n_db: "Links DB (primary)" {
  shape: cylinder
}
n_cache: "Link cache" {
  shape: hexagon
}
n_replica: "Read replica" {
  shape: cylinder
}
n_queue: "Click queue" {
  shape: queue
}
n_worker: "Click worker" {
  shape: rectangle
  style.multiple: true
}
n_stats: "Stats DB" {
  shape: cylinder
}

n_user -> n_api
n_api -> n_db
n_user -> n_api
n_api -> n_user {
  style.stroke-dash: 3
}
n_api -> n_cache
n_api -> n_replica
n_db -> n_replica
n_api -> n_queue
n_queue -> n_worker
n_worker -> n_stats
n_worker -> n_db

PlantUML: request sequence

@startuml
participant "Browser" as n_user
participant "Link API" as n_api
database "Links DB (primary)" as n_db
collections "Link cache" as n_cache
database "Read replica" as n_replica
queue "Click queue" as n_queue
note over n_user, n_api : What we are building, and how big
n_user -> n_api : POST /api/links HTTP/1.1
n_api --> n_user : HTTP/1.1 201 Created
note over n_api, n_db : Hashing the URL collides
n_api -> n_db : INSERT INTO links (code, long_url)
n_db --> n_api : ERROR: duplicate key value
note over n_api, n_db : A counter plus base62: no collisions by construction
n_api -> n_db : UPDATE id_blocks SET next_id = next_id + 1000
n_db --> n_api : next_id = 125001000
note over n_user, n_api : The redirect: 302, not 301
n_user -> n_api : GET /8sujL HTTP/1.1
n_api --> n_user : HTTP/1.1 302 Found
note over n_api, n_db : Every click is a database read
n_api -> n_db : SELECT long_url, expires_at FROM links
n_db --> n_api : (1 row)
note over n_api, n_cache : A cache in front of the database
n_api -> n_cache : GET link:8sujL
n_cache --> n_api : "https://shop.example.com/sale/42"
note over n_db, n_replica : Cache misses go to a read replica
n_db -> n_replica : SELECT now() - pg_last_xact_replay_timestamp()
n_replica --> n_db : lag = 00:00:00.180
note over n_api, n_db : Counting clicks in the links table
n_api -> n_db : UPDATE links SET clicks = clicks + 1
n_db --> n_api : UPDATE 1
note over n_api, n_queue : Clicks go to a queue, a worker counts them
n_api -> n_queue : PRODUCE clicks key=8sujL partition=7
n_queue --> n_api : ack offset=88341201
note over n_api, n_db : Custom aliases: one namespace, two sources
n_api -> n_db : INSERT INTO links (code, long_url, expires_at)
n_db --> n_api : (0 rows)
note over n_api, n_cache : Links that expire
n_api -> n_cache : SET link:spring-sale https://shop.example.com/s EX 3600
n_cache --> n_api : OK
@enduml

PlantUML: components

@startuml
left to right direction
agent "Browser" as n_user
component "Link API" as n_api
database "Links DB (primary)" as n_db
stack "Link cache" as n_cache
database "Read replica" as n_replica
queue "Click queue" as n_queue
collections "Click worker" as n_worker
database "Stats DB" as n_stats
n_user --> n_api
n_api --> n_db
n_user --> n_api
n_api ..> n_user
n_api --> n_cache
n_api --> n_replica
n_db --> n_replica
n_api --> n_queue
n_queue --> n_worker
n_worker --> n_stats
n_worker --> n_db
@enduml

Recap

The redirect path is the product: keep it short and keep the primary out of it.

1) Estimate first: 40 writes/s, 4 000 reads/s, 3 TB. 2) A counter in blocks plus base62 gives unique codes without retries. 3) 302 keeps every click visible. 4) Cache for hot links, replicas for misses, and a queue for click counting. 5) Aliases share the table but not the code shape; expiry caps the cache TTL.

Numbers: at the start and at the end

MetricStartEnd
Redirect p9930 ms12 ms
Reads on primary300/s20/s
Code collisions0/day0/day

Steps

  1. Case What we are building, and how big

    Two calls: POST /api/links turns a long URL into a short code, and GET /<code> redirects to it.

  2. Problem Hashing the URL collides

    First idea: take an MD5 of the long URL, base62-encode it and keep the first 7 characters.

  3. Fix A counter plus base62: no collisions by construction

    Give every link a unique number and encode it in base62: 125000417 becomes 8sujL.

  4. Case The redirect: 302, not 301

    A click arrives as GET /8sujL.

  5. Problem Every click is a database read

    Traffic reaches the 4 000 redirects/s from the estimate.

  6. Fix A cache in front of the database

    The API first asks the cache for link:<code>.

  7. Fix Cache misses go to a read replica

    The remaining misses move to a read replica that streams changes from the primary.

  8. Problem Counting clicks in the links table

    Marketing wants click counts.

  9. Fix Clicks go to a queue, a worker counts them

    The redirect now only publishes a small event and returns.

  10. Case Custom aliases: one namespace, two sources

    Users want readable links like /spring-sale.

  11. Fix Links that expire

    A link can carry expires_at.

  12. Recap Recap

    The redirect path is the product: keep it short and keep the primary out of it.

Terms

Base62 code
Give every link a unique number and encode it as a short string of letters and digits. Different numbers always give different codes, so there are no collisions as with hashing.