Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Redirect to long URL when request for short URL received

Non-Functional Requirements:

• low latency
• high availability

API Design

POST /url?long=

Response:

Status Created

Content-Type string

Body

GET /:short

Response:

Status Redirect

should redirect to long URL

or

Status NotFound

if long URL not found for provided "short"

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Load balancer.

Distributing the load and route requests to API servers processing appropriate subset of URLs.

API server.

Should be stateless and cache most recently used short URLs for performance.

Database.

We should optimise it for reading and it should allow sharding.

Detailed Component Design

Load balancer.

For scalability we may introduce sharding by short URL prefix (4 symbols for example) using consistent hash algorithm.

If corresponding upstream is dead, any API should be capable to respond correctly.

API server.

Should keep LRU cache with short URL - long URL pairs. Cache size should be limited.

Items in cache should have relatively small TTL - for when short URL is invalidated it should not stay in cache for too long.

Database.

We may simply store record {short_url, short_url_prefix, long_url} and have sharding by short_url_prefix field. This requires more space but sharding becomes more simple and we have broader choice for database.

Index [short_url_prefix, short_url] allows sharded and fast queries.