← System Design Simulator

URL Shortener System Design Interview Question

By Rahul Kumar · Senior Software Engineer · Updated · 7 components · 3 operations ·Source: Alex Xu, System Design Interview Vol 1, Chapter 8 (pages 119–131)

Problem: Design a URL shortener like TinyURL or bit.ly.

Overview

A URL shortener takes an arbitrary long URL like https://example.com/path?utm=x and emits a compact 7-character code such as bit.ly/3kP9xQa that redirects back to the original. It is the canonical read-heavy system — redirects outnumber creations roughly ten-to-one — and the service most interview candidates first encounter because it compresses nearly every distributed-systems concept into a small surface area: hashing, unique ID generation, caching, database sharding, rate limiting, HTTP semantics, and analytics fan-out. Real products in this space include Bitly, TinyURL, Rebrandly, Cuttly, Firebase Dynamic Links, Twitter's t.co, LinkedIn's lnkd.in, and Google's now-retired goo.gl. Companies use them to reclaim character budgets on SMS and Twitter, to attach click analytics to outbound marketing, and to gate redirects behind abuse checks. The interview version typically sizes for 100 million new links per day and 1 billion redirects per day, demanding sub-50ms p99 redirect latency — numbers large enough to force genuine design decisions but small enough to solve in 45 minutes.

URL Shortener — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive walkthrough for URL Shortener — animated architecture diagram, step-by-step flow with real payloads, component swap, and a discrete-event stress simulator.

Summary

A read-heavy service (about 10:1 read/write) that maps a short base62 code to a long URL and returns a 301/302 redirect. The book (Ch 8) settles on base62 conversion over hash+collision-check: a distributed unique ID generator (per Ch 7) hands out monotonic 64-bit IDs; each ID is base62-encoded to 7 characters and stored alongside the long URL in a relational database, with a cache in front of reads. Sized for the book's target of 100M new URLs/day, 1160 writes/sec, 11.6K redirect QPS, 365B rows over 10 years, and ~365 TB total storage.

Requirements

Functional

Non-functional

Capacity Assumptions

Back-of-Envelope Estimates

High-level architecture

A client POSTs a long URL through an anycast CDN edge into an L7 load balancer that terminates TLS and forwards plaintext HTTP to a stateless fleet of Spring Boot API replicas inside the VPC. The replica first consults a token-bucket rate limiter keyed by API-key or IP, then calls a distributed unique-ID generator — a Snowflake-style service that hands out monotonic 64-bit IDs composed of a 41-bit timestamp, 10-bit machine ID, and 12-bit sequence. That 64-bit integer is base62-encoded to 7 characters and stored as (short_code, long_url, user_id, created_at, expires_at) in a sharded MySQL cluster keyed by the first two characters of the code, fronted by a Redis cluster holding the hot working set. On GET /:code the replica does a single Redis GETEX; on miss it falls back to the owning MySQL shard, populates the cache, and returns an HTTP 302 with the long URL in the Location header. Click events are published to Kafka on a best-effort fire-and-forget pool so the redirect path never waits on analytics I/O. Capacity-wise, 35K peak redirect QPS at ~80% cache hit rate sends ~7K QPS to the DB tier; each shard needs well under 1ms p99 point-read latency — easily achievable with a covering index on short_code. A nightly job moves expired rows to cold storage, and a small admin service handles takedowns by flipping a revoked_at flag that the cache treats as a negative entry with 60s TTL.

Architecture Components (7)

Operations Walked Through (3)

Implementation

ShortenerController.java
package com.example.shortener.api;

import com.example.shortener.service.ShortenerService;
import com.example.shortener.dto.ShortenRequest;
import com.example.shortener.dto.ShortenResponse;
import com.example.shortener.model.UrlMapping;
import jakarta.validation.Valid;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.http.CacheControl;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.web.bind.annotation.*;
import org.springframework.web.servlet.view.RedirectView;

import java.net.URI;
import java.time.Duration;
import java.util.Optional;

@RestController
@RequestMapping("/")
public class ShortenerController {

    private final ShortenerService service;

    @Autowired
    public ShortenerController(ShortenerService service) {
        this.service = service;
    }

    @PostMapping(value = "/shorten", consumes = "application/json", produces = "application/json")
    public ResponseEntity<ShortenResponse> shorten(@Valid @RequestBody ShortenRequest req,
                                                   @RequestHeader(value = "X-User-Id", required = false) String userId) {
        UrlMapping mapping = service.createShortUrl(req.getLongUrl(), userId, req.getCustomAlias());
        ShortenResponse body = new ShortenResponse(mapping.getShortCode(), mapping.getLongUrl(), mapping.getExpiresAt());
        return ResponseEntity.status(HttpStatus.CREATED).body(body);
    }

    @GetMapping("/{code:[0-9a-zA-Z]{7}}")
    public ResponseEntity<Void> redirect(@PathVariable String code) {
        Optional<String> longUrl = service.resolve(code);
        if (longUrl.isEmpty()) {
            return ResponseEntity.status(HttpStatus.GONE).build();
        }
        return ResponseEntity.status(HttpStatus.FOUND)
                .cacheControl(CacheControl.noStore().cachePrivate())
                .location(URI.create(longUrl.get()))
                .build();
    }

    @ExceptionHandler(IllegalArgumentException.class)
    public ResponseEntity<String> onBadInput(IllegalArgumentException ex) {
        return ResponseEntity.badRequest().body(ex.getMessage());
    }
}
Base62Encoder.java
package com.example.shortener.encoding;

/**
 * Encodes monotonic 64-bit IDs into fixed-length 7-character base62 codes.
 * 62^7 = 3,521,614,606,208 — enough for 10 years of 100M writes/day.
 */
public final class Base62Encoder {

    private static final char[] ALPHABET =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private static final int BASE = ALPHABET.length;
    private static final int CODE_LEN = 7;

    private Base62Encoder() {}

    public static String encode(long id) {
        if (id < 0) {
            throw new IllegalArgumentException("id must be non-negative");
        }
        char[] buf = new char[CODE_LEN];
        long n = id;
        for (int i = CODE_LEN - 1; i >= 0; i--) {
            buf[i] = ALPHABET[(int) (n % BASE)];
            n /= BASE;
        }
        if (n != 0) {
            throw new IllegalStateException("id exceeds 62^7 capacity");
        }
        return new String(buf);
    }

    public static long decode(String code) {
        if (code == null || code.length() != CODE_LEN) {
            throw new IllegalArgumentException("code must be exactly " + CODE_LEN + " chars");
        }
        long n = 0L;
        for (int i = 0; i < CODE_LEN; i++) {
            char c = code.charAt(i);
            int v = indexOf(c);
            if (v < 0) throw new IllegalArgumentException("invalid char: " + c);
            n = n * BASE + v;
        }
        return n;
    }

    private static int indexOf(char c) {
        if (c >= '0' && c <= '9') return c - '0';
        if (c >= 'a' && c <= 'z') return 10 + (c - 'a');
        if (c >= 'A' && c <= 'Z') return 36 + (c - 'A');
        return -1;
    }
}
ShortenerService.java
package com.example.shortener.service;

import com.example.shortener.encoding.Base62Encoder;
import com.example.shortener.idgen.SnowflakeIdGenerator;
import com.example.shortener.model.UrlMapping;
import com.example.shortener.repo.UrlMappingRepository;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.stereotype.Service;
import org.springframework.transaction.annotation.Transactional;

import java.time.Duration;
import java.time.Instant;
import java.util.Optional;

@Service
public class ShortenerService {

    private static final Duration CACHE_TTL = Duration.ofHours(24);
    private static final Duration DEFAULT_EXPIRY = Duration.ofDays(365 * 10);

    private final UrlMappingRepository repo;
    private final SnowflakeIdGenerator idGen;
    private final StringRedisTemplate redis;
    private final UrlValidator validator;

    @Autowired
    public ShortenerService(UrlMappingRepository repo,
                            SnowflakeIdGenerator idGen,
                            StringRedisTemplate redis,
                            UrlValidator validator) {
        this.repo = repo;
        this.idGen = idGen;
        this.redis = redis;
        this.validator = validator;
    }

    @Transactional
    public UrlMapping createShortUrl(String longUrl, String userId, String customAlias) {
        validator.requireSafe(longUrl);
        String code = (customAlias != null) ? claimAlias(customAlias) : Base62Encoder.encode(idGen.nextId());
        UrlMapping mapping = new UrlMapping();
        mapping.setShortCode(code);
        mapping.setLongUrl(longUrl);
        mapping.setUserId(userId);
        mapping.setCreatedAt(Instant.now());
        mapping.setExpiresAt(Instant.now().plus(DEFAULT_EXPIRY));
        repo.save(mapping);
        redis.opsForValue().set(cacheKey(code), longUrl, CACHE_TTL);
        return mapping;
    }

    public Optional<String> resolve(String code) {
        String cached = redis.opsForValue().get(cacheKey(code));
        if (cached != null) return Optional.of(cached);
        Optional<UrlMapping> hit = repo.findByShortCode(code);
        hit.ifPresent(m -> redis.opsForValue().set(cacheKey(code), m.getLongUrl(), CACHE_TTL));
        return hit.map(UrlMapping::getLongUrl);
    }

    private String claimAlias(String alias) {
        if (repo.existsByShortCode(alias)) {
            throw new IllegalArgumentException("alias already taken: " + alias);
        }
        return alias;
    }

    private static String cacheKey(String code) {
        return "u:" + code;
    }
}
SnowflakeIdGenerator.java
package com.example.shortener.idgen;

import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;

/**
 * Twitter Snowflake: 64-bit IDs = 41 bits ts | 10 bits machine | 12 bits seq.
 * Produces up to 4096 IDs per ms per machine, i.e. ~4M IDs/sec per node.
 */
@Component
public class SnowflakeIdGenerator {

    private static final long EPOCH_MS = 1704067200000L; // 2024-01-01
    private static final long MACHINE_BITS = 10L;
    private static final long SEQ_BITS = 12L;
    private static final long MAX_MACHINE = (1L << MACHINE_BITS) - 1;
    private static final long MAX_SEQ = (1L << SEQ_BITS) - 1;
    private static final long MACHINE_SHIFT = SEQ_BITS;
    private static final long TS_SHIFT = SEQ_BITS + MACHINE_BITS;

    private final long machineId;
    private long lastTs = -1L;
    private long seq = 0L;

    public SnowflakeIdGenerator(@Value("${shortener.machine-id}") long machineId) {
        if (machineId < 0 || machineId > MAX_MACHINE) {
            throw new IllegalArgumentException("machineId out of range");
        }
        this.machineId = machineId;
    }

    public synchronized long nextId() {
        long now = System.currentTimeMillis();
        if (now < lastTs) {
            throw new IllegalStateException("clock moved backwards by " + (lastTs - now) + "ms");
        }
        if (now == lastTs) {
            seq = (seq + 1) & MAX_SEQ;
            if (seq == 0) {
                now = waitNextMillis(lastTs);
            }
        } else {
            seq = 0L;
        }
        lastTs = now;
        return ((now - EPOCH_MS) << TS_SHIFT) | (machineId << MACHINE_SHIFT) | seq;
    }

    private long waitNextMillis(long last) {
        long t = System.currentTimeMillis();
        while (t <= last) t = System.currentTimeMillis();
        return t;
    }
}

Key design decisions & trade-offs

Interview follow-ups

Related