System requirements

Functional:

1. Users can generate a short URL that maps to the original, longer URL
2. The shortened URL expires after a certain amount of time has passed
3. A different short URL has to be generated for each same original URL

Non-Functional:

1. Availability - Little down time
2. Reliability - Don't lose any data

Capacity estimation

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

API design

• POST generate_URL (user_id, original_URL) -> returns short_URL string
• GET original_URL (short_URL) returns original_URL string

Database design

u

High-level design

Client - makes a request to the server for either a shortened URL or an original URL. The client then redirects the user to an appropriate destination

Load balancer - distributes the traffic across multiple app servers

App server - If the request asks for a shortened URL, call shortened URL generation service for a unique URL. Once received this unique URL, make a call to the database and store the connection between shortened URL and original URL.

Shortened URL generation service - Given a URL, this service computes a unique shortened URL. To ensure that every URL is unique for the same origin, we can append the original URL with a number or key that will be auto incremented each time the service is trying to generate a new URL for this origin URL. This service likely has its own database that keeps track of the auto-increment number for each URL.

Database - Stores meta data such as user information and how many times a URL is clicked (for metrics). The key thing that we need to store is the mapping relationship between shortened_URL and original_URL. For scalability, we can go for a NoSQL database. It should also be replicated for data reliability. We can go with primary-replica replication to avoid data inconsistencies with multiple write databases.

Cache - Potentially placing a cache before the database so that "hot URLs" can be returned right away without making unnecessary calls to the database. This cache can be write-through so that whenever the data is updated in the database, it is also updated in the cache. The cache eviction policy can be LRU so less "hot URLs" can be automatically dropped.

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

• SQL vs NoSQL - Given that we do not require ACID compliant, I'm leaning towards NoSQL databases for horizontal scaling.
• Write-through vs read-through cache - We want high consistency (URLs should be updated), so I think write-through cache is better because data is always consistent with every new write/update. Some latency is expected but the tradeoff is that we achieve higher consistency.
• LRU vs other cache eviction policy - We could technically clear cache after a certain time has passed or use a simple queue, but given that some URLs maybe popular than others in a given time, it makes sense to go with LRU cache and evict the least recently used URLs.
• Primary-replica vs Primary -primary (or peer to peer) - It makes sense to have only one write database so that we don't have to deal with complex conflict management in case of write conflicts. This is critical because we want to ensure that there is one correct URL that each shortened version is mapped to.
• Round robin vs least connection vs other load balancing algorithm - If we want little overhead, we can go with round robin initially, but a more robust system should periodically perform a health check on the instances that it distributes the traffic to. A better strategy would be to go by least connections and monitor the state of instances at intervals to ensure that the instance is still active.

Failure scenarios/bottlenecks

• Deploying multiple app servers behind a load balancer (Horizontal scaling)
• Include a stand by load balancer in case of failed primarily load balancer
• Using write-through in stead of read-through cache to ensure data consistency for every write but also to prevent a broken system in case of cache failure (switch over to the database entirely)
• Replicated multiple instances of databases to increase reliability and prevent data loss
• Potentially partition data by the first letter of the hashed shortened URLs to speed up the search (assuming that there is normal distribution among the first letters of the hashed URLs)
• Use primary-replica replication strategy to ensure that there's no data inconsistencies from write operations. Read operations can read from one of the read replicas, further helping heavy read traffic.
• Use another load balancer to distribute traffic among read replicas of the database

Future improvements

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