Katkat
Back

Design a URL shortening service

NVIDIASoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

This problem tests your ability to design a high-scale, low-latency URL shortening service that requires distributed ID generation, efficient storage strategies, and high availability.

Problem: URL Shortener Design

Design a URL shortening service similar to bit.ly or tinyurl.com. The system allows users to provide a long URL and returns a shorter, alias-based URL. When the short URL is accessed, the system redirects the user to the original long URL.

Functional Requirements

  1. URL Shortening: User provides a long URL and receives a unique short link.
  2. Redirection: When a user visits the short link, redirect them to the original long URL.
  3. Custom Aliases: Users can optionally specify a custom string for the short URL.
  4. Analytics: Track the number of clicks for each shortened link.

Non-Functional Requirements

  1. Low Latency: Redirection must be extremely fast (ideally < 100ms).
  2. High Availability: The system must handle high traffic volume without downtime.
  3. Scalability: The service should support billions of URLs and thousands of requests per second.

Constraints & Assumptions

  • Assume 500 million new URLs are generated per month.
  • Assume a Read-to-Write ratio of 100:1.
  • Data should be persisted and accessible globally.

Deliverables

Provide a high-level architecture diagram and describe the following:

  • API Design: Define the endpoints for shortening and redirection.
  • Data Model: Choose between SQL and NoSQL and justify the schema.
  • ID Generation: Explain how to generate unique, short, and fixed-length identifiers.
  • Performance: How will you handle the high read load (e.g., caching, load balancing)?
  • Scalability/Availability: Explain how you will handle a surge in traffic or a database failure.

Hints

Hint 1

Consider how a distributed ID generation service (like Snowflake) could avoid collisions and ensure sequential growth.

Hint 2

Think about the impact of the 100:1 read-to-write ratio on your database choice and the role of an in-memory cache like Redis.

Hint 3

Address how you would handle 'hot keys' (a specific short URL that receives millions of clicks) to prevent database overloading.

Follow-up questions

  • How would you handle link expiration or 'garbage collection' for URLs that are never accessed?
  • If you needed to perform analytics (e.g., geographic location of clicks), how would you structure the data pipeline without impacting the redirection latency?
  • How would you prevent malicious users from spamming your system with invalid URLs or scraping all possible short link combinations?