### Functional:

1. Users input long URLs and the system returns short URLs (long URL to short URL must be 1:1)

2. Users click short URLs and the system redirects to corresponded long URLs

3. **APIs for conversations between short URLs and long URLs**

### Non-Functional:

1. **High availability**

2. **Low latency**

3. **High scalability (system and storage)**

## Capacity estimation

DAU: 1M users; write 1 url/user on average, read 10 url/user on average

Read QPS: 1M * 10 / 10**5 = 100

Write QPS: 1M / 10**5 = 10

Read Peak QPS: ~300

Storage: 1M * 10 * 100B = 1GB per day, 365GB per year, 1.5T for 5 years

## API design

Read: GET /

Write: POST /api/shorten

## Database design

User Table:

-  user\_uuid (primary key)

-  username

-  email

-  password

-  register\_at

Short URL Table:

-  short URL (primary key) (create index)

-  long URL (create index)

-  created\_by (user\_uuid)

-  create\_at

## High-level design

Several components:

Memcached for read operation enhancement.

The Lookup Service looks up whether a long URL exists in DB and will directly return the corresponded short URL to the user. If not, then insert a new long to short URL table entry and cache it aside.

The Redirection Service looks up whether the given short URL exists and will return the related long URL to the user. If not, throw a webpage error.

## Request flows

Same as above.

## Detailed component design

Each component is **a macro service** and contains several machines and are **distributed**. For example, Memcached, NoSQL database here are all distributed systems. This can prevent single point failure causing huge losses and multiple replica can help recover failed components.

The Lookup Service contains a short URL ID generator. We use Base62 as the encoding method. If a non-existed long URL comes, the system uses MD5 to encode (the long URL ++ the current time stamp). Since we want the short URL has a total of 7 characters, so in total this can represent 62\*\*7 different short URLs. We convert the MD5 hex result to Base62 and only take the last 7 characters. If there exists such short URL already we retry the process. After generating the short URL, we use distributed locks to atomically update the database.

When a request comes, there would be a **load balancer** first to balance the QPS and dispatch the QPS to different servers. Also, **in-between servers and Memcached/DB layers, we also need load balancers**.

## Trade offs/Tech choices

1. 1. NoSQL vs SQL: in this question our QPS is low so SQL could handle. However, we may need to write sharding logic on our own, deal with distributed logic on our own, etc. We choose NoSQL like MongoDB here since we may have to scale (becomes a distributed service, sharding horizontally, etc.)

## Failure scenarios/bottlenecks

1. **Single point failure**: each critical component are distributed to reduce the loss of single point failures.

2. If the **QPS gradually increases over time**, we may use LRU cache mechanism to cache frequently used short URLs and frequently added long URLs in the cache system. (long tail distribution in the URL usage) Also, add more machines to the places that bottleneck happens.

3. **Horizontally sharding the tables** in the database into different nodes can reduce the QPS on a single point.

4. **Use CDN** to cache the requested URLs/resources to speed up.

## Future improvements

1. **If the QPS suddenly spikes: we need to ensure the scalability and load balancing of the service can quickly respond to the surge of QPS: we can utilize the automatic scaling feature of cloud services to automatically add/reduce server instances based on traffic, and dispatch the requests evenly across the server instances using load balancers.**