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 partition tolerance 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. Read operation will have higher throughput than write operations. So we estimate read QPS will be triple of write. Which Read QPS will be around 158 in peak and write QPS around 16.
The service will aim to serve 10 million users eventually, if each user can create 10 URLs, so total urls would be 10000000 users * 10 url/user = 100000000 URLs. We expect it growth to double over a few years. So we can start plan it can maximum store around 200 million URLs.
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 partition tolerance 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
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 componet design.
I add a state diagram. so once we got a request to create a short url by input original URL, our application will first go check DB or cache whether this URL exist or not, if yes, application throw the exception of existing URL, if not we will send url to be shorted by Hash Function, (like I mentioned we may use Base62, or CRC32) to prevent it goes back to verify shorted url exist in DB or not. We need to make sure Hash Function algorithm we choose never create duplicated URLs.
Hash Function is one of the most important function to convert url, we can use Base 62 encoding the original URL generated ID in this case. In order to avoid the collision, we can add a timestamp behind shorted url to ensure there is no duplicated shorted url. For example:
Original url: https"//www.example.com/some/very/long/url?query=param
Generated ID is 12345 which yield dnh by Base62 conversion.
if current timestamp is 20230101T123456
shorted url will looks like https://short.url/dnh20230101T123456
Load balancer I would like to choose layer 4 for higher routing speed and lower latency. I think HAproxy is a good choice because it's better support in layer 4. Shorted URL is a simple system. We can choose to use round robin algorithm to load balance servers, which reduce the cost and no need extra monitoring system to monitor the work load on each server and connect to a suitable one.
We can choose use Redis as cache to implement a LRU cache
For database we can choose to use relational Database with good ACID because we care more about data consistence rather than partition tolerance. MySql can be a good choice because it support leader replicas and data sharding, also pretty good scalability. PostgreSQL also a good choice and it also support more complex query. Shorted URL may scale up with more users and more URLs to store, but the query won't be complex.
Cache: Redis
Reason: Support LRU implement and can be write by application
DataBase cluster: MySQL
Reason: According to CAP theory, we want this system can be data consistent, we don't want read a outdated data in replica because we set a any shorted url an expired time, but it's not like a high throughput system like amazon or facebook, it's okay we can tolerant some time lost availability when it has a networking issue or server crashed.
Load balancer: HAproxy
Reason: We want to use layer 4 load balancer instead of layer 7 because we want a higher routing speed and lower latency. Since we don't have login service or user authertication in this moment, we don't have stateful service which need layer 7. HAproxy handling layer 4 better than nginx. Also we choose round robin algorithm to reduce the cost and easier to implement since HAproxy has a strong healthcheck function.
Redirect to original url may failed:
if original url is expired or like return 404, how would we know it's the issue from original url or we read an out of date data in replica (During the new date being wrote but not sync to all replicas)
If peak QPS exceed our expectation, too many users to read and write in DB which out of limitation of our server to handle
if there are 200 million url will be stored in a single table, it will increase the loading time which effect user experience.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?