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:

• 100 milion URL Generated per month
• read to write ration 100:1.
• high availability
• low redirect latency

API Design

We meed a web server with 2 endpoints. One to generate a short url (POST /generate_short_url). and one to retrieve a long url using a short url as a key

In order to store the mappings (short URL -> Long URL) we shall use a no sql DB (cassandra). This will improve on performance, contant O(1) time for reads, eventual consistency and it will be very easily scalable. We can always add more servers/memory.

The database communicates with an URL generation service. Its responsibility is to generate a short url from a long one. This can be done using hash-ing. Given that we would have multiple servers/nodes running this I propose having a coordonation service that feeds something like id-ranges to the url generation service to make sure that we generate unique ones.

On top of this we also need a reddis cache in which we can store the most frequent hits to not load the DB

WE would also add a cleanup worker that cleans up unused/expired urls from the DB

High-Level Design

Let's describe happy path for writing.

Client submits long URL and that would hit our Load balancer which redirects the traffic to one of our web servers. The webserver then calls our URL generation service. This service is the one responsible for generating the short url using hashing. The generation of the new key will also take into consideration an unique id which is provided from a bucket of ids returned by a coordination service. Its job is to provide each Url generation service with a bucket of new ids to chose from when the service starts or runs out of ids.

After the new url is generated we store it in a DB with a created at timestamp

happy path for reading.

client submits long url, we hit the load balancer then our servers. We first check if there is a reddis cache hit. If yes then return, if not we can fetch the mapping from the cassandra db.

We can also add a cleanup woprker that removes old keys from the DB that have not been used in a while

Regarding the storage layer. we never store data just on one server. We will replicate it. We use a replicating factor of 3. When an url mapping is written the database automatically sends coppies to the other pysical machines. If one machin failes the other 2 replicas still have the data and the system will automatically create. a copy.

We can use Sharding to improve data splitting. We will a mathematical function to decide where the data belongs to

Detailed Component Design

Let's describe happy path for writing.

Client submits long URL and that would hit our Load balancer which redirects the traffic to one of our web servers. The webserver then calls our URL generation service. This service is the one responsible for generating the short url using base62 encoding. The coordonation service provides our URL GENERATION SERVICE a bucked of ids when the server starts or runs out of ids. We store that last used id in memory RAM and we do base62 encoding on that. Let's say that the id is 1000001 we convert this into a base 62 (4C9r) and after we return we increment.

After the new url is generated we store it in a DB with a created at timestamp

happy path for reading.

client submits long url, we hit the load balancer then our servers. We first check if there is a reddis cache hit. If yes then return, if not we can fetch the mapping from the cassandra db and store it in the cache. We will add an expiration date on the cache.

We can also add a cleanup worker that removes old keys from the DB that have not been used in a while.

Regarding the storage layer. we never store data just on one server. We will replicate it. We use a replicating factor of 3. When an url mapping is written the database automatically sends coppies to the other pysical machines. If one machin failes the other 2 replicas still have the data and the system will automatically create. a copy.

We can use Sharding to improve data splitting. We will a mathematical function to decide where the data belongs to

1. Shard Routing: The "Traffic Director"

You mentioned using a mathematical function for sharding, but in an interview, you need to specify where that math happens. If the Web Server has to do the math for every request, it needs to know exactly how many shards exist at all times.

The Solution: The Shard Proxy / Routing Layer

Instead of the Web Server talking directly to 100 different database nodes, we use a Routing Layer (often built into the NoSQL client or a proxy like Vitess or specialized routers in Cassandra).

• The Process: The Web Server sends the ShortCode (the Partition Key) to the Database Proxy.
• The Math: The Proxy calculates $Hash(ShortCode) \pmod n$ and routes the request to the correct physical shard.
• Abstraction: This allows you to add more shards without updating the code on every single Web Server.

2. Hotspot Management: The "Celebrity Link" Problem

This is a classic "Senior" trap. Even with a replication factor of 3, if a celebrity tweets a link, all millions of clicks will hit the same shard and the same 3 replicas. This is a "Hotspot."

Strategy A: Multi-Level Caching (The Shield)

You already mentioned Redis, but for a global hotspot, even one Redis instance might struggle.

• L1 Cache (In-Memory): Store the top 100 most popular links directly in the RAM of the Web Server itself. This is lightning fast and never even leaves the server.
• L2 Cache (Distributed): This is your Redis cluster.

Strategy B: Virtual Nodes (Consistent Hashing)

To prevent one physical server from being naturally "unlucky" with too many popular keys, we use Virtual Nodes. One physical server acts as 100 "virtual" points on the hash ring. This ensures that even if one area of the ring gets busy, the load is spread across many physical machines.

3. Traffic Distribution: Beyond the Load Balancer

You mentioned the Load Balancer, but at a massive scale, a single Load Balancer becomes a bottleneck (and a single point of failure).

The Strategy: DNS Round Robin + Layer 4/7 Balancing

1. DNS Level: When a user types your URL, the DNS returns different IP addresses for different Global Load Balancers (GLBs) based on the user's region.
2. L4 Balancer (Network): A high-speed hardware balancer (like F5 or Maglev) handles millions of raw packets and sends them to...
3. L7 Balancer (Application): Software like NGINX or Envoy looks at the actual HTTP request (the path, the headers) and sends it to the right Web Server.

The Distributed Level (Zookeeper): Zookeeper stores the "Last Allocated ID" in a persistent node (znode). When a KGS node requests a bucket, Zookeeper performs an atomic Compare-and-Swap (CAS). It says: "If the current value is X, change it to X+1,000,000 and give the range to this node." If another node asks at the exact same millisecond, the CAS will fail for the second node, and Zookeeper will force it to wait and grab the next range. This ensures no two KGS nodes ever hold the same bucket.

The Thread Level (KGS Node Memory): Inside a single KGS node, you might have 20-50 threads handling requests simultaneously. As we discussed, we use a Thread-Safe Atomic Counter (AtomicLong in Java or similar). This uses a CPU instruction called LOCK INC to ensure that even if two threads try to increment at the same nanosecond, the hardware serializes them. One gets 101, the other gets 102.