Design a URL Shortener

A URL shortener maps a long URL to a short alias and redirects anyone who requests the alias to the original URL. The system is read-heavy, the data model is a single key-to-value mapping, and the main design question is how to generate unique short keys at scale without collisions.

Requirements

Functional requirements

• Given a long URL, create a short URL. An optional custom alias and an optional expiry time can be supplied.
• Given a short URL, redirect to the original long URL.
• Links expire after a default period (for example, several years) or at the requested time.
• Users can delete their own links.

Non-functional requirements

• High availability. If redirects fail, every link on the internet that uses the service breaks.
• Low redirect latency. Redirects sit on the critical path of a page load. Target a p99 in the tens of milliseconds at the server.
• Short keys that are not guessable in order. Sequential keys let a client enumerate all links.
• Durability. A created link must not be lost.
• Read-heavy. Redirects far outnumber creations.

Out of scope for the base design: click analytics, user accounts, abuse detection. Analytics is covered under follow-ups.

Estimation

Assumptions (state them explicitly in an interview): 100 million new links per month, a read-to-write ratio of 100:1, links retained for 5 years, and about 500 bytes stored per link (long URL, key, timestamps, owner).

• Write rate: 100,000,000 / (30 days x 86,400 s) = 100,000,000 / 2,592,000 ≈ 40 writes per second.
• Read rate: 40 x 100 = 4,000 redirects per second on average. Assume a peak of 3x, so about 12,000 per second.
• Total links in 5 years: 100,000,000 x 12 x 5 = 6 billion.
• Storage: 6,000,000,000 x 500 bytes = 3 TB.
• Key length: a base62 alphabet (a-z, A-Z, 0-9) gives 62^n keys. 62^6 ≈ 5.7 x 10^10 and 62^7 ≈ 3.5 x 10^12. Six billion links fit in 7 characters (3.5 x 10^12 / 6 x 10^9 ≈ 580), which leaves a growth margin of roughly 580x. Six characters (5.7 x 10^10) would leave only about 9x.
• Bandwidth: a redirect response is a few hundred bytes. 12,000 x 500 bytes = 6 MB/s. Bandwidth is not a constraint.
• Cache memory: one day of redirects is about 4,000 x 86,400 ≈ 350 million requests. Assuming the distinct links behind them number at most that, and that caching the hottest 20% (70 million entries) captures most traffic, 70,000,000 x 500 bytes = 35 GB. That fits on a small cache cluster.

What each number implies:

• 40 writes/s fits on one database primary, so writes need no sharding. Sharding is driven by storage and read load, not writes.
• 12,000 reads/s at peak is beyond what one relational primary serves comfortably with 3 TB of data, but trivial for a cache. Plan on about 95%+ cache hits, leaving the store roughly 600 reads/s at peak.
• 3 TB exceeds a comfortable single node, so shard the store or use a partitioned key-value store (for example 6 shards of 500 GB, each replicated 3 times).
• 7 characters is the smallest length with a large margin, so keys stay short enough to type and share.
• 35 GB cache means a small cluster (for example 3 nodes of 16 GB, replicated) holds the working set.

See back-of-envelope estimation for the method.

API design

POST /api/v1/links
  body: { "long_url": "...", "custom_alias": "optional", "expires_at": "optional ISO-8601" }
  201 -> { "short_url": "https://sho.rt/aZ3k9Qx", "expires_at": "..." }
  409 -> custom alias already taken
  400 -> invalid URL

GET /{key}
  301 or 302 -> Location: <long_url>
  404 -> unknown key
  410 -> expired or deleted

DELETE /api/v1/links/{key}
  204

Creation should accept an Idempotency-Key header so a retried request does not create a second link (see API pagination, idempotency and versioning). Authenticated creation requires an API key, which also enables per-user rate limiting.

301 versus 302. A 301 Moved Permanently response can be cached by browsers and intermediaries, so later clicks skip the service. That lowers load but hides repeat clicks from analytics and makes deletion or retargeting ineffective for clients that cached the redirect. A 302 Found is not cached by default, so each click reaches the service. Use 302 when analytics or link expiry matter, and 301 when minimal load matters more.

Data model

A single table, keyed by the short key:

The access pattern is a point lookup by key and a point insert. There are no joins, no range queries, and no multi-row transactions. That fits a key-value store such as DynamoDB or Cassandra, which partition by key and scale horizontally without resharding logic in the application (see key-value and document stores). A relational database sharded by key also works at this scale: 3 TB and 12,000 reads per second are within reach of a small sharded cluster, especially behind a cache.

The only operation that needs uniqueness is insertion of a key. Key-value stores with conditional writes ("insert if the key does not exist") provide it. A relational database uses a primary key constraint.

High-level design

flowchart LR
    C[Client] --> LB[Load balancer]
    LB --> W[Write service]
    LB --> R[Redirect service]
    W --> KG[Key generation service]
    W --> DB[(Link store)]
    R --> CA[(Cache)]
    R -.->|cache miss| DB
    R --> AQ[[Click event queue]]
    AQ --> AN[Analytics pipeline]

Component responsibilities:

• Load balancer. Distributes requests and routes POST and DELETE to the write service and GET /{key} to the redirect service. See load balancing.
• Write service. Validates the URL, obtains a key, writes the mapping with a conditional insert, and returns the short URL. Stateless.
• Redirect service. Looks up the key in the cache, falls back to the store, checks expiry, and returns the redirect. Stateless and scaled independently because it handles 100x the traffic.
• Key generation service. Produces unique keys (see the deep dive).
• Link store. Durable mapping from key to URL.
• Cache. Holds hot mappings, with a TTL no longer than the remaining life of the link. See caching fundamentals.
• Click event queue. The redirect service publishes an event per click asynchronously so analytics never slows a redirect.

Redirect sequence:

sequenceDiagram
    participant C as Client
    participant R as Redirect service
    participant K as Cache
    participant D as Link store
    C->>R: GET /aZ3k9Qx
    R->>K: get aZ3k9Qx
    alt cache hit
        K-->>R: long URL
    else cache miss
        K-->>R: null
        R->>D: get aZ3k9Qx
        D-->>R: long URL and expiry
        R->>K: set with TTL
    end
    R-->>C: 302 Location long URL

Deep dive

Generating unique keys

Three approaches, with different trade-offs.

1. Hash the long URL and truncate. Compute MD5 or SHA-256 of the URL, encode it in base62, and take the first 7 characters. The same URL always yields the same key, so duplicates are detected for free. Truncation makes collisions possible: with 3.5 x 10^12 possible keys and billions of links, the probability that a new key collides with an existing one is the fill ratio: with 6 x 10^9 links stored, 6 x 10^9 / 3.5 x 10^12 ≈ 0.17% of inserts collide. Among all keys, the first collision between any two keys is expected after about the square root of the key space (birthday bound), roughly 1.9 million keys. The service must detect the collision with the conditional insert and retry, for example by hashing the URL plus a salt. Every insert may need a database round trip to verify uniqueness.

2. Counter plus base62. Keep a globally unique integer counter, and encode each value in base62. Uniqueness is guaranteed by construction, with no collision checks and no retries. The 7-character space holds 3.5 x 10^12 integers. Two issues:

• Keys are predictable. Consecutive counter values give consecutive-looking keys. Mitigations are to pass the counter through a reversible bijective scramble (for example, multiplication by a large constant coprime to 62^7 modulo 62^7, that is, an odd number that is also not a multiple of 31, or a block cipher over the integer) before encoding.
• The counter is a single point of contention. A single database sequence handles 40 writes per second easily, but it is a single point of failure. See below.

3. Pre-generated key pool. A separate key generation service creates random unique keys ahead of time and stores them in a table with a used flag, or in two tables (unused and used). Write servers request a batch (for example, 1,000 keys) and hand them out from memory. A key is moved to the used state when it is handed to a server, so no two servers get the same key. If a server crashes, the unused keys in its batch are lost. With 3.5 x 10^12 keys available, losing thousands is irrelevant.

To remove the counter as a single point of failure, split the counter range among writers: each write server leases a block of, say, 10,000 integers from a coordination service (ZooKeeper or etcd, or a database row incremented atomically) and issues keys from its block locally. Lease grabbing occurs once per 10,000 links. The coordination service is then off the hot path. See consensus for how such services stay consistent. A related approach for globally unique IDs is covered in design a unique ID generator.

A base62 encoder and decoder:

import java.util.List;
import java.util.OptionalLong;

public class Main {
    static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    static String encode(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("counter values are not negative");
        }
        if (n == 0) {
            return "0";
        }
        var out = new StringBuilder();
        while (n > 0) {
            out.append(ALPHABET.charAt((int) (n % 62)));
            n /= 62;
        }
        return out.reverse().toString();
    }

    // Empty for a character outside the alphabet or a value above Long.MAX_VALUE.
    static OptionalLong decode(String s) {
        long n = 0;
        for (char c : s.toCharArray()) {
            int digit = ALPHABET.indexOf(c);
            if (digit < 0) {
                return OptionalLong.empty();
            }
            try {
                n = Math.addExact(Math.multiplyExact(n, 62L), digit);
            } catch (ArithmeticException overflow) {
                return OptionalLong.empty();
            }
        }
        return OptionalLong.of(n);
    }

    public static void main(String[] args) {
        for (long n : List.of(0L, 61L, 62L, 125L, 3_521_614_606_207L)) {
            String key = encode(n);
            System.out.println(n + " -> " + key + " -> " + decode(key));
        }
        System.out.println(decode("ab-"));
    }
}

0 -> 0 -> OptionalLong[0]
61 -> Z -> OptionalLong[61]
62 -> 10 -> OptionalLong[62]
125 -> 21 -> OptionalLong[125]
3521614606207 -> ZZZZZZZ -> OptionalLong[3521614606207]
OptionalLong.empty

Custom aliases bypass the generator and go through the same conditional insert. Reserve a distinct namespace or minimum length for generated keys so a custom alias cannot collide with a future generated key.

Read path and caching

The redirect distribution is highly skewed: a small fraction of links receives most clicks. A cache-aside layer in front of the store (Redis or Memcached, see Redis and Memcached) absorbs most reads. Use LRU eviction (see cache eviction policies). Cache negative results (unknown keys) briefly to stop repeated lookups of nonexistent keys from reaching the database. A very hot key may need a local in-process cache in each redirect server as a second tier.

On deletion or expiry change, delete the cache entry. Because expiry is stored with the value, the redirect service also checks expires_at itself and does not rely on cache TTL alone.

Sharding, consistency, and cache numbers

• Shard key: the short key itself, hashed. Generated keys are effectively random after scrambling, so load is even. Sharding by owner or by creation date would create hot shards (a heavy user, or the newest shard taking all writes). The alternative, range partitioning on the key, is only safe if keys are scrambled.
• Hot links. A viral link can send tens of thousands of requests per second to one shard. The cache absorbs it; if one cache node is still saturated, add the in-process tier with a 5 to 30 second TTL on each redirect server, or replicate that key to several cache nodes.
• Consistency. Reads after creation must succeed: the creator is redirected to the new link immediately. Write with quorum or to the primary, and read the store from the primary on a cache miss for very new keys (or accept replica lag of tens of milliseconds and retry a 404 once). Otherwise eventual consistency is fine, since links are immutable apart from deletion.
• Cache TTL and size. Use a TTL of about 24 hours capped at the remaining link life, LRU eviction, and about 35 GB as computed above. A 1-hour TTL raises store load; a TTL of days lengthens the window in which a deleted link still redirects unless deletion also invalidates the entry (it should).
• Queue semantics for clicks. At-least-once delivery to the click queue is fine: counts may be slightly inflated, and analytics can deduplicate by event ID. Drop events rather than block a redirect if the queue is down.

Expiry and cleanup

Do not scan the table for expired rows. Options:

• Lazy deletion. On access, if the link is expired, return 410 and delete the row.
• Native TTL. DynamoDB and Cassandra support per-row TTL, which removes expired rows in the background.
• Periodic batch job. Deletes expired rows in small batches at low traffic.

A deleted key can be returned to the pool and reused only after a safety delay, because old caches and 301-cached browsers may still point to it. With a 3.5 x 10^12 key space, the simplest policy is never to reuse keys.

Malicious use and abuse

Check URLs against a blocklist of known malicious domains at creation time, restrict schemes to http and https, and rate limit creation per user and per IP. Random-looking keys make enumeration impractical, but they do not provide access control: anyone with a short URL can follow it.

Bottlenecks and scaling

• Redirect service. Stateless, so add instances behind the load balancer. Serve from cache in almost all cases.
• Cache. Partition by key with consistent hashing and replicate hot partitions.
• Link store. Partition by key hash. Because keys are effectively random, load spreads evenly and hot partitions arise only from individually popular links, which the cache absorbs. See sharding and partitioning.
• Key generation. Block leasing removes the coordination service from the hot path. Run it replicated.
• Multi-region. Deploy the read path in several regions with a regional cache and read replicas. Writes go to the leader region or to a store with multi-region writes, using globally unique keys (region prefix or leased blocks per region).
• Availability. Replicate the store across availability zones. If the cache is down, the redirect service reads from the store and applies rate limits so the store is not overwhelmed.

Failure modes

Redirects should stay up when creation is down, so the two services fail independently. At 10x (400 writes/s, 120,000 redirects/s peak, 30 TB over 5 years): the write path still fits a few writers, but the store needs about 60 shards, the cache needs 350 GB or more (a real cluster with hot-key handling), and a CDN or 301 caching becomes worthwhile for the head of the distribution. A 7-character key space still holds 60 billion links with about 58x margin.

Trade-offs and follow-up questions

• Hash-based versus counter-based keys. Hashing deduplicates identical URLs but needs collision handling. Counters need no collision handling but need a coordinated allocator and scrambling to hide the sequence.
• 301 versus 302. Lower load versus accurate analytics and revocation.
• How would analytics work? Emit click events (timestamp, key, referrer, coarse geolocation) to a log such as Kafka and aggregate them asynchronously. Never write counters synchronously on the redirect path.
• Same long URL submitted twice? Either return the existing key (requires a secondary index on a hash of the URL) or create a new key each time. Per-user separate links are needed if each user wants their own statistics.
• What if the key store loses data? Use synchronous replication within a region and regular backups. Losing a mapping breaks a public link permanently.
• What if we run out of keys? Move to 8 characters; existing 7-character keys stay valid because lengths differ. At 3.5 x 10^12 keys and 6 x 10^9 used, this is remote.
• What if a user must not be able to guess links? Use random or scrambled keys (about 41 bits of entropy at 7 characters is not a secret), so treat links as unlisted, not private. For private links, require auth on the redirect.
• What if a single custom alias is requested by two users at once? The conditional insert lets exactly one win; the other gets 409.
• What if the redirect target is malicious later? Periodically rescan popular links, and keep a kill-switch that deletes the cache entry and returns 410.
• Can a CDN help? A CDN can cache 301 responses at the edge (see content delivery networks), which is effective for very popular links but conflicts with immediate deletion unless purge is supported.