Design a URL Shortener (Bitly)

Writes:
  100M / day ÷ 86,400 s ≈ 1,160 writes/sec  (average)
  Peak ≈ 3× average ≈ 3,500 writes/sec      (end-of-day traffic bursts)

Reads (10:1 ratio):
  1B / day ÷ 86,400 s ≈ 11,600 reads/sec    (average)
  Peak ≈ 3× average ≈ 35,000 reads/sec      (viral link can spike 10×+)

Implication:
  → Read path is 10× the write path. Every design choice must favor reads.
  → Peak bursts are 3–10×. Provision for peak, not average.

Per-row estimate (relational row):
  short_code       : 8 bytes   (7 base62 chars + null)
  long_url         : 200 bytes (average; max 2KB cap)
  user_id          : 8 bytes
  created_at       : 8 bytes
  expires_at       : 8 bytes
  ─────────────────────────────
  Raw row          ≈ 230 bytes
  With indexes + overhead ≈ 500 bytes/row

Daily growth:
  100M rows/day × 500 B ≈ 50 GB/day
  → ~18 TB / year
  → ~90 TB over 5 years (without compression, without deletion)

Implication:
  → A single beefy Postgres box holds it for a year. Shard by year 2.
  → Compress long_url with zstd → ~60% saving. Enable TTL-based archival.

Read path (redirect):
  Payload: ~300 bytes (HTTP 301 headers + body + cookies)
  11,600 reads/s × 300 B ≈ 3.5 MB/s  (avg)
  Peak ≈ 35 MB/s ≈ 280 Mbps

Write path (create):
  Payload: ~500 bytes (JSON request + response)
  1,160 writes/s × 500 B ≈ 580 KB/s

Implication:
  → Well within a single NIC. Not a bottleneck.
  → Egress cost is the real concern at cloud scale (CDN reduces this).

80/20 rule: 80% of reads hit 20% of URLs.

Hot working set:
  20% × 100M new/day × ~30 days typical lifetime ≈ 600M hot codes

Memory per entry:
  key (short_code)   : 8 B
  value (long_url)   : 200 B
  Redis overhead     : ~80 B (hash table, pointers, TTL)
  ─────────────────────────
  ≈ 290 B per entry

Total cache:
  600M × 290 B ≈ 175 GB

Implication:
  → Single Redis box can't hold it. Shard by hash(short_code) across ~6 nodes
    of 32 GB each, or use Redis Cluster.
  → In practice, cache only top-N by recent access. 10–20 GB covers 95%+
    of the hit rate.

Base62 = [0-9] + [a-z] + [A-Z] = 62 characters

Combinations:
  6 chars → 62⁶  ≈ 56.8 B     (56 billion)
  7 chars → 62⁷  ≈ 3.5 T      (3.5 trillion) ← sweet spot
  8 chars → 62⁸  ≈ 218 T

At 100M writes/day = 36.5B/year:
  6 chars runs out in ~1.5 years
  7 chars gives us ~95 years of headroom
  → Use 7 characters. It's the industry default (bit.ly, t.co, youtu.be).

POST /api/v1/urls HTTP/1.1
Host: api.short.ly
Authorization: Bearer <jwt>
Content-Type: application/json
Idempotency-Key: 8f4b3c-... (optional, for retry safety)

{
  "long_url": "https://example.com/very/long/path?utm=campaign",
  "custom_alias": "launch-2026",   // optional
  "expires_at": "2026-12-31T23:59:59Z",  // optional, ISO 8601
  "metadata": { "campaign": "q2" }  // optional, opaque
}

--- 201 Created ---
{
  "short_code": "launch-2026",
  "short_url": "https://short.ly/launch-2026",
  "long_url":  "https://example.com/very/long/path?utm=campaign",
  "created_at": "2026-05-11T09:12:00Z",
  "expires_at": "2026-12-31T23:59:59Z"
}

--- 409 Conflict ---  (custom alias already taken)
{ "error": "ALIAS_TAKEN", "message": "launch-2026 is already in use" }

--- 400 Bad Request ---  (invalid URL, reserved alias, URL too long)
{ "error": "INVALID_URL", "message": "long_url must be http(s) and ≤ 2048 chars" }

GET /launch-2026 HTTP/1.1
Host: short.ly

--- 301 Moved Permanently ---      (or 302, see trade-offs)
Location: https://example.com/very/long/path?utm=campaign
Cache-Control: public, max-age=300
X-Shortener-Code: launch-2026

--- 404 Not Found ---              (code doesn't exist)
--- 410 Gone ---                   (code existed, deleted)
--- 403 Forbidden ---              (code expired)

CREATE TABLE urls (
  short_code     VARCHAR(10)  PRIMARY KEY,        -- 7 chars normally; 10 allows custom aliases
  long_url       TEXT         NOT NULL,           -- up to 2048 chars (enforce at app layer)
  user_id        UUID         REFERENCES users,   -- nullable for anonymous creates
  created_at     TIMESTAMPTZ  NOT NULL DEFAULT now(),
  expires_at     TIMESTAMPTZ  NULL,               -- NULL = never expires
  is_custom      BOOLEAN      NOT NULL DEFAULT false,
  is_deleted     BOOLEAN      NOT NULL DEFAULT false,  -- soft delete for GDPR
  metadata       JSONB        NULL                -- campaign tags, etc.
);

-- Index for user's link list (secondary access pattern)
CREATE INDEX idx_urls_user_created ON urls (user_id, created_at DESC)
  WHERE is_deleted = false;

-- Index for the TTL cleanup job
CREATE INDEX idx_urls_expires ON urls (expires_at)
  WHERE expires_at IS NOT NULL AND is_deleted = false;

-- Single-row counter feeding the base62 encoder.
-- Lives in a tiny dedicated DB or is replaced by Redis INCR in prod.
CREATE TABLE id_counter (
  id       INT PRIMARY KEY DEFAULT 1,
  next_id  BIGINT NOT NULL,
  CHECK (id = 1)  -- enforce singleton
);

-- Each app server batch-reserves 1000 IDs at a time → rarely hit.
-- UPDATE id_counter SET next_id = next_id + 1000 RETURNING next_id - 1000;

Stored in ClickHouse / BigQuery, not Postgres.

click_events (
  event_id      UUID,
  short_code    String,
  clicked_at    DateTime64,
  ip_hash       FixedString(32),   -- salted hash, not raw IP (GDPR)
  country_code  FixedString(2),
  user_agent    String,
  referrer      String
)
PARTITION BY toYYYYMM(clicked_at)
ORDER BY (short_code, clicked_at)

→ Columnar storage → aggregations (clicks per code per day) are fast.
→ Writes arrive via Kafka → Flink pipeline, not synchronously.

Total budget: 10ms p99

0.0ms  ─  TLS (keep-alive, already established)
0.2ms  ─  API Gateway auth check (cached JWKS)
0.3ms  ─  Rate limit check (Redis INCR, pipelined)
0.5ms  ─  Bloom filter check (in-process, nanoseconds)
1.0ms  ─  Redis GET short_code
           ├─ 95% hit → go to response
           └─ 5% miss → +5ms DB read → cache set
3.0ms  ─  Kafka produce (async, non-blocking — doesn't add to response time)
3.5ms  ─  Return 301 with Location header
           ───────────────────────────────
           Total on cache hit:  ~3–4ms  ✅
           Total on cache miss: ~7–8ms  ✅ (still under 10ms)

function shortenViaHash(longUrl: string): string {
  const hash = md5(longUrl);                    // 128-bit hash
  const encoded = toBase62(hash);               // full base62 string
  let candidate = encoded.slice(0, 7);          // take first 7 chars

  // Collision resolution loop — O(n) in worst case
  while (await db.exists(candidate)) {
    candidate = toBase62(md5(longUrl + counter++)).slice(0, 7);
  }
  return candidate;
}

// Problem: at 36B codes, ~1% of writes collide → 2 DB ops per create

function shortenViaRandom(): string {
  let candidate: string;
  let attempts = 0;

  do {
    candidate = generateRandomBase62(7);  // e.g. "xK9mQ2p"
    attempts++;
  } while (await db.exists(candidate) && attempts < MAX_RETRIES);

  if (attempts >= MAX_RETRIES) throw new Error("EXHAUSTED_RETRIES");
  return candidate;
}

// Unguessable ✅ but collision-check on every write ❌

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

function toBase62(num: number): string {
  if (num === 0) return "0000000";
  let encoded = "";
  while (num > 0) {
    encoded = ALPHABET[num % 62] + encoded;
    num = Math.floor(num / 62);
  }
  return encoded.padStart(7, "0");  // always 7 chars for consistency
}

// Examples:
toBase62(3_141_592);       // → "000DXYh"  (small number, padded)
toBase62(1_000_000_000);   // → "015ftgG"  (1 billion)
toBase62(3_521_614_606_207); // → "zzzzzzz" (max 7-char value)

// A 3-round Feistel network over the range [0, 62^7)
// Guarantees: bijective (no collisions), O(1), reversible
function shuffle(id: number): number {
  const MAX = 62 ** 7;  // 3,521,614,606,208
  let left = Math.floor(id / Math.sqrt(MAX));
  let right = id % Math.floor(Math.sqrt(MAX));

  for (let round = 0; round < 3; round++) {
    const temp = right;
    right = left ^ roundFunction(right, ROUND_KEYS[round]);
    left = temp;
  }
  return left * Math.floor(Math.sqrt(MAX)) + right;
}

// Usage in the create path:
const rawId = await idService.next();       // e.g. 3,141,592
const shuffled = shuffle(rawId);            // e.g. 2,109,847,331
const shortCode = toBase62(shuffled);       // e.g. "k9Qm2Xp" — looks random

if request.custom_alias:
    validate_alias(alias)           → 400 if reserved/invalid
    INSERT ... ON CONFLICT DO NOTHING
    if rowcount == 0                → 409 ALIAS_TAKEN
    return success

else:  (auto-generated)
    id = ID_SERVICE.next()          → from local pool (batched)
    short_code = toBase62(shuffle(id))
    INSERT ...                      → no conflict check needed (counter guarantees uniqueness)
    return success

async function createShortUrl(req: CreateRequest): Promise<CreateResponse> {
  // 1. Validation
  validateUrl(req.long_url);                         // throws on bad scheme/length
  checkSSRFBlocklist(req.long_url);                  // block internal ranges

  // 2. Idempotency
  if (req.idempotency_key) {
    const cached = await idempotencyStore.get(req.idempotency_key);
    if (cached) return cached;                        // network retry — return same response
  }

  // 3. Short code
  let short_code: string;
  if (req.custom_alias) {
    validateAlias(req.custom_alias);                  // reserved words, regex
    short_code = req.custom_alias;
  } else {
    const id = await idService.next();                // batched from pool
    short_code = toBase62(shuffle(id));               // Feistel to break predictability
  }

  // 4. Conditional insert — serves both paths
  const result = await db.query(`
    INSERT INTO urls (short_code, long_url, user_id, expires_at, is_custom)
    VALUES ($1, $2, $3, $4, $5)
    ON CONFLICT (short_code) DO NOTHING
    RETURNING short_code, created_at
  `, [short_code, req.long_url, req.user_id, req.expires_at, !!req.custom_alias]);

  if (result.rowCount === 0) {
    if (req.custom_alias) throw new AliasTakenError();
    throw new InternalError("counter produced a duplicate — should not happen");
  }

  // 5. Populate cache (write-through)
  const ttl = req.expires_at ? secondsUntil(req.expires_at) : DEFAULT_TTL;
  await cache.set(short_code, req.long_url, ttl);

  // 6. Build response, persist idempotency entry
  const response = buildResponse(short_code, result.rows[0], req);
  if (req.idempotency_key) {
    await idempotencyStore.set(req.idempotency_key, response, 86_400);
  }
  return response;
}

async function handleRedirect(short_code: string, req: Request): Promise<Response> {
  // 1. Bloom filter pre-check — rejects bogus codes without DB hit
  if (!bloom.mightContain(short_code)) {
    metrics.bloomReject.inc();
    return new Response(null, { status: 404 });
  }

  // 2. Cache lookup
  let long_url = await cache.get(short_code);

  if (long_url === null) {
    // 3. DB fallback with request coalescing
    long_url = await singleflight.do(short_code, async () => {
      const row = await readReplica.query(`
        SELECT long_url, expires_at, is_deleted
        FROM urls WHERE short_code = $1
      `, [short_code]);

      if (!row) return null;
      if (row.is_deleted) return { status: 410 };
      if (row.expires_at && row.expires_at < Date.now()) return { status: 403 };

      // Populate cache on hit
      await cache.set(short_code, row.long_url, CACHE_TTL);
      return row.long_url;
    });

    if (!long_url) return new Response(null, { status: 404 });
  }

  // 4. Emit click event — non-blocking, fire-and-forget
  kafkaProducer.produce("click-events", short_code, {
    clicked_at: Date.now(),
    ip_hash: hashIp(req.ip),
    country: req.geo?.country,
    user_agent: req.headers["user-agent"],
    referrer: req.headers["referer"],
  });

  // 5. Respond with 301 + cache headers
  return new Response(null, {
    status: 301,
    headers: {
      Location: long_url,
      "Cache-Control": "public, max-age=300",
      "X-Shortener-Code": short_code,
    },
  });
}

1. UPDATE urls SET is_deleted = true WHERE short_code = ? AND user_id = ?
2. DEL short_code   (evict from Redis)
3. CDN purge API:  POST /purge { path: "/launch-2026" }
4. Update bloom filter tombstone set (bloom itself can't remove; use a
   secondary "recently deleted" set checked on bloom-pass)

Gotcha:
  Browsers with 301 in their cache will NOT re-check until max-age expires.
  This is fundamental to 301 — can't be invalidated remotely.
  → For deletable links, use 302 with a short max-age instead of 301.

Input stream:  click-events (Kafka topic, ~11.6K events/sec)

Job 1 — Per-code rolling count (1-minute tumbling window)
  keyBy(short_code)
    .window(TumblingEventTimeWindows.of(Time.minutes(1)))
    .aggregate(new CountAggregator())
    .addSink(redisSink)   // → Redis key: counts:{short_code}:{minute}

Job 2 — Geo breakdown (5-minute window)
  keyBy(short_code, country_code)
    .window(TumblingEventTimeWindows.of(Time.minutes(5)))
    .aggregate(new CountAggregator())
    .addSink(clickhouseSink)

Job 3 — Raw event archive
  .addSink(clickhouseSink)   // raw events → ClickHouse, partitioned by day

Watermark: event_time - 30s (allows some network reorder)
Checkpoint: every 30s to S3 (exactly-once semantics on restart)

Redirect Service → Kafka:
  acks=1, buffered producer, linger.ms=10
  → at-least-once (producer retries on failure)
  → events may duplicate if app server crashes between produce and ack

Kafka → Flink:
  consumer offsets committed after checkpoint
  → exactly-once within Flink pipeline (via two-phase commit)

Flink → ClickHouse:
  idempotent insert with (event_id, event_time) dedup key
  → at-least-once writes, deduplicated on read

End-to-end: effectively exactly-once for analytics use cases.
At-most-once is NEVER appropriate here — undercount is unacceptable.

shard_id = hash(short_code) % N_SHARDS

Routing happens at the app layer (no sharding proxy needed at this scale).

Trade-offs:
  ✅ Point lookup is single-shard → O(1) routing
  ✅ Writes distribute evenly — no hot shard from sequential IDs
     (the Feistel shuffle on the counter was already essential)
  ❌ "All URLs for user X" becomes scatter-gather — not critical for this workload
  ❌ Resharding is expensive — use consistent hashing to minimize movement

When to reshard:
  - Storage per shard exceeds ~1TB (Postgres starts paginating painfully)
  - Writes per shard exceed ~2K/s sustained
  - Add shards in powers of 2 — halves the data-movement cost

Layer 1 — 301 + Cache-Control
  → Browsers skip us entirely after first hit. Largest lever.

Layer 2 — CDN edge cache
  → PoPs absorb ~99% of what's left. ~10K QPS reaches origin.

Layer 3 — Request coalescing at Redis
  → If 1000 concurrent misses for the same code hit the same app server,
    only one DB read fires. Singleflight pattern.

Layer 4 — Local in-process cache (short TTL)
  → Hot codes get pinned to a 10-second local LRU on the redirect service.
    Eliminates Redis round trip on the hottest 1000 codes.

Layer 5 — Throttle analytics for viral codes
  → If clicks/sec for a code > 10K, sample analytics events (1 in 10).
    Click count is estimated via counter math. Dashboard accuracy within 1%.

Create endpoint:
  create:ip:{ip}              → 60 / hour  (anonymous)
  create:user:{user_id}       → 1000 / day (authenticated)
  create:domain:{tld}         → 500 / hour (per target domain — spam cap)

Redirect endpoint:
  redirect:ip:{ip}            → 1000 / min (abuse: scraping, bots)
  redirect:code:{short_code}  → no limit   (viral traffic is legit)

Implementation: Redis sorted-set sliding window or token bucket.
Limits are soft — return 429 + Retry-After.

async function handleRedirect(short_code: string) {
  const { long_url, is_quarantined } = await resolve(short_code);

  if (is_quarantined) {
    // Don't auto-redirect — show an interstitial warning page
    return renderWarningPage(long_url);
  }

  if (badUrlCache.has(canonicalHost(long_url))) {
    return renderBlockedPage();
  }

  return redirect301(long_url);
}

function validateLongUrl(url: string) {
  const parsed = new URL(url);

  // Scheme: only http / https
  if (!["http:", "https:"].includes(parsed.protocol)) throw new Error("BAD_SCHEME");

  // No IP literals — force hostname
  if (isIPAddress(parsed.hostname)) throw new Error("NO_IP_LITERALS");

  // Resolve DNS and check — attacker can point a domain at 127.0.0.1
  const addresses = await dnsResolve(parsed.hostname);
  for (const ip of addresses) {
    if (isPrivate(ip) || isLoopback(ip) || isLinkLocal(ip)) {
      throw new Error("PRIVATE_IP_RESOLVED");
    }
  }

  // Length cap (2048 is the HTTP practical limit)
  if (url.length > 2048) throw new Error("TOO_LONG");
}

Never allow as custom aliases:
  api, admin, login, signup, logout, auth, oauth
  static, assets, favicon.ico, robots.txt, sitemap.xml
  dashboard, settings, billing, pricing, help, support
  Any existing route your API Gateway serves

Reserved for product:
  Top 10K brand names from trademark feed (coca-cola, tesla, etc.)
  ccTLDs (us, uk, jp) — reserved for future localization

Enforcement: single regex + allow-list file, checked before the conflict check.
Return 403 with a specific error code so UX can explain.

• URLs created per minute (growth + abuse detection)
• Unique creating users (baseline + anomaly)
• Cache hit rate (should stay > 90%)
• Bloom filter false-positive rate (tune when it drifts > 1%)
• Analytics pipeline lag (Kafka consumer offset vs head)
• URLs quarantined per hour (abuse pipeline health)
• Top 10 short codes by click rate (detect viral → pre-warm caches)
• Creates by authenticated vs anonymous (spam-campaign signal)

Trace: redirect.handle (total 4.2ms)
├─ gateway.auth                            0.2ms
├─ gateway.ratelimit                       0.3ms
├─ redirect.bloom_check                    0.02ms
├─ redirect.cache_get                      0.9ms  [HIT]
├─ redirect.emit_click_event (async)       0.01ms (non-blocking)
└─ redirect.respond                        0.1ms

Spans on miss path:
├─ redirect.singleflight_wait              1.2ms
├─ redirect.db_read                        5.1ms
├─ redirect.cache_set                      0.8ms

Sampling: 1% of all requests + 100% of slow (>50ms) + 100% of errors.