Requirements

Functional Requirements:

• a user can shorten a URL
• any person entering that short URL is redirected to the URL

Non-Functional Requirements:

• Redirect must be fast
• Scalability
• perfect correctness: a user shouldn't be redirected to the wrong URL.
• High availability

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

100 million daily active users

Read/write: ~1 write for 1000 redirects.

Storage requirements: scalability to millions of URLs. TTL? URLs should have a limited lifespan of a few months for example (esp. if no users).

QPS: Given 100 million DAU, with a few redirects (1-10) per users, that's a high estimate of 1B requests/day so 10k redirects per second.

With our read/write ratio, that's 10 writes per second. So 1M a day, and 300M a year. If limited lifespan, we need storage for around a billion of URLs, each URL representing basically a key/value relationship stored across, for example 3 servers, to maximise uptime. Let's assume ~100 bytes for key+value, that's 3B*100 = 300GB of storage required. If traffic 3x, we can have an estimate of max 1TB of storage, that should be resolved through horizontal scalability

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

GET short_urls/{short_url} -> returns the long URL

PUT url_dict/{long_url} -> generates a short URL key and adds the pair {short_url:long_url} to the storage

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.

Two paths from the user.

Either the user connects on the official website of the URL shortener and adds a URL. The server calls the PUT endpoint to generate the short URL and returns it to the client.

To do so, we produce a short code through a hash code, guaranteeing uniqueness through a collision check, and store the relationship in the database. The database must be a durable source of truth, surviving restarts, with each relationship written as several instances across data units.

Either the user enters a short URL. The DNS resolver returns to a server that automatically calls the GET endpoint, which returns the long URL and calls a redirect, conducting the client to the correct endpoint.

We use a cache to speed up the redirect for most commonly searched URLs to avoid querying the whole database.

To favor horizontal scalability, we use an API Gateway/Load Balancer when calling the GET endpoint to distribute the calls across different servers.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Storage model

• Key–value store: short_code → long_url, where short_code is the primary key.
• Columns: short_code(PK), long_url, created_at, expires_at.
• Lookup by short_codeis a single-key point read → O(1).

Sharding

• Partition by hash(short_code) mod N. Hashing distributes codes evenly, so no shard gets hot, and each lookup touches exactly one shard (no scatter/gather).
• As data grows past a single node, add shards and move partitions; the hash keeps distribution balanced.

Availability

• Each shard is replicated (primary + replicas) so a node failure doesn't take the mapping offline.

Consistency

• Writes (creation):need strong consistency — the code must be durably stored and unique before it's returned, so we never hand out a code that doesn't exist or reuse one.
• Reads (redirect):eventual consistency is acceptable. A lagging replica can briefly 404 a just-created code, but that's transient and never returns the wrong URL. Given reads are 1000× writes, favoring read availability and latency over read freshness is the right trade-off.

Expiry

• expires_at acts as a TTL so the store can auto-purge expired rows — the storage saving noted in capacity estimation.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Database already detailed

Cache: My suggestion, register the visits. The top 1% (for example) most visited websites likely concentrates the vast majority of redirects, so we store the key->value relationship in a cache for faster querying.

How to update it? If a code in the database reaches a certain threshold of visits (dynamically computed per week) over the past 24 hours, it is put to the cache with a TTL of a week, to capture trends and adapt.

The database being regularly cleaned to remove the expired codes, for each code, we verify if it is in cache, and if it's the case, we delete it in the cache too to avoid returning outdated URL.

On a cache miss (or after TTL expiry), look up the mapping in the database, return the redirect, and write it back into the cache (with a short TTL for cold keys).

To avoid IDs being easy to guess, we'll draw the codes from a large Base62 space, so guessing a valid one is in practice infeasible.

Finally, we need rate limiting, to prevent DDoS attacks. A max number of request per unit of time returning a 429 + Retry-After when crossing.

For extreme spikes: Real-time visit counter per code: crossing ~100 req/min promotes it to cache with a TTL; known scheduled blasts are pre-warmed at creation. Reads are served from cache/CDN, so the origin absorbsthe spike, not the DB.