Design a URL Shortener

This case study simulates a realistic FAANG system design interview for designing a high-scale URL shortening service like TinyURL or Bitly. It details the step-by-step dialogue, calculations, architectural diagrams, and trade-off considerations required to pass a Senior-level (L5/L6) design loop.

1. Present the Interview Question

2. Clarifying Questions

The candidate starts by asking clarifying questions to establish the system's operational boundaries:

• ‍Candidate: What is the expected scale of the system? How many new URLs are generated per month, and what is the read-to-write ratio?
  Interviewer: We expect to generate 100 million new URLs per month. The read volume is roughly 10x the write volume (1 billion redirects per month).
• ‍Candidate: What is the default expiration time for shortened links? Can users define custom expiration times?
  Interviewer: Yes, the default expiration should be 2 years. Users cannot define custom expirations for the scope of this interview.
• ‍Candidate: Can users request custom short aliases?
  Interviewer: Yes, users should be able to supply a custom alias (e.g. bit.ly/my-cool-promo).
• ‍Candidate: Do we need to collect analytics for shortened link clicks?
  Interviewer: Yes, basic analytics like click counts over time and visitor geo-locations are nice to have.

3. Functional Requirements

Based on the clarification phase, the candidate documents the functional scope:

• Create Short URL: Take a long URL, return a short unique URL key.
• URL Redirection: Look up the short key and redirect visitors to the original long URL with low latency.
• Custom Alias: Allow users to define a custom shortened path if it is not already taken.
• Expiration Clean-up: Expire links after 2 years and purge them from the system.
• Basic Analytics: Track the number of times a short link is clicked.

4. Non-Functional Requirements

The non-functional requirements dictate the scaling architecture constraints:

• High Availability: 99.999% uptime for the redirection service. People depend on these links.
• Low Latency Redirection: Redirection lookup must execute in under 30ms.
• Durability: Once a mapping is saved, it must never be lost before its expiration date.
• Unpredictability: Short URLs keys must be random/unpredictable to prevent malicious crawl harvesting.

5. Capacity Estimation

The candidate performs back-of-the-envelope calculations to size the infrastructure:

1. Traffic (Queries Per Second)

• Writes: 100 Million URLs per month = 100M / (30 days * 86,400 sec) = ~40 writes/sec (QPS).
• Reads (Redirects): 1 Billion lookups per month = 1,000M / (30 days * 86,400 sec) = ~400 reads/sec (QPS).

2. Storage (Metadata Sizing)

Assume a record is size-modeled as follows:

• Short Key (7 chars): 7 bytes
• Original Long URL (varchar): 500 bytes (average)
• User ID (UUID): 36 bytes
• Timestamps (created, expires): 16 bytes
• Total Record Size: ~560 bytes

Daily write storage: (100M / 30) * 560 bytes = 3.3M * 560 = ~1.86 GB/day.
Yearly write storage: 1.86 GB * 365 = ~680 GB/year.
5-Year Storage Capacity: 680 GB * 5 = ~3.4 TB.

3. Cache Size (80/20 Rule)

Assume 20% of the daily read redirection traffic is responsible for 80% of lookups.
Daily reads count = 1 Billion / 30 days = ~33.3 Million reads/day.
20% cache allocation volume = 33.3M * 0.20 = 6.66 Million records.
Required RAM Cache: 6.66M * 560 bytes = ~3.73 GB of RAM. (Easily cached on a single medium-sized Redis node).

6. Identify Core Components

The system consists of three main decoupled services:

• API Gateway: Acts as traffic entry, handles security rate limits, and routes queries.
• Write Service (Shortener Service): Processes long URLs, calls the key generator, saves mappings, and populates the cache.
• Read Service (Redirector Service): Receives incoming short links, queries Redis/Database, issues redirection headers, and logs metrics to a message queue.
• Unique ID Generator: Provides unique keys/counters to ensure zero collision.
• Distributed Cache: Low-latency Redis cluster to handle 90% of redirects.
• Data Store: Persistent, partitioned storage (NoSQL Key-Value).

7. High-Level Architecture

The candidate draws the initial High-Level Design (HLD) showing the split ingress path for writing and reading URLs:

8. API Design

The candidate defines REST endpoints for the core operations:

1. Shorten URL Request

POST /api/v1/urls

Request Payload:

Response Payload (201 Created):

2. Redirect Request

GET /{shortKey}

Headers Returned (302 Found):

9. Data Model

Since the operations are simple key-value lookups without relational table joins, the schema is highly optimized for flat key retrieval:

10. Database Selection

‍Candidate: I choose a NoSQL Wide-Column Datastore like Apache Cassandra or DynamoDB over a relational SQL database.
Reasoning: We do not require relational queries or multi-row ACID transactions. The primary access pattern is reading the row mapped to short_key. Cassandra scales horizontally by partitioning rows using a hash function on the Partition Key (short_key). This guarantees O(1) reads and write speeds, and allows us to easily support terabytes of data by adding nodes without complex primary-replica overheads.

11. Deep Dive into Key Generation

The candidate compares key generation strategies:

Option A: Hashing the Long URL

Hash the long URL using MD5 or SHA256, then Base62 encode it, and extract the first 7 characters.
Problem: Collisions are mathematically possible. If two long URLs generate the same first 7 characters, we must detect it by querying the DB. If it exists, append a dynamic salt to the long URL and re-hash. This creates database checking overhead on every write, degrading performance.

Option B: Centralized Unique ID Range Allocator (Recommended)

We can use a coordinated counter system (e.g. Apache ZooKeeper managing a Key Generation Service (KGS)). The KGS distributes ranges of unique numbers (e.g., Node 1 gets ID range 1–1,000,000, Node 2 gets 1,000,001–2,000,000).
Each compute node increments its local range counter. When it is exhausted, the node requests a new range. Once a node has a unique numeric ID (like 45,671,293), it performs a Base62 encoding calculation to turn it into a 7-character string:

• Base62 characters: [a-z, A-Z, 0-9] (total 62 characters).
• Length of 7 characters provides: 62^7 = ~3.5 Trillion unique combinations.
• This guarantees that no two servers will ever generate the same shortened key, completely eliminating collision checking.

12. Complete Request Lifecycle

Write Request Flow (Create Link)

1. Client posts long URL to API Gateway.
2. Gateway authenticates client and verifies rate limits.
3. Shortener Service receives request, calls the KGS local counter to get a unique numeric ID.
4. Shortener Service Base62 encodes the number to create a 7-character key (e.g., aB8x9Y2).
5. The service writes the mapping aB8x9Y2 -> longUrl asynchronously to Redis and Cassandra.
6. The server returns the shortened URL to the client (Latency: ~15ms).

Read Request Flow (Redirection)

1. Client browser clicks link: https://bit.ly/aB8x9Y2.
2. API Gateway receives query, routes it to Redirector Service.
3. Redirector Service queries the Redis cluster using key aB8x9Y2.
   • Cache Hit (90%+): Redis returns long URL immediately.
   • Cache Miss: Redirector Service queries Cassandra. If found, it writes it back to Redis for subsequent reads. If not found, returns a 404.
4. Redirector Service returns an HTTP 302 Found redirection response.
5. Redirector Service writes an analytics event containing timestamp and client IP metadata to Kafka.

13. Scaling Strategy

To handle spikes globally, we scale across layers:

• Geo-Redirection: Deploy Redirection gateways across multiple cloud regions close to users (US East, US West, Europe West, Asia East).
• Read Replica Scaling: Configure Cassandra multi-region deployment. Cassandra's masterless architecture allows local reads to execute fast in the nearest data center.
• Cache Replication: Deploy local Redis instances in each region to minimize cross-region network roundtrips.

14. Bottleneck Analysis

The candidate identifies potential failure hot-spots:

• Hot Key Caching Pitfall: A celebrity shares a short link, causing millions of lookups per second. A single Redis node hosting that key will crash due to network saturation.
  Mitigation: Enable Redis replication. Distribute read queries across multiple read replicas within the same cache cluster.
• KGS Range Expiry: If ZooKeeper goes offline, KGS instances cannot request new ID ranges, crashing write availability.
  Mitigation: KGS buffer sizes should hold 24 hours of ranges locally. If Zookeeper goes down, we have a large buffer window to recover the coordination cluster.

15. Trade-off Discussion: HTTP Redirections

‍Candidate:
- HTTP 301 (Permanent): The browser caches the redirection mapping locally. Subsequent clicks go straight to the long URL without hitting our redirection servers. This reduces our server load and network cost. However, because it bypasses our servers, we lose the ability to count clicks or gather analytics accurately.
- HTTP 302 (Temporary): The browser is forced to query our redirect servers on every single click. This increases server QPS reads, but guarantees we can capture 100% of click events and analytics.
Decision: We will use HTTP 302 to meet the analytics functional requirement, while deploying Redis replicas to handle the extra QPS scale cleanly.

16. Failure Scenarios

How the system survives node failures:

• Cassandra Read Failover: If Cassandra nodes go down, cached URLs continue resolving via Redis. For cache misses, a fallback placeholder error page is shown, or the lookup falls back to secondary replicas.
• Purging Expired Links: Scanning Cassandra tables to clean out millions of expired links degrades disk I/O.
  Mitigation: Configure Cassandra column TTL (Time To Live). Cassandra naturally discards columns after the TTL expires without running slow table scan queries.

17. Security Design

The system secures itself against crawler bots and DDoS attacks:

• Rate Limiting: Deny write requests exceeding 5 creations per minute per User IP to stop script spam.
• Obfuscation: Do not assign sequential short keys (e.g. aB8x9Y1, aB8x9Y2). An attacker can guess keys and scrape destination links. The KGS generator can shuffle numerical IDs or append a random salt during encoding to randomize key sequences.

18. Monitoring & Observability

Observability dashboard alerts:

• Metrics: Redis Cache Hit Rate (alert if it drops below 80%), API Redirection Latency (p99 limit: 30ms).
• Logs: Log click analytics to Kafka, which pushes data asynchronously to ClickHouse for analytical queries.

19. Cost Optimization

To save on cloud SSD costs, configure Cassandra tables with cold storage tiering. Expired records are automatically pruned, while historical analytical logs are compressed and archived in S3 glacier buckets.

20. Production Improvements

If given more budget: deploy Cloudflare CDN edge workers. Redirection lookups can execute directly in the CDN edge nodes closest to the user. Redis caches can be deployed globally to Edge locations, cutting network RTT down to single-digit milliseconds.

21. Interviewer Follow-up Questions

‍Candidate: Custom aliases bypass KGS. They must be validated against the datastore. To prevent race conditions (double allocation):
1. We acquire a distributed lock in Redis for that custom key: SET lock:myPromo true NX PX 5000.
2. Only the instance that acquires the lock queries Cassandra. If the key is free, it writes the row.
3. It releases the lock. The second concurrent request fails to acquire the lock and is returned a 409 Conflict error.

22. Final Architecture

The final optimized architecture incorporates the ID Range Allocator and the real-time analytics pipeline:

23. Summary

The URL shortener is a classic read-heavy system. We optimized reads by utilizing a Redis Cache-Aside layer. Write collisions were completely eliminated by implementing a Unique ID Generator with a range allocation model (ZooKeeper + KGS), converting numeric keys to short 7-character paths via Base62 encoding.

24. Cheat Sheet

25. Candidate Interview Evaluation