Katkat
Back

Design and Implement a URL Shortening Service

xAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

Tests your ability to design a globally distributed, highly available URL shortening service capable of handling high read/write throughput with sub-millisecond redirection latency and collision-free ID generation.

Scenario

Design a scalable, highly available URL shortening service similar to TinyURL or bit.ly, suitable for global deployment with low-latency redirection and high fault tolerance.

Requirements

Functional Requirements

  • Shorten URL: Generate a unique, compact alias (e.g., 7-8 characters) for a given long URL.
  • Custom Alias: Allow users to specify a custom alias if available.
  • Redirection: Redirect incoming requests on a short link to the original target URL with minimal latency.
  • Expiration & Lifecycle: Support optional expiration timestamps (TTL). Expired links should return HTTP 404 or 410.
  • Analytics: Record basic access metrics (click count, timestamp, user agent, referrer) asynchronously.

Non-Functional Requirements

  • Low Latency: p99 redirect latency under 15ms globally.
  • High Availability: 99.999% uptime for redirection paths.
  • Consistency vs. Availability: Prioritize read availability over absolute immediate write consistency across regions.
  • Scalability: Handle massive scale gracefully with no single point of failure.

Scale & Traffic Estimations

  • Write Traffic: 500 million new URLs created per month (~200 writes/sec average, 2,000 writes/sec peak).
  • Read Traffic: 100:1 read-to-write ratio (~20,000 reads/sec average, 100,000 reads/sec peak).
  • Storage: URLs kept for 5 years on average. Estimate data volume for URLs and metadata.
  • Cache: Target caching 20% of the daily hot URLs in memory.

What Your Design Should Cover

  1. API Design: Endpoints, request/response payloads, and standard HTTP status codes (301 vs 302/307).
  2. Short ID Generation Strategy: Compare hashing (MD5/SHA-256 + collision resolution) vs. unique distributed ID generators (e.g., Snowflake, centralized token range service) paired with Base62 encoding.
  3. Data Model & Storage: Choice of database (NoSQL key-value vs. Relational vs. Document) and partition/sharding key strategies.
  4. Caching & CDN Strategy: Multi-tier caching (Edge/CDN, Redis clusters) and cache invalidation.
  5. Edge Redirection & Geo-routing: Routing users to the nearest point of presence (PoP) to satisfy low-latency redirection.

Hints

Hint 1

To avoid hash collisions and lock contention, consider allocating unique integer ranges to worker nodes and encoding those integers into Base62 strings.

Hint 2

Carefully consider the choice between HTTP 301 (Permanent) and HTTP 302/307 (Temporary) redirects in terms of browser caching vs. server-side click analytics capture.

Hint 3

A distributed key-value store partitioned on the short URL hash can provide O(1) lookups, but handling viral short links requires local in-memory caching at edge nodes to avoid hot partition saturation.

Follow-up questions

  • How would you prevent malicious actors from using your service for phishing or spreading malware at scale?
  • How does your architecture handle sudden viral traffic (hot-key problem) where a single link receives 500,000 requests per second?
  • If deploying across multi-region active-active datacenters, how do you handle custom alias reservation without cross-region write contention?