System requirements

Functional:

• A user can:
• Input a full URL, receive a shortened URL
• Input a shortened URL, receive a full URL
• Receive analytics about most visited URLs
• Customize a URL to whatever shortened sequence they want
• Expire URLs

Non-Functional:

• Performance: optimized for high reads
• Scalability: starting small but should be able to scale easily
• Starting at ~50 writes/sec, should be able to scale to ~10,000 writes/sec comfortably
• Starting at ~5,000 reads/sec, should be able to scale to ~100,000 reads/sec comfortably

Capacity estimation

• 75,000 URLs created per day
• URLs accessed as follows:
• Popular: 100 times/hr
• Regular: 10 times/hr
• Inactive: 1 time/hr
• High read to write ratio

API design

POST /url

GET /url/{url_id}

Database design

We're essentially implementing a key/value store that should be able to scale easily. We want to optimize for a high read to write ratio but don't expect consistency concerns given the fact that requests don't collide with each other and eventual consistency is okay, e.g. if a shortened link doesn't route anywhere the first time, the user can reload and try again. Because of this, I think we should opt for a NoSQL database that maps hashes to URLs. Because of the high read pattern, we should replicate the database with a leaderless architecture. Changes should propagate every few seconds to the rest of the machines.

High-level design

• Requests should hit a load balancer that distributes them evenly across different machines.
• Read requests should be routed to a group of replicated databases via a load balancer

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

We need a hashing service that will take a URL and turn it into a unique hash. The hashing algorithm should have no collisions and needs to support ~40,000,000 unique values assuming we can recycle old/stale URLs on a yearly cadence. Thus, we should hash URLs to a 32-bit sequence.

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?