System requirements

• Functional:we need to be able to take a long URL and shorten it
• after the back end creates a mapping of long to short URL, the UI will display the short URL
  • the user can click this URL to check if it works
  • the user can also copy this URL to be used elsewhere
• need to validate URLs before creating a short URL
• need to store the mappings of long to short URLs

Non-Functional:

• Available about 99% of the time
• Scalability: if our user base grows, still need service to be able to serve
• Will have more reads than writes - 10:1
• use third party APIs to create account ie login with Google, Facebook, Github
• one user to many URLs - we need junction tables

Capacity estimation

• Short URL: 8 char * 1 byte/char = 8 bytes
• Long URL: assuming longest URL of 200 char * 1 byte = 200 bytes
• Memory for mapping = 208 bytes per entry
• Assuming about 10-50K users daily
• Assuming a user creates 10 mappings a day
• 50K users * 10 mappings = 500K mappings in a day
• 500K mappings * 208bytes ~ 100 million bytes in a day

API design

• /generate
  • input: a long URL, user id
  • have a helper function called validate that checks if URL is valid. if valid, continue. Otherwise, return a 400 saying URL is invalid
  • check DB if they already have a mapping in DB. Return error if yes. Continue if it does not exist
  • apply some hashing function which will shorten the URL
  • save the mapping into the DB, with short_url : original long url
  • if saving to DB fails, return error.
  • if saved in DB successfully, return 200 with the new short URL.
  • this short URL should display on UI
• /getUrls
  • input: userId
  • run a SQL query that checks user_to_urls table with the userId,
  • and returns all url_maps generated by this user

Database design

users table:

• userid: UUID

url_map table:

• url_id: UUID
• long_url: string
• short_url: string

user_to_urls junction table:

• userid: UUID
• url_map: UUID

High-level design

Request flows

Client will connect to the CDN first to see if their frontend has been cached.

Client connects to the LB. If main LB is down, they connect to the backup.

If user is running a request for getUrls, LB pings cache and returns that result

If user wants to generate a new URL, request then moves from cache to the server.

Once it has generated a new mapping, it would save that mapping into the main DB. The main is copied to backup DB.

The server returns the new short url to the cache. Cache saves it. Cache returns it to the LB. Then finally, the url is returned to the client.

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?