Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Support custom aliases as an optional feature.
• Short URL should have optional expiration date, defaults to none.

Non-Functional Requirements:

• List the key non-functional requirements (eg low latency, scalability, reliability, etc.)...
• Redirect must be highly available.
• Redirect is the hot path, not the creation of the short URL.
• Redirects vastly outnumbers creations.

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

We have two main endpoints.

1. POST /urls- this creates a short url. The payload/body of the request would look like this { original_url : str, (optional) custom_alias: str, (optional) expiration_date: str/datetime }. This endpoint creates and returns the short url. Return codes: 201 - successfully created short url. 409 - if the custom alias is already taken. 400 - expiration date is older than current datetime.
2. GET /{shortCode} - this endpoints gets the original url from this service and then redirects to the original url. shortCode is path param and is the key to retrieve the long url from database. Return codes: 302 - client is redirected to the original/long url and we get analytics and its not cached as 301 would be. 404 - if shortCode isnt found in the DB.

High-Level Design

We have 4 main components: server(API), Key Generation Service, Cache and Database.

The two request flows:

1. POST endpoint flow - client sends the request to server, server then checks if payload is correct. if all good, we retreive shortCode from KGS and write to the database this new entry. and then send back to the client 201 and in body the short url. If client provided the custom alias, then we skip KGS and check in DB if the custom alias has been used.
2. GET endpoint flow - client cliks on the short url, on the server we take the shortCode and check if its in cache, if it is we send to client response 302 and it redirect to the location (orgUrl). if its not in cache then check db and cache it and return. if shortCode isnt found in either cache or db we return 404.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Detailed Component Design

First component, Key Generation Service (KGS).

KGS is two part component: service and database. KGS generates upfront a list of short codes and stores them in its own database, where we have code and status (used or not-sued). KGS loads a small batch of codes from KGS database and uses random() in the query and marks them used, so now KGS has the list in memory for faster access. KGS marks each batch as used in the db atomically before loading into memory, ensuring no two nodes ever hand out the same key. When server receives POST call, server asks KGS for the code and afterwards saves the whole new entity in the main database.

This component is single point of failure. If it goes down, server cannot create new short urls. That is why we need to make KGS redundant. One KGS database but multiple KGS services.

Second component, Cache.

Cache component is important in GET request flow.

This whole system mainly deals with GET requests not POST. Let's assume its 100:1 read/write ratio. First, cache would be populated whenever there's a GET request and the url is found in DB and then we cache it. System would cache 20% of urls that probably would be responsible for 80% of traffic. Main worries is eviction policy for the cached urls. I would use Least Recently Used principal, so when cache is full system drops items which were accessed least recently. Probably would add Time to Live (TTL) policy as well to drop urls that havent been accessed in a fixed time window and TTL would also ensure that urls with expiration date also are dropped. If user disables URL, explicitly purge it from cache immediately. For viral links need to use CDN.

Third component, Database.

Main DB is partitioned across multiple nodes using consistent hashing on the short code. Same code always maps to same node, every lookup hits only one shard directly. Adding nodes only moves small slice of data from one neighbor node.

This system favours availability over consistency — a newly created short URL may take a few seconds to propagate across nodes, which is acceptable. The main bottleneck at 10x traffic is the database layer — consistent hashing and read replicas would need to scale horizontally. KGS is the most fragile component; at extreme scale we'd consider replacing it with a distributed ID generation approach like Twitter's Snowflake

Rate limiting - Per-IP throttling on to the POST endpoint, like 100 urls per hour per IP, so someone cannot programmatically create unlimited short urls and ddos the server.

Bust handling on GET, to stop someone hammering the GET endpoint or bots crawling.

Implement via token bucket or sliding window counter sitting in front of server. Return 429 if limits are exceeded.

Short codes are generated using randomly sampled base62 characters (a-z, A-Z, 0-9), not sequential counters, ensuring the keyspace is unpredictable and resistant to enumeration attacks.