1. Design URL Shortener

Topics: Scaling Reads, Aggressive Caching

Intro

Bitly is a URL shortening service that converts long URLs into shorter, manageable links. It also provides analytics for the shortened URLs.

Final Designs

Postgres / Zookeeper

Redis

                          +--------+
                          | Client |
                          +--------+
                              |
                       +--------------+
                       | API Gateway  |  routes by path
                       +--------------+
                       /              \
          +--------------+          +---------------+
          | Read Service |          | Write Service |
          +--------------+          +---------------+
            /          \               /          \
   +-------------+      |     +--------------+     |
   | Redis Cache |      |     | Redis Counter|     |
   +-------------+      |     +--------------+     |
                         \                        /
                          +--------------------------+
                          |  Database (replicated)   |
                          +--------------------------+

Functional Requirements ::2::

Features needed to satisfy the needs of the user. Actions that the application must be able to provide.

In Scope

1. Users should be able to submit a long URL and receive a shortened URL.

• Optionally, users should be able to specify a custom alias.
• Optionally, users should be able to specify an expiration date.

2. Users should be able to access the original URL by using the shortened URL.

Out of Scope

1. User authentication and account management

2. Analytics on link clicks (e.g., click counts, geographic data).

Non Functional Requirements ::4::

Specifications about how a system operates in terms of metrics, rather than what tasks it performs. Defines system attributes like scalability, latency, security, availability, and are often framed as specific benchmarks.

Core Requirements And Benchmarks

1. System guarantees uniqueness for created short codes, meaning no collisions

2. Redirection should occur with minimal delay less than 100 ms

3. System should be reliable and available 99.99% of the time, preferring availability > consistency

4. System should scale to support 1 Billion shortened URLs and 100 Million Daily Active Users

Out of Scope

1. Data consistency in real time analytics

2. Advanced security features like spam detection and malicious URL filtering.

General Estimations

Napkin estimations based on the functional and non functional requirements

A URL creator will usually have an imbalance between reads and writes. Meaning, at any given moment there will likely have more redirect requests than create requests. As an estimate, we can put a ratio of 1000 reads to 1 create

We must keep this in mind and adjust our caching, database, and architecture choices.

Set Up

How actions will be able to be executed and who will execute them. Define the core data and API contract before building each workflow.

Entities

The core objects or concepts within a system which define its functionality and data.

1. Long URL
2. Short URL
3. User

API ::2::

The contract between the client and the server, acts as the first point of reference in high level design. Usually this maps 1:1 with functional requirements, meaning 1 endpoint is set aside to provide each of the required functions.

1. Create(): POST To Generate A New Short URL

A POST endpoint to intake the long URL, optional alias, optional expiration date, and return the short URL.

// Generate short URL from long URL
Request: POST/{long_url}
Body:
    {
        "long_url": "https://www.example.com/some/very/long/url",
        "custom_alias": "optional_custom_alias",
        "expiration_date": "optional_expiration_date"
    }

Response: HTTP/1.1 201 Created
Body:
    {
        "short_url": "http://short.ly/abc123"
    }

2. Redirect(): GET To Retrieve An Existing Long URL

A GET endpoint that intakes the short url, and redirects the user to the original long URL.

// Using short URL, redirect to original long URL
Request: GET/{short_url}

Response: HTTP 302 Redirect to the original long URL

Guiding Obstacles

The non-functional benchmarks we must design for, and a preview of the bottlenecks we will hit and solve.

1. Short Unique URLs With No Collisions

Challenge In English

• Codes must be unique, as short as possible, and cheap to generate.
• These pull against each other: shorter codes leave less room to avoid collisions, random or hashed codes need a collision check that slows down as the table grows, and a counter guarantees uniqueness but needs coordination across servers.

Challenge By Metrics

• Zero collisions across all short URLs
• 1B URLs fits in 6 base62 characters (62^6 ~ 56.8B), 7 characters covers ~3.5T

Solved Below

• Create()
  • Bottleneck 1 (unique codes)
  • Bottleneck 2 (counter across instances, counter batching)

2. Fast Redirection Under 100 MS

Challenge In English

• Every redirect is a lookup on a table with up to 1B rows, so full scans are out.
• Even with an index, one disk-based database can't absorb the read volume.

Challenge By Metrics

• Redirect in under 100 ms
• Heavily read skewed: ~5000 reads : 1 write (500M reads/day vs 100k writes/day)
• 100M DAU * 5 redirects = 500M/day, ~5,787/sec on average
• 100x spike = ~578,700/sec, versus ~100k IOPS for one SSD
• Memory ~0.0001 ms vs SSD ~0.1 ms per access

Solved Below

• Redirect()
  • Bottleneck 1 (index)
  • Bottleneck 2 (cache)
  • Bottleneck 3 (CDN / edge)

3. Scale To 1 Billion Short URLs And 100 Million Daily Active Users

Challenge In English

• Storage looks like the scary part, but it isn't.
• The real risks are single points of failure, and reads and writes needing to scale independently: one database, one server, one counter.

Challenge By Metrics

• 99.99% availability (~52 min of downtime per year)
• ~500 bytes * 1B rows = ~500 GB total storage, which fits on one SSD
• ~1 write/sec (100k/day) vs ~578,700 reads/sec at spike

Solved Below

• Putting It Together
  • Splitting into Read Service and Write Service
  • Database replication
  • Backups

1. Create() Via Long URL => Short URL

Bare Bones

The simplest design that satisfies the functional requirement, before any benchmark forces a change.

Components

1. Client: Users interact with system through web or mobile app

2. Server: Receives requests from client and handles logic

3. Database: Stores mapping of short URLs to long URLs, user generated aliases, and expiration dates

Create Request Via POST()

Action

Implements the POST /urls endpoint defined in Set Up > API > 1. POST: Generate a new short URL. Functional Requirement 1: users can submit a long URL and receive a short URL.

Steps

1. Client Request()
2. Server Validates Request() (validate URL, check if already present in db)
3. Server Generate() Short Code
4. Server Request() Inserts Into Database()
5. Server Response() If Insert Successful
6. Server Response() with the short URL

Diagram

Create()                                Result()
 1. Client Request()                        6. Server Response()
                            +--------+       
Request():                  | Client |          On Success:     
POST/urls                   +--------+              HTTP 201: Created + short URL 
{                               ^                   {
    "long_url": ...             |                       "short_url": "http://short.ly/abc123"
    "custom_alias": ...         |                   }
    "expiration_date": ...      |         
}                               |               On Failure:      
                                |                   HTTP 400/409/500 (failure)
                                |                   {
                                |                      "error": "..."
Validate():                     v                   }    
 2. Check if valid URL  +----------------+
                        | Primary Server |
Request():              +----------------+   5. Database Response()
 3. generate short URL          ^ 
 4. SQL Query (INSERT)          |                On Success: returns inserted row
                                |                    (1 row, short_url = "abc123")
                                |                On Failure: returns database error
                                v                    (e.g., duplicate short_code)  
                            +-----------+    
    SQL Insert:             | Database  |
    INSERT INTO Urls        +-----------+

                            Urls Table          
                            {
                                string short_url           
                                string original_url
                                datetime creation_time
                                datetime expiration_time
                                created_by
                            }

API Contract

Request

    POST /urls
    Body:
    {
        "long_url": ...
        "custom_alias": ...
        "expiration_date": ...
    }

Response

    HTTP/1.1 201 Created
    Body:
    {
        "short_url": "http://short.ly/abc123"
    }

    HTTP/1.1 400 / 409 / 500
    Body:
    {
        "error": "..."
    }

Database

Lets start with the size of the database.

Long URL Table:             
                 | ------------------------- |
Indexing -->     | Short URL (~8 bytes)      |
                 | Long URL (~100 bytes)     |
                 | creation Time (~8 bytes)  |
                 | custom alias (~100 bytes) |
                 | expiration date (~8 bytes)|
                 | ------------------------- |

Leading to ~200 bytes per row
Rounding up to ~500 bytes to account for additional metadata
such as creator id, analytics id, etc.

If we store 1B shortened URLS we are looking at around:

~500 bytes * 1B rows = 500 GB of data

500 GB is within the capabilities of SSDs. And given that the number of urls is limited by the number of urls on the internet, we can expect it to grow but only modestly.

If we were to hit the hardware limit, we could shard our data across multiple servers, but for now a single Postgres instance as mentioned previously should be ok.

To estimate, we could say 100k new urls are created per day.

100k urls per day 

86,400 seconds in day

100k / 86,400 ~= Insert 1 row per second

Most database technology should can handle this as we already fixed the heavy read throughput via cache and have bounded our write throughput as low.

Bottlenecks and Benchmarks

Each bottleneck is a benchmark the bare bones design fails. Format: Benchmark -> What Breaks -> Fix -> Adds -> Tradeoff.

Benchmarks

Bottleneck 1: Short Unique Codes

What Breaks

The current magic function in step 3 to generate a short url has no guarantee of uniqueness.

Initial Solutions

Bad Solution: Long URL Prefix

Approach:

The simplest thing we could do is take a prefix of the input as the short code.

www.linkedin.com/ -> www.short.ly/www.link

Challenges:

This would break constraint 1. as different URLs could have the same short URL.

Good Solution: Random Number Generator or Hash Function

Approach:

To add entropy (randomness) to ensure our codes our unique, we could try a random number generator or hash function.

Challenges:

Even with entropy, there is a non negligible chance of generating duplicate short codes, due to our constraint 2 of short codes. This leads to a necessity of either generating longer short codes (breaking constraint 2) or adding a check for already existing code which becomes a bottleneck as the system scales (breaking constraint 3)

Great Solution: Unique Counter with Base62 Encoding

Approach:

One solution to guaranteeing no collisions is to increment a counter for each new url. We would then take the output and encode it using base62 encoding to ensure short representation.

Each counter value would be unique which then eliminates the risk of collisions.

Challenges:

In a distributed environment, maintaining a single global counter can be challenging due to synchronization issues. All instances of our primary server would need to agree on the counter value.

Challenges:

With length, if we have 1B urls, when base62 encoded will lead to 6 character strings.

So we would need to move to 7 character codes once we hit the trillions.

Fantastic Solution: Unique Counter With A Range Per Server

Approach:

Instead of every write asking for the next value, each server claims a range of values from a global counter and hands them out locally.

Global Counter: next_free = 3001

Server 1 claims [1, 1000]      -> uses 1, 2, 3, ... 1000 locally
Server 2 claims [1001, 2000]   -> uses 1001, 1002, ... 2000 locally
Server 3 claims [2001, 3000]   -> uses 2001, 2002, ... 3000 locally

Server 1 runs out -> claims [3001, 4000]

How it works:

1. A server atomically claims a block of 1000 values from the global counter
2. The server uses values from its range locally, base62 encoding each one. No network call per write, and no coordination between servers
3. When the range runs out, the server claims a new one

Why it's safe:

• Ranges never overlap, because the claim is atomic, so codes stay unique
• The counter is hit once per 1000 writes instead of once per write

Challenges:

• If a server dies, its unused values are lost. This is acceptable because 6 characters holds ~56.8B codes, so losing 1000 at a time is negligible
• Codes are not strictly increasing across servers, since each server uses a different range. This doesn't matter for uniqueness
• Codes are guessable (sequential within a range). If that matters, scramble the value before encoding it
• Where the counter lives is the open question, and it is a single point of failure. The sections below compare the options

Redis

Good Solution: Unique Counter With A Range Per Server

Approach:

Store the counter in Redis. Each claim is INCRBY 1000, which is atomic and returns the new block, so ranges never overlap.

Redis Global Counter: next_free = 3001

Server 1 claims [1, 1000]      -> INCRBY 1000
Server 2 claims [1001, 2000]   -> INCRBY 1000
Server 3 claims [2001, 3000]   -> INCRBY 1000

Challenges:

• Redis is hit once per 1000 writes, so its speed is not the concern
• It is one node, so it is a single point of failure for claiming new ranges. Servers keep working until their current range runs out, which buys time to recover
• Persistence is async by default, so a restart can lose recent increments and re-issue a range that was already handed out (breaks uniqueness)

Great Solution: Replicated Redis Counter With Failover

Approach:

Keep the Redis counter, but run a primary plus replica(s) with automatic failover (Redis Sentinel or Cluster). Servers claim ranges with INCRBY, as in Bottleneck 1.

Redis Primary (INCRBY 1000)  --async replication-->  Redis Replica
                                                     (promoted on failure)

Server 1: current [1, 1000],    spare [3001, 4000]
Server 2: current [1001, 2000], spare [4001, 5000]

Two additions make it safe:

1. Spare range: each server claims its next range early, before the current one is empty, so writes continue through the failover window (seconds).
2. Skip-ahead: on promotion, the new primary bumps the counter by a safety margin (e.g., +1,000,000) before serving claims.

Challenges:

• Replication is asynchronous, so the replica may be missing the last few increments. Without the skip-ahead it would re-issue a range that was already given out (breaks constraint 1)
• The skip-ahead margin must exceed any increments the replica could have missed, so it has to be picked generously (wasted values are cheap: 1,000,000 out of ~56.8B is ~0.002%)
• More moving parts: failover monitoring, and split brain risk if two nodes both think they are primary
• If Redis is down longer than the spare range lasts, writes fail

Fantastic Solution: Consensus Backed Range Store

Approach:

Claim ranges from a strongly consistent store (etcd, ZooKeeper, or a Postgres row updated inside a transaction) instead of Redis.

-- Postgres version
UPDATE range_counter
SET next_free = next_free + 1000
RETURNING next_free - 1000 AS range_start;

A claim is only acknowledged once a majority of nodes (or the committed transaction) has recorded it, so a promoted node can never be behind.

Why it works:

• No lost increments on failover, so no skip-ahead needed
• Slow claims don't matter: a server claims once per 1000 writes, and at ~1 write/sec that is roughly once every 15 minutes
• Servers still hold a spare range for runway while the store elects a new leader

Challenges:

• A claim is slower than a Redis INCRBY, but claims are rare
• Still an extra system to run if you don't already have one (skip it if your main database already provides the transaction)
• Losing a majority of nodes blocks new claims, so spare ranges are still worth keeping

DynamoDB or Postgres

Good Solution: Unique Counter With A Range Per Server

Approach:

Store the counter in the database we already run for the URL table. Each claim is one atomic operation that reserves a block of 1000 values.

-- Postgres
CREATE SEQUENCE short_code_range_seq INCREMENT BY 1000 START 1;

SELECT nextval('short_code_range_seq');
-- returns 1, then 1001, then 2001, ...
-- the caller owns [n, n + 999]

DynamoDB: one item, atomic add

UpdateItem(Key={"id": "short_code_counter"},
           UpdateExpression="ADD next_free :n",
           ExpressionAttributeValues={":n": 1000},
           ReturnValues="UPDATED_NEW")

returned value v -> the caller owns (v - 1000, v]

Why it works:

• No new component: the range store is the database we already have
• Durable, so a restart does not re-issue old ranges
• Claims happen once per 1000 writes, so the slower write does not matter
• Counter availability equals database availability, so there is no extra failure domain

Challenges:

• Failing over to an async Postgres replica can leave its sequence behind the primary, so a range could be handed out twice
• DynamoDB global tables are eventually consistent across regions, so two regions could hand out the same range
• If the database is down, servers can't claim new ranges once their current one runs out
• Sequences are not rolled back, so failed transactions burn values (harmless, gaps don't affect uniqueness)

Great Solution: Hardened Claims (Sync Replication, Spare Range, Insert Backstop)

Approach:

Keep the database range store from Good, and close its failover gaps with three additions:

1. Safe failover: use synchronous replication for the failover replica in Postgres, or keep the DynamoDB counter in a single region (or give each region a disjoint range space)
2. Spare range: each server claims its next range early, before the current one is empty, so writes continue while the database fails over
3. Insert backstop: the primary key on short_url rejects a duplicate code, so the server discards that range, claims a new one, and retries

Server 1: current [1, 1000],    spare [3001, 4000]   <- claimed early
Server 2: current [1001, 2000], spare [4001, 5000]

Claim range -> encode value -> INSERT row
                                  |
                       duplicate short_url?
                                  |
                  yes: claim a fresh range, retry

Why it works:

• Synchronous replication means a promoted replica is never behind, so no skip-ahead logic is needed (unlike the Redis Good solution)
• Runway = range size / write rate per server. At ~1 write/sec total, a range of 1000 lasts ~15 minutes, so a failover of seconds is invisible
• Even if a duplicate range slips through, the primary key turns silent corruption into a retry

Challenges:

• Synchronous replication adds write latency to the claim, which is fine since claims are rare
• Writes to the URL table also need the database, so if it is down longer than the spare range lasts, Create() fails regardless of where the counter lives
• Retry logic is one more code path to build and test
• Still tied to one database, so if writes ever outgrow one Postgres primary, the range store needs to move out (e.g., etcd or ZooKeeper)

Alternative: Snowflake Style IDs

Approach:

Skip the range tracker entirely. Each server builds a unique ID locally from three parts: a timestamp, its own worker ID, and a local sequence.

| 1 bit  | 41 bits       | 10 bits   | 12 bits  |
| unused | timestamp(ms) | worker ID | sequence |

= 64 bits total, ~11 base62 characters

How it works:

1. The server reads the current time in milliseconds
2. It appends its worker ID (unique per server, assigned at startup)
3. It appends a local sequence number that increments for each ID in the same millisecond (up to 4096 per ms per server), and resets when the millisecond changes
4. The combined value is base62 encoded into the short code

Why it is unique:

• Two servers never collide, because their worker IDs differ
• One server never collides with itself, because the timestamp and sequence never repeat
• No network call and no shared counter on the write path

Why we do NOT use it here:

• Codes are ~11 base62 characters versus 6 for the range approach, which breaks constraint 2 (as short as possible)
• Tracking is not removed, only moved:
  • Worker IDs must be unique, assigned once per server at startup (static config for a handful of servers, or a lease from etcd/ZooKeeper if servers autoscale)
  • The clock becomes a dependency. If a server's clock jumps backwards it can reissue an ID, so it must detect that and wait or refuse writes

When Snowflake IS the better answer:

• The ID has no length requirement (order IDs, tweet IDs, message IDs, event IDs)
• IDs should be roughly sortable by creation time
• Many servers generate IDs and you want zero coordination on the hot path

Interview line: "Snowflake removes the tracker, but the codes would be ~11 characters and we would still need unique worker IDs, so we keep the range approach to stay short."

Bottleneck 2: Scaling Writes

What Breaks

Bad Solution: Bigger Server (Vertical Scaling)

Approach:

Keep one Primary Server and give it more CPU and memory.

Challenges:

• Still a single point of failure, so one crash takes down Create() (breaks constraint 1)
• Create() and Redirect() still share the same machine (breaks constraint 2)
• Expensive, and there is a hardware ceiling
• Wasteful here, since ~1 write/sec doesn't need a bigger machine

Good Solution: Many Copies Of The Same Server (Horizontal Scaling)

Approach:

Run multiple identical instances of the Primary Server behind a load balancer. Every instance handles both Create() and Redirect().

                     +---------------+
Client  ------->     | Load Balancer |
                     +---------------+
                      /      |      \
                +--------+ +--------+ +--------+
                | Server | | Server | | Server |   (each does Create + Redirect)
                +--------+ +--------+ +--------+
                      \      |      /
                       +----------+
                       | Database |
                       +----------+

Challenges:

• Removes the single point of failure (meets constraint 1)
• Reads and writes still scale together (breaks constraint 2). To absorb the read spike you must add instances that carry write code you don't need, and the reverse
• One deployment for both paths: a bug in the redirect code can take Create() down with it
• Each instance needs its own counter range (see Bottleneck 1), which is wasted on instances that only serve redirects

Great Solution: Split Into A Write Service (Microservice)

Approach:

Separate Create() and Redirect() into two services. The Write Service handles Create() and the Read Service handles Redirect(). Each one runs multiple instances and scales on its own.

An API Gateway routes by endpoint: POST /urls goes to the Write Service, GET /{short_code} goes to the Read Service.

                    +--------+
                    | Client |
                    +--------+
                        |
                +----------------+
                |  API Gateway   |   routes by endpoint
                +----------------+
                /                \
    POST /urls /                  \ GET /{short_code}
              /                    \
  +---------------+            +--------------+
  | Write Service |            | Read Service |   (built in Redirect(), Bottleneck 4)
  |  (many inst.) |            +--------------+
  +---------------+
     /          \
+-----------------+    +------------------+
| Range Store     |    |    Database      |
| (Bottleneck 2)  |    |  (INSERT)        |
+-----------------+    +------------------+

How it works:

1. The API Gateway sends every POST /urls to any healthy Write Service instance (randomly or round robin)
2. Each instance is nearly stateless. Its only local state is its current range of counter values (Bottleneck 1), and losing that is harmless
3. The instance base62 encodes the next value, inserts the row, and returns the short URL
4. If an instance dies, the gateway stops routing to it and the others keep serving. Add or remove instances based on write load

Why it's safe:

• Codes stay unique because every instance claims non-overlapping ranges
• The primary key on short_url is a backstop, so a duplicate insert fails instead of silently overwriting
• Only the Write Service touches the range store, so Redirect() traffic can't starve it

Challenges:

• More moving parts: gateway, load balancer, and multiple services to deploy and monitor
• The gateway becomes a new single point of failure, so it also runs as multiple instances
• The database is still one write target. That is fine at ~1 write/sec, and database replication is covered in Redirect(), Bottleneck 5
• At ~1 write/sec this is about availability and independence, not throughput. If writes ever outgrow one Postgres primary, the next step is sharding by short code

Fix

Split off a Write Service with multiple instances behind an API Gateway.

Adds

Write Service (many instances), API Gateway, load balancer.

Tradeoff

More components to run and monitor, in exchange for no single point of failure on writes and independent scaling of Create() and Redirect().

2. Redirect() Via Short URL => Long URL

Bare Bones

The simplest design that satisfies the functional requirement, before any benchmark forces a change.

Components

1. Client: users interact through web or mobile app

2. Server: receives requests from the client and handles logic

3. Database: stores short URL -> long URL mappings, aliases, and expiration dates

Action

User requests a short URL and is redirected to the original long URL()

GET Processing Steps

1. Client Request()
2. Server Looks Up Short Code()
3. Server Validates()
4. Server Responds()

API Contract

Implements the GET /{short_code} endpoint defined in Set Up > API > 2. GET: Retrieve an existing long URL. Functional Requirement 2: users can access the original URL by using the short URL. The API contract does not change through any bottleneck below. Only the internals behind GET /{short_code} evolve.

Request

GET /abc123

Response

HTTP/1.1 302 Found
Header:
Location: https://www.example.com/

HTTP/1.1 404 / 410 / 500
Body:
{
    "error": "..."
}

Response 301 vs 302

• HTTP/1.1 301 (Permanent Redirect): Indicates the resource has permanently moved to the target URL. Browsers typically cache this response, so future requests for the short URL go directly to the long URL, bypassing our server.

• HTTP/1.1 302 (Temporary Redirect): Indicates the resource has temporarily moved to the target URL. Browsers do not cache this response, so future requests for the short URL go through our server first.

We use 302 because:

• It prevents browser caching and gives us direct control over the redirection, in case we need to update or expire links
• It allows us to track click statistics for each short URL, since every request is forced through our server

Database Operations

Relying solely on a disk-based database for redirects will present some challenges.

A typical SSD can handle ~100,000 Input/Output Operations Per Second.

The issue is the volume of read operations for our application. With 100M DAU, averaging each user does 5 reads() per day:

100,000,000 users * 5 redirects = 500,000,000 redirects per day

86,400 seconds per day

500,000,000 / 86,400 seconds ~= 5,787 redirects per second

And this is assuming evenly distributed reads() throughout the day which is unrealistic. Most reads() will occur during peak hours, meaning we need to design for high traffic spikes.

spikes 100x more traffic

(500,000,000 * 100) / 86,400 seconds ~= 578,700 redirects per second

A single database will struggle to keep up with the volume of traffic. A high read load would then lead to increased response times, potential timeouts, and could slowdown other database operations like write().

GET Diagram

User requests a short URL and is redirected to the original URL:

                                +--------+
Request:                        | Client |          Response:
GET/{short_url}                 +--------+          HTTP 302: Found
                                    ^               {
                                    |                   "Location": "https://www.example.com/"
                                    |               }
                                    |               or
                                    |               HTTP 404 (resource not found)
                                    |               {
                                    |                   "error": "..."
                                    |               }
                                    v
                            +------------------+
Read():                     | Primary Server   |    On Success:
1) QUERY short URL          +------------------+        Return 302 redirect
2) Redirect on match                ^               On Failure:
                                    |                   Return 404 (resource not found)
                                    |
                                    |
                                    v
                                +-----------+
Urls Table                      | Database  |
{                               +-----------+ 
    string short_url                                
    string original_url                             
    datetime creation_time                          
    datetime expiration_time                        
    created_by                                      
}

Bottlenecks and Benchmarks

Each bottleneck is a benchmark the bare bones design fails. Format: Benchmark -> What Breaks -> Fix -> Adds -> Tradeoff.

Benchmarks

Bottleneck 1: Lookup Speed

What Breaks

Step 2 looks up the short code in a table of up to 1B rows. Without help, the database has to check rows one by one.

Constraints:

1. Find the long URL quickly
2. Avoid full table scans on the short code

Bad Solution: Full 1 Billion Table Scan

Approach:

Do nothing. The database scans the table until it finds a matching short code.

Challenges:

• O(n) per lookup over up to 1B rows, far too slow for 100 ms (breaks constraint 2)
• Gets slower as the table grows

Good Solution: B Tree Index + URL Table

Approach:

1. B Tree Index: Sorted by "short_code". Finds any short code in O(log n) and returns a pointer to the row.

2. Urls Table: Holds the actual rows (short_url, original_url, expiration_time). The pointer takes us straight to the row, so no scanning.

Lookup() = one tree walk to find the row pointer, O(log n)

• one row read using that pointer, O(1) = O(log n) total

Example: Short URL Request GET /x7Bn

1. Start at the root. "x7Bn" >= "m4Kz", so go right
2. Scan the leaf for "x7Bn" and find it
3. Follow the row pointer to the Urls table and read original_url
4. Return 302 with Location: https://www.youtube.com/watch?v=...

B Tree:
    - Indexed by short_code, sorted alphabetically
    - Each node holds ~500 keys (sized to a disk page); only 2 are shown per node below

                      +------------------------+
                      |  "m4Kz"  (~500 keys)   |        root: separator keys
                      +------------------------+
                     /                          \
        short_code < "m4Kz"                short_code >= "m4Kz"
                   /                              \
  +-------------------------------+     +-------------------------------+
  | "abc123" | "f9Qw" (~500 keys) |     | "m4Kz" | "x7Bn"  (~500 keys)  |   leaf: short codes
  +----------+---------------------+    +--------+----------------------+
        |           |                          |             |
        v           v                          v             v
     row ptr     row ptr                    row ptr       row ptr


    ~500 keys per node -> 1 billion rows fits in ~4 levels (see complexity notes above)

Urls Table:
    -  Short Url acts as the row key with a value of the long url 

  | short_url | original_url                            | expiration_time |
  | --------- | --------------------------------------- | --------------- |
  | abc123    | https://www.example.com/some/long/url   | ...             |
  | f9Qw      | https://www.linkedin.com/in/someone     | ...             |
  | m4Kz      | https://www.github.com/some/repo        | ...             |
  | x7Bn      | https://www.youtube.com/watch?v=...     | ...             |

Challenges:

• O(log n) lookup. With 1 billion rows a B-tree is only a few levels deep, so this is fast. Each node branches by a factor of ~500, not just 2, so node counts per level grow fast: 1, 500, 250,000, 125,000,000, 62,500,000,000. By level 3 (4 levels total), capacity already exceeds 1B rows, versus ~30 levels for a binary tree.
• Extra storage for the index, and slightly slower writes (fine at ~1 write/sec)

Good Solution: Hash Function + Bucket

Approach:

Run the short code through a hash function to access a bucket in O(1), which may contain multiple small url values in a linked list

Challenges:

Bottleneck 2: Read Volume

Benchmark

Latency and Scale: spike vs ~100k IOPS.

What Breaks

Even with an index, every redirect is a disk read on one database.

100,000,000 users * 5 redirects = 500,000,000 redirects per day

86,400 seconds per day

500,000,000 / 86,400 seconds ~= 5,787 redirects per second

Spike (100x): (500,000,000 * 100) / 86,400 seconds ~= 578,700 redirects per second

A typical SSD handles ~100,000 IOPS (input/output operations per second), so the spike is several times what one database can do. The result is slow responses, timeouts, and slower writes.

Constraints:

1. Absorb ~578,700 reads/sec at spike
2. Keep redirects under 100 ms

Bad Solution: Bigger Database (Vertical Scaling)

Approach:

Give the single database more CPU, memory, and faster disks.

Challenges:

• Expensive, and there is a eventual hardware ceiling
• Still one machine, so still a single point of failure
• Every read still touches disk

Good Solution: Read Replicas

Approach:

Copy the database to several replicas and spread reads across them. Writes go to the primary.

Challenges:

• Read capacity scales with the number of replicas (meets constraint 1)
• Every read is still a disk read, so latency does not improve
• Replicas lag behind the primary, so a brand new short URL may 404 briefly
• More servers to run, when the data is highly repetitive (a few hot links get most clicks)

Great Solution: In Memory Cache (Redis)

Approach:

To improve redirect speed, we can add in memory cache like Redis or Memcached in between th primary server and database It will store frequently accessed short code -> long URL mappings.

Memory access time: ~100 nanoseconds (0.0001 ms)
SSD access time:    ~0.1 milliseconds
HDD access time:    ~10 milliseconds

Memory: ~1,000,000 IOPS
SSD:    ~100,000 IOPS
HDD:    ~100-200 IOPS

How it works:

1. The server checks the cache first
2. Cache hit: return the long URL straight from memory
3. Cache miss: query the database, store the result in the cache, return it

User requests a short URL and is redirected to the original URL:

                                +--------+
Request:                        | Client |          Response:
GET /{short_code}               +--------+          HTTP 302: Found
                                    ^               {
                                    |                   "Location": "https://www.example.com/"
                                    |               }
                                    |               or
                                    |               HTTP 404/410/500 (failure)
                                    |               {
                                    |                   "error": "..."
                                    |               }
                                    v
                            +------------------+                        +-------------+
Read():                     |      Server      |   < ---------------- > | Redis Cache |
1) QUERY short code         +------------------+                        +-------------+
2) Redirect on match                ^                    Purpose:
                                    |                    - Server checks cache before querying DB
                                    |                    - Fast key value store
                                    |                    - Maps short_code -> original_url
                                    v
                                +-----------+
Urls Table                      | Database  |    SQL Query:
{                               +-----------+    SELECT * FROM Urls WHERE short_code = ...
    string short_url
    string original_url
    datetime creation_time
    datetime expiration_time
    created_by
}

Why it works:

• Memory is roughly 1,000x faster than SSD, so hits are far under 100 ms
• Link traffic is skewed toward a small set of hot links, so a modest cache absorbs most of the spike and the database only sees misses

Challenges:

• Warm up: an empty cache sends early requests to the database until it fills
• Cache size/Eviction policy (LRU): Memory is limited, need to set policies
• Invalidation: updates and deletions must clear cached entries. Mostly ignorable for our case since URLs rarely change, but expired links need a TTL so they return 410
• One more component to run, and the cache is now a dependency on the read path

Bottleneck 3: Global Latency

Benchmark

Latency: under 100 ms for users worldwide.

What Breaks

A user far from our servers pays network latency on every redirect, even when the cache hits.

Constraints:

1. Keep redirects under 100 ms for distant users
2. Keep control over expiry and updates (the reason we chose 302)

Bad Solution: Single Region

Approach:

Run everything in one region and accept the distance.

Challenges:

• Users on the other side of the world pay a round trip across the globe
• One region outage takes down every redirect

Good Solution: Multi Region Servers

Approach:

Deploy the Read Service and cache in several regions and route users to the closest one.

Challenges:

• Lower latency for most users (meets constraint 1)
• Each region needs its own cache, and the database must be replicated across regions
• Much more operational work than the problem needs

Great Solution: CDN / Edge Computing

Approach:

Serve redirects from edge locations near the user. The edge caches short code -> long URL mappings, or runs a small function that looks them up.

Challenges:

• Redirects resolve close to the user, so latency drops the most
• Tension with 302: if the edge answers on its own, requests never reach our server, so click tracking is lost, but we can fix with a short TTL, or have the edge log the click asynchronously
• Freshness: a cached edge entry can outlive an expired or deleted link, so use a short TTL or purge on update
• Only worth it with a global user base. Regional traffic doesn't need it

Bottleneck 4: Scaling Reads

What Breaks

One Server handles every Redirect(), and shares a machine with Create(). Redirect() traffic (~578,700/sec at spike) can starve Create(), and the two can't scale or fail independently.

Fix

Split off a Read Service with multiple instances behind an API Gateway. This is the mirror image of the Write Service split, so the same matching Bad / Good / Great options are in the Create() section, Bottleneck 3.

Read specific points:

• Read Service instances are nearly stateless. They only talk to the cache and the database
• Scale the number of instances with redirect load, independent of writes
• The API Gateway routes GET /{short_code} to the Read Service

Bottleneck 5: Database Availability

What Breaks

One database is a single point of failure. If it dies, every cache miss fails, and once cached entries expire, every redirect fails.

Constraints:

1. Survive the failure of a single database node
2. Recover data after a serious failure

Bad Solution: Single Database

Approach:

Keep one database instance.

Challenges:

• One crash means downtime and possible data loss (breaks constraints 1 and 2)

Good Solution: Backups (Periodic Snapshots)

Approach:

Take periodic snapshots of the database and store them in a separate location.

Challenges:

• Protects against data loss (meets constraint 2)
• Restoring takes time, so downtime is still long
• Anything written since the last snapshot is lost
• The system has to work with the restored copy without issues

Great Solution: Replication With Failover

Approach:

Run identical copies of the database on different servers (e.g., PostgreSQL replication). If the primary goes down, promote a replica and redirect to it.

Why it works:

• Failover takes seconds instead of a restore, so it fits 99.99%
• Replicas also serve reads, which helps Bottleneck 2
• Keep backups too. Replication copies mistakes (like a bad delete) to every replica, snapshots don't

Challenges:

• Operational overhead: servers must work with any replica
• Async replication lag can lose the last few writes on failover
• Failover monitoring and split brain risk if two nodes both think they are primary