Loading...
## 1. System Requirements
### Functional Requirements
- **Shortening**: Users can input a long URL and receive a unique, short URL (alias).
- **Redirection**: Clicking the short URL redirects the user to the original long URL.
- **Custom Alias**: Users can define a custom alias (e.g., `mysite.com/summer-sale`) if available.
- **Expiration**: Users can set an expiration time for links.
- **User Accounts**: Authenticated users can manage their links (edit, delete).
- **Analytics**: Tracking metrics including click count, timestamp, country, and user agent.
### Non-Functional Requirements
- **Scalability**: Must handle read-heavy traffic (Read:Write ratio approx. 100:1). The system must scale horizontally — stateless application servers behind a load balancer, sharded databases, and clustered caches — so capacity grows by adding nodes, not upgrading hardware.
- **Latency**:
- **Redirection**: < 20ms (server processing time).
- **Shortening**: < 200ms.
- **Availability**: 99.99% uptime. The system must be highly available (AP in CAP theorem).
- **Durability**: Data must persist efficiently for up to 5 years.
- **Security**: Prevention of brute-force attacks and malicious URL injection.
---
## 2. Capacity Estimation (Back-of-the-envelope)
- **New URLs**: 100 million/month.
- **Write QPS**: ~40 writes/second.
- **Read QPS**: ~4,000 reads/second.
- **Storage**:
- Record size: ~500 bytes.
- 5-year storage: 100M * 12 months * 5 years * 500 bytes ≈ **3 TB**.
- **Cache**: Storing 20% of daily requests (hot URLs) in memory.
## 3. API Design
### 3.1. Create Short URL
`POST /api/v1/urls`
**Request:**
```json
{
"long_url": "https://example.com/very-long-path",
"custom_alias": "custom-alias",
"expire_at": "2026-12-31T23:59:59Z"
}
```
**Response:** `201 Created`
```json
{
"short_url": "https://sho.rt/custom-alias",
"hash": "custom-alias"
}
```
### 3.2. Get URL Stats
`GET /api/v1/urls/{alias}/stats`
**Response:** `200 OK`
```json
{
"total_clicks": 1502,
"breakdown": { "US": 500, "VN": 200 }
}
```
### 3.3. Delete Short URL
`DELETE /api/v1/urls/{alias}`
**Response:** `204 No Content`
### 3.4. Update Short URL
`PATCH /api/v1/urls/{alias}`
**Request:**
```json
{
"long_url": "https://example.com/updated-path",
"expire_at": "2027-06-30T23:59:59Z"
}
```
**Response:** `200 OK`
### 3.5. Internal/Redirection Endpoint
`GET /{alias}`
**Response:** `302 Found` (Temporary Redirect)
- **Header**: `Location: {long_url}`
- **Note**: We use **302** instead of 301 to ensure traffic hits our servers for analytics tracking.
## 4. High-Level Design
### Architecture Diagram Flow
1. **Client** sends a request.
2. **Load Balancer (LB)**: Distributes traffic across Web Servers.
3. **Web Server / API Gateway**: Handles validation, rate limiting, and authentication.
4. **Caching Layer (Redis)**: Stores mapping of `ShortURL -> LongURL`. Checks here first for redirection.
5. **Application Service**:
- **Shortening Service**: Generates unique ID.
- **Redirection Service**: Handles cache misses.
6. **Database**: Persistent storage for mappings and users.
7. **Async Workers (Kafka + Workers)**: Decouples analytics logging from the redirection path to ensure low latency.
### Architecture Diagram
```plantuml
@startuml
!theme plain
skinparam componentStyle rectangle
skinparam defaultFontSize 12
cloud "Clients" as clients
node "Edge Layer" {
[CDN / DNS] as cdn
[Load Balancer] as lb
}
node "Application Layer" {
[API Gateway\n(Auth, Rate Limit, Validation)] as gw
[Shortening Service] as shorten
[Redirection Service] as redirect
}
database "Cache Layer" {
[Redis Cluster\n(ShortURL → LongURL)] as redis
}
database "Data Layer" {
[URL Mapping\n(DynamoDB / Cassandra)] as urldb
[User DB\n(PostgreSQL)] as userdb
}
queue "Event Stream" {
[Kafka] as kafka
}
node "Analytics Pipeline" {
[Analytics Workers] as workers
[ClickHouse / TimescaleDB] as olap
}
clients --> cdn
cdn --> lb
lb --> gw
gw --> shorten
gw --> redirect
redirect --> redis : 1. Check cache
redirect --> urldb : 2. Cache miss
redirect --> kafka : 3. Push click event
shorten --> urldb : Write mapping
shorten --> redis : Warm cache
kafka --> workers
workers --> olap
shorten --> userdb : Auth lookup
@enduml
```
### Sequence: Redirect Flow
```plantuml
@startuml
!theme plain
skinparam defaultFontSize 12
actor User
participant "Load Balancer" as LB
participant "API Gateway" as GW
participant "Redirection\nService" as RS
database "Redis" as Cache
database "URL DB" as DB
queue "Kafka" as MQ
participant "Analytics\nWorker" as AW
User -> LB : GET /{alias}
LB -> GW : Forward
GW -> RS : Route
RS -> Cache : GET alias
alt Cache Hit
Cache --> RS : long_url
else Cache Miss
RS -> DB : Query by hash
DB --> RS : long_url
RS -> Cache : SET alias → long_url
end
RS ->> MQ : Async push click event
RS --> User : 302 Redirect (Location: long_url)
MQ -> AW : Consume event
AW -> AW : Aggregate & store
@enduml
```
### Sequence: Create Short URL Flow
```plantuml
@startuml
!theme plain
skinparam defaultFontSize 12
actor User
participant "API Gateway" as GW
participant "Shortening\nService" as SS
participant "ID Generator\n(Snowflake)" as IDG
database "URL DB" as DB
database "Redis" as Cache
User -> GW : POST /api/v1/urls\n{long_url, custom_alias?, expire_at?}
GW -> GW : Validate, rate limit, auth
GW -> SS : Create request
alt Custom Alias provided
SS -> DB : Conditional write\n(check alias not exists)
alt Alias taken
DB --> SS : Conflict
SS --> User : 409 Conflict
end
else Auto-generate
SS -> IDG : Get unique ID
IDG --> SS : 64-bit ID
SS -> SS : Base62 encode → alias
SS -> DB : Write mapping
end
DB --> SS : OK
SS -> Cache : SET alias → long_url
SS --> User : 201 Created\n{short_url, hash}
@enduml
```
## 5. Detailed Component Design
### 5.1. Unique ID Generation
To ensure short links are unique and collision-free, we cannot rely on simple database auto-increment (predictable and hard to shard).
**Chosen Approach: Base62 Conversion + Distributed ID Generator**
- **Base62**: Characters `[A-Z, a-z, 0-9]`.
- **Length**: 6 characters = $62^6$ ≈ 56.8 billion combinations.
- **ID Generator (Snowflake or Ticket Server)**:
- We generate a unique 64-bit integer ID first (e.g., `10000000001`).
- Convert this integer to Base62 (e.g., `10000000001` -> `sT4nZ`).
- This guarantees uniqueness without checking the DB for collisions.
### 5.2. Caching Strategy
**Cache-Aside Pattern**:
- **Read**: Check Cache -> If miss, Check DB -> Write to Cache -> Return.
- **Write**: Write to DB -> (Optional: Write to Cache immediately).
- **Eviction Policy**: LRU (Least Recently Used).
- **TTL**: Set expiration for cache keys (e.g., 24 hours) to handle "viral" links that eventually cool down.
### 5.3. Analytics Processing (Async)
Redirection speed is critical. We must not write to the analytics database synchronously during the redirect request.
1. User clicks link.
2. Server redirects user immediately (Latency < 20ms).
3. Server pushes an event `{short_id, timestamp, user_agent, ip}` to a **Message Queue (Kafka)**.
4. **Analytics Consumers** read from Kafka, aggregate data, and write to an **OLAP database** (e.g., ClickHouse or TimescaleDB) or a NoSQL store.
---
## 6. Database Design
### 6.1. Schema
We can use a **NoSQL database** (like DynamoDB or Cassandra) for the URL mappings due to massive scale and simple Key-Value structure.
#### Table: `URL_Mapping`
- **Partition Key**: `hash` (String) - The short alias
- **Columns**:
- `original_url` (String)
- `created_at` (Timestamp)
- `expiration_date` (Timestamp)
- `user_id` (String)
#### Table: `User` (Relational DB is fine here)
- `user_id` (PK)
- `email`
- `api_key`
- `plan_type`
### 6.2. Database Model
```plantuml
@startuml
!theme plain
skinparam defaultFontSize 12
entity "URL_Mapping" as url {
* hash : String <<PK>>
--
original_url : String
created_at : Timestamp
expiration_date : Timestamp
user_id : String <<FK>>
}
entity "User" as user {
* user_id : UUID <<PK>>
--
email : String <<unique>>
api_key : String <<unique>>
plan_type : Enum
created_at : Timestamp
}
entity "Click_Event" as click {
* event_id : UUID <<PK>>
--
hash : String <<FK>>
clicked_at : Timestamp
country : String
user_agent : String
ip_address : String
referer : String
}
user ||--o{ url : "creates"
url ||--o{ click : "tracks"
@enduml
```
### 6.3. Database Partitioning (Sharding)
- **Hash-Based Sharding**: Use the `hash` (short alias) to determine which database shard stores the data.
- This ensures even distribution of data across nodes.
---
## 7. Security & Abuse Prevention
- **Rate Limiting**: Per IP and per API key (e.g., 100 creates/hour for free tier, 10K for paid).
- **URL Validation**: Check against Google Safe Browsing API or internal blocklist before accepting URLs.
- **Abuse Detection**: Monitor for mass creation patterns; flag and block suspicious accounts.
- **Input Sanitization**: Reject URLs with invalid schemes, excessively long URLs (> 2048 chars), or known phishing patterns.
---
## 8. Expiration & Cleanup
- **DynamoDB TTL**: Native TTL attribute on `expiration_date` — DynamoDB auto-deletes expired items.
- **Cache Eviction**: Redis keys are set with TTL matching the link expiration; expired keys are automatically purged.
- **Fallback**: Scheduled cleanup job runs daily to sweep any records missed by TTL (e.g., for Cassandra deployments).
- **Redirect Behavior**: If a link is expired, return `410 Gone` instead of redirecting.
---
## 9. Monitoring & Observability
| Metric | Target | Tool |
|--------|--------|------|
| Redirect latency (p99) | < 20ms | Prometheus + Grafana |
| Cache hit ratio | > 95% | Redis metrics |
| Kafka consumer lag | < 1000 events | Kafka monitoring |
| Error rate (5xx) | < 0.01% | APM (Datadog/New Relic) |
| Uptime | 99.99% | Health checks + PagerDuty |