Loading...
List non-functional requirements for the system...
1. The service will handle shortening request one at a time. No batch processing.
2. The service will not de-duplicate input URLs. One same URL can be shortened into different new URLs.
3. The service will not validate the Original URL.
Estimate the scale of the system you are going to design...
Assuming 100000 requests per second. That will be 24*3600*100000=8.6B URLs per day, 3.15T URLs per year. If every ShortenedURL - OriginalURL is about 100Byte long in average, the storage will be 315TB per year.
Assuming an URL shortening request can be handled in 10ms, then one core could process 100 requests per second, and we will need 100000/100 = 1000 cores.
Define what APIs are expected from the system...
string Shorten(string OriginalURL)
string Redirect(string ShortenedURL)
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...
Since we only guarantee that shortened URLs are unique, we use them as primary key. Only one table:
| ShortenedURL : string | OriginalURL : string |
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...
We will have 4 components in this design: web server, shortening server, redirection server, and database
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...
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...
Let us deep dive the Shortening server first. The Shortening server can adopt a shortening algorithm to ensure the keys are unique. In trivial case, there is only one server, so the Shortening server can query database to get the biggest key, apply increment to get the next key, assign it to the incoming OriginalURL, and persist to DB. However, as the request per second could be 100000 high, multiple Shortening servers should be introduced, which should be 1000 cores all together.
Correspondingly, multiple DB will be needed as well. To avoid collision, we can use a predefined key space and assign them evenly across all DBs without overlap. A typical solution here will be consistent hash, which breaks the key space into a large number of sections, so each DB has same key space size without collision. If any of the DB is down, its data and requests will be delegated to the next server in the ring.
When an redirection request comes in, the redirection server lookup the ring assignment scheme to figure out which DB the ShortenedURL is stored on, and get OriginalURL from it.
Explain any trade offs you have made and why you made certain tech choices...
One trade off I made is no de-duplication on OriginalURLs. The chance for OriginalURLs is not low especially for hot URLs, like google/FB etc.. The reason to consider it as no-goal is that the chance of duplication heavily depends on user behavior, which is not predictable. Also, without this functionality we greatly simplified the design - we do not need to check if OriginalURL exists in current DB or not, so only one table is needed.
Try to discuss as many failure scenarios/bottlenecks as possible.
One typical failure would be server or DB down. Since the design here multiple servers and DBs, if one server is down, Load Balancer will recognize this and route requests to other servers. If one DB is down, its data will be copied to the next server on the ring and all incoming requests will be delegated to it also until the broken one is back.
We can also replicate servers and DBs to reduce the chance of failing requests or losing data.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
There are multiple hash algorithms that can be adopted instead of just using key increment mechanism of a DB. Assuming we use base64 space, which is 2^6, then 10byte long ShortenedURL can be mapped to 2^60~ key space, while 3.15T less than 2^42, so the spaces can store URLs for 2^18 years. This will shorten the URLs more.