Design a URL shortener

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

We assume 5 million new links a day. That is 5,000,000 / 86,400 = 58 new links per second on average.

Traffic is not flat over a day. We take a peak factor of 2.2: the busiest time of day carries 2.2 times the average.

58 x 2.2 = 127, so we plan for 125 new links per second.

Bitly's own figures give 6 to 16 clicks per link. We take 7, so clicks are 125 x 7 = 875 per second at peak.

We measure load in requests per second: 875 clicks + 125 new links = 1,000. Clicks are 87.5% of the load, and each click is a read.

Bandwidth is small: 1,000 requests x 1 KB = 1 MB per second, plus a few KB to open each new connection.

It limits nothing in this problem, but we pay for every byte we send.

Storage per link: a 7-byte code, a long URL of about 100 bytes, the owner and two times. That is about 150 bytes.

DynamoDB, the table we use, adds 100 bytes per item for its index. So each link takes 250 bytes.

Storage per year: 5 million x 365 = 1.825 billion links. At 250 bytes each, that is 456 GB, or 425 GiB.

Code length: a base62 code uses 0 to 9, a to z and A to Z, so each position has 62 choices.

Six characters give 62^6 = 56.8 billion codes. Seven give 62^7 = 3.52 trillion.

At ten times the load, we make 18.25 billion links a year. Six characters run out in about 3 years, and seven last about 190 years. So we use 7.

Per task: each copy of the Link service is a task with one vCPU, a virtual processor.

A task spends about 2 ms of CPU on a request, so it serves 1,000 / 2 = 500 requests per second.

We keep each task near 70% busy, which leaves room for a burst. So we count 350 requests per second per task.

Per item: DynamoDB sells capacity in read capacity units (RCU) and write capacity units (WCU), each per second.

A click is an eventually consistent read: it may miss a write from the last second, and it costs 0.5 RCU. So 1 RCU serves 2 clicks per second.

A new link is a write of under 1 KB, which costs 1 WCU.

One item takes at most 3,000 RCU and 1,000 WCU per second, however many units the table has. So one link serves at most 6,000 clicks per second from the table.

Check in: Close the page and derive 1,000 requests per second from 5 million links a day. Say each line out loud.

Start with one service and one table

If we draw caches and queues first, we cannot say what each one fixes. The interviewer asks why a box is there, and we have no answer.

We start with a load balancer, one service and two DynamoDB tables. The Link service takes every request.

A click is one lookup in the Links table by its code. The service answers 302, which tells the browser where to go. We come back to why 302, and not 301.

A new link adds 1 to the ID counter, a table with one item. The service turns the new number into a 7-character code and saves the link.

A redirect is one lookup by one key, so a key-value table fits. We need no joins and no queries across links.

We use provisioned capacity: we buy a fixed number of units per second, and we pay for them used or not.

Reads: 875 clicks x 0.5 = 437.5 RCU. We aim for 70% use at peak, so 437.5 / 0.7 = 625 RCU.

Writes: 125 new links x 1 = 125 WCU. 125 / 0.7 = 179, so 180 WCU.

The ID counter gets the same 125 writes per second, all on its one item. It gets 180 WCU too, and one item allows 1,000.

The Link service uses auto-scaling: it adds tasks as load grows. 1,000 / 350 = 2.9, so 3 tasks run.

Stage 1 runs this design in SysPad at 1,000 requests per second. Each card is a part of the system, and each arrow carries requests.

Read the four tiles of Stage 1. "First to saturate" reads "Nothing at this load".

A part saturates when it gets more requests than it can serve. The tile's note names the busiest part: the Links table, at 70%.

The latency tile shows 6ms for the slowest path. That is 1.5 ms in the load balancer, 2 ms in the service and 2 ms in the table.

The sum is 5.5 ms, inside our 10 ms target.

The cost tile shows $1,583 per month. It prices the peak load as if it ran all month, so real bills are lower. We compare stages, not totals.

$988 of it, 62%, is egress: data sent out of AWS to the internet, here our replies to browsers. AWS bills it per GB, after 100 GB a month free.

The 302 itself is about 0.5 KB. But most clicks open a new connection, so the server also sends its TLS handshake, the setup for encryption: about 4 KB more.

So a click sends about 4.5 KB, and many small requests pay mostly for handshakes. A browser that resumes an earlier session sends about 0.5 KB.

Press 1,500. The Links table and the ID counter both saturate.

The 70% target buys 43% of headroom, because 1 / 0.7 = 1.43. The table runs out near 1,430 requests per second, and the counter near 1,440.

The trade-off:

We pay for every unit we buy, used or not. At peak, 30% of them sit idle, and that is our headroom.

Stage 1: One service and one table, 1,000 requests per second

• Load: 1,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $1,583/mo

Check in: Say how you got 625 read units. Start from 875 clicks per second.

Ten times the traffic

The interviewer asks: Traffic grows ten times, to 10,000 requests per second. What breaks first?

Press 1,000 on Stage 2, then press 10,000. The design is the same. Only the load changes.

At 10,000, two cards turn red: the Links table and the ID counter.

The latency tile now shows "≥" before the number. Past saturation, SysPad can give only a lower limit for latency.

Read the warnings under the canvas. Each red card has its own lines, and the two cards fail for different reasons.

The Links table is short of units we bought. Clicks ask for 4,375 RCU against 625, and new links ask for 1,250 WCU against 180.

That is money. If we buy more units, the table is fine.

DynamoDB splits a table into partitions. One item lives in one partition, and a partition takes at most 1,000 WCU per second.

The ID counter has the same write warning, plus a line about a hot partition: one partition asked for more than it takes.

The counter is one item. Every new link writes it, so it gets 1,250 writes per second against 1,000.

Buying more write units does not help. The item stays in one partition, and the partition stays at 1,000.

The Link service is not the problem. Auto-scaling runs 29 tasks, because 10,000 / 350 = 28.6.

The trade-off:

Two red cards need two different fixes. The table needs money. The counter needs a change of design.

Stage 2: The same design at 10,000 requests per second

• Load: 10,000 req/sec
• First to saturate: Links table
• Estimated cost: $11k/mo

• Latency past saturation is a lower bound, not an estimate. Links table is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Links table: Read capacity 700% used (provisioned): 4375 of 625 RCU/s at 10000 RPS.
• Links table: Write capacity 694% used (provisioned): 1250 of 180 WCU/s at 10000 RPS.
• ID counter: Write capacity 694% used (provisioned): 1250 of 180 WCU/s at 1250 RPS.
• ID counter: Hot-partition write throttling: hottest key draws 1250 WCU/s, above the 1000 WCU/s per-partition ceiling.

Check in: With 10,000 pressed, choose "Open in SysPad". Set the ID counter to 2,000 write capacity units and press Simulate. Say why it stays red.

Buy units for the table, lease IDs for the counter

The table is short of something we can buy. The counter is short of something we cannot: one item takes 1,000 writes per second, ever.

For the table, we buy units. Reads: 8,750 clicks x 0.5 = 4,375 RCU. At 70%, that is 6,250 RCU.

Writes: 1,250 / 0.7 = 1,786, so 1,800 WCU. Storage is one year at the new rate: 4,250 GiB.

For the counter, we change the design. We use an ID lease: each task takes a block of 1,000 IDs with one write.

The write adds 1,000 to the counter and returns the new value. The task owns the 1,000 IDs up to that value and hands them out from memory.

The counter now gets 1,250 / 1,000 = 1.25 writes per second. We give it 5 WCU.

Step through the figure to see the lease.

Counter IDs come in order, so codes from them are easy to guess. So we pass each ID through a fixed shuffle before we encode it.

The shuffle multiplies by a large number that shares no factor with 62, modulo 62^7. Each ID still gets its own code, and the codes no longer look like a sequence.

A task that restarts loses the rest of its block. That wastes at most 1,000 IDs out of 3.52 trillion.

Press 10,000 on Stage 3. Nothing saturates. The cost tile shows $14k per month.

Press 15,000. The Links table saturates on reads, near 14,300. That wall is money again: more read units move it.

From here to 100,000 requests per second, nothing new breaks. Every wall is a number we buy.

The trade-off:

Writes are 12.5% of requests but 34% of the table bill. A write unit costs 5 times a read unit, and a click costs half a read unit.

So per operation, a new link costs 10 times a click.

Storage is the biggest line on the table bill, 43%, and it grows every year. That is the case for expiry.

A cache now would save $527 a month in read units and cost $503. It pays for itself and little more. The next twist gives a better reason.

Leasing IDs in blocks

1. Every new link adds 1 to the same item. At 1,250 new links a second, one item gets more writes than it takes.
2. Task A adds 1,000 with one write. It now owns the 1,000 IDs up to the new value.
3. Each new link takes the next ID from memory. The counter sees no traffic.
4. Every task leases its own block, so no two tasks share an ID. The counter gets 1.25 writes a second.
5. A fixed one-to-one shuffle hides the order before encoding. Codes stay unique and stop being easy to guess.
6. A task that crashes loses the rest of its block. That wastes at most 1,000 IDs out of 3.52 trillion.

Stage 3: More units for the table, leased ID blocks for the counter

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $14k/mo

Check in: Say why buying more write units cannot fix the ID counter. Use one number.

One link, one item, one ceiling

The interviewer asks: A link goes viral. It draws 10,000 clicks per second for an hour. What breaks?

This is a modest spike. Coinbase's 2022 Super Bowl QR ad drew over 20 million hits in one minute, about 333,000 per second.

The load is 8,750 normal clicks + 10,000 viral clicks + 1,250 new links = 20,000 requests per second.

The viral link is 10,000 of 18,750 clicks, or 53% of all reads.

Stage 4 shows the event an hour in. Auto-scaling has raised the table to 14,000 RCU: 9,375 RCU of clicks / 0.7, rounded up.

At 20,000, "First to saturate" names the Links table.

Read the warnings under the canvas. None says the table is short of read units: it uses 9,375 of its 14,000 RCU, or 67%.

The warning names a hot partition. The hottest key draws 5,000 RCU per second, above the 3,000 that one partition serves.

That key is the viral link. 10,000 clicks x 0.5 RCU = 5,000 RCU, all on one item.

The table has room. One item does not. DynamoDB can give a hot item a partition of its own, but no partition serves more than 3,000 RCU.

So one link can serve at most 6,000 clicks per second from the table.

Press 10,000. A preset scales the whole load, so the viral link falls to 5,000 clicks per second. That is 2,500 RCU, and it fits.

The wall is at 12,000 requests per second, where the viral link makes 6,000 clicks per second.

The first minutes of the spike, before auto-scaling catches up, are a design fact we reason about. The one-item ceiling holds in every minute.

Step through the figure to see why more units do not help.

The trade-off:

Provisioning 40,000 RCU changes nothing here. We would pay for units that the hot item cannot use.

The cost tile shows $23k per month, and the system still fails on the one link that matters most.

One item, one ceiling

1. Normal clicks go to many links, so they spread over many partitions. The table has 14,000 read units.
2. The viral link is one item, so all its clicks go to one partition. It needs 5,000 read units, and a partition serves 3,000.
3. More read units add room to the table. The one item still gets at most 3,000.
4. A cache answers the viral link from memory. Only 875 misses a second reach the table.

Stage 4: One link goes viral, 20,000 requests per second

• Load: 20,000 req/sec
• First to saturate: Links table
• Estimated cost: $23k/mo

• Latency past saturation is a lower bound, not an estimate. Links table is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Links table: Hot-partition read throttling: hottest key draws 5000 RCU/s, above the 3000 RCU/s per-partition ceiling.

Check in: With 20,000 pressed, choose "Open in SysPad". Set the Links table to 40,000 read capacity units and press Simulate. Say why it stays red.

Serve the hot link from memory

The viral link needs 5,000 RCU, and its item gets 3,000. Most clicks must stop before they reach the table.

We put a Link cache in front of the table. It is Valkey, an in-memory key-value store, on one cache.r7g.xlarge node and one replica.

Memory sets the size. We cache every link made or clicked in the last day: 50 million new links + about 25 million older ones.

75 million entries x 200 bytes = 15 GB. One node has 26.32 GiB, and 19.7 GiB is usable after the default 25% reserve. So one node fits.

The hit rate is the share of lookups the cache answers itself. Normal clicks hit 90%, because most clicks go to links a few hours old.

Bitly found that a popular link gets half its clicks in about 3 hours.

The viral link always hits. Blended: (8,750 x 0.9 + 10,000) / 18,750 = 95.33%.

A cache miss goes on to the table. Misses are 10% of normal clicks: 875 per second.

When we save a new link, we also put it in the cache, so its first click does not miss.

The table now sees 875 misses + 1,250 new links = 2,125 requests per second.

Reads need 875 x 0.5 = 437.5 RCU, and at 70% that is 625. We round up to 700.

Press 20,000 on Stage 5. Nothing saturates. The cost tile shows $22k per month, against $23k on Stage 4.

Read units fall from 14,000 to 700, which saves $1,244.88 a month. The cache costs $503.42, so this bill is about $741 lower.

The latency tile shows 6ms. It shows the slowest path, and it counts each step by the share of requests that take it.

A create is now the slowest path: 1.5 + 2 + 2 = 5.5 ms in the load balancer, the service and the table.

Only 4.67% of clicks miss and go on to the table, because 100% - 95.33% = 4.67%.

So the tile counts a click as 1.5 + 2 + 0.2 + 0.0467 x 2 = 3.79 ms.

By hand, a hit takes 1.5 + 2 + 0.2 = 3.7 ms, and a miss asks the cache, then the table: 5.7 ms.

One miss takes longer than one create, but few clicks miss. All of these are inside our 10 ms target.

Press 30,000. The Links table saturates again, this time on writes. 30,000 x 6.25% = 1,875 new links per second, against 1,800 WCU.

That wall is at 28,800, and it is money again.

In the news feed problem, a cache failed because each key belonged to one user. Here many clicks ask for one key, so the cache works.

The trade-off:

The cache costs $503 a month and removes 13,300 RCU.

A cache cuts reads, not replies. Every click still gets its 1 KB reply, so egress is $15,010 a month on both stages, about 67% of this bill.

It is one more part that can fail. If it goes down, every click reads the table again. The last beat gives the numbers.

A link never changes after we make it, so a cached link is never stale. A delete must also remove the cache key.

Stage 5: A link cache in front of the table

• Load: 20,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $22k/mo

Check in: Say why this cache works when the news feed cache did not. Use the hit rate in your answer.

Count every click with one write

The interviewer asks: Marketing wants click counts per link per day. How do you add them?

The first answer most people give: a Click counts table with one item per link per day. Each click adds 1, and the redirect waits for the write.

Write units: 18,750 clicks / 0.7 = 26,786, so 27,000 WCU. 100 RCU serve the stats page.

Storage: 75 million items a day x about 130 bytes = 9.75 GB a day, or about 300 GiB a month.

Press 20,000 on Stage 6. "First to saturate" names Click counts.

Read the warnings under the canvas. The hottest key draws 10,000 WCU per second, against 1,000 for one partition. That key is the viral link's count for today.

Press 1,500. A preset scales the whole load, so the viral link makes 750 clicks per second. Its item keeps up.

The wall is at 2,000 requests per second, where the viral link makes 1,000 clicks per second. That is all one item takes.

At 20,000, the cost tile shows $35k per month. Click counts alone cost $12,720. Everything else is the Stage 5 design, at $22,329.

One write per event costs one write unit per event. And an event on a hot key is a write to a hot item. Both problems have one cause.

The trade-off:

Counting clicks this way costs 1.7 times all the other parts we run together, $12,720 against $7,319. It still fails on the link that gets the most clicks.

Stage 6: Count every click with one write

• Load: 20,000 req/sec
• First to saturate: Click counts
• Estimated cost: $35k/mo

• Latency past saturation is a lower bound, not an estimate. Click counts is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Click counts: Hot-partition write throttling: hottest key draws 10000 WCU/s, above the 1000 WCU/s per-partition ceiling.

Check in: Name the two problems with one write per click. Give a number for each.

Take counting off the redirect, and batch it

We still need every click counted. But the redirect should not wait for it, and the viral link must not land on one item.

Each Link service task keeps click events in memory. Every 100 clicks, it sends one record to a stream and does not wait.

A stream is an ordered log that other services read later. We use Kinesis.

18,750 clicks / 100 = 187.5 records per second. Each record is 100 clicks x 200 bytes = 20 KB.

A stream is split into shards. One shard takes 1 MB or 1,000 records per second.

187.5 records x 20 KB = 3.75 MB per second. At 70%, that needs 3.75 / 0.7 = 5.4 shards, so we use 6.

Each record gets a random partition key, the value that picks its shard. So the viral link spreads over all 6 shards.

The Click loader reads the stream and unpacks each record into 100 rows. It inserts 10,000 rows at a time: 1.875 inserts per second.

The Click store is ClickHouse, a columnar store. It keeps each column together, so counting a day of clicks reads only the columns it needs.

It takes 350 million clicks a day x about 30 bytes = 10.5 GB a day, or 3.8 TB a year. Two nodes each keep a full copy.

Press 20,000 on Stage 7. Nothing saturates. The cost tile shows $24k per month.

Counting now costs $1,351 a month. One write per click cost $12,720.

The latency tile still shows 6ms, the 5.5 ms of a create. The service does not wait for the stream, so the stream is not on the path.

Press 2,500, a load that one write per click could not carry. Nothing saturates.

Press 30,000. The Links table saturates on writes, as it did in Stage 5.

Two design facts we reason about by hand. If the key were the link code, the viral link would put 100 records x 20 KB = 2 MB per second on one shard.

A shard takes 1 MB per second, so half of those records would fail. A random key avoids it.

Lag: 18,750 clicks / 58 tasks = 323 per task per second, so a buffer of 100 fills in 0.3 seconds. The loader fills 10,000 rows in about 1 second.

So counts are about 2 seconds behind. At quiet times, a 5-second timer sends a buffer that is not yet full.

Step through the figure to follow the clicks.

The trade-off:

Counts are seconds behind, and a crashed task loses up to 100 clicks. At one crash a minute, that is under 0.001% of clicks.

A click is a count, not money, so we accept both. We pay with three more parts to run.

Clicks in batches

1. Each click writes its link's count. The viral item gets 10,000 writes a second against a limit of 1,000.
2. Each task keeps clicks in memory. Every 100 clicks, it sends one record and does not wait.
3. Each record gets a random key, so the viral link spreads over all 6 shards.
4. Keyed by link code, the viral link puts 2 MB a second on one shard. A shard takes 1 MB, so half would fail.
5. The loader inserts 10,000 rows at a time. The click store takes about 2 inserts a second, not 18,750 writes.
6. A count is about 2 seconds behind. A crashed task loses at most 100 clicks.

Stage 7: Clicks go to a stream, then in bulk to a click store

• Load: 20,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $24k/mo

The questions with no load story

The interviewer asks: Walk me through the API and the data model. How do you make the codes?

None of these parts breaks under load, so no stage is about them. An interviewer asks about every one, so we answer each in a line or two.

Create: POST /api/v1/links with the long URL, an optional alias and an optional expiry. It returns 201 Created with the code and the short URL.

Create can fail in four ways. 400 means a bad URL, and 409 means the alias is taken.

It returns 422 for a URL on a blocklist, and 429 when a caller sends too many requests.

The client sends an idempotency key with each create. If it retries, it gets the same link back, not a second one.

Redirect: GET /{code} returns 302 Found, with the long URL in the Location header. An unknown code gets 404. An expired or deleted link gets 410 Gone.

Stats: GET /api/v1/links/{code}/stats returns daily counts, or 403 if the caller does not own the link. Delete returns 204.

Why 302 and not 301: a browser may cache a 301 even when we state no expiry. A 302 is cached only if the response says so.

With 301, a second click from that browser may never reach us. That cuts load, but the count is wrong.

Worse, expiry, delete and abuse takedown stop working for that browser. Analytics is a requirement, so we answer 302.

A 301 with a short max-age header is a middle road, if the interviewer pushes on load.

Data: the Links table is keyed by the code. Each item holds the long URL, the owner, the created time and the expiry time.

The ID counter is one item that holds the next number. One write adds 1,000 and returns the new value.

Owners see their own links through a secondary index on owner. It costs one more write unit per new link: about $842 a month at 10,000 requests per second.

The click store keeps one row per click: code, time, country, referrer and device. A rollup view keeps the count for each code and day.

IDs: we chose a counter with leased blocks. It gives the shortest codes, needs no collision check, and writes the counter once per 1,000 links.

A hash of the URL gives the same code for the same URL, with no counter. But two owners of one URL then share stats, unless we mix in the owner.

Random 7-character codes need no counter and are hard to guess. Hashes and random codes can both collide.

A new code collides with a chance of (links stored) / 62^7. After one year at ten times the load, that is 18.25 billion / 3.52 trillion = 0.52%.

So 1 create in 192 must retry, and after five years 2.6% do. Each try is a conditional write: it succeeds only if the code is free.

A failed conditional write still costs its write unit.

A table of keys made in advance also avoids collisions. But it is a second table to fill and guard, and leased blocks do the same job with one item.

Custom aliases use the same conditional write, and a clash returns 409. Aliases have 8 or more characters or a dash, so they never match a counter code.

Expiry: DynamoDB TTL deletes expired items in the background, and those deletes use no write units.

Storage at ten times the load costs $1,063 a month after one year, and it grows. A default expiry for anonymous links caps it, say 2 years with no clicks.

The trade-off:

Each choice here has a price we can name. 302 costs us load, the counter needs a shuffle to hide its order, and the owner index costs $842 a month.

Check in: Say why the answer is 302 and not 301. Name two things a 301 breaks.

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, what a user sees, and how stale the data can get.

The Link cache primary dies. The replica takes over in seconds. Until then, every click reads the table.

At 20,000 requests per second, that is 9,375 RCU against 700. The viral item needs 5,000 RCU against 3,000.

So we keep the replica, and each task holds the hottest few thousand links in its own memory. That also covers a full cache outage.

The ID counter is throttled or down. Each task still holds a block. At 10,000 requests per second, 29 tasks share 1,250 new links a second.

So a block of 1,000 lasts about 23 seconds. We fetch the next block when half is used, or lease 10,000 for minutes of cover.

The click pipeline is down. Redirects do not notice, because they do not wait for it. The stream keeps 24 hours, and the loader catches up.

Two more to name: scripts that walk codes to find private links, and long URLs that point to phishing pages.

Rate limits and the shuffle answer the first. A blocklist check on create answers the second, with a 422.

Consistency: a link is written once, then only deleted or expired. So caching it is safe.

A delete removes the cache key, and a 24-hour expiry on each cache entry is the backstop.

A read right after create may miss a link made under a second ago. Before we answer 404, we do one strongly consistent read, which sees every write, for 1 RCU.

Click counts are about 2 seconds behind, and a crash can lose up to 100 clicks. We say both out loud.

Minutes 0 to 5: requirements. Create, redirect, aliases, expiry and analytics. Ask the scale.

Minutes 5 to 10: the numbers. 125 new links and 875 clicks per second, 425 GiB a year, and 7 characters.

Minutes 10 to 15: the API with its status codes, 302 and not 301, and the data model.

Minutes 15 to 22: one service and one table on the board. Size the table in read and write units.

Minutes 22 to 28: ten times the load. Buy units for the table, and lease ID blocks for the counter.

Minutes 28 to 35: a viral link. Name the one-item ceiling, then add the cache with the working for its hit rate.

Minutes 35 to 41: analytics. Stream, batch, columnar store, and why not one write per click.

Minutes 41 to 45: what fails, and what you would do next.

The trade-off:

Each answer to a failure has a price. The replica is half the cache bill. A bigger ID block wastes more IDs when a task crashes.

Counts that are best effort can lose clicks, and we say so before the interviewer asks.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.