linkjobai revised this gist 5 days ago. Go to revision
1 file changed, 32 insertions
shortener.md(file created)
| @@ -0,0 +1,32 @@ | |||
| 1 | + | # System Design Interview: Designing a URL Shortener | |
| 2 | + | ||
| 3 | + | The URL shortener (think bit.ly) is a classic warm-up design question. Here's a structure that fits in 35 to 45 minutes. | |
| 4 | + | ||
| 5 | + | ## Requirements | |
| 6 | + | ||
| 7 | + | - Functional: create a short link for a long URL; redirect short to long; optional custom alias and expiry. | |
| 8 | + | - Non-functional: very read-heavy (often 100 reads per write), low-latency redirects, links must not collide. | |
| 9 | + | - Rough scale: 100M new links a month means about 40 writes a second and 4,000 reads a second. | |
| 10 | + | ||
| 11 | + | ## Generating the short key | |
| 12 | + | ||
| 13 | + | 1. **Counter + Base62:** a globally unique ID (database sequence, or a Snowflake-style ID) encoded in Base62. Seven characters give 62^7, about 3.5 trillion keys. Predictable, so add a shuffle if guessing links is a concern. | |
| 14 | + | 2. **Hash and truncate:** MD5 or SHA-256 of the URL, then take 7 characters. Needs collision handling (retry with a salt). | |
| 15 | + | 3. **Pre-generated key service:** a separate service hands out unused keys in batches; there's no collision check on the hot path. | |
| 16 | + | ||
| 17 | + | ## Storage and API | |
| 18 | + | ||
| 19 | + | - `POST /links {long_url}` returns `{short}`; `GET /{short}` returns a 301 or 302 redirect. | |
| 20 | + | - 301 is cached by browsers (less load, but you lose click analytics); 302 keeps every hit visible. | |
| 21 | + | - A key-value store (DynamoDB, Cassandra) keyed by the short code is a natural fit. | |
| 22 | + | ||
| 23 | + | ## Scaling reads | |
| 24 | + | ||
| 25 | + | Put a cache (Redis) in front of the database; a small fraction of links gets most of the traffic. Add a CDN or edge redirects for the hottest links. | |
| 26 | + | ||
| 27 | + | ## Extras to volunteer | |
| 28 | + | ||
| 29 | + | Analytics via an async event stream (Kafka), abuse and malware scanning on creation, and a TTL-based cleanup job for expired links. | |
| 30 | + | ||
| 31 | + | --- | |
| 32 | + | *Disclosure: I'm on the team behind [Linkjob AI](https://www.linkjob.ai/), an interview assistant.* | |
Newer
Older