System requirements

Functional:

1. URL shortening: given a normal url, the service returns a unique shortned URL.
2. URL retrieving: given a shortened url, the service returns/redirects to the original url.
3. Let the user choose URL expiration? Or set 30-days expiration.

Non-Functional:

List non-functional requirements for the system...

1. millions of input urls per day (write request)
2. hundred millions of url retrieving per day (read request)
3. high availability/scalability
4. high consistency (no confliction for concurrent shortening requests, the same url is mapped to the same shortened url and vice versa)

Capacity estimation

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

10 million URL shortening per day, write request is 100 QPS

100 million URL retrieval per day, read request is 1000 QPS

One entry (long url, short url), 100B

10^7 * 100B = 1GB per day, 365GB per year, 3.65TB per 10 years

If URL has 30-days expiration, then it is 30GB per month.

3.65B URLs per year, if using base-64 encoding, 6-7 digits.

API design

Define what APIs are expected from the system...

REST api:

POST $originalUrl

GET $shortUrl

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

The data structure is key-value pairs. So we should use no-sql database. Redis or dynamo. If expiration is 30 days, can use Redis without a DB.

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

DNS

Load Balancer

Proxy servers to redirect to write or read server, also optionally rate-limiting and user authentication.

write servers:

1. generate short URL based on original URL and write to DB
2. optional: if original URL already exists, return that short URL directly. If short URLs are not shared by users, then this detection is not needed.

read servers:

1. Check if short URL (key) exists in cache, if so, return
2. Otherwise, read from Database.
3. If not exists in DB, return invalid request to client.

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

Write flow:

1. client requests from DNS to get server address.
2. client sends URL shortening request to load balancer/reverse proxy
3. Request is directed to one of the write servers. Write server generate unique shortened URL, saves (shortened URL -> original URL) to key-value store, returns shortened URL to client. Also notify client to cache result (assume key-value pair is immutable)
4. Error handling

Read flow:

1. client requests from DNS to get server address.
2. client sends URL shortening request to load balancer/reverse proxy
3. Request is directed to one of the read servers. Read server first consult in-memory cache (Redis) to get the original URL, if cache miss, query from DB and returns it to client.
4. If shortened URL doesn't exists in DB, returns invalid URL to client.

Analytics flow:

1. Any read or write request is also sent to analytics server as an event. Then it is stored in the data warehouse as raw event log. Further processing on the raw data is done to generate usage metrics.

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

URL shortening algorithm:

1. Option1: MD5 hashing: 128-bit (16 bytes)
   1. collision resolution (more hashing)
   2. generated URL is longer compared to option 2
2. Option2: auto-incrementing counter with base-64 encoding (7 chars)
   1. generated URL is shorter
   2. If using multiple write servers, need to resolve conflict

Write server:

1. Option 1- single write server. Write request is 100 QPS. So a single server can handle all traffic. To avoid single point of failure, can have a back-up server or fail over to any read servers
2. Option 2- multiple write servers. Can handle traffic separately. No single point failure. But may need to resolve write conflicts.
3. Given the QPS, we should use option 1

Read servers/cache/database:

1. add caches to improve read request latency
2. given the volumn, can use in-memory cache. Cache should be LRU-evicted.
3. database can push newly added URLs to cache through message queues

Trade offs/Tech choices

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

1. single write server with back-up server: single server is enough to handle write traffic. It provides trivial consistency (no need to resolve write conflicts)
2. auto-increment counter with base-64 encoding for URL shortening algorithm. Generated URL is shorter. Easier to implement. Work with single write server.

Failure scenarios/bottlenecks

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

1. Add load balancer to split traffic to different reverse proxies, servers to handle high read traffic
2. If writer server is down, fail over to back-up server.
3. If read server is down, use another read server
4. Database should be key-value pair based Redis servers which handles replication/partition automatically

Future improvements

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

Already mentioned how to resolve failure/bottlenecks in the last section. We could add some more user customization functions, e.g., set custom expiration for each URL, manage user owned URL list.