Loading...
POST /shorten/
{
longUrl: "http://abcd",
}
-- returns
{
shortUrl: "http://short-url"
}
GET /lookup/
{
shortUrl: "http://short-url"
}
-- returns
redirect 301/304 --> http://abcd
Non-relational - primarily a key-value mapping of short-long urls
Maybe DynamoDB
Data:
long url: 90 bytes
short url: 10 bytes
maybe timestamp, access date, etc
~ 500 bytes or 0.5 kB per entry
Shorten Service:
Notification Queue
Lookup Service:
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
A user will submit a post/get request. I and be directed to the corresponding service load balancer.
The Short Service load balancer will direct the request to an available Short Service server. The servicer will create an async shorten job, to add to the job queue. This will then perform an MD5 hash of the long url. The last 9 digits of the hash will be stored in the database as the "short url", and mapped to the original url. Once complete, a notification will be enqueued with the short url to be returned to the user.
Lookup requests will first be directed to the CDN - acting as a cache for quick lookups. Otherwise, they will go to the Lookup Service load balancer, which will direct the request to an available Lookup Service server. That will then perform a lookup of the short url, and return the long url.
Both services will first check the local cache to see if the url has already been generated. The Short Service will write the short-long url entry in both the database and the cache.
Both services will share access to a cache. The cache will implement a LRU policy. It will also be scaled horizontally. We probably want to store roughly 1 weeks worth of data in the cache.
200 million urls / 7 days * 0.5 kB per url ~ 10 GB of storage needed.
10 GB is small enough that an average server can handle the entire weeks worth of urls - so we don't need to shard them. Instead, we can duplicate the entire cache and put a load balancer between the cache and service. The cache will be duplicated for redundancy.
At this rate, the database storage will grow by 1/2 TB per year. So after 20 years, the storage will only be ~10 TB. This is reasonable. We can also implement consistent hashing to distribute across multiple servers.
The database will also have read replicas to ensure quick read times.
The shorten service will utilize an asynchronous processing queue to ensure quick throughput. The number of works can be scaled as high as required during peak usage.
The shortening service will shorten urls by performing an MD5 hash of the original url. The last 10 digits of each hash will be used as the short key. In the event of a collision, the hash will be incremented until a collision does not exist, and then stored.
The data itself is not really relational - we don't need to perform complex joins on any data, it's mostly a key-value mapping. So we can take advantage of horizontal scaling with a service like DynamoDB, and use consistent hashing to prevent data loss and minimize downtime.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Based on 200 million url requests per month, and 2000 million read requests, that corresponds to roughly 70 url requests per sec, and 700 reads per sec. Depending on the hashing / database access time, the services may need to be scaled horizontally to ensure fast responses and availablity. So each service is behind a load balancer, and can scale independently
The shortening service utilizes an async message queue to process jobs, offloading some of the workload.
Many reads could overload the database, so a redis cache will be used to lookup short urls quickly, as well as verify existing urls before write. The cache could fail, so we will also scale it out horizontally, duplicating the entire cache over several nodes, behind a load balancer.
All load balancers will be in pairs, active-passive or active-active.
To prevent excessive load during high traffic peaks, we will use a Content Delivery Network to cache frequently used urls locally to the region they are accessed from.