Design a highly scalable URL shortening service (like bit.ly).
Requirements:
-
Provide an API to create a short URL for a given long URL.
-
Provide an API to redirect (resolve) a short code back to the original long URL.
-
The mapping must be
unique
(no two long URLs should end up with the same short code unless explicitly intended) and
reversible
(given a short code, you can retrieve the original URL).
-
The system should handle high read traffic (redirects) and support horizontal scaling.
-
Discuss caching and persistence choices.
Deliverables:
-
High-level architecture (services, storage, caches, CDN/edge considerations).
-
Data model/schema for storing mappings.
-
Strategy for generating short codes:
-
Option A: hashing the long URL
-
Option B: generating globally unique IDs and encoding them (e.g., Base62)
-
How to guarantee global uniqueness across multiple instances/regions.
-
Follow-up: If you use hashing, how do you detect and handle hash collisions? Provide at least two approaches and their tradeoffs.
Assumptions (state any others you need):
-
Short codes should be as short as possible (e.g., 6–10 characters) and URL-safe.
-
Redirect latency should be low (e.g., p95 < 50 ms) and the service must tolerate partial failures.