How does URL shortening for TinyUrl, Bit.ly work?

Complete System design guide with handwritten math calculations

Published in

Javarevisited

16 min readFeb 19, 2024

We are constantly sharing information online. Whether it’s articles, videos, or products, web addresses (URLs) are the gateway to accessing this content. However, long URLs can be cumbersome to share, especially on platforms like social media or messaging apps where character limits apply. This is where websites like bit.ly and TinyURL come into play.

They help with making long links shorter and more readable. These shortened links not only look cleaner but also make sharing content across various platforms a breeze.

Now that you know the secret, imagine millions of users around the world shortening URLs every day. This puts a significant strain on the underlying infrastructure. And that is where high-level system design comes into the picture.

Starting with this series on system design, our aim is to break down the functionality, architecture, challenges, scalability, system APIs, performance, and resource estimation associated with each system. We will provide the essential insights required to tackle similar projects in real-world scenarios. Just as coding involves more than just writing lines of code, design also means building intuition and a structured thought process. Because you cannot really write good code without having a clear picture of your design.

If this is not enough, read through till the end of the article for a special surprise announcement that may supercharge your system design skills!

Through this series, we hope to improve your design intuition and help you become a skilled, curious engineer capable of building large-scale systems.

Ensure you don’t miss the surprise waiting for you at the end of this article — read on for an extra dose of excitement and a surprise announcement.

What will be your unique learning proposition?

If you are not very system design-savvy, you may get to learn some of the cool things below:

Sequencer
Encoding types: Base 58, Base 64 encoding
Global Server Load balancing
Handwritten math calculations on resource estimations

If you have zero idea about these concepts or heard these for the first time and want to grasp the fundamentals of System Design building blocks first, we have got you covered. Before diving into the rest of the article below, you can check out the below video first:

What shall we cover about the system design?

We have divided it into 7 modules

1. Functional and non-functional requirements
2. Resource estimation — Servers, bandwidth, storage
3. Building blocks in-depth why and how
4. System APIs
5. Components and Workflow diagram
6. Encoding schemes and calculations
7. Non functional requirements mapping

Why are shortened URL’s more convenient?

Easy to remember or type: they optimize link usage across different forms of devices due to their enhanced accessibility and non-breakability.
They are visually professional, engaging, and facilitate a higher degree of sharing possibilities.
They require smaller storage space at the user’s end.

MODULE 1: REQUIREMENTS

Functional requirements

The actual functionality of this system will cover the points below. You cannot really start a design without knowing the requirements, right?

Short URL generation: Our service should be able to generate a unique shorter alias of the given URL.
Redirection: Given a short link, our system should be able to redirect the user to the original URL.
Custom short links: Users should be able to generate custom short links for their URLs using our system.
Deletion: Users should be able to delete a short link generated by our system.

Non-functional requirements

The criteria specify how a system should behave rather than what it should do.

Availability: Our system should be highly available, because even a fraction of the second downtime would result in URL redirection failures. Since our system’s domain is in URLs, we don’t have the leverage of downtime, and our design must have fault-tolerance conditions instilled in it.
Scalability: Our system should be horizontally scalable with increasing demand.
Readability: The short links generated by our system should be easily readable, distinguishable, and typeable.
Latency: The system should perform at low latency to provide the user with a smooth experience.
Unpredictability: From a security standpoint, the short links generated by our system should be highly unpredictable. This ensures that the next-in-line short URL is not serially produced, eliminating the possibility of someone guessing all the short URLs that our system has ever produced or will produce.

MODULE 2: RESOURCE ESTIMATION

In this part, we’ll be doing some math to figure out how much resources we will need for our system. It’s important because when we’re building something, we need to know how big it could get and plan ahead for things like storage, bandwidth, servers and so one.

Assumptions

We assume that the shortening:redirection request ratio is 1:100
There are 200 million new URL-shortening requests per month.
A URL shortening entry requires 500 Bytes of database storage.
Each entry will have a maximum of five years of expiry time, unless explicitly deleted.
There are 100 million Daily Active Users (DAU).

Let’s break it down:

Shortening:redirection request ratio- 1:100: This means that for every URL shortening request made, there will be 100 redirection requests to that shortened URL. For example, if 1,000 URLs are shortened, there will be approximately 100,000 redirections to those shortened URLs.
200 million new URL-shortening requests per month: This indicates the number of new URLs that users want to shorten each month. So, in a given month, there are 200 million unique URLs that users want to make shorter.
A URL shortening entry requires 500 Bytes of database storage: Each URL that is shortened and stored in the database takes up 500 Bytes of storage space. This includes all the necessary information to redirect users to the original URL.
Each entry will have a maximum of five years of expiry time, unless explicitly deleted: This means that every URL entry in the database will remain active for up to five years from the time it was created. If not deleted before then, it will expire and be removed from the database automatically.
100 million Daily Active Users (DAU): This indicates the number of users actively using the service on a daily basis. These users are actively creating shortened URLs, clicking on shortened links, or both.

Storage Estimation:

Since entries are saved for a time period of 5 years and there are a total of 200 million entries per month, the total entries will be approximately 12 billion.

Since each entry is 500 Bytes, the total storage estimate would be 6 TB.

Query Rate Estimation:

We are trying to estimate how many URL’s will come per second.

This will later help us in bandwidth calculation.

Based on the estimations above, we can expect 20 billion redirection requests per month -> for 200 million url shortening requests.

We have 200 million URL shortening & 20 billion redirection requests per month.

We can extend our calculations for Queries Per Second (QPS) for our system from this baseline. The number of seconds in one month, given the average number of days per month, is 30.

With a 1:100 shortening to redirecting ratio, the URL redirection rate per second will be:

Bandwidth estimation

Bandwidth=Traffic × Average Response Size

Traffic is the number of requests per unit of time (e.g., requests per second).
Average Response Size is the average size of the response in bytes.

Shortening requests: We know that the expected arrival rate will be 77 new URLs per second.

This translates to → The total incoming data would be 308 Kbps per second.

Redirection requests: Since the expected rate would be 7.7K URLs redirections per second, the total outgoing data would be 30.8 Mbps:

Incoming bandwidth = 308 Kbps

Outgoing bandwidth = 30.8 Mbps

Server Estimation:

Before calculating the approximate number of servers required in this system, let’s consider a small example:

Assumptions:

There are 500 million (M) daily active users (DAU).
A single user makes 20 requests per day on average.
Recall that a single server can handle 8,000 requests per second(RPS).

When we claim that only 15 servers are sufficient for 500 million users, the math seems off. Major services employ significantly more servers because merely tallying requests per second doesn’t paint the whole picture of server needs.
Additionally, the calculation assumes each request is managed by a single server, but in reality, requests may traverse various types of servers, including web, application, and storage servers.

Therefore, to calculate the number of servers required, we will consider two factors:

Number of Daily Active Users (DAU)
Daily user handling limit of a server

This is a more realistic number — 12,500 servers.

Cache — Memory Estimation

We need memory estimates in case we want to cache some of the frequently accessed URL redirection requests. Let’s assume a split of 80–20 in the incoming requests. 20 percent of redirection requests generate 80 percent of the traffic.

Since we would only consider caching 20 percent of these per-day redirection requests, the total memory requirements estimate would be 66 GB.

So, 66 GB of cache would be good enough.

Time for the announcement:

If you’re liking what you’re reading, you’re going to love what I have in store for you on my YouTube channel.

We’re providing a range of exclusive perks, such as virtual video collaborations, member-only polls, premium content only for our members, and so much more.

In the context of this article, our exclusive videos will guide you through all the essential aspects of system design, deep-dive into the components, offer extra insights into math concepts, share valuable tips, and provide actionable strategies that can strengthen your System design skills.

Who am I?

Across 7 years, I have led projects on AWS, Java, Spring Boot, Kafka, ELK stack, Splunk, Apache Mesos, etc, optimizing systems for cost-effectiveness, achieving savings of up to 30% , reduced latency by 50% through performance tuning techniques, and enabled systems to handle a higher volume of transactions.

So, I am quite certain you can rely on my expertise.

In addition to that, we will also have videos dedicated to common interview questions about Java threads and concurrency, detailed plans for Spring Boot projects, and plenty of project ideas. All this special content is just for you!

As you support our channel, join our expanding community and get access to things you won’t find anywhere else.

To become a valued member right now, click this link.

MODULE 3: Building blocks we will use

With the estimations done, we can identify the key building blocks in our design.

Database: stores the mapping of long URLs and the corresponding short URLs.
Sequencer: offers unique IDs that will act as a starting point for making each short URL.
Load Balancer: ensures smooth request distribution among available servers at various layers.
Cache: stores the most frequent short URL-related requests.
Rate Limiter: to avoid system exploitation.
Servers: to handle and navigate the service requests along with running the application logic.
Base-58 encoder: transforms the sequencer’s numeric output to a more readable and usable alphanumeric form.

MODULE 4: System APIs

To expose the functionality of our service, we can use REST APIs for the following features:

Shortening a URL
Redirecting a short URL
Deleting a short URL

Shortening a URL

We can create new short URLs with the following definition:

A successful insertion returns the shortened URL to the user. Otherwise, the system returns an appropriate error code to the user.

Redirecting a short URL

To redirect a short URL, the REST API’s definition will be:

A successful redirection lands the user at the original URL associated with the url_key.

Deleting a short URL

Similarly, to delete a short URL, the REST API’s definition will be:

A successful deletion returns a system message, URL Removed Successfully

Database Design:

Let’s take a look at the data we need to store:

User Data:

UserID: A special ID or API key to uniquely identify users worldwide.
Name: The user’s name.
Email: The user’s email address.
Creation Date: The date when the user registered to create short url.

ShortURL Data:

Short URL: A unique short URL, typically 7 characters long.
Original URL: The original long URL.
UserID: The unique ID or API key of the user who made the short URL.

MODULE 5: COMPONENTS + WORKFLOW DEEP-DIVE

Database: For services such as URL shortening, the amount of data to store is minimal. However, the storage needs to be horizontally scalable. The type of data we need to store includes:

User details.
Mappings of the URLs: long URLs that are mapped onto short URLs.

Why horizontal scalable?
Horizontal scalability is crucial for services like URL shortening because it allows us to handle increasing amounts of traffic and data without overloading our system

NoSQL database would be a good choice as we expect many reads in our system. Also, the stored records are separate and don’t have connections except for the details of the user who made the URL.

MongoDB is a good option because:

It can use replicas for heavy reading.
It’s good at handling write operations happening at the same time without any issues.

A NoSQL database is great for our system because it can handle lots of reading without slowing down. It’s flexible with different kinds of data and can grow easily if we need it to. Plus, it’s fast at finding the information we need, even when lots of people are using it at the same time.

2. Short URL generator:
Our short URL generator consists of two parts:

A sequencer for creating unique IDs
A Base-58 encoder to make the short URLs easier to read.

Sequencer:

In a URL shortening service, generating unique IDs is crucial for creating distinct shortened URLs. It typically works by incrementing a counter or using a distributed algorithm to generate IDs across multiple servers without collisions. This ensures that even with high concurrency and rapid URL shortening requests, each shortened URL receives a unique identifier, preventing conflicts and ensuring the integrity of the service.

Base-58 Encoder:

While generating unique IDs is essential, creating shortened URLs that are human-readable and easy to share is equally important for user experience. This is where a Base-58 encoder comes into play. Base-58 encoding is similar to Base-64 encoding but excludes characters like 0 (zero), O (uppercase letter o), I (uppercase letter i), and l (lowercase letter L) to avoid confusion and improve readability.

3. Load Balancing:

To ensure high availability, we will use:

Global Server Load Balancing (GSLB): distributes requests across various global servers, particularly during on-site failures, ensuring efficient traffic handling.
Local load balancing.

Why are both needed?
Global server load balancing is essential for distributing incoming traffic across multiple geographically dispersed data centers or regions. With the increasing globalization of online services and the growing demand for low-latency user experiences, global load balancing is crucial for delivering consistent performance across different regions. It enables companies to serve their customers efficiently regardless of their geographic location and ensures high availability by directing traffic away from regions experiencing issues or outages.
Local load balancing focuses on distributing traffic within a single data center or network to optimize resource utilization, improve response times, and prevent individual servers from being overloaded.

4. Cache: Memcached can be the ideal cache solution for our read-heavy application. A caching layer in each data center will be implemented to deal with requests happening nearby. We also discussed about cache storage requirements earlier.

5. Rate Limiter: Each user will have a unique key: api_dev_key, which will be used to limit the number of shortening and redirection tasks a user can do within a certain time.

Workflow:

Let’s explore how each part of the system works together to achieve its functionality.

Shortening: When a user requests a short link, the application server forwards the request to the Short URL Generator (SUG). Once the short link is generated successfully, one copy is sent to the user, and the url_key is stored in the database for future use.
Redirection: When a user requests redirection, the application server checks the caching system and database for the required record. If found, the user is redirected to the associated long URL; otherwise, an error message is displayed.
Deletion: A record can be deleted by requesting the application server, which then checks the caching system and database for the required record. If found, the url_keyalong with its record is deleted; otherwise, an error message is displayed.
Custom Short Links: The system checks the eligibility of the requested short URL, ensuring it meets the criteria (maximum length of 11 alphanumeric digits). If eligible, the system checks its availability in the database. The user receives a successful short URL generation message if available, or an error message otherwise.

Below is the diagrammatic illustration:

MODULE 6: Encoding

Encoding in URL shortening changes jumbled-up data like letters and symbols into a special format that works well for sending information over the internet. This makeover guarantees that the short links created are safe for URLs and won’t cause any trouble when they’re used or shared.

There are different ways of encoding:

Base 64 Encoding: Uses a 64-character set (A-Z, a-z, 0–9, +, /) to represent binary data.
Base 62 Encoding: Similar to Base 64 but excludes characters that are not URL-safe (e.g., +, /). It utilizes a 62-character set (A-Z, a-z, 0–9).
Base 58 Encoding: A variation of Base 62 that further excludes similar-looking characters like 0 (zero), O (capital o), I (capital i), and l (lowercase L) to enhance readability.

We’re using Base 58 encoding for our system to enhance readability and avoid confusion between visually similar characters.

Let’s see how we can convert a number from base 58 to base 10 and vice versa.

Base 58 to Base 10 conversion:

Base 10 to Base 58 conversion:

Let’s perform a quick calculation to determine the optimal number of characters for our shortened URL.

URL with length 5, will give 58⁵ = ~656 Million URLs
URL with length 6, will give 58⁶= ~38 Billion URLs

As our system generates 12 billion URLs ( from storage utilization), utilizing 6 characters in base58 will give approximately 38 billion URLs. Hence, each generated short URL will consist of 6 characters.

For 6 characters in short url, from where should the sequencer calculation begin?

Let’s break it down. When you give us a long URL and we need to shorten it, we use something called a SUG(Short URL generator). Remember, that’s made up of two parts: the sequencer and the base 58 encoder.

Now, when we get a long URL, we start by using the sequencer to generate a series of numbers. These numbers are then converted to a base 58 encoding, which gives us the short URL with 6 characters. But here’s the catch: where do we start counting with the sequencer to get those 6 characters just right? That’s the question we need to answer.

Upon performing reverse calculations, it was determined that to achieve a minimum of 6 characters in base-58, the required number in base-10 should be approximately 1 billion.

Base 10 number: 1000,000,000

1000000000 % 58 = 18
  17241379 % 58 = 9
    297265 % 58 = 15
      5125 % 58 = 21
        88 % 58 = 30
         1 % 58 = 1
Base 58 equivalent: [1][30][21][15][9][18]
                  : 2XNGAK

So, the minimum base 10 number for a base 58 sequence of length 6 is 1 Billion. The sequencer will start generating short URLS from 1 Billion for any random user.

MODULE 7: Reviewing non-functional requirements

So, based on what we designed so far we understand that we are able to meet the functional requirements.

But how are we meeting the non-functional requirements?

Let’s discuss and wrap-up.

Availability:

Building blocks will have built-in replication; which ensures availability and fault tolerance.
Global server load balancing (GSLB) is used to handle the system’s traffic for request distribution.
Rate limiters are used to limit each user’s resource allocation; and prevents DoS attacks.

Scalability

Using horizontally sharded databases.
MongoDB — as the NoSQL database.

Readability

Introduction of the base-58 encoder to generate short URLs.
Removal of non-alphanumeric characters.
Removal of look-alike characters.

Latency

MongoDB, because of its low latency and high throughput in reading tasks.

Unpredictability

By randomly selecting an unused unique ID from the pool allocated to each server. This approach deviates from assigning IDs sequentially, mitigating the risk of predicting subsequent short URLs.

Additionally, utilizing cryptographic hash functions (such as SHA-256) to hash the original URL and then encode the resulting hash into a shorter representation would be better.

That’s all for this article.

Thanks for reading.

If you liked this article, please click the “clap” button 👏 a few times.

It gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Connect with me — Varsha Das | LinkedIn

If you’re seeking personalized guidance in software engineering, career development, core Java, Systems design, or interview preparation, let’s connect here.
Rest assured, I’m not just committed; I pour my heart and soul into every interaction. I have a genuine passion for decoding complex problems, offering customised solutions, and connecting with individuals from diverse backgrounds.

Follow my Youtube channel — Code With Ease — By Varsha, where we discuss Java & Data Structures & Algorithms and so much more.

Subscribe here to receive alerts whenever I publish an article.

Happy learning and growing together.