Katkat
Back

Design a Highly Available URL Shortener

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question tests your ability to design a distributed, highly available system that handles high-read traffic and ensures data integrity for short-URL mappings.

Problem Statement

Design a URL shortening service similar to bit.ly. The system should allow users to submit a long URL and receive a short, unique identifier. When the short URL is visited, the system must redirect the user to the original long URL.

Requirements

  • Functional: Generate a short alias for a long URL; redirect to the original URL; support custom aliases; enforce link expiration.
  • Non-Functional: High availability is critical (redirects cannot fail); the system must handle a high read-to-write ratio (100:1); redirect latency must be under 100ms.
  • Scale Assumptions: Assume 100 million new URLs are shortened per month and 1 billion redirects occur per month.

What to provide

  1. API Design: Define the necessary REST endpoints.
  2. Data Model: Propose a database schema (SQL vs. NoSQL) that supports efficient lookups.
  3. High-Level Architecture: Include load balancers, application servers, storage layers, and caching strategies.
  4. Key Decisions: Explain how you handle ID generation (collisions, uniqueness, distribution) and how you ensure high availability during primary database failure.

Worked Example

Input: POST /api/v1/shorten with body {"long_url": "https://example.com/very/long/path"} Output: {"short_url": "https://tiny.url/aBcDeF"}

Input: GET /aBcDeF Output: 301 Redirect to https://example.com/very/long/path

Hints

Hint 1

Consider using Base62 encoding to convert a unique auto-incrementing ID into a compact string representation.

Hint 2

A distributed key-value store like Redis is highly effective for caching frequently accessed URLs to minimize database read load.

Hint 3

Think about using a consistent hashing strategy or a dedicated service to generate unique IDs if you decide to shard your database.

Follow-up questions

  • How would you handle a scenario where a specific URL becomes a 'hot key' and receives millions of requests per second?
  • How would you implement analytics, such as tracking the number of clicks per short URL, without impacting the performance of the redirection path?
  • If the database becomes corrupted, what strategies would you use for data recovery and maintaining consistency between the database and the cache?