System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. Shorten a long URL to a unique short URL.
   1. To support unique short URLs, we can consider hash function or auto commit IDs to ensure no duplicated short URLs.
2. Convert a short URL to the corresponding long URL.
3. (Optional) User features. For example, login user account, user can manage URLs (view historical URLs, delete).
4. (Optional) enable expiry date of the URL shortening, that way, we can release resources and save costs.

Non-Functional:

List non-functional requirements for the system...

1. Latency: generating unique short URL and redirecting to original long URL should be of low latency.
   1. Data storage with store the mapping between long URL and short URL should be designed for quick lookups.
2. Availibility: avoid down time.
   1. Monitoring and logging: monitor APIs TPS, latency p99 alarms, and so on.
   2. Disaster recovery strategy: besides manually fixing the server, we can set up health check in load balancer.
   3. API rate limiting per user to avoid overload.
3. Scalability: database and server should handle high traffic, without performance degradation.
   1. As for read operations, we can consider caching system to improve the read performance.
   2. As for write operations, we need to generate short URLs quickly and check duplicates quickly. As for generating short URLs quickly is to run hash functions over long URL, and we can also generate auto commit ID (hash function) for short URL.

Capacity estimation

Estimate the scale of the system you are going to design...

Assume we are supporting 1 million users, and each user create 5 short URLs per day, and read 10 times each per day in average.

We need 1.8 billion short URLs per year. Short URLs contain a-zA-Z0-9 charactors, 62 chars.

To support 10 years short URLs, we need 1M*5*365 = 1.8B short URLs per year, so we need at least 6 bytes length short URL (62^x > 1.8B * 10).

We need 6*1.8B = 10GB database. Also add 20% buffer for metadata and potential higher traffic.

API design

Define what APIs are expected from the system...

1. Shorten a long URL to a short URL.
   1. Post https://tinyurl.servername.com/v1/shorten, JSON {longurl: xxx}
   2. Response status codes:
   3. 200 OK
   4. 400 invalid argument / Bad request
   5. 503 server error
2. Convert a short URL to a long URL.
   1. Get https://tinyurl.servername.com/v1/expand?shorturl=xxx
   2. Response status code 302 with the corresponding long URL.
3. (Optional) User register.
   1. Post https://tinyurl.servername.com/v1/register, JSON {user: xxx,password:yyy,email:zzz}
4. (Optional) User login.
   1. Get https://tinyurl.servername.com/v1/login, JSON {user: xxx,password:yyy}
   2. 200 OK login
   3. 401 wrong password / user
5. (Optional) User check historical URL mapping.
   1. Get https://tinyurl.servername.com/v1/historyUrls
   2. response JSON {status: 200, data: {historicalURLs: [{longURL: xyz, shortURL: zyx}]}}
6. (Optional) User (bulk) delete a URL mapping.
   1. Delete https://tinyurl.servername.com/v1/Urls, JSON {status: 200, data:[longURL: xyz, shortURL: zyx]}

We can support IP based rate limiting, even before user login. After user login, server can also throttle excessive requests per user, that way, it avoid single user degrade the experience of others.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

non relational database provides fast lookup, easy scalability. There are trade-offs: when we have user data and analysis data, we will introduce complicated queries including sorting users by high click count, and so on; then we may consider relational database to handle complex queries, and ensure consistency.

Here is an example if we choose non-relational database.

1. long url short url mapping data:
   1. keys: longUrl, shortUrl, user (guest or user1), index
   2. shortUrl must be unique.
   3. index (hash) can help to retrieve and write quickly.
2. (optional) analysis data:
   1. keys: userID, shortURL, click count

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

client -> load balancer -> server -> database

1. Cache system. Based on click count, cache the most frequent used short URL and long URL mapping. It will improve latency of redirecting API.
2. We can also use microservices, separate services for different APIs, e.g. shortening API, redirecting (converting short URL to long URL) API, and have L7 load balancer. That way, we will separate write / read intensive APIs, and it will help with scalability (each server can scale independently based on needs).

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?