System Design Interview Question: Design URL Shortener

This is a system design interview question, which is to design a URL shortener tool like TinyURL or Bitly from the ground up. We'll cover everything from design requirements, architecture, and component design to scaling for high-performance and security best practices.

Defining the Scope: Functional and Non-functional Requirements

First, we need to define this system's functional and non-functional requirements.

We have two functional requirements:

1. When given a long URL, we have to create a short URL
2. When given a short URL, we must redirect the user to the long URL.

The non-functional requirements for our service are to prioritize low latency (fast responses) and high availability (always online).

Clarifying Questions for the Interviewer

Here are some clarifying questions that we might ask the interviewer to ensure we're aligned on the system's scale:

• Usage: Estimate the number of URLs we'll need to create each second (let's say it's 1000).
• Characters: Can we use numbers and letters (alphanumeric) or other symbols? (We'll assume alphanumeric characters).
• Uniqueness: Do we generate a unique short URL each time, even if multiple users submit the same long URL? (For this design, we will).

Estimation: Data Math

With this information, we need to calculate how long the URL should be after shortening. Of course, we're trying to make it as short as possible, but we need to keep in mind the number of created URLs each year.

First, let's estimate the number of unique URLs needed for a significant period. A common approach is to plan for at least a few years of operation. For simplicity, let's calculate for 10 years.

• Seconds in a Year: Seconds in a year: 60 seconds/minute × 60 minutes/hour × 24 hours/day × 365 days/year = 31.536 million seconds
• Total Seconds in 10 Years: 31.536 million × 10= 315.36 million seconds
• Total URLs in 10 Years: 1,000 × 315.36 million = 315.36 billion unique URLs

This means our database will handle 1000 writes per second and every year, we will have 1000 × 60 × 60 × 24 × 365 = 31.5B URLs created. If we assume that we will typically have 10x more reads than writes, that means that we'll be getting more than 10 × 1000 = 10000 reads per second.

Now, we need to figure out how many characters will give us enough unique short URLs for our 10-year volume. Given that the character set size is 62, the length of the URL identifier can be calculated as follows:

• 62¹ = 62 unique URLs (1 character)
• 62² = 3844 unique URLs (2 characters)
• …and so on.

Continuing this calculation, we see that 62⁷ (around 3.5 trillion) is the first value larger than our projected 315 billion URLs needed.

Therefore, to support our projected growth over the next ten years, our shortened URLs need a minimum of 7 characters.

High-Level Architecture

Our system will have these key components:

Users: We will have users who send their long URLs to be shortened or who send us a short URL, and we need to redirect them to the long URL.

Load Balancer: All of these requests go through a load balancer, which distributes the traffic across multiple web server instances to ensure high availability and balance of the load.

Web Servers: These server replicas are responsible for handling the incoming HTTP requests.

URL Shortener Service: We also need a URL shortener service that contains the core logic for generating short URLs, storing URL mappings, and retrieving the original URLs for redirection.

Database: Stores the connection between short URLs and their long counterparts. Before designing the database, we need to consider the potential storage requirements for our shortened URLs.

Each URL will include the unique identifier (roughly 7 bytes), the long URL (up to 100 bytes), and user metadata (estimated at 500 bytes). This means we need up to 1000 bytes per URL. Over ten years, with our projected volume, this translates to approximately 315 terabytes of data.

Before moving any further, let's first think about the API Design of our single web server.

API Design

Let's define the basic API operations for our service. As stated in our functional requirements, we will use a REST API, and we need two endpoints.

1. Create a Short URL (POST /urls)

Input: JSON payload containing the long URL {“longUrl”: “https://example.com/very-long-url"}

Output: JSON payload with the shortened URL {“shortUrl”: “https://tiny.url/3ad32p9"} and 201 Created status code.

If the request is invalid or malformed, we'll return 400 Bad Request response, and in case the requested URL already exists in the system, we'll respond with 409 Conflict.

2. Redirect to Long URL (GET /urls/{shortUrlId})

Input: shortUrlId path parameter

Output: Response with 301 Moved Permanently and the newly created short URL in the response body as JSON { "shortUrl": "https://tiny.url/3ad32p9" }

301 status code instructs the browser to cache the information, which means that the next time the user types in the short URL, the browser will automatically redirect to the long URL without reaching the server.

However, if you want to track each request's analytics and ensure it goes through your system, use the 302 status code instead.

Database: Storing the shortened URLs

The next part is the Database layer. This layer stores the mapping between short URLs and long URLs. It should be optimized for fast read and write operations.

The schema could be simple: a primary key for the short URL id and fields for the long URL and possibly creation metadata.

{
  "shortUrlId": "3ad32p9",
  "longUrl": "https://example.com/very-long-url",
  "creationDate": "2024-03-08T12:00:00Z",
  "userId": "user123",
  "clicks": 1023,
  "metadata": {
    "title": "Example Web Page",
    "tags": ["example", "web", "url shortener"],
    "expireDate": "2025-03-08T12:00:00Z"
  },
  "isActive": true
}

Here, we mostly need to think about the reads we will get to the database. If we typically get 1000 Writes per second, then we can assume that we at least get 10–100.000 Reads per second.

In this case, we need to use a high-performance database that supports fast reads and writes. That means we need to go with a NoSQL database (like a document store like MongoDB, a wide-column store like Cassandra, or a key-value store like DynamoDB) since they're specifically designed to handle a large amount of scale.

It won't be ACID compliant, but we are not concerned about it because we're not going to do a bunch of JOINs or complex queries, and we don't need those ACID rules and atomic transactions here.

URL Shortener Service

One of the core parts of this system is the URL Shortener Service. This service generates short URLs without introducing collisions between different long URLs pointing to the same short URL.

There are various methods to implement this service; here are some of them:

• Hashing: Generate a hash of the long URL and use a part of it as the identifier. However, hashing can lead to collisions.
• Auto-increment IDs: Use a database auto-increment ID and encode it to a short string. This ensures uniqueness but might be predictable.
• Custom Algorithm: Design a custom algorithm to generate unique IDs with a mix of characters to ensure uniqueness and non-predictability.

For example, to avoid collisions, there's a very simple way—we can generate all the possible keys with 7 characters and store them in a database as keys, where the key is the generated URL and the value is boolean; if it's true, then this URL is already used, and if it's false, then we can use this URL to create a new map.

So, whenever a user requests to generate a key, we can find a URL from this database that is not currently in use and map it to the long URL in the request body.

Do you think we will use an SQL or NoSQL database in this case? Consider a scenario where two users asked to shorten their long URLs, and they both got mapped to the same key from this database.

In this case, the URL will be mapped to one of their requests, and the other one will be broken. So, we will use SQL because it comes with ACID properties. We can create a transaction for each session here to perform these steps in isolation, and we won't have such issues in this case.

High Availability & Low Latency

Our current system obviously won't be able to handle 1000 URLs per second of traffic.

Caching

To make this more scalable, we first need a Caching layer (e.g., Redis) to cache popular URLs for quick retrieval in an in-memory cache with tools like Redis.

Given that some URLs might be accessed much more frequently than others, we need an eviction policy that prioritizes frequently accessed items. Two suitable caching eviction policies for this scenario are:

• The LRU eviction policy removes the least recently accessed items first. This policy is effective for a URL shortener because it ensures that the cache keeps the most recently and frequently accessed URLs available, which can significantly reduce access times for popular links.
• Or a Time To Live TTL-based eviction policy assigns a fixed time-to-live to each cache entry. Once an entry's TTL expires, it is removed from the cache. This policy can be useful for URL shortening services to handle the caching of URLs that are only popular for a short duration.

TTL can also help us automatically refresh the cache contents and can be combined with other policies like LRU for more effective cache management.

Database Scaling: Combining Replication and Sharding

We need to implement replication and sharding strategies to ensure that the database supports high availability, fault tolerance, and scalability.

Considering that our 7-character set has 3.5T unique URLs, we can use key-based sharding to distribute the URL records evenly across multiple shards.

Let's say we distribute it across 3 shards, and each shard will store approximately 1.16T URLs. This ensures scalability as the number of URLs grows.

We can also implement master-slave replication within each shard to ensure high availability and fault tolerance. This setup allows for quick failover and recovery in case of node failures.

Optionally, if the service targets a global user base, we can consider geographical sharding and replication to minimize latency and improve user experience across different regions.

This combination allows the service to handle a large volume of URL shortenings and redirections with minimal downtime and fast response times.

Security Considerations

Here are some security considerations to keep in mind for our service:

• Input Validation: Let's sanitize every URL a user submits. We must check for valid protocols (HTTP, HTTPS, etc.) and ensure the URL is well-formed. This helps prevent injection attacks.
• Rate Limiting: We can protect our service from DDoS attacks by limiting the number of requests a single source can make. Consider a token bucket algorithm for this.
• Monitoring and Logging: A robust logging system (like the ELK stack) is essential. It lets us analyze logs to find bottlenecks and suspicious activity and ensure overall system health.
• Obfuscation: We don't want easily predicted short URLs. To deter attackers from guessing valid links, let's add randomness to our generation algorithm.
• Link Expiration: Optionally, we can consider allowing users to set expiration dates on their shortened URLs. This limits the lifespan of potentially malicious links.

If you'd like to learn more about each component we discussed here, I have a detailed System Design Interview Concepts Tutorial that goes over each one in more detail.

System Design Interview Concepts [Full Tutorial]

Join my Free Web Developers Community and Get Access to All Courses.