Beginner
Storage & Retrieval
20 min

Design a URL Shortener

A URL shortener converts long URLs into short codes (e.g. bit.ly/abc123) and redirects users transparently. Behind this simple facade lies a system that must generate unique short codes, store billions of mappings, and serve redirects with sub-20ms latency globally.

HashingRedisNoSQLHorizontal ScalingCaching

Design it yourself

Don't just read it — drag components onto a canvas and get Aria's interviewer review.

Requirements

Functional

  • Given a long URL, generate a unique short URL (e.g. https://short.ly/abc123)
  • Redirect users from a short URL to the original long URL
  • Custom aliases — let users choose their own short code
  • Expiry — short URLs can be set to expire after a given time
  • Analytics — track click counts, referrer, and geography (stretch goal)

Non-Functional

  • 100M URLs created per day (≈ 1,160 writes/sec)
  • 10:1 read-to-write ratio → 1B redirects/day ≈ 11,600 reads/sec
  • 99.99% availability — a redirect failure is immediately user-visible
  • Redirect latency < 20ms at p99
  • URLs must remain accessible for at least 5 years

Capacity Estimation

Writes100M / day ≈ 1,160 / sec
Reads (10:1)1B / day ≈ 11,600 / sec
Storage per URL~500 bytes (URL + metadata)
Storage (5 years)100M × 365 × 5 × 500B ≈ 91 TB
Cache target80% of reads served from Redis

High-Level Components

API Gateway / Load Balancer

Routes POST /shorten to the Write Service and GET /{code} to the Redirect Service. Handles TLS termination, rate limiting, and bot filtering.

Write Service

Generates a unique 7-character base62 code using a distributed counter. Writes the mapping to the primary database and optionally warms the cache.

Redirect Service

Receives a short code, checks Redis cache first (targeting 80% hit rate), falls back to the database on a miss. Returns HTTP 302 with the Location header set to the original URL.

Database (Wide-Column Store)

Stores { shortCode → { longUrl, userId, createdAt, expiresAt } }. A wide-column store like Cassandra or DynamoDB is ideal — the access pattern is almost exclusively single-key point lookups.

Cache (Redis)

Caches the hot 20% of URLs that account for 80% of traffic. TTL aligned with URL expiry. LRU eviction policy. Reduces database read load by ~80%.

Analytics Service (async)

Redirect Service publishes click events to Kafka. The Analytics Service consumes events asynchronously and writes aggregates to a separate store. Fully decoupled from the latency-critical redirect path.

Architecture Diagram

Rendering diagram…

Deep Dives

Short Code Generation

Three viable approaches exist:

1. MD5 / SHA-256 + truncation — Hash the long URL, take the first 7 characters. Fast but has collision risk: two different URLs can produce the same 7-char prefix. Mitigate by appending user ID or timestamp before hashing, then re-hashing on collision.

2. Auto-increment ID + Base62 (recommended) — A globally unique integer (from a dedicated ID generator or database sequence) is encoded into base62 (digits 0-9, lowercase a-z, uppercase A-Z). 7 characters in base62 = 62^7 ≈ 3.5 trillion unique codes. Collision-free by design. The challenge is making the ID generator distributed and high-throughput — Twitter's Snowflake algorithm is a common reference.

3. UUID — Simple and collision-free, but 36 characters is far too long for a URL shortener.

Java — Base62 encoding of a distributed counter ID

// Base62 encode a numeric ID
private static final String CHARS =
    "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

public static String encode(long id) {
    StringBuilder sb = new StringBuilder();
    while (id > 0) {
        sb.append(CHARS.charAt((int) (id % 62)));
        id /= 62;
    }
    while (sb.length() < 7) sb.append('0'); // left-pad
    return sb.reverse().toString();
}

// encode(1_000_000_000L) → "1L9zKa2"
// encode(1_000_000_001L) → "1L9zKa3"  (next sequential code)

Redirect: 301 vs 302

HTTP 301 (Permanent Redirect) is cached by browsers. After the first visit, subsequent clicks never touch our servers — analytics breaks, and we lose the ability to update or expire the URL.

HTTP 302 (Temporary / Found) is NOT cached by browsers. Every click hits the Redirect Service, giving us accurate analytics, the ability to change the destination, and the ability to honour expiry.

Use 302. Always. Unless you explicitly want to hand off a URL permanently and never track it again.

Java — 302 redirect endpoint

// Spring Boot — Redirect endpoint
@RestController
public class RedirectController {

    @GetMapping("/{code}")
    public ResponseEntity<Void> redirect(@PathVariable String code) {
        String longUrl = urlService.resolve(code); // throws 404/410 if missing/expired
        return ResponseEntity
            .status(HttpStatus.FOUND)           // 302
            .location(URI.create(longUrl))
            .build();
    }
}

Caching Strategy

URL redirects follow a power-law distribution: a small number of URLs (viral links, campaign short codes) receive the vast majority of traffic. This makes caching extremely effective.

Cache-aside pattern: Redirect Service checks Redis → cache miss → reads from DB → writes result to Redis with TTL.

What to cache: shortCode → longUrl only. Do not cache analytics counters — write-through invalidation is not worth the complexity.

Eviction: LRU. Recently-accessed URLs are statistically most likely to be accessed again.

TTL: Set Redis TTL = remaining seconds until URL expiry. Redis auto-removes expired entries, so the cache never returns a stale redirect for a URL the database has expired.

Java — Cache-aside redirect resolution with expiry awareness

// Cache-aside in the Redirect Service
public String resolve(String code) {
    // 1. Cache check
    String cached = redis.get("url:" + code);
    if (cached != null) return cached;

    // 2. Database fallback
    UrlMapping mapping = db.findByCode(code)
        .orElseThrow(() -> new NotFoundException(code));

    if (mapping.isExpired()) throw new GoneException(code);  // 410 Gone

    // 3. Populate cache with remaining TTL
    long ttlSeconds = mapping.expiresAt()
        .minusSeconds(Instant.now().getEpochSecond())
        .getEpochSecond();
    redis.setex("url:" + code, Math.max(ttlSeconds, 1), mapping.longUrl());

    return mapping.longUrl();
}

Custom Aliases

Custom aliases (e.g. short.ly/product-launch) require a uniqueness check before persistence. Two patterns:

Optimistic insert: Attempt DB insert with a unique constraint on the code column. Catch the duplicate-key exception and return 409 Conflict. Simple, correct, but a wasted write on every conflict.

Redis pre-check: Before the DB insert, check a Redis SET for the alias. If present → 409 immediately. If absent → proceed to insert. Still rely on the DB unique constraint as the source of truth (race condition protection), but the Redis check eliminates most unnecessary writes in normal operation.

Blacklist reserved aliases (about, api, admin, login) in a config file checked at startup.

Scaling Writes

At 1,160 writes/sec a single database master handles comfortably. At 10x that scale (e.g. a viral event), options are:

Read replicas: Redirect Service reads from replicas; Write Service writes to primary. 11,600 read RPS distributed across N replicas.

Horizontal sharding: Shard by the first character of the short code (or hash of the code). 62 possible shards from base62 first character.

ID Generator Service (Snowflake-style): Dedicated microservice generates monotonically increasing 64-bit IDs using timestamp + datacenter ID + sequence number. Completely avoids distributed locks on the counter.

Java — Simplified Snowflake ID generator

// Snowflake-style ID: 64 bits
// [sign 1][timestamp 41][datacenter 5][worker 5][sequence 12]
// 41-bit timestamp → ~69 years from epoch
// 12-bit sequence → 4096 IDs / millisecond / worker node

public class SnowflakeIdGenerator {
    private final long datacenterId;
    private final long workerId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public synchronized long nextId() {
        long ts = System.currentTimeMillis();
        if (ts == lastTimestamp) {
            sequence = (sequence + 1) & 4095; // 12-bit mask
            if (sequence == 0) ts = waitNextMillis(lastTimestamp);
        } else {
            sequence = 0;
        }
        lastTimestamp = ts;
        return (ts << 22) | (datacenterId << 17) | (workerId << 12) | sequence;
    }
}

Key Trade-offs

HTTP 301 vs 302 redirect

302 Temporary

301 is cached by browsers — analytics breaks and URLs cannot be updated or expired. 302 always hits our service.

Base62 counter vs MD5 hash for code generation

Base62 counter

Guaranteed uniqueness, predictable code length, no collision handling needed. MD5 truncation can collide and requires a retry loop.

SQL vs NoSQL for the mapping store

NoSQL (Cassandra / DynamoDB)

Access pattern is pure key-value. NoSQL scales horizontally without sharding complexity. Only prefer SQL if analytics queries on the same data are a core requirement.

Sync vs async analytics

Async via Kafka

Click tracking must not add latency to the redirect. Decoupling via Kafka means analytics failures are invisible to the user.

Interview Tips

  • 1Start by clarifying scale. "100M URLs/day" vs "1,000 URLs/day" changes the architecture. Ask before drawing anything.
  • 2Know base62 vs MD5 and the collision trade-offs. Interviewers almost always probe code generation.
  • 3Mention 302 vs 301 proactively — it shows you think about product requirements (analytics), not just technical plumbing.
  • 4LRU cache eviction is the right choice here — explain why (recently accessed = likely accessed again).
  • 5If asked to scale writes, introduce a Snowflake-style ID generator rather than a single database auto-increment column.
  • 6Bring up the analytics decoupling via Kafka — it demonstrates you understand the critical path and know how to protect it.

Discussion

Discussion

Sign in to join the discussion.

Loading discussion…
All System Design Cases