Design a URL Shortener at Scale

Generate keys from a counter, handed to servers in ranges and encoded in base 62, so seven characters cover about 3.5 trillion links with no collisions to check. Store key to URL in a sharded key-value store, serve redirects from a cache in front of it, and record clicks asynchronously so the redirect never waits on analytics.

mediumPattern: Choosing and modeling a database·From Devana's Google question set

Problem

Design a link shortening service. A user submits a long URL and gets a short one back; anyone who opens the short URL is redirected to the long one.

Cover how short keys are generated, the redirect path, click analytics, custom aliases chosen by the user, and optional expiry.

POST /links              {url, alias?, expires_at?}  -> {key, short_url}
GET  /{key}              -> 302 redirect to the long URL
GET  /links/{key}/stats  -> clicks by day, referrer and country

This is one of Devana's own questions, written in the style of Google's interviews. It is not a question leaked from Google, and Devana is not affiliated with Google.

Requirements

• 10^11 links in total, and 10^5 redirects per second.
• Redirect latency under 20 ms at the 99th percentile.
• Keys of 7 characters or fewer.
• Links may expire, and users may choose custom aliases.
• Worth asking before you start: can a link's target be edited, and how fresh do analytics need to be?

Scenarios

Hints

Open one at a time, and try the problem again after each.

A worked answer

How to say it in the interview

Spend the first minutes on numbers: redirects per second, total links and key length. They drive the design: 62^7 justifies seven characters, the read rate justifies the cache, and the storage size justifies sharding. Then present key generation as a choice among three options, with the reason you picked counters.

The core in code

The piece worth writing in the interview: turning an id from the allocated range into a short key and back. Base 62 uses digits and lowercase and uppercase letters, all safe in a URL.

Python

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)                      # 62

def encode(n):
    if n == 0:
        return ALPHABET[0]
    key = []
    while n > 0:
        n, digit = divmod(n, BASE)
        key.append(ALPHABET[digit])
    return "".join(reversed(key))

def decode(key):
    n = 0
    for ch in key:
        n = n * BASE + ALPHABET.index(ch)
    return n

class IdRange:
    """A block of ids handed to one server by the allocator."""

    def __init__(self, start, size):
        self.next, self.end = start, start + size

    def next_key(self):
        if self.next >= self.end:
            raise RuntimeError("range used up: fetch a new one")
        n, self.next = self.next, self.next + 1
        return encode(n)

JavaScript

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const BASE = ALPHABET.length; // 62

function encode(n) {
  if (n === 0) return ALPHABET[0];
  let key = "";
  while (n > 0) {
    key = ALPHABET[n % BASE] + key;
    n = Math.floor(n / BASE);
  }
  return key;
}

function decode(key) {
  let n = 0;
  for (const ch of key) n = n * BASE + ALPHABET.indexOf(ch);
  return n;
}

class IdRange {
  // A block of ids handed to one server by the allocator.
  constructor(start, size) {
    this.next = start;
    this.end = start + size;
  }

  nextKey() {
    if (this.next >= this.end) throw new Error("range used up: fetch a new one");
    return encode(this.next++);
  }
}

Both versions are tested against the same cases, including every example on this page.

• decode is for debugging and range checks; the redirect path never needs it, because it looks the key up directly.
• JavaScript numbers are exact up to 2^53, far above the 62^7 keys that fit in seven characters, so no BigInt is needed.
• A server that crashes loses the unused part of its range. That wastes ids but never duplicates one, which is the right way to fail.

Follow-up questions

Common mistakes

• Taking 7 characters of an MD5 hash with no plan for collisions.
• Writing analytics synchronously in the redirect path.
• Skipping the numbers, so the key length and the sharding are never justified.
• Choosing 301 and then promising exact click counts.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with a whiteboard he can read.

Practice this problem in a mock interview

Related problems

• Design an Event and Webhook Platform: An outbox for exactly the committed changes, per-endpoint queues, signed deliveries and replay.
• Consistent Hashing for a Cache Tier: Virtual nodes on a sorted ring; each key belongs to the first position at or after its hash.
• Choosing and modeling a database: the pattern guide, with more practice questions.