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 3 seconds.
Scalability - We will get more and more requests to create short URLs, so the storage has to be highly scalable.
200 requests per second for functionality (1) (creating short URL).
20,000 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. We will round it up to 256 bytes.
Per day, the service would generate 200 * 60 * 60 * 24 * 256 = 4.4GB of data.
Within 5 years, it would generate about 4.4 * 365 * 5 =
8 TB of data. Considering some growth and some buffer, let's assume it would be 15 TB.
shortenURL(str long_url, user_ID, expiration_time): Takes a long URL and returns a short URL.
redirectURL(str short_url): Takes a long URL and returns the associated long URL.
The primary data model for this system is a simple mapping from short URL to a long URL. We do not need complex relational query.
It requires strong consistency. Once the short -> long mapping is written, all readers should be able to read it.
A key-value pair, such as DynamoDB or Redis, would fit the bill. It is horizontally scalable and performant. It can be configured to be strongly consistent.
As discussed above, the data model would be:
We may choose to have some secondary indices for additional features. For example, if we put a secondary index on User ID, we would be able to list all the short URLs created by the user.
shortenURL() API: Client sends the request. API Gateway forwards it to Shortening Service. It creates the short URL -> long URL mapping and store it in the database.
redirectURL() API: Client sends the request, checked by regional/local CDN, if not found, then head to the API Gateway then Shortening Service, checking first in Redis then Database and of course update the frequency_accessed in CDN, database, and redis.
Caching: The redirectURL() API's performance and scalability are critical. We use two caching layers for efficiency.
Near clients, a CDN caches short-to-long URL mappings for top requests, such as popular social media links. Hosted at IXPs, it reduces response time and handles heavy traffic without hitting the API Gateway, enhancing scalability and fault tolerance.
In the data center, Redis nodes store a larger mapping set with hundreds of GBs of memory, offering faster access than the database and boosting performance.
Both CDN and Redis use Least Recently Used eviction to keep popular mappings cached.
Partitioning:
Database and Cache should be partitioned for improved scalability.
Short URL is a good choice for a partitioning key because:
Other partitioning keys (user ID) would have disadvantages about these points.
Issues with User_ID:
There are two ways to create a short URL:
There is a tradeoff:
Pro of Hash approach is that you don't have to generate random numbers. Con is that the created hashes might collide. In particular, since our random string (8 characters) will be shorter than what the hash algorithms generate (20 bytes or larger), the risk of collision would increase.
Pro of random generation is the possibility of collision is lower. If a newly created random string collides with an already existing one, we can simply generate one more random string. Con is that it would require computational power to generate random numbers. However, since Linux and other OSes support fast random number generation with /dev/urandom, we assume the cost is manageable.
We will pick random generation in this exercise.
Caching improves scalability on reads significantly. As the number of reads increases and pressures Shortening Service, we can increase caching capacity on both CDN and in the data center to serve more requests from caching.
[Mid-level deep dive topic]
As the number of write requests to shortenURL() increases, it might put too much pressure on the database, causing slowness, errors, or even crashes.
To avoid this, we can introduce a message queue to buffer the requests. Shortening Service would push a message in Message Queue, representing the request. Queue Worker would pull from the queue, creates the mapping in DB, and notifies the client the mapping is ready. The system can inform the client with long polling.
Supporting custom URL.