DEV Community

Cover image for Sytem Design: Shorten URL Problem
Nguyen Nguyen
Nguyen Nguyen

Posted on

Sytem Design: Shorten URL Problem

#systemdesign

1. Functional Requirements

  • Input: original long URL
  • Output: shorten URL
  • Redirect from short URL to original URL
  • Custom alias is allowed
  • Short URL have expiration time (optional)
  • Analytics (click count, IP, country...)

2. Non-functional Requirements

  • Redirect latency < 50ms
  • High availability
  • Read-heavy system.

3. High-level Architecture 

                   +----------------+
Client ----------> | URL Service    |
                   +----------------+
                     |          |
              Redis Cache    PostgreSQL
                     |
                 Redirect

                     |
             Async Event (Kafka)
                     |
             +----------------+
             | Analytics      |
             | Consumer       |
             +----------------+
                     |
                ClickHouse
             (Analytics DB)
Enter fullscreen mode Exit fullscreen mode

a. URL Creation workflow 

Client
   |
POST /shorten
   |
Insert into DB
(long_url)
   |
DB generates ID = 12345
   |
Encode Base62
   |
short_code = "3D7"
   |
UPDATE url
SET short_code = '3D7'
WHERE id = 12345
   |
Return https://sho.rt/3D7
Enter fullscreen mode Exit fullscreen mode

b. URL Redirection workflow 

GET /AbCd12

↓

Redis

↓

Hit

↓

Return 301

↓

Miss

↓

DB

↓

Update cache

↓

301 Redirect
Enter fullscreen mode Exit fullscreen mode

4. Database

Core URL

URL

id
short_code (unique)
long_url
created_at
expired_at
user_id
Enter fullscreen mode Exit fullscreen mode

Look up URL

SELECT long_url
FROM url
WHERE short_code='AbCd12'
Enter fullscreen mode Exit fullscreen mode

Analytics

Raw events

click_events
------------
event_id
short_code
timestamp
ip
country
city
referrer
user_agent
device
browser
os
Enter fullscreen mode Exit fullscreen mode

Aggregated Stats

aggregated_stats
----------------
short_code
period_type
period
country
browser
device
click_count
Enter fullscreen mode Exit fullscreen mode

If we're using an OLAP database like ClickHouse, these aggregate tables can be maintained automatically using Materialized Views, eliminating the need for custom aggregation jobs.

5. Short Code Generation

Short Code Generation Solution

  • Small system: Random String
  • Most production systems: Auto-Increment ID + Base62
  • Large distributed systems: Snowflake ID + Base62 (optionally obfuscate the ID before Base62 encoding to avoid exposing sequential IDs)

Snowflake structure

| 1 bit | 41 bits | 10 bits | 12 bits |
|-------|---------|----------|----------|
| Sign  | Timestamp | Worker ID | Sequence |
Enter fullscreen mode Exit fullscreen mode

Snowflake ID generation algorithm

lastTimestamp = 0
sequence = 0

current = now()

if current == lastTimestamp
    sequence++
else
    sequence = 0

if sequence > 4095
    wait until next millisecond

lastTimestamp = current

id =
(timestamp << 22)
|
(workerId << 12)
|
sequence
Enter fullscreen mode Exit fullscreen mode

ID generation capacity

4096 × 1000 × 1024
≈ 4.2 billion IDs/second
Enter fullscreen mode Exit fullscreen mode

6. Why Base62?

Base62 includes: a-zA-z0-9
Those are URL-friendly characters

6 characters -> 62^6 ≈ 56 billion URL
7 characters -> 62^7 ≈ 3.5 trillion URL
8 characters -> 62^8 ≈ 218 trillion URL

7. Cache & Expiration

Always cache expired_at, short_code, long_url

Check expired_at value

if expired

↓

404

Otherwise, redirect 301
Enter fullscreen mode Exit fullscreen mode

A cronjob run periodically to remove expired short URL from cache

8. Analytics 

Redirect

↓

Kafka

↓

Analytics Consumer

↓

Batch Update
Enter fullscreen mode Exit fullscreen mode
  • Donot update DB every request
  • Using multiple asynchronous workers

Top comments (0)