Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Number of requests to generate a short url per second = 1000 approx
Number of requests to access an already shortened url per second = 10K approx
Assume the length of a shortened URL = 7 chars
Char set of a shortened URL = 62 (a-z, A-Z, 0-9). Hence we have to use base-62 encoding.
Number of unique shortered URLs which can be generated = 62^7 = 4 trillion approx.
42 bits are required to represent 4 trillion.
Number of seconds in a day = 10^5 approx
With 1000 requests per second, the time after which 4 trillion URLs get exhausted = 4 trillion/1000 seconds
= 4 * 10^9 seconds
= (4 * 10^9)/10^5 days = 40,000 days
= 40,000/365 years
= 120 years approx.
So a 7-char shortened URL satisfies our requirement.
Define what APIs are expected from the system...
POST https://
Returns: 201 OK alongwith shortened URL
GET https://
Returns 30x (redirect) with the original url OR
40x if the shortened url has expired
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...
Given the high number of possible short urls generated, a NoSQL database is suitable. The system also has a high number of concurrent reads and writes which may not be efficiently handled by a SQL database. So NoSQL database is suitable.
A key-value store like DynamoDB can be used.
Database Schema
==============
Shortened URL (key)
Original URL (value)
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...
User: The end-user who wishes to be redirected to the original URL or generate a short URL.
CDN: Content Distribution Network - it is located in multiple geographies to support fast redirection if the service has global users.
Validation: Requests to generate a short url are first validated to verify that the input original url is valid.
Compute/generate: Generation algorithm for a unique short url runs here
Distributed Cache: A distributed cache like Redis or Memcached which stores the mapping of shortened and original urls in a cache for fast access on subsequent requests. The cache is distributed between multiple nodes of a cluster.
DB: A key-value database which stores the shortened and original URLs persistently.
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...
User: The end-user who wishes to be redirected to the original URL or generate a short URL.
CDN: Content Distribution Network - it is located in multiple geographies to support fast redirection if the service has global users.
Validation: Requests to generate a short url are first validated to verify that the input original url is valid.
Compute/generate: Generation algorithm for a unique short url runs here
Distributed Cache: A distributed cache like Redis or Memcached which stores the mapping of shortened and original urls in a cache for fast access on subsequent requests. The cache is distributed between multiple nodes of a cluster.
DB: A key-value database which stores the shortened and original URLs persistently.
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...
Base62 encoding
==============
To generate a unique short url, we will perform base62 encoding on a unique 42-bit number.
Approaches for unique number generation
================================
Approach 1: Central server auto-increments a number on every request. This approach is similar to Flickr's unique number generation algorithm.
However, this can lead to a single point of failure and overwhelm the central server if the load on the system increases.
Approach 2: Number generation is decentralized. Every node computes an md5 or similar checksum on the original URL. This ensures that a unique short URL is created for each input URL. However, some bits of the hash must be truncated to accommodate in 42-bit limit. This can lead to collisions and hence inconsistency.
Approach 3: Partition the 4 trillion url space in slots equal to the number of worker nodes generating the short url. Each worker node manages its own partition and auto-increments the number. When a partition is exhausted, the node can pick up a new partition.
If a node fails before exhausting its partition, it can start using another partition. Even if the partition space is ~1 milion, this will waste < 1 day worth of urls given that there are 4 trillion urls.
Use a service management/discovery technology like Zookeeper for sharding the partition space. Partition space can be created small so that even if nodes are added in future, re-sharding is not required. For example, create 100 partitions but only 10 nodes are functional initially. As load increases, add more nodes.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?