System Design: URL Shortening Service at Internet Scale

You are asked to design a URL shortening service for hundreds of millions of users with high availability and low latency. The system must support at least 100,000 requests per second (RPS).

Functional and Non-Functional Requirements

• Create short tokens for long URLs and redirect requests to their original URLs.
• Enforce per-link expiration; expired links must not resolve.
• High concurrency; thread/process safe with low-latency redirects.
• Sustain ≥100k RPS overall.

Questions

1. Data model, storage schema, and indexing: What would you use, and how would you implement TTL handling efficiently?
2. Token generation: How would you generate collision-resistant, non-enumerable tokens? Discuss randomness, length, and access controls.
3. Expired data cleanup: How would you clean up expired data efficiently? Compare lazy deletion versus scheduled batch sweeps and their impact on cache and storage.
4. Scaling reads/writes: How would you use distributed caching and consistent hashing? Include cache invalidation and hot-key mitigation.
5. Multi-region: How would you design cross–data center replication and consistency guarantees for create/read operations, including handling propagation delay, failover, and conflict resolution?
6. External interface and operations: What APIs, rate limiting, abuse prevention, and observability (metrics, logs, alerts) would you implement?
7. Capacity and SLOs: Provide back-of-the-envelope capacity estimates (QPS, storage, bandwidth) and SLOs for latency and availability.