Loading...
create a short url by given original url
redirect short url
query by original url
query all urls
analytics
custom short urls
urls storage will grow double in a few years, need a high scalable system to handle the growth, Need a high consistence database, can give up some availability since we don't require it response every time we request.
Can tolerant 1 million users, average QPS would be 58, the peak QPS would be 3 times of average around 174
void create_short_url(String url)
/***
create a shorted url by using provided url, first to use a if condition check whether given url is a valid url, then we will use a hash function to generate a shorted url, finally validate with Database to ensure this is a unique url, and write in Database
API Method: PUT https://www.shorternURL/create_short_url/{url}
***/
String query_shorted_url(String url)
/***
GET method to get the shorted url in database by using given original url, check its a valid given url, then try query in DB search by the given URL, error handling if shorted url not exist
API Method: GET https://www.shorternURL/query_shotred_url/{url}
***/
String redirect_url(String shorted_url)
/***
GET the original URL in database by given shorted_url, error handling if original url doesn't exist or original url return not 200 status code.
GET https://www.shorternURL/redirect_url/{shorted_url}
***/
Map
/***
GET list of all urls and return in a map data structure.
GET https://www.shorternURL/query_all_urls
***/
String custom_short_urls(String url)
/***
let user self-define the shorted url, need a validation function to ensure it's not an existing shorted url
***/
/***
I gave some explanation of each API method instead of implement them in here. There are other functions Need to be added such as boolean validate_url(String url) to check whether this url return 200 and not duplicated in DB, and a hash function to shorted URL, I may consider to use Base62, or CRC32. I won't consider to add rate limiter in here since we only have 58 in average QPS.
***/
As we know it's a system with higher Read throughput than write. (Estimated Read QPS ~ 158, Write QPS ~ 16)
And also we are higher required consistent data and we can sacrifice availability because it's not a very high QPS even it doubled in next a few years. Relational Database with strong ACID would be a good choice in this case. (Like Oracle DB or Microsoft SQL server) Since it with a higher read throughput, we may consider to use a database cluster with leader and replicas mechanism.(Only leader database allow to write)
Here are data model look like:
table name: Url
id | original_url | shorted_url | created_date | expired_date | user_id
table name: User
id | username | password | last_time_login
We need multiple API servers as server cluster, and load balancer will route the request to one server, Since shorten URL is a simple system with limited functionalities, we don't use Microservices. We just need one application hold by server clusters which can read and write url in database, validate url and hold a hash function. We also need a cache to increase the speed of read request, I would recommend implement an LRU cache and add some logics to read cache first, then read in database cluster if read cache missed. then after server received response from database, our application on server can write in cache to update most recent accessed url.
Database cluster would be a single leader and replicas mechanism. Will explain it in Detailed compoent 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...
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?