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:

• Low latency: user input must be returned near instantaneously
• Scalability is of medium importance: the primary action of the system is not at all compute heavy, scalability should primarily focused on horizontal not vertical; more machines should be brought online according to demand in regions that are aligned with their proximity to the average request's request origin
• Reliability must be extremely high: the service should always be available
• Idempotency is important as well: requests should result the same way across the same input

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

There should be an API like "generate_tiny_url()". It should accept user input, and clean and validate it to prevent injection attacks and ensure all input is alphanumeric. Then pass the string through a hashing function to produce the tiny URL, which is then returned to the user as a path underneath the service's top level domain, for example: turl.com/<hash>

There should also be a forwarding API, that forwards traffic directed at the returned path to the actual long URL.

High-Level Design

The client makes the request to the generate_tiny_url() API. The request hits the load balancer which performs a round-robin distribution to an API_gateway instance by performing a hash of the request's source IP header value and forwards the request. The API_Gatway creates a "Request" instance that contains all of the request details. The API_Gateway instance then validates and cleans the requests incoming long url, returning an error if it isn't valid. If it is valid, the API_Gateway instance then uses it as a lookup key in the DB read replica to see if a tiny url has already been generated, and if so, returns the tiny_url associated. Otherwise, passes off the request details to the server responsible for performing the URL translation. This is then written to the database (which then writes it to the read replica when available). The result of the translation is then passed back to the API_Gateway instance, which then sends the response containing the tiny URL to the forward proxy to mask the IP address of the API Gateway when the forward proxy forwards the response to the client. The API_gateway should also handle forwarding requests, looking up the long url in the read replica of the db to forward the client to, or returning an error if the short url doesn't tie to a long url

Database Design

Within the redis instance attached to each of the load balancers: The IP address of the request is used as a lookup key, and its associated attributes are 'allowed : BOOL' and 'average_requests_per_minute: float'.

The main DB containing the URL translations contains an indexed column which contains the long url with a primary key constraint. This works given the deterministic translation process: the result is the same every time for a given long url. A secondary column is the translated tiny url for that primary key.

Both redis and the main database use a 'least recently requested' policy to determine evictions as the databases grow in size.

Detailed Component Design

Note: all blocks marked with an asterisk should scale horizontally depending on network demand.

The load balancer(s) is responsible for forwarding and validating request traffic, keeping track of the incoming IP addresses and the rate at which they are making requests. If their rate exceeds a certain threshold, they are marked as blocked in the redis instance and the request automatically fails to pass further than the load balancer. Presumably the request will be routed to the nearest geographic load balancer, so tracking IP addresses shouldn't be that difficult, and therefore in the case of a scraping or DDOS situation, the threshold should be low enough that that all load balancers should have similar records of violating IP addresses.

The API_Gateway is responsible for parsing the user input for injection attacks and a valid request format: long urls should be formatted appropriately (no raw IP addresses, domains labeled accordingly) and be non-malicious endpoints (the API_gateway should have an internal block-list of domains). After the long url is validated, the API Gateway should then check for an existing record via the read replica and return the short url if so. Otherwise, pass the request off to the server to perform the long url to short url translation which is then returned to the API Gateway to be sent back via the forward proxy to the client, and the translation is also written to the database. If a request comes in to simply be forwarded to the long url using a short url as a key, then the API_gateway sends the forwarding signal back to the client to send them to the long url after looking it up in the DB read replica via the short key.