Requirements

Functional Requirements:

1. System can create a unique short URL from a given URL.
2. Given a shorten URL, system can redirect the user back to the original URL.

Non-Functional Requirements:

1. System can redirect the user back to the original URL in under 100 ms.
2. System is available 99.99% of the time.
3. System must be handle to handle traffic spike by scaling horizontally.

Capacity Estimation

The system will have a read to write ratio of about 100 : 1 (read heavy).

Let's say there's about 1 billion user with 10% daily active users (100M).

A single user can request about 10 URL / day -> 1 billion request / day. This about 12000 QPS on average (and let's assume on peak it can be 2 - 3x.

Let's say to store a single URL can take up to 500 bytes. -> 10M * 500 bytes -> 2 TB / year

projection on YoY is about 10 %

API Design

1. API to create a short URL: POST / api/v1/urls (parameters: long URL, response short URLs)
   1. failed cases: 400 invalid input / URL, 409 for eisting short URL
   2. optionally can use custom short URL by sending as part of the request
   3. return 201 on success
2. API to read a short URL (redirect) GET /{shortUrl} (response is 301 to the original URL)
   1. return 404 on URL not found

High-Level Design

1. Load balancer, receive request and route the request to the correct healthy service

2. Shortener service. Handles short URL creation, interact with ID generator and DB and also store the store URL in cache

3. Redirect service, Get the mapping from cache, if not found fallback to Db

4. ID generator, generate a unique short URL from a given request. Generation logic: base 62 encoded from a incrementing id

5. DB, persistent later that store URL mapping

6. Cache, to reduce db load, store URL mapping

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

Table: URL mapping

Primary Key: short URL

Other columns:

Long url

Expires at

Created at

User id (optional)

Db choice: dynamo

Reason: support partition out of the box, horizontally scale

Consistency: consistent on create, eventual on read

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.

ID generator: generate unique ID using base62 of incrementing ID (initial ID seed stores in dynamo). With this there won't be any collision. If we support alias, we can check for collision and retry generation.Incrementing IDs are guessable, which we accept for simplicity; a more secure alternative is random codes with a collision check.

Cache: on read, we will store the retrieved mapping from DB in cache. The TTL in cache is set with jitter to avoid thundering herd. Hot codes are cached in Redis + served via CDN edge, so a viral link doesn't hammer the origin