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
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:
User enters a long URL.
The system generates a unique short URL using Base62 encoding.
The short URL and long URL are stored in a database.
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:
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.
Last updated