System Design: Designing a Scalable & Highly Available URL Shortener

High-level Design of URL Shortner

Tiny URL System Design

Introduction

System design Interview problems are intentionally open-ended. It gives an interviewer opportunity to evaluate design skills and also the depth of technical concepts. Day-to-day engineering work involves architecting a lot many scalable systems. This interview provides a platform to judge a candidate’s problem-solving & communication skills as well.

It’s difficult to nail a System Design round without sufficient preparation & practice. Also, it’s intimidating for candidates who don’t have a background in Distributed Systems. At times, interviewees seem to lose their focus & deviate from the topic if they don’t follow a structured methodology.

It’s essential to have conceptual clarity of system design concepts before tackling a problem. In this article, I have chosen a simple problem of designing a URL Shortening service. It’s an easy problem for any beginner. There is no concrete right or wrong answer to a system design problem. However, the candidate has to justify the design choices made while solving the problem.

We will be looking at how we must go about solving a design problem systematically. Along the way, I’ll also touch upon distributed system fundamentals, APIs, Database Schema design & design trade-offs. Let’s get started.

Let’s start the design

Understanding the problem/product

The problem statement here is ‘Design a URL Shortner like tinyurl.com’. If you don’t know or have never heard of TinyUrl.com, take a pause & visit the website. Before beginning the discussion, one needs to understand the product & it’s behaviour.

Tiny URL

Having used the product will give you an idea of how clients interact with it. Further, it’s always good to ask the interviewer a few clarifying questions —

• Who are the users of this system — Enterprise users or in general any user
• How are they going to use it — Web Browsers or Mobile devices
• Application’s goal — Shorten any URL on the internet or organization’s internal URL
• Can customers provide custom short URLs?
• Data storage — Temporary short URLs or permanent ones

The responses to the above questions will help one gain clarity about the problem. Asking questions also shows that an individual doesn’t jump into the solution. It helps one to clear any doubt and proceed with the design with enough clarity.

Requirements

Let’s break our requirements into Functional & Non-Functional requirements.

Following will be the Functional requirements:-

1. The system should convert a long URL to a short URL
2. On typing short URL in the browser, the user must be redirected to the long URL link
3. User should have the ability to provide a custom short URL for a given long URL
4. The system should store the URL for a year & later purge all old entries

Following will be the Non-Functional requirements:-

1. The service must be highly available & scalable
2. It should handle high throughput with minimum latency
3. The application should be durable and fault-tolerant

As we have clarity on what needs to be designed, we can proceed to the next step in design.

CP vs AP System

We need to decide whether the system will be a CP or an AP system.

For URL shortener, are we fine to compromise Consistency over Availability? This is something that needs discussion with the Interviewer.

In this case, let’s assume that if a new URL is created it may not be immediately available for use. For eg:- A newly created URL can be available after a delay of few milliseconds. Until then, the system will throw an error indicating the URL is not found. The system will be highly available and continue to respond to the user’s queries.

As we have chosen to design an AP system, every read request may not follow the most recent write. However, the system will be eventually consistent.

Capacity Estimation

Traffic Computation

While designing a large-scale system, we need to know how many users will use the system. What will be the data access patterns? how many application & data servers will be needed.

The answer to the above questions in guestimation. The candidate is supposed to come up with a rough estimate of how many users will use the service?

Assume that we have 200 Mn users. Out of the 200Mn users, 2 Mn users can be actively shortening the URL. For each day, on average, let’s say 10 requests (read + write) are received.

So, we have 20 Mn such records created every day. The remaining 20Mn users would be getting the long URL back from the short URL. Assuming each user fires 10 requests, we have an overall 200 Mn request. This turns out to be 2300 requests/per sec.

Traffic?

Storage Computation

20 Mn URLs are generated every day. Let’s say the system is designed to handle requests for the next five years.

Total URLs to be stored = 20 Mn * 30 (days) * 12 * 5 = 36 Bn

We will store long URL, short URL, created and modified fields in the data store. Every record will consume 0.5 Kb of memory. Thus, the total storage needed will be 36 Bn * 0.5 Kb = 18 TB

APIs

As agreed in the requirements, we will have the below APIs:-

• Shorten long URL

Shorten long URL

The request body will take customShortUrl as an optional parameter. If not present, it will assume empty.

Backend server will perform validation on the length of the long URL. Accordingly, it will return the following response codes:-

▹ 400- Bad request

▹ 201- Created. Url mapping entry added

▹ 200- OK. Idempotent response for the duplicate request

• Fetch long Url from short URL

Long URL from short URL

If the system finds the long URL corresponding to the short URL, the user will be redirected. The HTTP response code will be 302.

The service will throw a 404 (Not Found) in case the short URL is absent. It will perform a length check on the input. In case, the length exceeds the threshold, 400 (Bad Request) will be thrown.

Building Blocks & URL Shortening Algorithm

Key Components

Following will be the key components in the URL shortening application:-

1. Clients- Web Browsers/Mobile app. It will communicate with the backend servers via HTTP protocol
2. Load Balancer- To distribute the load evenly among the backend servers
3. Web Servers- Multiple instances of web servers will be deployed for horizontal scaling
4. Database- It will be used to store the mapping of long URLs to short URLs

Below is a high-level sketch of the components and interaction between them:-

High-level Design of the system

Shortening Algorithm

We estimated that the system would need to store 36 Bn URLs. The short URL can consist of lower-case (‘a’ — ‘z’), upper-case (‘A’-’Z’) & numbers (0–9). To support 36 Bn URLS, the short URL must be at least 6 characters long.

⁶²⁶ = 56.8 Bn.

One of the simplest approach to convert a long URL to a short URL is to use hashing. Pass the long URL to a hashing function to obtain a fixed-length string (For eg:- 32-byte string). Then extract the first 6 characters to get the short URL.

However, there are two downsides of using the above approach:-

1. Two different URLs can map to the same short URL. This is as a result of collisions. Using a uniform hash function can reduce the chances of a collision. Additionally, a pseudo-random number can be used for hashing
2. If a User tries to shorten the same long URL multiple times, he should get a different result every time. In this case, due to collision, chances that the long URL returns the same short URL are high

URL Generator service

We need to guarantee uniqueness for every long URL that is being shortened. For this, we can pre-generate a set of short URLs and persist it in the database. A new layer can be introduced to manage these short URLs. Let’s call this service layer URL Generator Service.

The service will act as a source of all short URLs. The URL Shortener service will get a new short URL from this service. Subsequently, it will store the mapping between long & short URLs. Following diagram illustrates this process:-

Role of URL Generator Service

The above process will ensure that every request is allocated a unique short URL. There are a few challenges with the above approach. We considered the case of a single service requesting a tiny URL. What if multiple URL Shortener services running are running?

Concurrency Issues

Scaling the above system may result in concurrency issues. If not handled correctly, the same URL may get allocated to two different services.

Scaling the URL Shortener service

To solve this, we can associate state to a tiny URL. The tiny URL can have two states — ACTIVE, and INACTIVE. By default, all URLs will be in an INACTIVE state. Once it’s allocated to a client, it must be marked as ACTIVE. Only ACTIVE URLs can be assigned to clients.

To improve latency, the URL Generator Service can prefetch all tiny URLs from the datastore. This will avoid database calls for every new request. Moreover, it can now use a locking data structure to synchronize access by multiple client applications.

Database Schema

We will need a single table to store the mapping between long URLs and short URLs. Following schema can be used:-

URL Mapping schema

Since the short_url column is a primary key, its indexed and lookups will be quick. Two timestamp fields created_at and modified_at have been included. These fields will help to purge out all the old entries in the table.

To decide between RDBMS or No-SQL database system, let’s revisit our storage estimates. We want to store at least 18 TB of data. Further, we want to serve the requests with minimum latency.

It’s better to have the data distributed on different machines. This will prevent a single point of failure. Hence, data sharding will be necessary in this case.

Further, we don’t have a data model with relations. There is no requirement for joins here. Also, we expect our data to grow in size gradually. Additionally, our system is supposed to function as an AP system.

Taking the above points into account, NoSQL seems like a clear winner here. NoSQL databases have built-in sharding and are easier to scale.

Trade-offs & Bottlenecks

How to scale reads

• Caching- By introducing a cache, we can scale the read queries. If multiple queries are received with the same short URL, the service can return long URL from the cache. We can use LRU (Least Recently Used) as the Cache eviction policy.

Caching

• Data replication- We can segregate the reads from the write queries. Writes can be performed on the master and data can be replicated to slaves. Slaves can be used for executing read queries.

Data replication

How to shard the data

Storing data on a single database server can cause bottlenecks. There can be a single point of failure. With growing traffic, the read/write pressure on a database will also increase. Hence, it’s better to distribute data on different database servers.

We have the following three strategies for sharding the data:-

1. Range-based partitioning- In this strategy, URLs starting with ‘a-h’ can be assigned to server 1, the ones starting with ‘i-o’ to server 2 and so on. With this approach, there is a possibility of uneven data distribution. This might result in one shard having twice or thrice the data of another
2. Hash-based partitioning- This method eliminates the possibility of uneven data distribution. However, it doesn’t scale well when new servers are introduced or existing ones are removed.
3. Consistent Hashing- This partitioning strategy overcomes the limitations of the above two strategies. The data distribution is even and the addition or removal of new servers has an impact on a minimum number of records.

Cleanup of URLs

An asynchronous job needs to be scheduled to remove all the expired shortened URLs. This job will filter all the expired URLs and return them to the data store for future use. Once the URLs are cleaned up, the tiny URL’s state will be changed to INACTIVE. The service will continue to function as it is and allocate one of the INACTIVE URLs to a new client request.

References

• Giphy
• System Desing Interview
• Design a URL shorter like Bitly
• Tiny URL system design

Level Up Coding

Thanks for being a part of our community! Subscribe to our YouTube channel or join the Skilled.dev coding interview course.

Coding Interview Questions | Skilled.dev