Designing A Simple Url Shortening Service A TinyURL Approach - System Design

System requirements

Functional:

Take url as post request
Redirect a short URL to the original long URL.
generate new link Incase of url not match
Return generate short url

Non-Functional:

Scalable to concurrrent requests.
Low latency and High availability
Reliable to all geographical location.
Load balancing system required in terms to maintain load on a server.
Data durability to ensure short URLs are never lost.

Capacity estimation

DAU: 10 million users.

Requests/User: 2 requests per day.

Record Size: 500 bytes (including short URL, long URL, metadata).

Peak Factor: 2x average traffic during peak hours.

Calculations:

Traffic Estimation: Peak RPS=10M×286,400×2≈463RPS\text{Peak RPS} = \frac{10M \times 2}{86,400} \times 2 \approx 463 RPSPeak RPS=86,40010M×2​×2≈463RPS
Data Storage:  Total Records (1 year)=10M×2×365≈7.3B records\text{Total Records (1 year)} = 10M \times 2 \times 365 \approx 7.3B \text{ records}Total Records (1 year)=10M×2×365≈7.3B records Storage=7.3B×500 bytes≈3.65 TB\text{Storage} = 7.3B \times 500 \text{ bytes} \approx 3.65 \text{ TB}Storage=7.3B×500 bytes≈3.65 TB
Cache Capacity (assuming 20% of records are frequently accessed): Cache Size=0.2×7.3B×500≈730 GB\text{Cache Size} = 0.2 \times 7.3B \times 500 \approx 730 \text{ GB}Cache Size=0.2×7.3B×500≈730 GB
Bandwidth (assuming 1 KB per request/response): Bandwidth=463 RPS×1 KB≈463 KB/sec≈3.7 Mbps\text{Bandwidth} = 463 \text{ RPS} \times 1 \text{ KB} \approx 463 \text{ KB/sec} \approx 3.7 \text{ Mbps}Bandwidth=463 RPS×1 KB≈463 KB/sec≈3.7 Mbps
Compute Instances (assuming 50 RPS per instance): Instances Required=46350≈10\text{Instances Required} = \frac{463}{50} \approx 10Instances Required=50463​≈10

API design

Shorten URL:

Request:

json
Copy code
{
  "long_url": "https://www.example.com/longurl"
}

Response:

json
Copy code
{
  "short_url": "https://short.ly/cb"
}

Redirect URL:

GET https://short.ly/cb
Response: 302 Redirect to https://www.example.com/longurl.

Get Analytics:

Request:

json
Copy code
{
  "short_url": "https://short.ly/cb"
}

Response:

json
Copy code
{
  "click_count": 500,
  "created_at": "2024-11-01T12:34:56Z"
}

Database design

Database Design

Table Structure:
- short_url: VARCHAR(10) (Primary Key)
- long_url: TEXT
- created_at: TIMESTAMP
- click_count: INT

Cache

Use Redis or Memcached for fast lookups.
- Frequently accessed short URLs are cached to reduce database load.

Encoding Algorithm (Base62)

Characters: 0-9, a-z, A-Z (62 characters).
Convert unique ID to a base62 string.
Example:

def encode_base62(num):
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    base = 62
    encoded = []
    while num > 0:
        encoded.append(chars[num % base])
        num //= base
    return ''.join(reversed(encoded))

ID Generation

Use a distributed ID generator (e.g., Snowflake, UUID) to ensure unique IDs in a distributed system.

High-level design

API Gateway: Handles user requests (shorten and redirect).
URL Shortening Service: Core logic for encoding/decoding URLs.
Database: Stores the mapping between short and long URLs.
Cache: Speeds up read operations for frequently accessed URLs.
Analytics Service: Tracks usage metrics for short URLs.
kubernates: In order to scale horizontal by number of server instances
Load Balancer :

Request flows

URL Shortening Process:

User Input: User submits a long URL via API.
Generate Short URL:
- Use a unique identifier (ID) encoded in base62 (alphanumeric).
- Example: ID 125 → base62 cb.
- Append the base62 code to the domain: short.ly/cb.
Store in Database:
- Store mapping in a key-value format:
  - Key: Short URL (e.g., cb).
  - Value: Long URL (e.g., https://www.example.com/longurl).

URL Redirect Process:

User accesses short.ly/cb.
The system looks up the short URL in the database.
If found, redirect the user to the long URL.
If not found, return a 404 error.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?