Loading...
The functional requirements for this system are:
The non functional requirements for this system are:
Estimate the scale of the system you are going to design...
Traffic Vol Estimation:
Number of writes per day: 100,000 per day = 1 per second (WPS)
Number of reads per day = 100 x 100,000 per day = 100 per second (QPS)
Data storage Estimation:
We will be storing data in a no-SQL database such as DynamoDB so that we can get single digit read and write latencies and high availability (both non-functional requirements).
Each entry will be stored in a table named something like URLEntries
Table schema will be:
UUID (Primary Key) - length 12
LongURL
CreationTime (Epoch s)
ExpirationTime (Epoch s)
UserID
and URL will be https://www.servicename.com/UUID
To store one entry of this schema will take 12bytes + 100 bytes (for longURL since this will include https://www.xyz*) since the domain can't be assumed + 8 bytes (64 bit epoch for future-proofing) + 8 bytes + 12 bytes = 440 ~~ 450B per entry.
We will be storing URLs for 3 years and then expire URLs.
Thus database size expected = 100,000 x 365 x 3 x 500B (approx) = 500 x 1000 x 1000 x 100B
= 50 x 1000 x 1000 x 1000 B = 50GB of data
Define what APIs are expected from the system...
The following APIs will be supported:
Purpose: This will be the primary write API in the service, where users can create shortened URLs.
API path: PUT /api/v1/tinyurl
We have used PUT over POST for idempotence:
Request will contain the following parameters:
Headers:
Response will be:
```
{
"short_url": "https://myservice.com/abcdef",
"long_url": "https://wikipedia.org/mindworkgames",
"createdAt": "YYYY-MM-DD HH:SS",
expiration: "YYYY-MM-DD HH:SS"
```
In case of a incorrect uuid, we will return an HTTP 404. If we get invalid inputs or input in bad format, we will return a 400. We will restrict creation of shortURLs to 20 per user per day by default and the rates being breached will result in 429s.
Purpose: Redirect the users who enter the short URL to the original URL.
API path: GET /api/v1/{uuid}
UUID will be the
Headers:
Request will be empty.
Response will contain the redirect link
If it is an invalid UUID, we will return an HTTP 404 page not found, HTTP 429 if rate limits are breached and 400 for a bad request in terms of a bad URL or bad URL format. We are adding v1 before the API methods to implement versioning in case requirements change in the future.
Purpose: Provide analytics about the URL. Response will contain number of views on the URL accumulated over time, on that day and the creation date.
API Path: GET /api/v1/analytics/{uuid}
Headers:
Response:
{ "views": 1000, "daily_views": 500, "creation_date": YYYY-MM-DD }
If the URL is invalid, we will return a 404. A 429 for breaching rate limits and a 400 for bad request.
We will perform basic input validation and ensure that the uuid is within acceptable ranges. The UI application will use OAuth for authentication, we will enforce rate limiting to 1000 requests per day per IP address.
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
We will be using DynamoDB for our database since it fulfills the latency requirements and is optimized for high-read volume applications. Additionally, it is replicated and sharded across various geographical regions so it will provide us with high availability.
We are okay with trading off against strongly consistent databases in this case since a URl can take a few seconds to successfully redirect and we can show a 404 till then.
Table schema will be:
UUID (Primary Key) - length 12
LongURL - max length 100
CreationTime (Epoch s)
ExpirationTime (Epoch s)
UserID - max length 12
We will use CreationTime as RangeKey and UUID as partition key. We will also create a GSI on UserId to support analytics and efficient reads per user ID.
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
We will have a UI component which will have a frontend client to send requests to create new URLs to the backend service. They will communicate via an API Gateway through a load balancer to ensure we can scale up and down easily for traffic spikes. We will implement a Redis based cache to cache the most frequently accessed URLs (we can cache 20% of the URLs per day based on activity). We will then have an ECS based service that will support the backend APIs mentioned in API design. They will be scaled horizontally as and when required by using auto-scaling policies and dynamically increasing the size of the ECS cluster. Additionally, the ECS cluster will be connected to a DynamoDB database with the above schema. We can use LRU based eviction for the cache. We will use Kinesis to send events to an SQS queue which will then be fed into OpenSearch through a Lambda for analytics.
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...
Request flow for creating new shortened URLs:
User logins to my service using the react web application. They authenticate and then navigate to the page to create a URL. They enter the required details and click submit. A put request is sent to the backend server via the API gateway. API gateway performs rate-limiting and authorization / authentication before forwarding it to one of the ECS instances. The ECS instance creates a new URL for the given full URL and then returns the response to the user. Meanwhile, the ECS instance creates a new record in DynamoDB and stores it. All requests to ECS will be fronted by a load balancer to equally distribute traffic. We will use round-robin scheduling.
Request flow for redirecting to original URL:
User types in shortened URL in the browser and the service calls the GET API via API gateway after performing its authorization, authentication, rate limiting etc checks. Then the service checks the cache (in-memory) to see if that URL is present, else it gets the information from DynamoDB and updates the cache if required. All requests to ECS will be fronted by a load balancer to equally distribute traffic. We will use round-robin scheduling.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
The two most important components here are the database and the Redis cache.
Database:
DynamoDB, sharded based on consistent hashing on UUID and replicated across various geographical regions for high availability.
We will index on userID to provide more features on the viewing of URLs created by a particular user. Also we will be using creationTime as rangeKey to find URLs created recently.
We will use TTL to expire URLs one week after expiration date. We will retain for an extra week for security, auditing and compliance reasons.
Redis / ElastiCache
We will use an in-memory cache to store most accessed URLs. From Day 1, 20% of the URLs will be stored in the cache. We will use LRU cache eviction strategy and monitor hit ratios and eviction rate to tune the cache size over time. By this method, we can ensure that the most recently accessed URLs are in the cache. This works well with our access patterns because URLs that were recently accessed are more likely to be accessed again.
Explain any trade offs you have made and why you made certain tech choices...
Complexity vs. Scalability:
Try to discuss as many failure scenarios/bottlenecks as possible.
It is possible that cache updates fail and the cache contains outdated URLs, this will increase the latency of the system.
Another failure scenario is that it is possible that ECS instances go down. We will use health checks and auto-scaling to ensure that these instances are brought down and new instances are brought up automatically.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
We will create lambda batch processes that feed off ElasticSearch to update the cache in batch, ensure that the DynamoDB replicas are scaled appropriately.
We can provide paginated LIST APIs in the dashboard and also provide analytics visually in the form of Kibana dashboards.
We can also add Prometheus or CloudWatch for logging, monitoring and add CloudWatch alarms to detect outages.