Loading...
User enters a URL and gets a shortened one, redirecting to the exact same URL with a permanent redirect on the shortened one
User can access the original URL when entering the short one
A pair of (original url, short url, user) is unique and only exists once.
Reliability -> the shortened URL must redirect correctly
Scalability -> based on the current users per month, we need to ensure that the system can scale easily (especially from a storage and caching perspective)
very low latency
very high availability
100.000 monthly users
5 URLs shortened per months
-> 500.000 shortened URLs per month
Define what APIs are expected from the system...
We'd need a POST endpoint to create the shortened URL
POST /create -> Body: {url: string, userId: string} -> response: ok; {url: string; shortenedUrl: string}, error: {url: string, error: string}
We need a GET endpoint for the redirection from the short URL to the original URL
GET /:short -> response: ok; 301 Permanent Redirect; error: 404 not found
Core entities:
Important consideration: read write ratio is not in balance -> much more reads expected
flowchart TD
n2["Backend Service"];
n5["Client"];
n1[("Database")];
n5 --> n2;
n2 --> n1;
n1 --> n2;
n2 --> n5;
The Client sends a request to the Backend Service for both creation of short URLs and for the actual redirects.
When sending a POST request the backend generates the short url and stores it in the DB. We want to avoid collision for the same user having the same short url multiple times, so if it already exists and is created by the user formerly, the user will get the current existing short URL. The user gets the shortened URL as the response.
When the user sends a GET request the backend service checks the DB to see if an entry exists for the short url. if so, it sends a redirect to the original url. Otherwise the user gets an error as the short url does not exist.
flowchart TD
n2["Backend Service"];
n5["Client"];
n1[("Database")];
subgraph n3["API Gateway"]
end
n4["Write Service"];
n6["Read Service"];
n7[("Redis Cache")];
n5 --> n3;
n3 --> n2;
n3 --> n5;
n2 --> n3;
n2 --> n4;
n2 --> n6;
n4 --> n1;
n6 --> n1;
n6 --> n7;
First we'd need to decide which database we'd need to use. considering the core entities from before (user, short url, original url) all kind of DB should be fine in this case. we don't have complex relations which would be a better fit for relational databases or a lot of unstructured data that would be a better fit for document based databases. so it depends on the expertise of the team and the owner of the system.
For this design we'll choose a Postgres relational database.
Now we need to consider again the imbalance between read and write ratios. The read ratio is expected to be much higher than the write ratio.
Considering that we'll have 500.000 Short Urls per month and each of it taking 500 bytes to store, this is an annual memory usage of 500.000 * 12 * 500 = 3 GB
It should be easily scalable with a single Database from a storage perspective and can be scaled vertically if needed.
The scalability needs to be achieved by the heavy read operations in this system. Checking the DB on every read request is not scalable. So a caching will be appropriate here. For this system design redis is chosen, but it could be any other in memory cache depending on the expertise of the owner. On each write to the DB the redis cache is updated as well. Every read request first checks Redis instance and falls back to the DB if not found. here it should be worth to store it in redis again. This can be achieved by communication between the read and write services. for the sake of reducing the complexity i won't ellaborate more on that.
Coming back to the trade for the Database replication. As said the storage amount per year is not much so any complexity is not introduced here to have multiple replicas. As those need to be kept in sync which adds unnecessary complexity tot he overall system.
Finally the Backend Service from the high level design is split into two separate microservices, one of them responsible for the writes and one for the reads.
Depending on the need the Read Service could have multiple instances (replicas) running. One of the advantages here is that the read mostly shouldn't have collisions compared to having a single backend service with multiple replicas and read/write responsibilities. then a lot of complexity is introduced to mitigate consistency issues between the writes.
As the client should be unaware of which service he's calling, an API gateway is introduced which is responsible for distributing the traffic to the correct backend service.
A single Redis instance can be a bottleneck, but for the current scale it should be fine.
Scaling the redis replica counts.