Design a scalable URL shortener
Company: Microsoft
Role: Data Engineer
Category: System Design
Difficulty: easy
Interview Round: Technical Screen
##### Question
Design a **highly scalable URL shortening service** (like bit.ly / TinyURL) that converts long URLs into short links and supports redirection. Cover the architecture, data model, short-code generation, uniqueness, caching, scaling, and operational concerns below.
1. **Functional 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 **globally unique** (no unintended collisions) and **reversible** (given a short code, you can always retrieve the original URL via lookup).
2. **Non-functional requirements & assumptions**
- High availability and **high QPS**, with reads/redirects typically far outnumbering writes.
- Support **horizontal scaling** across multiple instances/regions.
- Short codes should be as short as possible (e.g., **6–10 characters**) and **URL-safe**.
- Low redirect latency (e.g., **p95 < 50 ms**); the service must tolerate **partial failures**.
- State any other assumptions you need.
3. **APIs**
- Define example endpoints for creating short links and performing redirects (request/response shapes, status codes).
4. **Data model & storage**
- What you store per short link (e.g., `short_code`, `long_url`, `created_at`, `expiry`, `owner_id`).
- Choice of datastore(s): KV store vs relational DB vs both, and why.
5. **Short-code generation strategy**
- **Option A:** hash the long URL.
- **Option B:** generate globally unique IDs (e.g., Snowflake / auto-increment) and **Base62**-encode them.
- How you ensure uniqueness and performance under concurrency.
6. **Guaranteeing global uniqueness** across multiple instances/regions.
7. **Caching & performance**
- Use of in-memory cache (e.g., Redis) and/or CDN for hot links.
- Cache key design, TTL, and cache-miss behavior.
8. **Scalability & reliability**
- Partitioning/sharding strategy.
- Replication, failover, and consistency trade-offs.
9. **Operational concerns**
- Abuse prevention (rate limits), observability/metrics, link expiration, and analytics logging (optional).
10. **Follow-up:** If you use a **hash** of the long URL to generate the short code, **how do you detect and handle hash collisions?** Provide at least two approaches and their trade-offs.
Overview: Design a scalable URL shortener with create and redirect APIs, Base62 short-code generation, global uniqueness, KV storage, caching, CDN optimization, sharding, replication, abuse prevention, observability, expiration, analytics, and hash-collision handling.