Loading...
1. Given a long URL, create an associated short URL.
2. Given a short URL, return the associated long URL.
Availability - This service has to be highly available. Especially functionality (2) (redirection).
Response time - Functionality (2) has to have low response time, e.g., less than 10ms. Functionality (1) (creating short URL) can takes more time - less than 10 seconds.
Scalability - We will get more and more requests to create short URLs, so the storage has to be highly scalable.
80 requests per second for functionality (1) (creating short URL).
8000 requests per second for functionality (2) (redirecting request with a short URL to long URL).
I assume the random portion of shortened URLs to be 8 characters.
I also assume long URLs are on average 100 characters.
Each long -> short URL conversion would include:
Each entry is 144 bytes.
Per day, the service would generate 80 * 60 * 60 * 24 ~ 7MB of data.
Within 2 years, it would generate 5GB of data.
str shortenURL(str long_url, user_ID, expiration_time=None): Takes a long URL and returns a short URL.
str redirectURL(str short_url): Takes a long URL and returns the associated long URL.
For the main storage, I believe a NoSQL database, for example MongoDB, would be a good choice, for its horizon scalability and fast response time. Because shortenURL() can take some time, the service can relax the consistency requirement. It can use eventual consistency model, as long as write is propagated to all the database replicas within a reasonable amount of time. After a short URL is created, it would be acceptable to take some time (e.g. < 10s) for it to be available for use by redirectURL() API.
The database would be:
This would allow potential new features, e.g., listing URLs by a user, or looking up short URL given a long URL.
Although Cassandra would provide more scalability than MongoDB, the flexibility in schema design and secondary indexes make MongoDB more suitable than Cassandra.
Because the data size is not huge (5GB in 2 years), relational DB can be used, too. RDB's strong consistency and rich query capability might be helpful. But a NoSQL DB would be a safer choice if the service were to grow exponentially in the future. MongoDB can be configured to provide consistency suitable for this service, e.g., acknowledge write has been propagated to all replicas.
One of the most important requirements is performance of redirectURL() endpoint. As such, a cache system, e.g., Redis, would be used to improve the read performance. This is particularly important as there will be some short URLs that are particularly popular.
See diagram from the high level architecture.
All the components - Load Balancers, Web Servers, Cache and Database should have multiple instances for improved availability.
Database and Redis should be sharded by geographic location. This is important for the response time requirement for redirectURL() API. Because this API should return quickly, it would be beneficial if a request can be handled by a data center that is closest to the client.
Data are protected by MongoDB's primary - secondary replication. Even if one MongoDB server is lost, copies of data would exist in other replicas, enabling recovery.
If one Redis server is lost, other Redis servers can serve more requests while the server is being recovered.
Load Balancers and Web Servers are stateless, so backup servers can be prepared and be started quickly in case of failure.
Load balancing algorithm can use the hash of short URL in redirectURL() API. Weighted round robin would be an improvement over round robin, if web servers have different capacities.
Global Server Load Balancing can be used to route traffic based on the client's geographic location.
CDN can be introduced to catch and serve a request even before it reaches the Load Balancers.
shortenURL() API:
Client sends the request. GSLB would decide where this request should be served based on the client's geo location. For example, if the request is made from Western US, forward the request to a datacenter in the same region.
GSLB would use the request's origin IP address to decide where it comes from. It then chooses the right data center, based on location and health status of data centers, and returns the server IP address to the client.
From their, the request would go through the local Load Balancer and reaches the web server. Web Server would generate a random string to make a short URL, and saves it in the database, along with the long URL and other data. It would also update the Redis Cache so that it has this entry.
redirectURL() API:
Client sends the request. GSLB would decide where this request to be served. If the data is cached by CDN, it is served by the CDN.
CDN can cache a response to a request to a specific URL. In this service, since there's a unique association from the request URL (shortened URL) and the response (long URL), CDN would be effective in caching and reducing the response time for the clients.
Otherwise, the request would go through local load balancer and reaches the web server.
Web Server first checks the cache. If the entry is there, the associated long URL is read from the cache and is returned.
If not, it is read from the database and returned. Web Server would also store the entry in cache for future requests to the same short URL.
Web Server has to generate a shortened URL.
There are two choices - a randomly generated string vs a string based on hash.
The pro of randomly generated string is that it avoids conflicts. If it is based on hash, it may collide, because we would only be using part of the hash (instead of the full 20 bytes for SHA1, for example).
For the main storage, I believe a NoSQL database, for example MongoDB, would be a good choice, for its horizon scalability and fast response time. Because shortenURL() can take some time, the service can relax the consistency requirement. It can use eventual consistency model, as long as write is propagated to all the database replicas within a reasonable amount of time. After a short URL is created, it would be acceptable to take some time (e.g. < 10s) for it to be available for use by redirectURL() API.
The database would be:
This would allow potential new features, e.g., listing URLs by a user, or looking up short URL given a long URL.
Although Cassandra would provide more scalability than MongoDB, the flexibility in schema design and secondary indexes make MongoDB more suitable than Cassandra.
Because the data size is not huge (5GB in 2 years), relational DB can be used, too. RDB's strong consistency and rich query capability might be helpful. But a NoSQL DB would be a safer choice if the service were to grow exponentially in the future. MongoDB can be configured to provide consistency suitable for this service, e.g., acknowledge write has been propagated to all replicas.
Data center going offline due to a disaster - GSLB should be able to reroute requests to a healthy data center.
Too many redirectURL() requests on one popular short URL - caching at CDN level should help.
Cache server is lost - Redis Cache servers should be replicated , for example by primary - replica architecture.
Supporting custom URL.