System requirements

Functional:

• Create short URL for long URL
• Redirect users with short URL to long URL
• Authenticate user
• Analytics for shorten URL
• User generated short URL
• Manage deleted URLs

Non-Functional:

• Availability: Choosing availability over consistency. System should consider fault tolerance
• Scalability: System needs to be able to handle high traffic for redirection and creation of short URLs

Capacity estimation

URLs to shorten - 200/sec

Redirection traffic - 20000 redirects/sec

Avg size of long URL - 2KB

Avg size of short URL - 256B or 0.256KB

User metadata: 5KB

Total data to be stored - 200 * 60 * 60 * 24 * 10KB = 172 GB per day

API design

shortenURL()

input: long URL, user id

output: short URL

redirect()

input: short URL, user id

output: redirection to long URL

Database design

Use key value store like dynamodb for strong consistency and scalability for large amount of data.

Data can be partitioned using long url as the partitioning key.

High-level design

Client

• Sends request for redirection or creation of short URL

API gateway

• Handles request routing
• Implements rate limiting

Shortening service:

• Handles URL shortening(hashing)
• Logs analytics data

Redirection Service:

• Redirects user with short URL to long URL
• Logs analytics data

Analytics Service:

• Collects logs from redirection and shortening service and generates analytics

Authentication Service:

• Authenticates user

DynamoDB:

• Stores long-short URL pair

Cache:

• Store frequently accessed URLs
• Improves read performance and reduces latency

Request flows

Shorten URL: Client sends long URL for shortening. Service shortens URL. Store long-short URL in DB and update cache

Redirect: Client sends request with short URL. Access short URL from cache. If not present in cache, get it from database

Authenticate user: Authentication service verifies user and sends request to shorten service

Detailed component design

Trade offs/Tech choices

• Use MD5 caching technique for shortening URL
• Using NoSQL DynamoDB since system requires high throughput and nosql databases are highly scalable
• Cache will be updated mostly for redirection service since the system is high read
• Trading slower write latency with high read latency

Failure scenarios/bottlenecks

• Hash collision
• Single point of failure during peak traffics

Future improvements

• Real time analytics
• Fix hash collision