Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• 100M DAU
• Peak QPS: 10k writes, 100k reads
• Data storage: Petabytes of data
• Highly available
• Low latency (quick)

Notes:

• Eventual consistency is probably fine here
• Will want some caching layer for hot reads to protect database
• Want to ensure that when we generate a URL we don't have conflicts
• Want some caching layer to ensure we are close to the user for frequent lookups

Assumptions:

• No authentication for this design

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 /shortURL

Request body should contain:

• longURL

Response body should contain

• shortURL

GET /longURL/:shortURL

GET parameter is the shortURL ID

Response body should contain:

• longURL

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.

• Global CDN (something like Fastly) for edge caching, so frequent lookups are close to the user, to increase read latency. ShortURLs expire naturally, so we can rely on things falling out of an LRU style cache.
• Our core API which creates our shortURL and returns our longURL. We'll want to be able to scale this out to ensure redundancy. Enabling some autoscaling rules here may even be helpful.
• Our core API will be creating the shortURL. In order to do this, we will likely need to hash the longURL to create a fixed character string, and then also base62 encode it. This also ensures two of the same longURLs, uploaded by different users, will result in the same shortURL.
• Load balancer will sit between the Global CDN to route requests from the client to underlying servers. We can probably use relatively simple healthchecking for our underlying servers here, or we can get more sophisticated and try to load balance based on resource constraints. For this design, our API is probably going to be CPU constrained since it's computing the short URL and not storing much in memory, or waiting (I/O).
• Underlying database to store everything, SQL database here seems fine for our use case - something like MySQL. Our database table would have shortURL as a primary_key for easy lookups. One table is probably okay, but at petabytes of data we'll need multiple databases and a sharding strategy. For this, sharding by the created shortURL (which is unique) via a consistent sharding strategy will allow us to scale our database out.
• Metrics - we'll want to know when someone gets a longURL. Since writing a counter to a database can be tricky and slow things down, it's probably better to fire off a metric to a queue of some kind - maybe kafka - for processing later ("we saw a new event").
• We can make our DB more resilient to reads if we want with a key value cache layer like Redis. With 100k RPS this is probably a good idea.

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.