Loading...
Given a URL, output a shortened URL
When accessing shortened URL, should redirect to real URL
Aim for five 9's availability
Read latency under 100ms for P95
Triple redundancy to prevent data loss
10^7 users -> 10% DAIU = 1 million daily users
Assuming each user creates 1 URL/day -> In 1 year, we will have 365 million * 75 bytes =~ 3 * 10^10 or 30 GB of data
365 million let's store these links for 10 years = 3.65 billion URLs
0-9, a-z A-Z = URL is case-sensitive -> 62 possible letters for each char in hashed url. 62^7 = 3.5 * 10^12 possible values. So we can use 7 char hash (can store 1000 years of urls)
75 bytes per URL + 7 bytes for hash = average of 82 bytes/URL
82 bytes * 3.65 billion URL =~ 300 billion bytes = 300 GB storage needed
Triple redundancy for storage =~ 1 TB total storage.
POST /urls:create
{
"url": "https://example.com"
}
Response 200 OK:
{
"shortUrl": "https://short.ly/a6s3lkd"
}
DELETE /urls/{id}
Response 204 No Content
GET https://short.ly/a6s3lkd
Response 302
Location: "https://example.com"
Given that we will need to keep over 3.65 billiion records, this seems more suitable to use a key/value store DB with high availablility/scalability and low latency, e.g. dynamo DB
Since our DB would need to serve 1 TB of data, that would not fit in the memory of a single node, we can instead partition keys using algorithm such as consistent hashing
DB schema:
URLs (Key-Value)
"a6s3lkd": "https://example.com"
For the hottest keys, we can also implement a cache in front of the DB to serve the hottest records.
We can also use cache write-around strategy, where we write a record to both DB and cache at same time to keep records in sync. For cache reads, we can use a cache-aside strategy where on cache misses, we will then fetch from DB directly and then write to cache afterwards.
Let's use LRU (least recently used) to keep the most recent hot cache records in the cache memory and discard older infrequently accessed records. LFU could also work in this case, to keep only most frequently accessed links, however there could be some URL that used to be frequent but are not out of date/invalid that should get removed from our cache, so LRU is better approach. We can also set a TTL on cache records, e.g. 1 week so we don't keep the cache too large with un-needed records.
See diagram
For the shortening service, we use some kind of hashing algorithm such as SHA-2 to produce a hash, and then we can truncate to 7 characters, as that's all we need for our system.
Then before inserting into our DB/cache, we first check for collision. In case the hash already exists, we simply re-generate and try another. Since we have 1000x the hash space, collisions should be rare.
For the url redirection service, we will do a cache lookup first on the hash, if it exists we can just return it (and update the TTL back to 1 week). If not, then lookup from DB and then write to cache.
Explain any trade offs you have made and why you made certain tech choices...
Ensure that all services are auto-scaling and have replicas in multiple AZ's within a geography. The DB can be globally available, e.g with 1 write region and read replicas to all other regions.
If cache goes down, there could be a thundering herd problem where all requests go to DB and overload it. Autoscaling cluster for cache to handle spikes in traffic. We need to add auto-scaling to DB to be able to handle such surges in traffic.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?