Loading...
Create Short URLs from Long URLs
Redirect from Short URLs to Long URLs
Redirect from Short URLs to Long URLs with low latency
Handle high traffic from popular URLs
Able to handle an increased number of users
Consistently convert the long URL to the same short URL using base62 efficiently
Storage requirements:
Short URL = 10bytes
Long URL = 250bytes
Total storage requirement for a URL => 300bytes
Total Storage in a year => 300bytes * 60secs * 60min * 24 hrs * 365days = 10GB
5 year estimate = 50GB
How many servers would we need?
20,000 reads per second -> peak
200 writes per second -> peak
Total requests per second => 20,200
1 server => 200 requests per second
20,200 / 200
Total Bandwidth requirements => 101 servers
100,000 active users
1,000 new users per day
Read to Write Ratio: ~100:1
createShortURL(long_url) => returns short URL and stores mapping of short_url to long_url
readShortURL(short_url) => returns long URL
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...
Use a NoSQL database to store short URL to long URL mappings. NoSQL database like Cassandra or MongoDB could be used for high throughput reads and eventual consistent writes. Since the Short URL service is a read-heavy system we would need to redirect with low latency. Redis could be used given the amount of in memory storage available. It would reduce database load by retrieving the most frequently used short URLs from the memory before reading from disk storage.
To support low latency we could use CDNs to host the frequently used short URLs distributed regionally low response times during reads.
Additionally, to support fault tolerance, since the Short URL service can tolerate eventual consistency, to ensure high availability, we can have partitioned database based on the base62 keyed URLs, and have two replicas in a leader follower schema. Writes would go to the leader and the follower databases the updated short URLs would be propagated to the followers while the most frequently used URLS would be stored in the CDN and also in memory in the Redis Cache.
An API Gateway could be used to direct requests to the services. We should separate write servers from read servers.
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...
CDN => Stores frequently requested short URLS and redirects to long URLs
Redis => Stores the short URL to long URL key value mapping
Load Balancer => Distributes the requests load to the servers
Write Service => Accepts long URL, encodes to base62 and stores in Redis
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...
Client makes a create short URL request to the API Gateway providing the long url which is directed to create URL service which converts the long URL to base62 and returns the value to the client while storing the key value mapping of short URL to long URL in the Redis store.
The Redis store caches the most frequently requested short URLs in memory and the rest on disk.
The write is propagated to follower databases for high availability, redundancy, and fault tolerance asynchronously since eventual consistency is tolerable.
After the writes to the leader, the CDN is updated to hold the most frequently requested short URLs.
The client can request to read a short URL and the request is sent to the API Gateway. The API Gateway checks the CDN to see if the short URL is stored. If the short URL is in the CDN then it is returned to the client otherwise, the CDN redirects the request to Redis and the requests are distributed through the load balancer to the server with the most available bandwidth. Redis checks if the short URL is available in the cache, and if it is not, then it checks on disk and retrieves the mapping to the long URL to the client and redirects the client to the long URL.
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 write service stores the key value mapping of short URL to long URLs. It uses base62 encoding for reduces risk of collisions and consistent encoding. It then writes the mapping to the Redis store and the Redis store updates the cache and CDN with most frequently requested URLs
Explain any trade offs you have made and why you made certain tech choices...
SQL for NoSQL databases. A traditional database could be used, however, we need high throughput reads and eventual consistentency can be tolerated which NoSQL databases like Redis, and Cassandra are great at whereas SQL databases have high consistency, and slower reads compared to key value stores.
We could have used other hashing techniques outside of base62 encoding like md5, however, we would have to reduce the number of bytes for stored for the short URL which increases the risk for collisions and having to account for it.
We could iterate on the key used to store the URLs with a key that is further encoded like Snowflake's [database-number][base62-key] to handle a higher number of databases servers and requests but this is early on in the design and currently the design that we have should be enough to handle the amount of users of the system.
Try to discuss as many failure scenarios/bottlenecks as possible.
We have a load balancer that directs to the correct server and the databases have 2 - 3 replicas for each leader. If one database fails, another leader is elected and which the failed database is back in service, missed writes are logged and written to the failed database
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Improved encoding such as the Snowflake design of key-value store in addition to horizontally scaling by adding additional servers in a distributed manner. Addtionally, we can add a Log and Monitoring services as well as heart beat to check the health of the servers for quick debugging.