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:

• Low latency
• Scalable
• High Availability

Capacity Estimation

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

• 100 million DAU
• High read/write ratio. For every URL that is created, it will be read many times. Let's assume average 100 reads per write: 100/1
• Storage requirements: 100 million DAU * an estimate of 5 URLs per user = 500 million urls per day. Storage involves mapping a short url to a long one = storing both. So let's say the short url is 12 characters and the long one could be 64 characters. So 76 characters = 76 bytes roughly 75 * 500 million = 37.5GB per day = after one year we need 37.5 * 365 = 13.7TB. This is entering the order in which sharding may be necessary (10s of TB)
• Growth: Let's estimate 1 million users per day = 365 million users per year.
• Bandwidth: 100 million DAU * ?
• QPS ?

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/long-urls

body {

"longUrl": string

}

GET /api/long-url/[shortUrl]

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.

Load balancer sits in front of the server, after the CDN. It routes traffic between multiple servers. Use a Level 7 load balancer here to route traffic intelligently.

The server itself handles API routes for GET and POST.

• GET checks if the cache contains the URL and if not, fetches directly from the server, and updates the cache. Otherwise, fetches from the Redis cache.
• POST writes directly to the database. The ID is the short url. It is computed by hashing the URL, and then encoding it in a high base (e.g. base62)

45GB/day means that database sharding will be required.

Consistent hashing on the URL's database ID to partition shards?

CDN can actually cache the response to /api/[shortUrl] since it never changes!

Given the high read/write ratio, we are optimizing for high-read count here. This means: Caching! So, a redis cache sits in front of our database and caches responses to requests for any given URL, with the short url as the hash key, and the long url as the hash value in each KV string. Since the URL mappings never change, and extremely long TTL can be used. Maybe lazy-caching since some URLs may never be used and we don't want to overfill the cache.

Due to the nature of this system, some URLs will be read far, far more than others, with some extremely hot paths. This means that we need to optimize for hot-read-paths.

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...

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.