Loading...
Out of scope:
If we keep each URL for 5 years, we're storing 5 x 365 x 1 billion URLs at a given time = 2 trillion URLs
Given the URL and some meta data, we can say we need 500 bytes per URL = 1 PB of storage
POST /v1/user/create
{
email, hashed password
}
->
{
User
}
POST /v1/url/create
{
longUrl,
shortUrl: (optional, will generate if not user provided - must be unique)
// assume user info is passed in header
}
->
{
}
POST /v1/url/:id/delete
-> 200 OK
GET /:hash:
-> 301 redirect to long URL
user
url
metrics
Note that we will definitely need to partition given the size. We can partition based on the hash ranges.
Given that we have more reads than writes, I will choose a relational database like MySQL. We don't need to have fast write access because reads are happening far more often in our system than writes. We can index on our hash so that we can more quickly find our URLs that we need to get to.
Client starts on any device.
We have an API gateway that can handle authentication, rate limiting, and routing.
We have a load balancer to handle horizontal scaling. Algorithm for routing doesn't matter too much here, but let's just go with least connections to make sure we're not clogging up a single server.
Our user service handles anything relating to users, like creating them, deactivating them, and authentication. A user can log in to manage their URLs.
Our URL service is where the meat happens. When a user clicks a URL, we first check in cache. Our cache stores the most frequently visited URLs in an LRU cache using something like Redis as it's good for distribution.
If it's there, great, if not we go to the database which is indexed and find the long URL. We will return a 301 redirect if we find the URL or a 404 if we don.t
We'll also log the click to track click metrics.
We have a cron job that goes through and prunes old URLs.
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...
One point of interest here is hashes for our URLs. We need 8 character hashes to account for the volume of URLs. We can use 36 character hashes. We need to prevent a user from accessing the hashes. There are a few ways of doing this, but we should prepopulate every possible combination beforehand. This way we don't need to generate hashes on the fly as a user creates them. When a user creates a URL, we will grab the next available URL. We could still potentially get in a lock fight here, but with a distributed locking system like Redis and a database transaction we should be able to avoid this most of the time. If it does happen, we will error out to the second place user.
We can cache our most frequently visited URLs. That way, we don't need to make a trip to our database each time one of these URLs are accessed. We can scale up cache as needed as we will generally have an idea of what links are most popular.
We can gain additional speed by partitioning our database. Given we have a hash that's prepopulated, it will be straightforward to use consistent hashing. If we have a hotspot, that will be alleviated by caching.
We traded off on-the-fly hash generation and instead built the hashes first. This costs us more money up front, but guarantees that we never have to worry about hash collisions and mismatches.
I chose MySQL for the database instead of a NoSQL option as we really didn't need NoSQL write speed.
Redis for caching and locking.
If our auth/user service goes down, we can still service our redirects.
If too many people write at a given time, we can lock up our database.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?