Katkat
Back

Design a URL Shortener (High-Level and Low-Level Design)

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests the ability to design a distributed, scalable URL shortening service by addressing key generation strategies, storage schema, and caching policies.

Problem Statement

Design a URL shortening service similar to bit.ly. The system should allow users to input a long URL and receive a unique, short alias. When a user visits the short alias, they should be redirected to the original long URL.

Requirements

  1. Functional:

    • shorten(long_url): Converts a long URL to a short alias.
    • redirect(short_url): Returns the original long URL.

  2. Non-Functional:

    • High availability: The redirect service must be extremely fast.
    • High scale: Support 100 million new URLs per day with a read-to-write ratio of 100:1.
    • URL persistence: Shortened URLs should not expire unless specified by the user.

Expected Deliverables

  • API Design: Define the request and response structures.
  • Data Model: Propose a database schema for storing mappings.
  • Key Generation: Explain how to generate unique, short identifiers (e.g., 6–8 characters) and how to handle collisions.
  • Architecture: Provide a high-level diagram or description including load balancers, application servers, databases, and caching layers.

Constraints

  • Assume 5 years of data retention.
  • Total reads per day: 10 billion.
  • Total writes per day: 100 million.

Example

  • Input: https://www.example.com/very/long/path/to/resource
  • Output: https://tiny.url/aB3dEf
  • Redirect: Requesting https://tiny.url/aB3dEf returns a 302 redirect to the original URL.

Hints

Hint 1

Consider using Base62 encoding (a-z, A-Z, 0-9) to generate short, dense character strings from a numeric ID.

Hint 2

Decide whether to use a SQL or NoSQL database based on the read-heavy nature and the need for horizontal scalability.

Hint 3

Implement a caching strategy (e.g., LRU cache) to store the most frequently accessed URLs to reduce database load.

Follow-up questions

  • How would you handle a scenario where two users attempt to shorten the same long URL simultaneously?
  • If the database becomes a bottleneck, how would you partition or shard the data?
  • How would you implement analytics to track the number of clicks on a shortened URL?