Case Study: A URL Shortener
The classic interview question done properly and then run in production: requirements, numbers, API, data model, five ways to make a short code, a 301 that hides your clicks, a hot link, a bot and a dead shard.
An interactive System Design lesson: 24 steps, about 35 minutes, on a live simulation in your browser.
The interviewer says: design bit.ly. Before you draw a box, pin down what it must do. Functional: given a long URL, return a short one; a click on the short one redirects to the long one; users may pick a custom alias (/spring); links may expire; the owner sees click counts.
Non-functional: redirects must be fast (a few milliseconds inside our walls) and almost never down, because a broken short link is a broken link in someone's tweet forever. Codes must be unique and short. Creating links can be a little slower and a little less available. Analytics may lag by minutes.
What you will learn
Requirements and numbers
- What are we building?: A URL shortener is two systems sharing one table: a rare write that has to invent a unique key, and a constant read that has to be fast and never down.
- The napkin: reads crush writes: Do the estimate to find the bottleneck, not to get the number right: here it says the read path is the whole problem and the write path is small.
- Drill: how long is a code?
API, data model, design
- The API: one POST, one GET: The create path is: get a unique number, encode it, write it with a conditional put. Uniqueness is guaranteed by the store's SET NX, not by hoping.
- The data model: one key, one value: Choose the store from the queries: a single-key lookup at huge scale wants a key-value store partitioned by that key.
- Follow one click: The redirect path reads the cache, falls back to the store, and fires the click event without waiting for it.
The redirect: 301 or 302
- Click it again: A 301 is cached by the browser for good: every later click is free for you and invisible to you.
- 302: every click comes home: 301 trades your analytics and your ability to change the link for less load; 302 pays a request per click to keep both.
Making the short code
- The single counter dies: A single ID service is a single point of failure for writes only: know which path each component sits on before you call it critical.
- Lease a block, lose a block: Leasing ID ranges takes the ID service off the hot path; the price is gaps when a server dies and codes that do not sort by time.
- Hash the URL instead: A hash makes the code a function of the URL: no coordination and free de-duplication, but codes collide, so every write must be conditional.
- Two characters, 120 links: Collisions start at about the square root of the code space, not near its size: 2.2 million links for 7 characters, 73 for 2.
- Random codes nobody can guess: If links can be private, codes must be unguessable: random draws with a conditional write, never a counter.
- Snowflake: a clock steps back: A Snowflake ID is only as good as the machine's clock: a clock that steps back stops ID generation on that machine until it catches up.
- A fast clock reorders IDs: IDs from many machines are roughly time-ordered at best: never use them to decide which of two events happened first.
- Drill: the conditional write
A link goes viral
- A link goes viral: Skewed popularity makes the cache, not the database, the thing that serves a viral link; the shard behind it barely notices.
- The click queue fills up: Fire-and-forget to a queue isolates the hot path from the slow path: when the slow side falls behind, it loses data, not availability.
Abuse and failure
- A shard goes down: A cache hides a dead shard only for the keys it already holds; every cold key on that shard is down until the shard, or a replica of it, answers.
- A bot floods the create endpoint: Limit the write path per client, at the edge: an abuser drains only its own bucket and never reaches the ID service or the store.
- Expired links: 410 Gone: An expiry is data, not a cache setting: check it on every read, including reads served from the cache.
- Custom aliases: 409 Conflict: A custom alias is just a key the user picked: the same conditional write decides it, and a loser gets 409.
Recap & playground
- Cheat sheet
- Playground