URL Shortener (bit.ly)

1. Hook

#

Every time you click a bit.ly or t.co link, a distributed system silently resolves a 7-character code to a full URL and redirects you — in under 10 milliseconds — before your browser even renders the loading spinner. Behind that invisible handshake sits a deceptively rich design problem: how do you build a service that creates billions of short codes, never loses a mapping, and serves hundreds of thousands of reads per second with single-digit millisecond latency, all while preventing abuse, surviving data-centre failures, and staying profitable?

The URL Shortener is a canonical warm-up question in system design interviews precisely because it spans the full stack — hashing, storage, caching, CDN, security, and analytics — without overwhelming complexity. Master it and you have a reusable vocabulary for every “design at scale” discussion that follows.

2. Problem Statement

#

Functional Requirements

#

1. Shorten: Given a long URL, return a unique short code (e.g., https://sho.rt/aB3xYz).
2. Redirect: GET /<code> responds with HTTP 301/302 to the original URL.
3. Custom aliases: Users may optionally specify a desired short code (subject to availability).
4. Expiry: URLs may have an optional TTL after which the short link is invalidated.
5. Analytics: Track click count, referrer, and geo per short code (async, non-blocking on redirect).

Non-Functional Requirements

#

Out of Scope

#

• Rich link preview / Open Graph metadata generation
• A/B split redirects
• QR code generation
• Browser extensions or mobile SDKs

3. Scale Estimation

#

Assumptions

• 100 M new URLs shortened per day (write-heavy by internet standards, but still dwarfed by reads)
• 20 B redirects per day (200:1 read:write)
• Average long URL: 200 bytes; short URL record: ~500 bytes total (with metadata)
• Retention: 5 years

Key insight: The system is overwhelmingly read-dominated. The primary design challenge is serving 2.3 M reads/second at sub-10 ms latency — not the write path.

4. High-Level Design

#

graph TD
    Client["Browser / Mobile App"]
    DNS["DNS / Anycast"]
    CDN["CDN Edge PoP\n(Cloudflare / Fastly)"]
    LB["L7 Load Balancer\n(NGINX / Envoy)"]
    WriteAPI["Write API Cluster\n(Shorten Service)"]
    ReadAPI["Redirect Service Cluster\n(Read-heavy)"]
    Cache["Redis Cluster\n(code → long_url)"]
    DB["Primary DB\n(PostgreSQL / Cassandra)"]
    DBReplica["Read Replicas × N"]
    Analytics["Analytics Kafka Topic"]
    AnalyticsConsumer["Flink / Spark\nStreaming Consumer"]
    AnalyticsStore["ClickHouse\n(Analytics OLAP)"]

    Client -->|"GET /aB3xYz"| DNS
    DNS --> CDN
    CDN -->|"Cache miss"| LB
    LB --> ReadAPI
    ReadAPI -->|"L1 miss"| Cache
    Cache -->|"L2 miss"| DBReplica
    ReadAPI -->|"fire-and-forget"| Analytics

    Client -->|"POST /api/shorten"| LB
    LB --> WriteAPI
    WriteAPI --> DB
    DB -->|"replication"| DBReplica
    WriteAPI -->|"prime cache"| Cache

    Analytics --> AnalyticsConsumer --> AnalyticsStore

Read path: Browser → CDN (HTTP cache, TTL ~60 s for 302) → Redirect Service → Redis L1 (hit rate ~95%) → DB read replica (cache miss). Response is a single 302 HTTP redirect.

Write path: Client → Write API → generate code → persist to primary DB → prime Redis → return short URL. Entirely off the critical redirect path.

5. Deep Dive

#

5.1 Short Code Generation — Base62 + Counter vs. Hashing

#

This is the crux of the design. There are three viable strategies:

Strategy A: MD5/SHA-256 hash of the long URL, take first 7 chars

Hash the URL, encode as Base62, truncate to 7 characters. Simple, but collision probability is non-trivial: with 7 Base62 characters you have 62⁷ ≈ 3.5 trillion slots. For 100 M URLs/day over 5 years that is ~182 B entries — about 5% of the keyspace. The birthday paradox means you will start seeing collisions well before saturation; you need a retry loop with an incremented salt.

Worse, two users shortening the same URL get the same code — which is a feature for deduplication but a bug if user A’s URL expires and user B’s doesn’t.

Strategy B: Auto-increment counter + Base62 encode (chosen)

Maintain a globally unique, monotonically increasing counter. Encode it in Base62 ([0-9A-Za-z]). A 7-character Base62 number gives ~3.5 T unique codes — enough for 96 years at 100 M/day.

The counter can live in a dedicated Counter Service backed by Redis INCR (atomic, single-threaded in Redis). To avoid a hot single Redis node and the SPOF it creates, pre-allocate ranges to each Write API node: node 1 owns [1..1000], node 2 owns [1001..2000], and so on. Each node burns through its range in memory before requesting a new batch — similar to Flickr’s ticket servers or Twitter Snowflake.

// Java 17 record for a pre-allocated counter range
public record CounterRange(long start, long end, AtomicLong current) {

    public static CounterRange of(long start, long end) {
        return new CounterRange(start, end, new AtomicLong(start));
    }

    public OptionalLong next() {
        long val = current.getAndIncrement();
        return val <= end ? OptionalLong.of(val) : OptionalLong.empty();
    }
}

public final class Base62Encoder {
    private static final String ALPHABET =
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    public static String encode(long n) {
        if (n == 0) return "0";
        var sb = new StringBuilder();
        while (n > 0) {
            sb.append(ALPHABET.charAt((int)(n % 62)));
            n /= 62;
        }
        return sb.reverse().toString();
    }
}

Strategy C: UUID / random

128-bit random, truncated. No coordination needed, but high collision risk and no natural ordering for range scans.

Verdict: Counter + Base62 wins. It’s collision-free by construction, produces compact codes, and the batch-range trick eliminates coordination on the hot path.

5.2 Redirect Service

#

The Redirect Service is a thin, stateless HTTP layer. Its sole job is:

1. Parse /{code} from the path.
2. Look up the long URL in the local L1 cache (an in-process Caffeine cache, 10 K entries, 5 s TTL).
3. On miss, look up Redis (sub-millisecond over a private network).
4. On Redis miss, query a DB read replica and backfill Redis (TTL: 24 h).
5. If the code is expired or unknown, return 404.
6. Emit a click event to Kafka (fire-and-forget, async, non-blocking).
7. Return HTTP 302 to the long URL.

301 vs 302: A 301 (permanent) is cached by the browser indefinitely — great for bandwidth, terrible for analytics since subsequent clicks never reach your servers. Bit.ly uses 301 for bandwidth savings but loses analytics fidelity on repeat visitors. Most enterprise shorteners use 302 (temporary) so every click is trackable. Use 302 unless bandwidth is the dominant cost.

5.3 CDN Layer

#

For popular short codes (viral links, marketing campaigns), push the 302 redirect to CDN edge nodes. CDN Cache-Control: max-age=60 means the edge serves the redirect without touching origin for 60 seconds. At 2.3 M peak RPS, even a 70% CDN hit rate offloads 1.6 M RPS from the origin fleet.

Custom aliases and codes with imminent expiry should be tagged Cache-Control: no-store to avoid serving stale 404s from CDN.

6. Data Model

#

Primary URL Table (PostgreSQL or Cassandra)

#

Indexes:

• Primary key on code — covers all redirect lookups.
• (user_id, created_at DESC) — covers “show my links” dashboard queries.
• Partial index on expires_at WHERE expires_at IS NOT NULL — efficient TTL sweep job.

Partitioning: At 91 TB over 5 years, partition by created_at month in PostgreSQL. Old partitions (> 5 years) are detached and archived to object storage (S3 Glacier).

Why not Cassandra? For pure key-value redirect lookups, Cassandra’s wide-column store is a natural fit and scales writes horizontally without a leader. However, Cassandra sacrifices ad-hoc querying and strong consistency. If analytics and user dashboards are important (they are), PostgreSQL with read replicas and a Redis cache layer is simpler to operate. At truly massive scale (>10 B codes), migrate the hot redirect table to Cassandra while keeping the analytics in PostgreSQL.

Redis Cache Schema

#

SET url:{code} "{long_url}" EX 86400

A single string key per code. At 500 bytes per entry and 95% hit rate, a 3-node Redis cluster (128 GB each) comfortably holds the working set.

7. Trade-offs

#

Counter Service: Centralised vs. Distributed Range Allocation

#

Conclusion: Batch range allocation balances simplicity and scalability. Gaps of up to 1000 codes on a node crash are invisible to users and don’t affect correctness.

301 vs. 302 Redirect

#

SQL vs. NoSQL for URL Store

#

Conclusion: Start with PostgreSQL + read replicas + Redis cache. Migrate redirect lookups to Cassandra only when writes exceed 50 K/s sustained.

CAP Trade-off

#

The system leans AP on the redirect path (availability + partition tolerance). A Redis replica can serve slightly stale data — an expired URL might redirect for a few seconds after expiry. This is acceptable. The write path is CP: counter allocation and URL persistence are strongly consistent so no duplicate codes are ever issued.

8. Failure Modes

#

9. Security & Compliance

#

Authentication & Authorisation: Anonymous shortening is permitted (rate-limited). Authenticated users (OAuth2 / JWT) can manage their own links. Admins can take down any link. RBAC: anonymous, user, admin.

Input Validation: Long URLs are validated against RFC 3986 before storage. Block known malicious domains via a real-time threat-intelligence feed (Google Safe Browsing API). Reject URLs with non-HTTP/HTTPS schemes to prevent javascript:, file:, and data: injection.

Rate Limiting: Anonymous shortening is rate-limited to 10 requests/hour per IP (token bucket in Redis). Authenticated users get 1000/hour. Prevents bulk abuse and link-spam campaigns.

Encryption: All data in transit via TLS 1.3. Long URLs at rest are stored in plaintext (they’re already public) but the database volume is encrypted (AES-256). User PII (email, IP) is hashed or pseudonymised per GDPR.

Audit Log: Every create, update, and delete of a short code is written to an immutable append-only audit log (write to Kafka, consume into ClickHouse with no delete capability). Supports GDPR Right-to-Erasure: mark code as deleted and null out the long URL; the audit event retains the pseudonymised user ID.

PII / GDPR: Click events store hashed IP (SHA-256 + rotating salt per 24 h) rather than raw IP. Referrer headers are stripped to the domain only. Geo is inferred from IP at collection time and the raw IP is discarded.

10. Observability

#

RED Metrics (per service)

#

Saturation Metrics

#

• Redis memory utilisation: alert at 75% — time to add a shard.
• DB replica replication lag: alert at > 5 s — reads may become stale.
• Counter range exhaustion rate: alert when a node requests a new range more than once per minute (means range size is too small).

Business Metrics (ClickHouse dashboard)

#

• Clicks per short code per hour (viral detection)
• Geographic distribution of clicks
• Top referrer domains
• DAU/MAU of shortening feature

Tracing

#

Distributed traces via OpenTelemetry (OTLP → Jaeger / Tempo). Every redirect request carries a trace-id header. Sampling strategy: 1% baseline + 100% on error. Tail-based sampling in the collector keeps storage costs manageable.

11. Scaling Path

#

Phase 1 — MVP (< 100 RPS)

#

Single PostgreSQL instance, no Redis, single Redirect Service pod. Deploy on a managed PaaS (Railway, Render, or a single EC2 instance). Total infrastructure: $50/month. Focus: correctness, not scale.

Phase 2 — Growth (100 RPS → 10 K RPS)

#

Add Redis (ElastiCache, 1 primary + 1 replica). Add 3 read replicas to PostgreSQL (RDS Multi-AZ). Redirect Service scales horizontally behind an ALB. CDN in front (Cloudflare free tier). What breaks first: PostgreSQL primary on write storms — add connection pooling (PgBouncer).

Phase 3 — Scale (10 K → 100 K RPS)

#

Redis Cluster (6 nodes: 3 primary + 3 replica). Write API uses batch counter ranges. Separate read and write DB roles. Add a CDN Purge API workflow for expiring URLs. Kafka for analytics decoupling. Add a geo-distributed cache (Redis at edge via Cloudflare Workers KV). What breaks first: Redis cluster hot-slot on viral codes — enable read from replicas (READONLY on replica nodes).

Phase 4 — Hyper-scale (100 K → 1 M+ RPS)

#

Multi-region active-active. Cassandra replaces PostgreSQL for the redirect table (partition key: code). Counter generation moves to Snowflake-style local generation per region. CDN handles 80%+ of traffic. Redirect Service deployed in 20+ PoPs globally. Analytics becomes a separate service owned by a separate team. What breaks first: cross-region replication lag for newly created codes — accept eventual consistency with a 1–2 s replication window (most new codes are not shared immediately).

12. Enterprise Considerations

#

Brownfield Integration: Enterprises often need to integrate a URL shortener into an existing marketing platform or CMS. The Write API should expose a REST and gRPC interface. The redirect domain should be white-label (custom domains like go.acme.com), requiring a wildcard TLS certificate and CNAME delegation — solved with Cloudflare’s SSL for SaaS product or cert-manager in k8s.

Build vs. Buy: Managed options (Bitly Enterprise, Rebrandly, short.io) cost $300–$2000/month for high-volume plans but remove operational burden. Build when: custom analytics integration, data sovereignty requirements, or > 1 B redirects/month (where managed pricing becomes punitive). Typical TCO for a self-hosted solution at 100 K RPS: ~$8 K/month cloud spend + 1 SRE FTE.

Multi-Tenancy: SaaS teams need namespace isolation — each tenant gets a subdomain (tenant.sho.rt) and their codes are namespaced ({tenant_id}:{code}). The Redis key becomes url:{tenant_id}:{code}. DB partitioning by tenant_id prevents noisy-neighbour query storms.

Vendor Lock-In: Redis is the highest lock-in risk. Design the cache layer behind an interface (UrlCache) so you can swap Redis for Memcached, DynamoDB DAX, or an in-process Caffeine cache without changing the Redirect Service.

Conway’s Law: The system naturally splits into three teams: Platform (counter service, storage, DB), Product (shorten API, custom domains, expiry), and Data (analytics, ClickHouse, dashboards). Microservice boundaries should mirror these team boundaries to avoid cross-team coupling on deployments.

13. Interview Tips

#

1. Start with clarifying questions: “Do we need analytics?” and “Is 7 characters fixed?” change the design significantly. Anchoring to requirements before drawing boxes shows seniority.

2. Lead with the read path: Interviewers expect you to notice the 200:1 read:write skew immediately. Open with “this is a read-heavy system — my primary concern is redirect latency, not write throughput” and you signal the right mental model.

3. Common mistake — hashing without collision handling: Candidates propose MD5 truncation and stop there. Always acknowledge the birthday problem and describe your retry or deduplication strategy.

4. Deep-dive bait: The counter service is a rich rabbit hole. Know Snowflake IDs, Flickr-style ticket servers, and the batch-range pattern. Expect the interviewer to ask “what happens if the counter service node crashes mid-range?”

5. Vocabulary that signals fluency: “probabilistic early expiration”, “cache stampede”, “fan-out on write”, “Base62 keyspace”, “HTTP 301 vs 302 analytics trade-off”, “Anycast DNS for geo-routing”. Drop two or three naturally and don’t over-explain them.

14. Further Reading

#

• Designing Data-Intensive Applications — Martin Kleppmann, Chapters 5–6 (Replication & Partitioning) — the canonical primer on the distributed storage concepts underlying this system.
• Bitly Engineering Blog — “Building a reliable URL shortener” — real-world lessons on Redis cluster sharding and CDN cache invalidation at scale.
• RFC 3986 — Uniform Resource Identifier (URI): Generic Syntax — defines what a valid URL is; essential for input validation logic.
• Google Safe Browsing API documentation — for integrating real-time malicious URL detection into the write path.