Katkat
Back

Design a high-scale URL shortener

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This problem tests your ability to design a distributed, highly available URL shortening service that manages massive read-heavy traffic and ensures low-latency redirection.

Problem Statement

Design a URL shortening service similar to bit.ly or tinyurl.com. The system needs to support millions of requests per day with a high read-to-write ratio.

Functional Requirements

  1. URL Shortening: Given a long URL, the service should generate a unique, shorter, and random-looking alias (e.g., bit.ly/3xYz).
  2. URL Redirection: When a user visits the shortened URL, the service should redirect them to the original long URL.
  3. Custom Aliases: Allow users to pick a custom alias if it is not already taken.
  4. Expiration: Links should expire after a certain duration (optional, but requested by the client).

Non-Functional Requirements

  1. Low Latency: Redirection must be extremely fast, ideally under 100ms.
  2. High Availability: The service must be highly available; if one component fails, the rest of the system should continue to operate.
  3. Scale: The system should support 100 million new URLs per month with a 100:1 read-to-write ratio.

Deliverables

Provide a high-level architecture diagram or description covering:

  • API design (request/response format).
  • Data storage strategy (NoSQL vs. SQL, schema design, and partitioning).
  • Mechanism for URL shortening (e.g., base62 conversion, hashing, or ID generation).
  • Strategy for handling high read volume (caching, load balancing).
  • Handling of concurrency and collisions.

Hints

Hint 1

Consider how to map a unique integer ID to a short URL string using Base62 encoding (A-Z, a-z, 0-9).

Hint 2

Evaluate the trade-offs between using a SQL database for relational consistency versus a NoSQL Key-Value store like Cassandra or DynamoDB for horizontal scale.

Hint 3

Think about using a cache layer like Redis to store the most frequently accessed URLs to minimize database read pressure.

Follow-up questions

  • How would you handle the requirement to generate analytics, such as the number of clicks per link or the geographic location of the users?
  • If the database is partitioned by hash, how do you handle hotkeys (e.g., a viral link that receives millions of hits in a short window)?
  • What changes would you make if you needed to ensure that the shortened URLs are impossible to guess or brute-force?