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

• Long URL (100B)
• Short URL (8B)
• Created time (8B)
• Created by user ID (20B)
• Expiration time (8B)

Each entry is 144B, rounding off to 256B

Total data to be stored - 200 * 60 * 60 * 24 * 256 = 4.4 GB per day

Within 5 years, it will be 4.4 * 365 * 5 = 8TB of data

Including cache, it will be ~15TB of data

API design

shortenURL()

input: long URL, user id

output: short URL

redirect()

input: short URL, user id

output: redirection to long URL

Database design

We need a simple long to short URL mapping. We won't need any complex queries for this system.

However, it requires string consistency.

DynamoDB would be a good choice. It is horizontally scalable and can be configured for strong consistency.

We can also provide secondary index like userid to quickly look urls created by given user

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

Database and cache should be partitioned for improved scalability.

We can use short url as partitioning key. Since users will be using short url more often, it will be a good choice as it will ensure data is distributed evenly.

Other partitioning keys won't be able to give this advantage.

Trade offs/Tech choices

• Use random hashing 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

Fault Tolerance

• All components should have multiple instances. We should have monitoring and alerting systems for in case of failures

Scalability for shorten service

• If there's an increase in writes, we can introduce message queues
• This will reduce load on database and improve efficiency

Future improvements

• Real time analytics
• Custom URLs