Design a URL Shortener

Design a URL shortening service like bit.ly. Users submit a long URL and receive a short alias (e.g., short.ly/xK9p2). Clicking the short URL redirects to the original.

Capacity Estimation

Write throughput: 100M URLs/day ≈ 1,160 writes/sec

Read throughput: 10B redirects/day ≈ 116,000 reads/sec → read:write ratio ~100:1

Storage: Average URL = 500 bytes. 100M × 365 × 5 years × 500 bytes ≈ 90 TB over 5 years

Short code length: Base62 with 7 chars → 62^7 ≈ 3.5 trillion unique codes. Enough for centuries.

High-Level Architecture

Client
  │
  ▼
Load Balancer
  │
  ├── Write Service  → generates short code → writes to DB + cache
  └── Read Service   → looks up short code → 301 redirect
                              │
                        [Redis Cache]  →  [Cassandra / DynamoDB]

Key insight: reads vastly outnumber writes. Optimise the read path with an in-memory cache (Redis). The cache is populated on first read and expires with the URL's TTL.

Implementation-level detail: ID generation service class design

Snowflake ID generator — a widely-used pattern for generating unique, roughly time-sortable IDs without a central coordinator:

64-bit ID layout: [1 unused bit][41-bit timestamp][10-bit machine ID][12-bit sequence]

• Timestamp (41 bits): milliseconds since a custom epoch — gives IDs a natural chronological ordering and ~69 years of range before overflow.
• Machine ID (10 bits): up to 1024 distinct generator instances can run concurrently without ID collisions, each assigned a unique machine ID at startup (via config or a coordination service).
• Sequence (12 bits): up to 4096 IDs per millisecond per machine, incrementing within the same millisecond and resetting when the clock ticks forward.

class SnowflakeIdGenerator {
    private final long machineId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;

    SnowflakeIdGenerator(long machineId) { this.machineId = machineId; }

    synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & 0xFFF; // 12-bit mask
            if (sequence == 0) timestamp = waitNextMillis(lastTimestamp); // sequence exhausted this millisecond
        } else {
            sequence = 0;
        }
        lastTimestamp = timestamp;
        return (timestamp << 22) | (machineId << 12) | sequence;
    }
    private long waitNextMillis(long last) {
        long ts = System.currentTimeMillis();
        while (ts <= last) ts = System.currentTimeMillis();
        return ts;
    }
}

The resulting long ID is then encoded to a short, URL-safe string via Base62 (digits + upper/lowercase letters), which is what actually appears in the shortened URL — Snowflake solves uniqueness without coordination, Base62 solves making a large number look like a short code.

Why not just a random string? A random approach needs a collision check against the database on every generation (an extra read before every write); Snowflake IDs are unique by construction, so no collision-check round-trip is needed at all.

Malicious URL protection

A URL shortener is a common vector for phishing and malware distribution specifically because the short link hides the actual destination from the user until after they've clicked — this is a real abuse case the design must account for, not an edge case. Standard mitigation: check the submitted long URL against a threat-intelligence blocklist (e.g. Google Safe Browsing's API, or a similar third-party feed) SYNCHRONOUSLY at shorten-time before creating the mapping, rejecting known-malicious URLs outright; for URLs not on any blocklist yet, some systems additionally re-check periodically after creation (since a legitimate site can be compromised after a short link to it already exists) and disable the short link retroactively if it's later flagged.

Rate limiting the shorten endpoint

The POST /shorten endpoint (unlike the read-heavy redirect path) needs its own rate limiting (API Rate Limiting Gateway) — without it, the create endpoint is an easy vector for abuse (mass-generating short links for spam campaigns, or exhausting the ID space maliciously, though Snowflake's ID space is large enough that exhaustion isn't realistic). A per-IP and per-account limit on creation, distinct from the redirect endpoint's own (much higher) traffic tolerance, is the standard mitigation.

Click analytics

On each redirect: async-publish a click event { shortCode, timestamp, referrer, userAgent, approxLocation }
  to a message queue (Message Queue System) — NEVER synchronously written on the hot
  redirect path itself, since that would add latency to every single redirect for a
  feature (analytics) that isn't required for the redirect to succeed

Click tracking must be decoupled from the redirect's critical path — the redirect response should be returned to the client immediately, with the click event published asynchronously (fire-and-forget to a queue) for a separate analytics pipeline to consume and aggregate. Synchronously writing an analytics record before returning the 301 would directly violate the sub-10ms p99 redirect latency requirement stated in Requirements, for a feature that has no bearing on whether the redirect itself succeeds.

API Design

POST /api/v1/shorten
Body: { longUrl, customAlias?, ttlDays? }
Response: { shortUrl, expiresAt }

GET /{shortCode}
Response: 301 Redirect to longUrl
          404 if not found or expired

Database Design

url_mappings
  shortCode   VARCHAR(8)   PK
  longUrl     TEXT         NOT NULL
  userId      VARCHAR(36)  nullable
  createdAt   TIMESTAMP
  expiresAt   TIMESTAMP    nullable (null = never expires)

Why Cassandra / DynamoDB? The access pattern is key-value: lookup by shortCode. Wide-column stores are optimised for this and scale horizontally. PostgreSQL works fine at smaller scale.

Database schema with explicit indexes

CREATE TABLE urls (
    id           BIGINT PRIMARY KEY,       -- the Snowflake ID itself
    short_code   VARCHAR(10) NOT NULL,     -- Base62-encoded id
    long_url     TEXT NOT NULL,
    created_at   TIMESTAMP NOT NULL,
    expires_at   TIMESTAMP,
    click_count  BIGINT DEFAULT 0
);

CREATE UNIQUE INDEX idx_short_code ON urls (short_code); -- the hot read path: lookup by short_code on every redirect
CREATE INDEX idx_expires_at ON urls (expires_at);         -- supports a background job cleaning up expired URLs

The unique index on short_code is the single most important index in this schema — it's on the read path for every redirect request, which per the capacity estimation is the overwhelming majority of traffic; without it, every redirect would be a full table scan.

Class-level design for the shortening service:

interface IdGenerator { long nextId(); }
interface UrlRepository { void save(ShortUrl url); Optional<ShortUrl> findByShortCode(String code); }

class UrlShorteningService {
    private final IdGenerator idGenerator;
    private final UrlRepository repository;
    private final Base62Encoder encoder;

    ShortUrl shorten(String longUrl, Duration ttl) {
        long id = idGenerator.nextId();
        String shortCode = encoder.encode(id);
        ShortUrl url = new ShortUrl(id, shortCode, longUrl, Instant.now(), Instant.now().plus(ttl));
        repository.save(url);
        return url;
    }
}

IdGenerator and UrlRepository as interfaces (not concrete classes referenced directly) is Dependency Inversion applied directly — UrlShorteningService depends on abstractions, making the Snowflake generator and the specific database swappable without touching this class.

Scaling Strategy

1. Cache first: Redis holds the hot 20% of URLs that serve 80% of traffic
2. Read replicas: Route all redirect traffic to read replicas; writes go to primary
3. CDN edge caching: For ultra-popular URLs, cache the redirect at edge nodes to reduce latency to <1ms
4. Partitioning: Shard Cassandra by shortCode hash for even distribution

• Base62 vs MD5 hashing: Base62 counter is simpler and avoids collisions; MD5 is faster but requires collision handling.
• 301 (permanent) vs 302 (temporary) redirect: 301 allows browsers to cache the redirect (fewer server hits), but you lose click analytics. Use 302 if click tracking matters.

• Short code generation at scale: A single counter is a bottleneck. Solution: pre-generate batches of codes per application server.
• Cache stampede: If a popular URL's cache entry expires, thousands of simultaneous cache misses hit the DB. Solution: probabilistic early expiration.

• DB unavailable: The read service can still serve cached URLs. Write service fails gracefully with 503.
• Cache unavailable: Fall through to DB. Performance degrades but the service stays up.