Om's Brain

1. Bit.ly

6 min read

Diagram in progress 😊.. v0 below

bitly.excalidraw

1️⃣ Problem Statement

Build a URL shortening service like:

https://www.google.com/search?q=system+design
 
↓
 
https://bit.ly/aB3xYz

When users visit the short URL, they should be redirected to the original URL.

2️⃣ Requirements Gathering

Functional Requirements

Core Features

  1. Create short URL from long URL
Long URL
↓
Short URL

Example:

https://google.com/search?q=test
 
↓
 
bit.ly/aB3xYz
  1. Redirect users
bit.ly/aB3xYz
 
↓
 
https://google.com/search?q=test

Optional Features

Custom Alias

User can provide custom code:

bit.ly/omi
bit.ly/interview
bit.ly/sdeprep

instead of

bit.ly/aB3xYz

Expiration Time

bit.ly/event2026

Valid only until:

2026-12-31

After expiry:

404 / Link Expired

3️⃣ Non-Functional Requirements

Low Latency

Redirect should feel instant.

Target:

< 200 ms

Reason:

  • Human perceives anything below ~200ms as real-time.

Scalability

Support:

100 Million DAU
1 Billion URLs

Uniqueness

Every short URL must be unique.

Bad:

bit.ly/abc123
 
→ Google.com
 
and
 
bit.ly/abc123
 
→ Amazon.com

Collision must never happen.

High Availability

System should remain operational even during failures.

Prefer:

Availability > Strong Consistency

because URL shortening is not a banking system.

4️⃣ CAP Theorem Decision

Need Strong Consistency?

Examples that require it:

  • Banking
  • Ticket Booking
  • Trading Systems

Reason:

Every read must see latest write.

Bitly?

Not necessary. Scenario:

Create URL
 
↓
 
Immediately open URL
 
↓
 
Fails for few seconds

This is acceptable.

Decision

CP ❌
AP ✅

Choose:

High Availability
Eventual Consistency

5️⃣ Core Entities

User

User

URL

Short URL
Long URL

6️⃣ API Design

Create Short URL

POST /urls

Request:

{
  "originalUrl": "https://google.com",
  "customAlias": "omi",
  "expirationTime": "2026-12-31"
}

Response:

{
  "shortUrl": "bit.ly/omi"
}

Redirect

GET /{shortCode}

Example:

GET /aB3xYz

Response:

302 Redirect
Location: https://google.com

7️⃣ Database Design

URL Table

ColumnDescription
short_urlGenerated code
original_urlActual URL
created_atCreation timestamp
expiration_timeOptional expiry
user_idCreator

User Table

ColumnDescription
user_idPrimary Key
emailUser email
metadataOther info

8️⃣ Basic High Level Design

Client
   |
   v
Application Server
   |
   v
Database

Create URL Flow

Client
   |
POST /urls
   |
   v
Server
   |
Generate Short Code
   |
Store Mapping
   |
   v
Database
   |
Return Short URL

Redirect Flow

Client
   |
GET /abc123
   |
   v
Server
   |
Lookup Original URL
   |
   v
Database
   |
Return Original URL
   |
302 Redirect

9️⃣ 301 vs 302 Redirect

301 Permanent Redirect

Client caches redirect.

Future requests may never reach Bitly.

Pros

  • Lower server cost
  • Less traffic

Cons

  • No analytics
  • Harder monitoring

302 Temporary Redirect

Every request hits Bitly.

Pros

  • Analytics tracking
  • Monitoring
  • Click counting

Cons

  • Higher traffic

Interview Choice

302 Redirect ✅

Reason:

Analytics and observability are valuable.

🔟 Deep Dive #1 - Generating Unique Short Codes

Option 1: URL Prefix

Take first few characters.

Example:

https://google.com
 
↓
 
https:

Problem

Many URLs share same prefix.

https://twitter.com
https://facebook.com

High collision rate.

❌ Reject

Option 2: Random Number + Base62

Generate:

Random Number

Then convert to:

Base62

Characters:

0-9
A-Z
a-z

Total:

62 characters

Why Base62?

6-character code:

62^6 ≈ 56 Billion combinations

Problem

Birthday Paradox

Even with 56 billion combinations:

1 Billion URLs

can still produce collisions.

Solution

Before insert:

Generate Code
   |
Check DB
   |
Collision?

If yes:

Generate Again

Option 3: Hash Long URL

SHA256(url)

Then:

Base62 Encode

Take first:

6 chars

Problem

Still collisions.

Same fix:

Check DB first

Use:

1
2
3
4
...

Convert using Base62. Example:

1 -> 1
10 -> A
61 -> z
62 -> 10

Benefits

  • Fast
  • Unique
  • No collision checks

Drawback

Predictable IDs Competitors can:

bit.ly/1
bit.ly/2
bit.ly/3
...

and scrape links.

Solution

Use Bijective Function

Counter
   |
Obfuscation
   |
Base62

Example library:

Sqids

Produces:

fG8xT2
kL9pQ1

instead of predictable values.

1️⃣1️⃣ Deep Dive #2 - Reducing Redirect Latency

Step 1: Database Indexing

Without index:

1 Billion rows
 
↓
 
Full Scan

Very slow.

Use:

PRIMARY KEY(short_url)

Database builds:

B-Tree Index

Lookup becomes:

O(log N)

Step 2: Redis Cache

Client
   |
Server
   |
Redis
   |
Database

Cache Structure

Key   = Short URL
Value = Original URL

Example:

abc123
    ↓
https://google.com

Read Through Cache

Check Redis

If hit:

Return immediately

If miss:

Read DB
↓
Update Cache
↓
Return Result

Eviction Policy

LRU

Least Recently Used.

Old URLs automatically removed.

Step 3: CDN (Optional)

Store redirects at edge locations.

China User
   |
China CDN

instead of

China User
   |
California Server

Tradeoff

Pros:

  • Faster global latency

Cons:

  • Lose analytics visibility

1️⃣2️⃣ Deep Dive #3 - Scaling

Estimate Traffic

Given:

100 Million DAU

Approx:

10^8 users

Seconds/day:

10^5

RPS:

10^8 / 10^5
 
≈ 10^3
 
≈ 1000 RPS

Peak:

10k - 100k RPS

Scale Application Layer

Vertical Scaling

Bigger Server

More CPU More Memory

Horizontal Scaling (Preferred)

          +---- Server 1
Client -> LB
          +---- Server 2
          +---- Server 3

Split Services

Instead of:

One Monolith

Use:

API Gateway
     |
     +--> Read Service
     |
     +--> Write Service

Reason:

Reads >> Writes

Redirect traffic dominates.

Auto Scaling

Scale based on:

CPU > 75%
Memory > 75%

Add instances automatically.

1️⃣3️⃣ Scaling Counter Service

Problem:

Multiple Write Servers

Each maintaining own counter.

Server A -> Counter = 10
Server B -> Counter = 10

Collision!

Solution

Global Counter

Write Service
      |
      v
Redis Counter

Redis command:

INCR

Because Redis is single-threaded:

1
2
3
4
5

Guaranteed unique.

Optimization

Allocate batches:

Server A -> 1-1000
 
Server B -> 1001-2000

Reduces Redis calls.

1️⃣4️⃣ Database Scaling

Storage estimate:

~500 bytes per row

For:

1 Billion URLs

Storage:

500 GB

Modern SSDs:

Multiple TBs

So:

Single DB is enough.

If needed:

Sharding

Shard by:

short_url

Example:

hash(short_url) % N

Routes data to correct shard.

1️⃣5️⃣ High Availability

Redis Cache Failure

Not critical.

Cache Miss
↓
Database
↓
Rebuild Cache

System still works.

Global Counter Failure

Critical. Need:

  • Replication
  • Snapshots
  • Failover

Database Failure

Use:

Primary DB
    |
Replica DB

and

Hourly Snapshots
→ S3

Recovery:

Replica Promotion
or
Restore Snapshot

Final Architecture

                    +----------------+
                    |  API Gateway   |
                    +----------------+
                       /         \
                      /           \
                     v             v
           +---------------+ +---------------+
           | Read Service  | | Write Service |
           +---------------+ +---------------+
                  |                 |
                  |                 |
                  v                 v
             +---------+      +------------+
             | Redis   |      | Global     |
             | Cache   |      | Counter    |
             +---------+      +------------+
                  |                 |
                  +--------+--------+
                           |
                           v
                    +-------------+
                    | PostgreSQL  |
                    +-------------+
                           |
                           v
                    Replica + Backup

Interview Summary

Functional Requirements

✅ Create short URL
✅ Redirect users
✅ Custom Alias
✅ Expiration Time

Non-Functional Requirements

✅ Low Latency (<200ms)
✅ Scalability (100M DAU)
✅ Unique Short Codes
✅ High Availability
✅ Eventual Consistency

Key Technologies

  • PostgreSQL
  • Redis Cache
  • Redis Global Counter (INCR)
  • Base62 Encoding
  • B-Tree Index
  • API Gateway
  • Horizontal Scaling
  • Read/Write Service Separation
  • Database Replication
  • Snapshots/Backups

Mindmap

Graph View