Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• Users can create a short URL for a long URL (rate-limited).
• URLs need to be as short as possible.
• Users are redirected from short URLs to long URLs.
• No analytics.
• The short URLs are auto-generated.

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• Perf: Sub-100ms, ~50ms P50 for redirects
• Scale: 100M new short URLs created per day, links never expire, 10 years of unique URLs.
• Availability target: 99.95%+ for reads and 99.9% for writes
  • Writes are acceptable to be slightly less strict since creation tolerates retries

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

• Read:write ratio of 100:1
• Writes: ~1,200 QPS
• Reads: ~100K QPS average, plan for 2–3x peak (~300K QPS)
  • ~100K QPS × ~1 KB response ≈ ~1 Gbps outbound
  • Cache tier will be essential to handle/decouple read scale and minimize database load.
• Each mapping ~500 bytes (short code + long URL + timestamps + owner)
• 100 mil/day × 500 bytes = ~50 GB/day → ~18 TB/year → ~180 TB after 10 years
• 100M * 365 * 10 = 365 billion unique short URLs

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

POST /api/v1/shorten

• Req: { "long_url": "{}" }
• Res: { "short_url": "{}", "long_url": "{} }
• Errors: rate-limiting

GET /{short_url}

• Permanent redirect to the long URL.
  • Permanent redirect to reduce latency and load compared to a temporary redirect. If analytics or other features that require a temporary redirect are needed in the future, we can switch to using a temporary redirect then.
• Errors: rate-limiting, unknown short_url

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Create short URL

1. The client requests the creation of a short URL for a given long URL.
2. The load balancer balances the load across servers and enforces rate-limiting.
3. A short URL is generated and added to the database.
4. The short URL is returned to the client.

Get short URL

1. The client requests the long URL for a given short URL.
2. The server checks the cache for the short_url response.
   1. If found, returns the response immediately.
   2. If not found, the response is processed with following steps and then added to the cache.
3. The server checks the database for the short_url.
   1. If found, proceeds to the next step.
   2. Otherwise, a not found error is returned.
4. A perm. redirect to long_url is returned.

Short URL generation

• Length: 7 character since it would provide 62^7 ~= 3.5 trillion unique URLs which is plenty more than the 365 billion we need to support while 62^6 ~= 56 billion which would not be enough.
• ID generation: We will use a database-generated primary key with integer obfuscation (e.g. Squids) which will map a sequentially generated unique ID to an obfuscated 7 character base62 str.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

We'll use a SQL database for sequential primary key generation, and strong consistency. Use a distributed form of SQL so we can easily shard as needed. Distribute rows by hash(id). We'll use the following schema:

short_urls

• id: primary key, sequentially generated. The short URL is a Squid 1:1 mapping of the id onto 7 character width base62 strings, we can convert between id and short_url programmatically.
  • No secondary index needed to look up short_urls.
• long_url

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Short URL generation

We use sequential primary key generation from the SQL database to provide unique IDs for each short URL. To keep the underlying ID private, we obfuscate it via Squids with a salted alphabet. This will allow us to convert between the primary key ID and the short URL with a deterministic 1:1 mapping that is also only convertible by us.

Cache

We'll scale the cache layer based on read demand. We'll use a 2 day TTL and a LRU eviction policy. We will lazily load data into the cache; on cache miss, generate the response, then store it in the cache.