# URL Shortener

A **URL shortener** is a widely used service that converts long URLs into shorter, more manageable links. Think of services like **Bitly** or **TinyURL**—they allow users to take long URLs and generate short, unique URLs that redirect to the original link.

In this blog, we’ll cover:

* **Understanding how a URL shortener works**
* **Detailed Low-Level Design (LLD)**
* **Java implementation with Base62 encoding**
* **Common interview questions and answers**
* **Scalability considerations**

<figure><img src="/files/leBGNVVcpCIGGnOWiTcy" alt=""><figcaption><p>URL Shortner </p></figcaption></figure>

***

### **1️⃣ How Does a URL Shortener Work?**

When a user provides a long URL, the system generates a unique short URL. The mapping is stored in a database, so when someone accesses the short URL, they are redirected to the original long URL.

#### **Flow:**

1. User enters a **long URL**.
2. The system generates a unique **short URL** using **Base62 encoding**.
3. The short URL and long URL are stored in a database.
4. When a user visits the short URL, the system looks up the long URL and redirects the user.

***

### **2️⃣ Low-Level Design (LLD)**

#### **Functional Requirements:**

✅ Generate a short URL for a given long URL\
✅ Redirect users when they visit the short URL\
✅ Handle large-scale traffic efficiently

#### **Non-Functional Requirements:**

✅ High availability and low latency\
✅ Idempotency (same long URL should generate the same short URL)\
✅ Scalability to handle millions of URLs

***

### **3️⃣ Components in LLD**

#### **1. URL Generator**

* Generates a unique short URL using **Base62 encoding**.

#### **2. Database**

* Stores mappings between short and long URLs.

#### **3. Redirect Service**

* When a short URL is accessed, it retrieves the corresponding long URL and redirects the user.

***

### **4️⃣ Class Diagram (UML)**

```plaintext
+-----------------+
|  URLShortener   |
+-----------------+
| - counter: long |
| - storage: Map  |
+-----------------+
| + shortenURL()  |
| + getLongURL()  |
| + encode()      |
| + decode()      |
+-----------------+
```

***

### **5️⃣ Java Implementation**

#### **Step 1: URL Shortener Service**

```java
import java.util.*;

public class URLShortener {
    private static final String BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int BASE = 62;
    private static long counter = 1;
    private static final Map<String, String> shortToLong = new HashMap<>();
    private static final Map<String, String> longToShort = new HashMap<>();

    // Encode ID to Base62
    private String encode(long id) {
        StringBuilder shortURL = new StringBuilder();
        while (id > 0) {
            shortURL.append(BASE62.charAt((int) (id % BASE)));
            id /= BASE;
        }
        return shortURL.reverse().toString();
    }

    // Decode Base62 to ID
    private long decode(String shortURL) {
        long id = 0;
        for (char ch : shortURL.toCharArray()) {
            id = id * BASE + BASE62.indexOf(ch);
        }
        return id;
    }

    // Generate Short URL
    public String shortenURL(String longURL) {
        if (longToShort.containsKey(longURL)) {
            return longToShort.get(longURL);
        }
        String shortURL = encode(counter);
        shortToLong.put(shortURL, longURL);
        longToShort.put(longURL, shortURL);
        counter++;
        return "http://short.ly/" + shortURL;
    }

    // Retrieve Long URL
    public String getLongURL(String shortURL) {
        String key = shortURL.replace("http://short.ly/", "");
        return shortToLong.getOrDefault(key, "URL Not Found");
    }

    public static void main(String[] args) {
        URLShortener urlShortener = new URLShortener();
        
        String longURL = "https://example.com/some/very/long/url";
        String shortURL = urlShortener.shortenURL(longURL);
        System.out.println("Shortened URL: " + shortURL);
        
        String originalURL = urlShortener.getLongURL(shortURL);
        System.out.println("Original URL: " + originalURL);
    }
}
```

***

### **6️⃣ How Are URLs Made Short?**

The **Base62 encoding** system is used to convert a numerical ID into a **short alphanumeric string**.

* It uses **digits (0-9), lowercase letters (a-z), and uppercase letters (A-Z) → 62 characters**.
* If we store each URL with an **auto-increment ID**, we can convert the ID into a short string.

#### **Example:**

| ID   | Base62 Encoding |
| ---- | --------------- |
| 1    | "b"             |
| 100  | "1C"            |
| 1000 | "g8"            |

***

### **7️⃣ Common Interview Questions & Answers**

#### **Q1: How does Base62 encoding work?**

👉 **Base62 encoding** converts a numeric ID into a string using 62 characters. It helps shorten the URL while maintaining uniqueness.

#### **Q2: How do we handle duplicate URLs?**

👉 We store a **longURL → shortURL** mapping. If the long URL already exists, return the same short URL.

#### **Q3: How can we ensure that the generated short URLs are unique?**

👉 We can:

* Use an **incrementing counter**.
* Use a **hash function (MD5/SHA256)** for randomness.

#### **Q4: How do we handle collisions in a hash-based approach?**

👉 If a hash collision occurs, we **append a random character** or use **re-hashing**.

#### **Q5: How to scale this system for millions of users?**

👉 We can:

* Use **distributed databases** (e.g., Cassandra, DynamoDB).
* Use **caching (Redis)** to speed up URL lookups.
* Implement **load balancing**.

***

### **8️⃣ Scaling Considerations**

| **Aspect**               | **Solution**                        |
| ------------------------ | ----------------------------------- |
| **Storage**              | Use NoSQL DB (e.g., MongoDB, Redis) |
| **Performance**          | Use in-memory caching (Redis)       |
| **Availability**         | Deploy across multiple servers      |
| **Short URL Collisions** | Use UUID-based hashing              |

***

### **9️⃣ Conclusion**

We have successfully designed and implemented a **URL shortener** using Java. The key concepts covered include: ✅ **Base62 encoding** for URL shortening\
✅ **HashMap-based storage** (can be replaced with a database)\
✅ **Scalability considerations**

This design can be improved by adding **rate-limiting, user authentication, and analytics tracking**.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jobprep.byterooms.com/system-design/lld/url-shortener.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.