URL Shortener

1. Problem and requirements

Users submit a long URL and receive a short link such as https://mkm.li/aZ3x9Qp. Anyone opening the short link is redirected to the original destination.

Functional requirements

Non-functional requirements

Out of scope

Link editing (changing the destination of an existing code), QR code generation and team workspaces. Destination editing is deliberately excluded because it interacts badly with permanent (301) redirects cached by browsers.

301 or 302?

Decision: 302 with Cache-Control: private, max-age=0 by default, because F3, F5 and N4 all require every click to reach us. Owners can opt a link into 301 when they want maximum speed and accept losing analytics and fast disabling for it.

2. Capacity estimation

Assumptions: 10 million new links a month, 100 million redirects a day, peak traffic 10× the average, an average stored mapping of 500 bytes, and links kept for 5 years.

These are estimates from stated assumptions, not measurements. Real capacity also depends on burstiness, cache hit rate and replication.

What this says: writes are trivial. The work is the read path at about 12,000 lookups a second at peak, plus a click-event stream of 100 million a day that must not slow it down. One PostgreSQL primary with a replica can serve the misses, provided the cache absorbs most reads.

3. Architecture and APIs

High-level architecture

flowchart LR
  U[Browser] --> CDN[Edge / CDN]
  CDN --> LB[Load balancer]
  LB --> R[Redirect service]
  LB --> C[Link API]
  R --> RC[(Redis cache)]
  R -->|miss| RR[(PostgreSQL replica)]
  C --> PG[(PostgreSQL primary)]
  C --> RC
  C --> SB[Safe Browsing check]
  PG -. replication .-> RR
  R -->|click event, async| K[[Kafka: clicks]]
  K --> AG[Analytics aggregator]
  AG --> AS[(Analytics store)]

Redirect and creation are separate deployments: they have different traffic (1,000× apart), different SLOs and different failure tolerance. A spike in creations, or a bad deploy of the Link API, must not affect redirects.

API contracts

POST /api/links
Authorization: Bearer <token>
Idempotency-Key: 1b9e…

{ "url": "https://example.com/very/long/path?utm=x", "alias": "launch-2026", "expiresAt": "2027-01-01T00:00:00Z" }

201 Created
{ "code": "launch-2026", "shortUrl": "https://mkm.li/launch-2026",
  "url": "https://example.com/very/long/path?utm=x", "expiresAt": "2027-01-01T00:00:00Z", "status": "ACTIVE" }

410 Gone (not 404) for expired or disabled links tells clients the code existed and will not come back, so it is never reused for a different destination.

Deployment

flowchart LR
  subgraph Edge
    CDN[CDN: static 404 page, TLS, DDoS protection]
  end
  subgraph App [Kubernetes or VMs]
    R1[redirect x N, autoscaled on CPU]
    C1[link-api x 2]
    A1[aggregator x 2]
  end
  subgraph Data
    RD[(Redis primary + replica)]
    P[(PostgreSQL primary)]
    PR[(PostgreSQL read replica)]
    KF[[Kafka, 3 brokers]]
  end
  CDN --> R1
  CDN --> C1
  R1 --> RD
  R1 --> PR
  C1 --> P
  P -.-> PR
  R1 --> KF
  KF --> A1

4. Internal design and workflows

Class diagram

classDiagram
  class UrlMapping {
    +code
    +destination
    +ownerId
    +createdAt
    +expiresAt
    +status LinkStatus
    +isRedirectable(now) bool
  }
  class UrlShortenerService {
    +create(cmd) UrlMapping
    +disable(code, owner)
    +delete(code, owner)
  }
  class RedirectService {
    +resolve(code) Resolution
  }
  class IdGenerator {
    <<interface>>
    +next() long
  }
  class BlockIdGenerator {
    -current long
    -end long
    +next() long
  }
  class Base62Encoder {
    +encode(long) String
    +decode(String) long
  }
  class UrlRepository {
    <<interface>>
    +insert(mapping)
    +findByCode(code) Optional~UrlMapping~
  }
  class LinkCache {
    +get(code) CacheEntry
    +put(code, entry, ttl)
    +putMissing(code)
    +evict(code)
  }
  class DestinationPolicy {
    +check(url) Verdict
  }
  class ClickPublisher {
    +publish(ClickEvent)
  }
  UrlShortenerService --> IdGenerator
  UrlShortenerService --> Base62Encoder
  UrlShortenerService --> UrlRepository
  UrlShortenerService --> DestinationPolicy
  UrlShortenerService --> LinkCache
  RedirectService --> LinkCache
  RedirectService --> UrlRepository
  RedirectService --> ClickPublisher
  IdGenerator <|.. BlockIdGenerator

Identifier generation: the decision worth explaining

How the chosen approach works:

1. Each Link API instance reserves a block of 10,000 IDs at a time with one atomic statement: UPDATE id_block SET next = next + 10000 RETURNING next - 10000.
2. It hands out IDs from the block in memory. No database round trip per link, no collisions across instances.
3. Before encoding, the ID goes through a reversible bit permutation (a small Feistel network over the ID space with a secret key). Consecutive IDs become unrelated-looking codes, so aZ3x9Qp reveals nothing about aZ3x9Qq.
4. The result is Base62-encoded and left-padded to 7 characters.

Encoding is not encryption. The permutation makes codes non-sequential, which stops casual enumeration. Links that must stay private should not rely on an unguessable URL at all: they need authentication.

static final char[] ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toCharArray();

String encode(long id) {                 // id already permuted, 0 <= id < 62^7
    char[] out = new char[7];
    for (int i = 6; i >= 0; i--) { out[i] = ALPHABET[(int) (id % 62)]; id /= 62; }
    return new String(out);
}

Custom aliases go through the same table. The primary key on code makes a taken alias fail with a constraint violation, which becomes 409 ALIAS_TAKEN. Aliases are restricted to [A-Za-z0-9-]{4,32}, and a reserved-word list blocks api, admin, login and lookalikes.

Data model and indexes

erDiagram
  LINK ||--o{ CLICK_DAILY : "aggregated into"
  LINK {
    text code PK
    text destination
    uuid owner_id
    timestamptz created_at
    timestamptz expires_at
    text status
    bool permanent
  }
  CLICK_DAILY {
    text code PK
    date day PK
    bigint clicks
    jsonb top_referrers
    jsonb top_countries
  }
  ID_BLOCK {
    text name PK
    bigint next
  }

CREATE TABLE link (
  code        text PRIMARY KEY,                         -- unique code and alias space
  destination text NOT NULL CHECK (length(destination) <= 2048),
  owner_id    uuid NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz,
  status      text NOT NULL DEFAULT 'ACTIVE',           -- ACTIVE | DISABLED | DELETED
  permanent   boolean NOT NULL DEFAULT false
);
CREATE INDEX link_by_owner  ON link (owner_id, created_at DESC);            -- "my links"
CREATE INDEX link_expiring  ON link (expires_at) WHERE status = 'ACTIVE';   -- expiry sweeper

Deleted links keep a tombstone row (status = 'DELETED', destination cleared) so a code is never reissued to someone else.

Redirect sequence (cache-aside with negative caching)

sequenceDiagram
  participant B as Browser
  participant R as RedirectService
  participant C as Redis
  participant D as PG replica
  participant K as Kafka
  B->>R: GET /aZ3x9Qp
  R->>C: GET link:aZ3x9Qp
  alt cache hit (link)
    C-->>R: destination, status, expiresAt
  else cache hit (missing marker)
    C-->>R: MISSING
    R-->>B: 404
  else cache miss
    R->>D: SELECT ... WHERE code = ?
    alt found
      D-->>R: row
      R->>C: SET link:code (TTL = min(1 h, expiresAt - now))
    else not found
      R->>C: SET link:code MISSING (TTL 60 s)
      R-->>B: 404
    end
  end
  R->>R: isRedirectable(now)? else 410
  R--)K: publish ClickEvent (fire and forget, buffered)
  R-->>B: 302 Location: destination

Create sequence

sequenceDiagram
  participant U as User
  participant A as Link API
  participant P as DestinationPolicy
  participant D as PG primary
  participant C as Redis
  U->>A: POST /api/links (url, alias?, Idempotency-Key)
  A->>A: validate URL (scheme http/https, length, not our own domain)
  A->>P: check(url): Safe Browsing + blocklist
  P-->>A: SAFE
  A->>A: code = alias or Base62(permute(nextId()))
  A->>D: INSERT link (PK on code)
  alt alias taken
    D-->>A: unique violation
    A-->>U: 409 ALIAS_TAKEN
  else inserted
    A->>C: DEL link:code (clears any MISSING marker)
    A-->>U: 201
  end

The DEL after insert matters: if someone requested the alias before it existed, a MISSING marker is cached for 60 seconds, and deleting it makes the new link work immediately.

Link states

stateDiagram-v2
  [*] --> ACTIVE: created
  ACTIVE --> DISABLED: owner disables
  DISABLED --> ACTIVE: owner re-enables
  ACTIVE --> EXPIRED: expires_at passed
  ACTIVE --> DELETED: owner deletes
  DISABLED --> DELETED: owner deletes
  EXPIRED --> DELETED: owner deletes
  DELETED --> [*]

EXPIRED is computed at read time from expires_at rather than written by a job, so an expiry is exact even if the sweeper runs late. The sweeper only evicts cache entries and archives rows.

Data ownership and transaction boundaries

• The link table is owned by the Link API. The redirect service only reads it.
• Creation is a single-row insert. No multi-step transaction is needed.
• Click counts are owned by the aggregator and are never written on the redirect path.

5. Failure modes and consistency

Caching and invalidation, summarised

• Pattern: cache-aside. The redirect service reads Redis, falls back to the database and populates the cache.
• TTL: one hour, or the time until expiry if sooner, with ±10% jitter.
• Negative entries: 60 seconds, deleted on create.
• Invalidation: explicit DEL on disable, delete and expiry change. The TTL is the safety net if an eviction is lost.
• Consistency: a disabled link can redirect for at most the time between the write and the eviction (normally milliseconds), or one TTL if the eviction fails.

Security and abuse

• Creation needs an account or an API key; anonymous creation (if offered) is limited per IP and requires a challenge.
• Destinations are checked against Google Safe Browsing and an internal blocklist at creation and re-checked daily.
• Only http and https destinations are allowed; javascript:, data: and file: are rejected.
• Rate limits: creation per account and per IP (see 03 · Rate Limiter), redirect misses per IP.
• Owners can only manage their own links; GET /api/links/{code}/stats is owner-only.

6. Scaling evolution

7. Operations and validation

Metrics and SLOs

Test plan (to build)

Benchmark (to measure)

A k6 test drives redirects with a Zipf-distributed code set (a few codes very hot, a long tail cold) at 1×, 5× and 10× the average rate. To be recorded: p50, p95 and p99 for hits and misses, the cache hit ratio, and database CPU. A second run with Redis stopped records the degraded mode. No results are claimed until these tests have been run.

8. Decision records

DR-1: Pre-allocated ID blocks with a permutation

• Decision: reserve ID blocks of 10,000 per instance, permute, Base62-encode to 7 characters.
• Rejected: random tokens (a uniqueness check on every insert, rising collision rate); URL hashing (cannot give two owners different expiries for the same URL); Snowflake IDs (11-character codes for a capability we do not need yet).
• Consequence: no collisions, no round trip per create, short and non-sequential codes.

DR-2: 302 by default

• Decision: 302 with no caching; 301 is opt-in per link.
• Why: disable, expiry and analytics requirements all need every click to reach the service. The cost is higher redirect traffic, which the cache absorbs.

DR-3: PostgreSQL before a NoSQL key-value store

• Decision: keep links in PostgreSQL until stage 5.
• Why: 600 GB over five years fits one well-provisioned primary; we get constraints for aliases, transactions and simple operations. A key-value store (DynamoDB, Cassandra) becomes attractive only when one primary cannot absorb the writes, which at 4 writes/s is far away.

9. Limitations, and implemented versus proposed

Known limitations

• Click counts are approximate by design.
• A 301 link that is later disabled keeps redirecting in browsers that cached it.
• Re-scanning destinations daily leaves a window in which a newly malicious site is still served.

Status