Design URL Shortener

Core Logic: Hashing and Mapping

At its most fundamental level, a URL shortener must perform a bijection between a long URL and a short code. We avoid using the raw long URL as the database key because long strings are inefficient for indexing and lookup operations. Instead, we generate a short, unique identifier, typically six to eight characters long, composed of base62 characters (A-Z, a-z, 0-9). The core reasoning is to reduce the storage footprint and optimize the lookup speed by keeping the indexed keys small. We use a hashing function to map the long URL, but because collisions can occur, we must implement a detection mechanism. If a collision is found, we append a salt or a sequence counter to the input URL and re-hash until a unique code is found, ensuring the mapping remains deterministic and reliable for future lookups in our persistent storage layer.

import hashlib, base64

def generate_short_code(long_url, salt=""):
    # Concatenate salt to handle potential hash collisions
    raw_hash = hashlib.md5((long_url + salt).encode()).digest()
    # Convert bytes to base64 and strip padding for a URL-friendly code
    encoded = base64.urlsafe_b64encode(raw_hash).decode()[:7]
    return encoded

# Example usage: converting a long URL to a short slug
print(generate_short_code("https://www.example.com/very/long/path"))

Database Strategy

A high-performance URL shortener relies heavily on read latency. Since the number of times a link is accessed typically far exceeds the number of times a new link is created, we prioritize read speed. A key-value store or a highly indexed relational database is ideal here. We store the mapping as a document containing the short code (our primary key), the long URL, the creation timestamp, and potentially metadata like user ID or expiration dates. Because we perform lookups by short code constantly, the database index must be highly optimized for this specific column. We avoid complex joins or secondary indexes to keep the storage engine lean. If the load is extreme, we horizontally partition our data based on the short code ranges to ensure that no single database node becomes a bottleneck for the system's traffic.

class URLStore:
    def __init__(self):
        # Simulation of an in-memory index for O(1) lookups
        self.db = {}

    def save_mapping(self, short_code, long_url):
        # Storing with a timestamp for potential cleanup/TTL jobs
        self.db[short_code] = {"url": long_url, "created": 1672531200}

    def get_url(self, short_code):
        return self.db.get(short_code, {}).get("url")

storage = URLStore()
storage.save_mapping("abc1234", "https://google.com")

Handling Scale with Counters

Relying purely on hashing can lead to collisions as the dataset grows, which requires constant database queries to check for existing codes. A more robust, collision-free approach is to use a distributed counter service or a global sequence generator. By assigning a unique, monotonically increasing integer to every new URL request, we can convert that integer to a base62 string. This removes the randomness of hashing and guarantees that every short code generated is unique without needing to check for collisions in the database. This approach requires a centralized, high-availability counter service (like an atomic incrementor) that acts as the source of truth for new assignments. While this adds a dependency on a sequence generator, the tradeoff is significant: zero collisions and high predictability in URL generation, which is far more scalable for systems expecting billions of links.

def encode_base62(num):
    # Map integer ID to base62 character set
    chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
    res = []
    while num > 0:
        num, rem = divmod(num, 62)
        res.append(chars[rem])
    return "".join(reversed(res))

# Unique IDs prevent collisions entirely
print(encode_base62(1000000)) # Unique code for the 1-millionth link

Caching and Traffic Optimization

For a system that serves millions of users, querying the database for every single redirect would be prohibitively slow and expensive. We must implement a caching layer, such as an in-memory store like a distributed cache cluster, to keep the most frequently accessed URLs readily available. When a user requests a short URL, the application first checks the cache. If the key exists (a cache hit), we return the long URL immediately without hitting the primary database. If it is a cache miss, we fetch from the database, store the result in the cache, and then redirect the user. We should implement an eviction policy like Least Recently Used (LRU) to ensure that the cache capacity is always dedicated to the most active links. This dramatically reduces read latency and offloads the database, making the service responsive even during heavy traffic spikes.

cache = {}

def get_redirect_url(short_code, db):
    # Check cache first for rapid response
    if short_code in cache:
        return cache[short_code]
    # Fetch from database on miss
    long_url = db.get_url(short_code)
    if long_url:
        cache[short_code] = long_url # Populate cache
    return long_url

API Gateway and Redirection

The final stage of the user interaction involves the actual HTTP redirection. The server should return a 301 (Permanent Redirect) status code if the URL mapping is considered static, or a 302 (Found) status code if the intent is for temporary redirection or tracking analytics. The API gateway handles these requests by parsing the incoming path, stripping the short code, and issuing the redirect headers. We must ensure that our headers are lightweight and that the connection is terminated as close to the user as possible. By offloading the redirection logic to a global content delivery network (CDN) or an edge-based proxy, we can minimize the distance the request travels. This architectural decision ensures that even if our core database is undergoing maintenance, the high-traffic redirection paths remain available to users based on cached edge responses.

class Redirector:
    def handle_request(self, short_code):
        url = get_redirect_url(short_code, storage)
        if url:
            # 301 for permanent, 302 for analytics/temporary
            return f"HTTP/1.1 301 Moved Permanently\nLocation: {url}\n"
        return "HTTP/1.1 404 Not Found"

service = Redirector()
print(service.handle_request("abc1234"))

Interview questions

All System Design interview questions →

Check yourself

Take the full System Design quiz →