Design a scalable URL shortener

Quick 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.

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.

Microsoft logo
Microsoft
Jan 22, 2025
easyData EngineerTechnical ScreenSystem Design
31
0

Design a highly scalable URL shortening service, similar to Bitly or TinyURL. The service converts long URLs into short links and redirects short-code requests back to the original URL.

Constraints & Assumptions

  • Redirect reads are much higher volume than short-link creation writes.
  • Short codes should be URL-safe, globally unique, and preferably 6 to 10 characters.
  • Redirection should be low latency and highly available.
  • The mapping must be reversible by lookup: given a short code, the service can retrieve the original URL.
  • Include abuse prevention and operational concerns.

Clarifying Questions to Ask Guidance

  • What expected read QPS, write QPS, and total number of links should we design for?
  • Are custom aliases required?
  • Should redirects be permanent or temporary for browser caching and analytics?
  • Do links expire?
  • Is active-active multi-region support required on day one?

Part 1 - Define Requirements And APIs

What functional and non-functional requirements would you support, and what APIs would you expose?

What This Part Should Cover Guidance

  • Create short link and resolve or redirect short code.
  • Example request and response shapes, status codes, validation, and error cases.
  • Latency, availability, scalability, and partial-failure assumptions.

Part 2 - Design Storage And Data Model

What data would you store, and what datastore would you choose?

What This Part Should Cover Guidance

  • Mapping from short_code to long_url plus metadata such as owner, expiry, created time, status, and analytics flags.
  • KV or wide-column store for high-volume point lookups, with relational storage for accounts and admin metadata if needed.
  • Sharding, replication, and consistency tradeoffs.

Part 3 - Generate Globally Unique Short Codes

How would you generate short codes and guarantee uniqueness across instances and regions?

What This Part Should Cover Guidance

  • Hash-based option and its collision tradeoffs.
  • Unique ID plus Base62 option.
  • Conditional insert or unique constraint as the final arbiter.
  • Region-aware or shard-aware ID generation for active-active operation.

Part 4 - Optimize Redirect Performance

How would you handle caching, scaling, and reliability?

What This Part Should Cover Guidance

  • Redis or in-memory cache, CDN or edge caching, cache-aside behavior, TTLs, negative caching, and cache stampede prevention.
  • Partitioning by short code, read replicas, failover, and degraded behavior when analytics or cache fails.

Part 5 - Handle Operations And Hash Collisions

How would you handle abuse, observability, expiration, analytics, and hash collisions?

What This Part Should Cover Guidance

  • Rate limiting, malware/phishing checks, structured metrics, redirect logs, async analytics, TTL cleanup, and collision-resolution strategies.
  • At least two hash-collision handling approaches and their tradeoffs.

What a Strong Answer Covers Guidance

  • Separates write path from read-heavy redirect path.
  • Chooses a collision-resistant code-generation strategy and explains uniqueness under concurrency.
  • Optimizes the hot redirect path without putting analytics on the critical path.
  • Discusses operational risks, abuse, observability, and failure handling.

Follow-up Questions Guidance

  • Why might you choose 302 instead of 301?
  • How many codes are possible with 7 Base62 characters?
  • How would you handle a celebrity link that becomes extremely hot?
  • How would you support custom aliases safely?
  • What changes for active-active multi-region writes?