Loading...
The system should convert the long url into a 9 character alphanumeric code.
The system should ensure that similar urls submitted by different users should have different codes.
A good hashing function should be used to convert the long url to a short url
A key-pair database such as dynamoo db should be used for easy horizontal scalling due to the high number of urls generated daily.
The system should be highly availabe to ensure that url redirects do not fail
The system should be highly effective ensuring that no two different urls have the same short url
100,000,000 urls created per day
Assuming to store each key-value pair {short_url: long_url} is 100 bytes and we need storage for 5 years:
100,000,000 * 365 * 10 * 100 = 36.5 TB
Total storage needed to store urls for the next five years is 36.5 TB
Assuming the number of users for the next 5 years will be 10 million and the mount of meta data required to store data for one user is 2KB:
10,000,000 * 2 = 20GB
1: CreateShortUrl(
user_id,
long_url
)
method = POST
return: short_url
2: GetLongUrl(
short_url
)
method = GET
return: long_url
status_code = 301 (url redirect)
The database used for user information will be: PostgreSQL for consistency purposes:
UserData:
first_name: string
last_name: string
email = string
password = string
The database used for storing {short_url: long_url} key-value pairs will be DynamoDB for easy horizontal scalling for high availability
ShortUrls Key-value pairs:
{
short_url: long_url
user_data: user_id
}
The system will have several load balancers between the client and the application servers so as to distribute the traffic among the servers depending on the traffic load. Between the application servers and the database servers will be several cache servers to cache recently accessed data by the api servers. The cache will use an Least Recently Used eviction policy to evict cache. The databases will be of two types, relational databases such as Postgres to store user information and a non-relational database such as DynamoDB to store key-value pairs of short_url to long_url. The sharding on dynamo db will be based on a consistent hashing algorithm that maps the short_urls to the non-relational database depending on the characters of the short_url.
The authenticated user fills us out a form with a long_url field which he/she then submits the form via a post method. On the backend the server recieves the post data containing both the long_url and the id of the user who submitted the form. The hashing algorithm then maps the long_url into a short_url depending using both the user_id and the long_url to create the hash. Based on the hash value, the short_url is then mapped to one of the database shards via a consitent hashing algorithm. The system then returns the value of the short_url to the user with a status code of 200 indicating successful creation.
On clicking the generated short_url , a get request is sent to the server. The server then queries the database and returns the associated long_url with a status code of 301 indicating a permanent redirect.
Application server
Their would be several Application servers to distribute the workload so as to faciltate faster response times as requests are served quickly.
Load Balancers:
The load balancers will distribute the traffic among the application servers using a weighted round robin algorithm which will check the capacity of the server and the current server load before allocating traffic.
Cache Servers:
The cache server will cache recently requested data to reduce the number of expensive database reads. The cache eviction policy used will be LRU (Least Recently Used) which will evict least recently accessed cache data.
DynamoDB: Horizontal Scalling
PostgreSQL: Consistency
Load balancers: Reduce traffic bottle necks
Multiple API Servers: To reduce server response times
Multiple Databases: Master - Slave Architecture tp make sure that their is a failover mechanism to ensure that data is not lost. A slave is selected to be a master temporarily in the event that the master database fails.
Trade offs: The slave databases on different nodes will recieve new data at different times leading to a minimal delay in data consistency which in this case is permissible.
Load balancers: To redirect traffic to other servers in the case that a particular server fails. To also distribute traffic among the various application servers.
Master - Slave database architecture: To ensure that read request are distributed among the multiple slave databases and also to make sure that their is a failover mechanism incase the master database fails.
To user a multi-master architecture to ensure that recently stored data that has not been copied to slave databases is not lost.