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

URL Shortner

---

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)

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

---

5️⃣ Java Implementation

Step 1: URL Shortener Service

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.