System requirements

Functional:

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

1. a user inputs a long URL, the service returns a short URL using Rest GET API.
2. user input the short URL, the service redirects it to the original URL using Rest GET API.
3. A user can choose to customize short URLs.
4. one short URL can only redirect to one original URL. One original URL can have multiple short URLs.
5. [expanded requirement] Data analysis on URL hits data, set an expiration date for short URL, add user login authentication

Non-Functional:

List non-functional requirements for the system...

1. Availability: the system should be highly available
2. consistency: consider eventual consistency for high performance(cache)
3. persistency: durable database.

Capacity estimation

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

1. assume DAU is 1M, each user create 5 url daily. the service creates 50 new url per second.
2. storage: 1M*5*100b*365=200TB per year, 3 replica gives us 600TB, store for 5 years, then 3PB.

API design

Define what APIs are expected from the system...

1. createShortUrl(long url) -> short url
2. getLongUrl(short url) -> long url

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

• Relational database(PostgreSQL): provides ACID(atomicity, consistency, idempotency, durability). Ideal if you have complex queries or require transactions.
• NoSQL database(MongoDB): provides a flexible data structure, and high scalability, which better fit here for its high volume of URLs, and we don;t need complex query or transactions.
• Cache(Redis): to enhance read performance for frequent access URLs.

URL

1. primary key: id(hash of the short URL)
2. short url
3. assigned to: long url
4. status: assigned/ available / expired
5. create at
6. expired timestamp
7. create by user

User

1. primary id
2. username
3. email
4. password: hashed password

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

1. short URL service: this service creates new short URL, also it checks whether a user input short URL has been used before, it returns an unused short URL, or True/False for the user input URL.
2. load balancers are behind each backend services, each backend service has multiple instances for high availability
3. cache layer before the database, to keep the mapping of short URL and long URL, it cache miss, then fetch from database and write to cache.
4. NoSQL database for URL

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

get short a URL flow: client request-> load balancer -> backend service -> database, database generate a short URL or pick user input short URL, then write to URL database. write the mapping to cache.

get a long url from a short url: client request-> load balancer -> backend service -> cache. If cache has the short URL, then return it's corresponding long URL and redirect. Otherwise, backend service connects to database to find the short URL and it's long URL. Also write the short URL to cache.

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

The short url generation service garantee all short urls are unique. By checking if the database already has this primary key.

1. how to generate unique key?
2. hash the short URL.
3. how to redirect to long url?
4. keep a cache before database, cache 20% popular short url, so that no need to hit database. cache could be LRU.
5. how to clean expired URL?
6. a job can regularly run against the cache and database to clean expired short URLs.

Trade offs/Tech choices

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

1. Instead of scanning the entire database to get available urls, we can assign short urls to backend service beforehead:
2. reduce latency
3. if one backend service is down, all short url is gone, we waste those urls
4. how to give back the short url to user?
5. push : once url is created, server push to client.
6. we need a mapping of which client connects to which server, extra maintance work
7. this is fast comparing to poll, will not have empty response
8. poll: user poll from service, either long polling or websocket: long polling is to pull service in a time interval, user might get empty response. Websocket is better but it might have some debugging difficulty.
9. Cache and database
10. user query a short url, if it is not in cache, query the database and write it to cache.
11. this may add more traffic to database if query not in cache
12. Or once a new long url is assigned, then add it to cache.
13. may increase latency when creating the short url

Failure scenarios/bottlenecks

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

1. the backend service, the database is horizontally scaled.
2. Consider adding a security check for DDOS attack, limiting request rate by a user.
3. database could be a bottleneck as the URL number grows, we can shard the database for faster lookup

Future improvements

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

1. log each request and create metrics of URl hits data(from where, which user..),
2. Expired URL may go to a code database