System requirements

Functional:

• URL shortenning: create a new short URL from an URL
• URL dredirection: given a short URL get forwarded to the real one

Non-Functional:

• Scalability: the system will have big number of users with many redirections and some URLs with very high demand
• Latency: low for redirection
• Consistency: eventual consistency is acceptable
• Availability: the system must be higly available, specially for redirections

Capacity estimation

1 million active users

• Average 1 URL shortening per day
• Average 10 URL redirections per day

1 million URL shortening per day. 200 per second

10 million URL redirections per day. 20.000 per second

Storage

URL record size estimation: 1 KB

• User: 256 B
• Full URL: 512 B
• Short URL: 16 B
• Published date: 4 B

1 year: 1 KB * 10^6 * 365 = 365 GB

3 years: more than 1 TB

API design

shortenURL()

• Input: long URL
• Output: short URL

redirectURL()

• Input: short URL
• Output: HTTP 302 redirecting to long URL

Database design

URL record size estimation: 1 KB

• User: 256 B
• Full URL: 512 B
• Short URL: 16 B
• Published date: 4 B

High-level design

Main components:

• DNS: transaltes service name to IP
• CDN: stores highly used redirections in geographically distributed servers. Improves response time and reduces system load improving performance
• Load balancer: routes client requests to web servers for request execution. Distrubutes load, provides high availability and scalability
• Web servers: perform the logic for shortening and redirection. Without state for simplicity and scalability
• MongoDB as main persistent storage for URLs
• Redis as cache for fast access and ofload MongoDB

Request flows

Write path

• User sends request to shorten URL
• Shorten URL Service generates shorten URL, stores in URLs database

Read path

• User requests the full URL from a short URL
• If available in CDN the redirection is returned from the CDN
• If redirect not in CDN, request is sent to Redirect URL Services, which looks in the Redis cache. If found: it's returned, if not: it's retreived from MongoDB and stored in Redis

Publish in CDN path

• Periodically, the Hot URL manager Service, queries in Redis to identify most used short URLs and publishes them in the CDN

Detailed component design

Redis cache

In a system with a high ratio of queries / writes, it's important to have a fast cache to:

• Reduce database requests
• Reduce latency
• Increase scalability

It is used to cache shortURL --> longURL mappings once published

Stores entries with a TTL so they are expired when no used, because it's expected that URL queries diminish over time

Also LRU eviction policy is used in case to many entries are created and memory is not enough

A sorted set is used to identify short URLs that will be published in the CDN when they exceed a threshold. In that moment they are deleted from the sorted set

CDN

For celebrity problem, wehn short URLs are published in social networks, a CDN is used to:

• Reduce cache queries
• Reduce latency
• Increase scalability

After the number of requests of a shortURL exceeds a threshold, for example 100, it's promoted to the CDN

Web Servers

For providing scalability and availability, several web servers handle requests received in the Load Balancer

The architecture is stateless to increas scalability and avoid operational problems

Trade offs/Tech choices

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

MongoDB is used instead of a RDBMS for storing URLs because:

• The high number of information to store
• No complex queries are needed
• No structured data requiered
• Eventual consistency is reasonable having high availability

Only highly queried URLs are stored in the CDN to reduce costs, as the number of shortened URLs is very high

Redis cache uses LRU to evict not commonly used short URLs

Failure scenarios/bottlenecks

The main bottlenecks could be in the getRedirection requests son a CDN and a Redis cache are used before querying the MongoDB database

The URLs database could also be a bottleneck, and a component difficult to scale reducing availability. MongoDB with eventual consitency is selected, with partitioning and data replication, to:

• Have high availability
• Improve write speed

To avoid Single Point Of Failure:

• CDN is highly available
• Load Balancer is highly available with an active-active failover
• Web Servers are replicated and restarted in case they stop working
• MongoDB use data replication into several instances

Future improvements

To avoid Redis SPOF Redis Sentinel will be used for automatic failover