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.
[Generally speaking, you would like to keep the requirements scope small. You only have 35 - 50 min in an interview. If you have a lot of requirements, you'd risk running out of time. We could add other requirements like custom link. But we will start with a small set of requirements. Easier to expand later than shrink.]
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.
[You do not have to be exact in this calculation. You can say this object would have these data, and it would roughly be 128 bytes, 256 bytes, 1KB, etc.]
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 * 2 =
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=None): Takes a long URL and returns a short URL.
redirectURL(str short_url): Takes a long URL and returns the associated long URL.
[Junior-level deep dive topic.]
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, 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.
See diagram from the high level architecture.
API Gateway provides DDoS protection, TLS termination, and forwards requests to right service nodes.
We have two microservices. Shortening Service specializes in creating the short URL -> long URL mapping and storing it in the database. Mapping Service answers redirectURL() calls.
Because redirectURL() needs high performance, we would introduce cache in two places: one inside the datacenter (e.g. Redis Cache) and another outside (CDN). CDN storage can be expensive, so it would store a smaller set of the most commonly accessed URLs. Redis Cache can store a larger set. Both would have Least Recently Used eviction policy.
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. If the mapping is found in a regional, nearby CDN, it is returned from the CDN. Otherwise, the request reaches API Gateway and the Mapping Service. It checks if the mapping exists in Redis Cache. If it does, the mapping is returned. If not, it reads the Database.
[Mid-level deep dive topic]
Performance and scalability of redirectURL() API is extremely important for this system. As such, we employ two levels of caching. Requests will naturally have locality of access, so caching will be effective.
At the closest location from the clients, we will have CDN storing short -> long mappings for the most frequently requested URLs. For example, if a celebrity posts a short URL link in their Social Network post, this mapping should be in CDN. CDN can be hosted at Internet Exchange Points (IXPs), making the response time from client quite short. It has limited storage space, so it should store a small set of the most frequently accessed mappings. High volume of requests are handled by CDN, without even reaching the API Gateway. It is quite beneficial from scalability & fault tolerance perspective.
In the data center, we will employ a caching node, e.g., Redis. As we can install multiple Redis nodes with 100s of GBs of memory, it can store larger set of mappings. It is still faster than accessing the database, so this would provide performance and scalability gain.
Both CDN and Redis Cache can employ Least Recently Used eviction algorithm to ensure currently popular mappings stay in cache.
[Mid-level deep dive topic]
Database and Cache should be partitioned for improved scalability.
Short URL is a good choice for a partitioning key because:
Other partitioning keys (long URL, user ID) would have disadvantages about these points.
[Junior-level deep dive topic]
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.
All the components - Load Balancers, Web Servers, Cache and Database should have multiple instances for improved availability. There should be robust monitoring and alerting systems on them.
Caching improves scalability on reads significantly. As the number of reads increases and pressures Shortening Service, we can increate 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.