Design a scalable URL shortening service

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: 1) High-level architecture (services, storage, caches, CDN/edge considerations). 2) Data model/schema for storing mappings. 3) Strategy for generating short codes: - Option A: hashing the long URL - Option B: generating globally unique IDs and encoding them (e.g., Base62) 4) How to guarantee global uniqueness across multiple instances/regions. 5) 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.