Requirements


Functional Requirements:


  • Create a short URL for a given long URL.
  • Return the long URL associated with a given short URL.



Non-Functional Requirements:


  • List the key non-functional requirements (eg low latency, scalability, reliability, etc.)...


we will need to handle scalability and reliability as the throughput is relatively considered as high, no matter medium or large scale. Also, under this high visiting volumn, we will need to consider data replication, server replication, to increase the availability

From ta user experience point of view, low latancy is a MUST as well.


API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...


Here are my endpoints:

  1. GET getLongURL: String shortURL -> which used to retrieve the full URL by taking the shortURL as an input parameter.
  2. POST generateShortURL: String fullURL -> which used to generate and return the short URL, by taking the full/long URL as an input parameter.


So for error handling, we have the following key aspects to consider.

  1. for GET getLongURL: String shortURL, if the shortURL given is not found in our database (we will need to further polish it, as the design my require a K-V store db like Redis), it could be permanently deleted. In that case, we could be returning a standard 400 error, with a nice user interface and message to the user.
  2. POST generateShortURL: String fullURL. If the user is sending in a duplicated URL (let's talk about the retrieving full URL logic later), our design can handle it by redirecting the user by 302 status code, to GET getShortURL: String longUR.

As for Rate Limiting, yes, a rate limiting is useful, considering this is a shortenURL tool, so my preferrenced design would be setting this rate limiter to be allow for GET a maximum two visit per ip per device, and for POST, one visit per ip per device. What do you think? (To the coach: this is something I really do NOT know what is the interviewer expecting)


State Code: We can do 200 for success, with HTTP response. 400 for GET as a non-existing URL. 302 for a redirect to the original URL


Now the real question is, should we validate whether the URL is live or not, my guess is YES. We should be validating the URL beforehand, as we are targeting a large scale system, so if the URL itself is a dead link, that's something affecting our reliability. So later I will add such a component to verify the URL's status


High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.


There will be two main entries:

  1. "Request a Short URL": GET full URL by sending in a short URL, which sends the short URL, then the Redirect Service try to find it in the cache layer, if not then go to the persistent layer, if we found it we then redirect the user to the full URL with a 302 state code. Otherwise a 400 error code indicating this short URL isn't even existed in our database.
  2. "Post a Full URL": POST a full URL in to get a short URL. Same gateway, then the server should handle duplicate check first, if there is a dup, then we simply just return the original short URL to the user (rather than giving an error for better UX). Otherwise, we generate the shorten URL, persist the URL and return to the user.


Graph Design as drawn, additionally for Components:

  1. API Gateway: CDN + Rate Limiter + Authentication + Load Balancer + Data Metrics
  2. Redirect Service: This is a component that does the logic flow for GET full URL redirect request, and part of the Server (replicas)
  3. Check for Dup Service: This is a component to do the dup check for error handling by checking the Shorten URL, and part of the Server (replicas)
  4. Shorten URL Generating Service: This is another component does the logic to generate Shorten URL by accepting a Full URL, part of the Server (replicas). To ensure we could have a unique unique Shorten URL, my suggestion is first generate a UUID and combine with the request timestamp, then using a Hash algorithm to encryt this UUID + timestamp.
  5. Write Service: This is the component does the logic to write the generated Shorten URL, part of the Server (replicas).
  6. Redis: There will be multiple replicas here, work as the hot memory cache for low latency. This is functioning as a Most Recent Used, I presume that a recent used URL will soon be used again, so if a URL is used (From the Persistent DB maybe), then we save it here.
  7. Persistent DB: Also we should have replicas, primary option is a Cassandra DB. We will add some schedule cleanup job, to occasionally move some Least Recent Used cool data from cache Redis to the persistent layer.



Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.


Let's deep dive into these:

  1. API Gateway: This is a component that contains Rate Limit, that protects our system from being maliously attacked, also we will have a load balancer here to better route to the most available server for availability.
  2. Check for Dup Service: This is basically, checking the our Redis + Cassandra DB, since they are both K-V storage, it won't take too long to check the index, this will get us a guardrail to stay away from a duplica. Also, it would be normal to take longer for a write operation.
  3. Shorten URL Generating Service: This service is going to generate the unique shorten URL. The key is we should generate some UUID (which has almost zero chance to make a duplica) and combining with the request's timestamp, like snowflake mode. Then with one more hash algorithm wrapping this snowflake in, this will get us almost guaranteed unique URL.
  4. Caching: Redis is the main cache layer component, it should be functioning as a Most Recent Used, I presume that a recent used URL will soon be used again, so if a URL is used (From the Persistent DB maybe), then we save it here.
  5. Persistent DB: With a large scale of shorten URL system, this is a database that almost need to be partitioned carefully, one way is to shard the database based on user's ID, location, and probably we may want to maintain a user activity log, to balance the database's workload.