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.

To ensure low latency, high availability, and massive horizontal scalability, the system relies on the following core components:

* **API Gateway / Load Balancer:** Layer 7 routing and rate limiting.

* **Range Manager (etcd/Zookeeper):** A quorum-based consensus system to manage ID generation and prevent split-brain scenarios.

* **Caching Layer:** Redis for distributed caching, augmented by Local In-Memory Caches (e.g., Guava) on App Servers for viral hotspots.

* **Database (ScyllaDB):** A high-throughput, masterless NoSQL database chosen for its C++ performance and native horizontal scaling capabilities.

---

### 2. The Entry (Write Path) & Burst Handling

*Goal: Generate a unique short URL quickly while protecting the system from abuse.*

1. **Rate Limiting & Burst Handling:** When a user `POST`s to `api/v1/shorten`, the request hits the API Gateway. We use a **Token Bucket** algorithm based on the user's IP or API key. If a user bursts past their limit, the gateway immediately returns an **HTTP 429 (Too Many Requests)**. Critically, it includes a `Retry-After: 60` header to provide a backoff hint to clients.

2. **ID Generation (Avoiding Split-Brain):** The request routes to an App Server. To guarantee no URL collisions without bottlenecking the database, we use a block-allocation strategy.

* The App Server checks its local memory for an available ID.

* If depleted, it requests a new range (e.g., `100,000 - 200,000`) from the **Zookeeper/etcd** cluster. The quorum ensures that even if two servers request a range simultaneously, they are guaranteed mutually exclusive blocks.

* **Outage Handling:** If an App Server crashes, its unused IDs are lost. Because our ID space is massive, this gap is an acceptable trade-off for high performance.

3. **Encoding & Storage:** The App Server takes the unique base-10 ID, converts it to **Base62** (creating the short code), and writes the mapping to ScyllaDB. It then returns a `201 Created`.

---

### 3. The Exit (Read Path) & Hotspot Mitigation

*Goal: Redirect users to the long URL with absolute minimum latency, handling viral traffic spikes safely.*

When a user `GET`s `api/v1/long/:shortUrl`, the system prioritizes speed through multiple fallback layers:

1. **CDN & Edge Caching:** Geographical DNS routing directs the user to the nearest edge node. If the short URL is heavily requested in that region, the CDN handles the 301 redirect entirely (0-10ms latency).

2. **App Server Local Cache (Hotspot Handling):** For hyper-viral links that bypass the CDN, querying Redis might create network bottlenecks. The App Servers maintain a small, LRU (Least Recently Used) local memory cache (e.g., Caffeine/Guava) for the top 1% most popular URLs, allowing instant redirection.

3. **Distributed Cache (Redis):** If not in local memory, the server checks the Redis cluster.

4. **Database Fallback & Cache Miss Path:** On a Redis cache miss, the App Server queries ScyllaDB.

* **Thundering Herd Protection:** If a popular URL's TTL expires, 10,000 concurrent requests might miss the cache simultaneously and crash the database. To prevent this, we implement a **Distributed Mutex Lock**. The first request acquires the lock, queries ScyllaDB, and repopulates Redis. The remaining 9,999 requests wait a few milliseconds for the cache to refresh, protecting the database layer.

5. **Redirect:** The server returns an **HTTP 301 (Moved Permanently)** to reduce future server load, or a **302 (Found)** if granular click analytics are explicitly required for that URL.

---

### 4. Horizontal Scalability & High Availability

* **Database Sharding Strategy:** We **do not** use range-based sharding for the database, as that causes write hotspots. Instead, we use ScyllaDB’s native **Hash-Based Partitioning**. The `shortUrl` string is hashed, and the data is distributed evenly across the masterless ring. To scale horizontally, we simply add more nodes to the ScyllaDB ring, and data rebalances automatically.

* **High Availability:** We configure ScyllaDB with a Replication Factor of 3 (`RF=3`). Every URL is copied to three separate physical nodes. If a database node suffers an outage, reads and writes seamlessly route to the surviving replicas.

* **Consistency:** We accept **Eventual Consistency** for the read path. It is acceptable if a newly created URL takes a few milliseconds to propagate across all database replicas and global cache nodes.

### 5. Data Cleanup

For temporary URLs, we utilize a Time-To-Live (TTL) attribute. Instead of running heavy batch deletion jobs that consume resources, we utilize ScyllaDB and Redis's native row-level TTL features. The database automatically tombstonnes and reclaims the storage of expired URLs during its standard background compaction processes.

Limitation and Future Scope

We know that here we use incremental based counter and then based conversation that gives us some advantage in a distributed system but there are some limitation as well. Like incremental based id can easily be predictable so security concern is there.

In future like we devide temporary url and permanent url. We can have a separate system like secure url . The api can be like api/v1/secure/shorten/:longUrl

The thing is for the secure url things instead of using incremental counter we can use random unique id -> base conversation -> check for duplicate and go on. We can also explore some hashing based techniques there

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10