URL Shortener

When discussing the system design of a URL shortener like TinyURL or Bit.ly, ensure you cover the following key aspects. Structuring your notes around these will help you stay organized during the interview.

---

Requirements

Functional Requirements

• Shorten a given URL and return a unique, shortened version

• Redirect users to the original URL when they use the shortened URL.

• Custom alias support

• Optionally, allow expiration and analytics (clicks, user analytics, etc.).

Non-Functional Requirements

• Focus on availability over consistency: The service should always be up.

• Low Latency: Redirection should be fast.

• Scalability: Support millions or billions of URLs.

• Durability: Store URLs reliably to prevent data loss.

---

Estimation and Capacity Planning

• QPS (Queries Per Second): Estimate reads and writes (e.g., 10:1 ratio).

• Storage Requirements: Assume average URL length and calculate storage needs (e.g., 1 billion URLs).

---

Entities

• Original URL

• Shortened URL

• User

---

API Design

• POST /shorten -> returns a shortened URL.

  • { originalUrl, customAlias?, expirationTime? }

• GET {shortUrl}-> Redirects to the original URL.

  • HTTP 302 (temporary redirect) instead of HTTP 301 (permanent redirect which browser caches)

• Optional APIs for stats or management:

  • GET /stats/{shortUrl}.

b) Database Schema

• ShortUrl (short_key, original_url, created_at, expiration_date)

• Index on short_key for fast lookups.

c) URL Shortening Logic

• Short Key Generation:

  • Use a Base62 encoding scheme (characters a-z, A-Z, 0-9) to keep keys short and human-readable.

    • A 6-character Base62 key can represent over 56 billion unique URLs (62⁶).

  • Counter/Sequence: Increment a global counter and encode the value in Base62.

    • A single Redis instance on modern hardware can handle 80,000 to 100,000 operations per second (OPS) for simple commands like INCR, assuming:

      • Redis is running on dedicated high-performance hardware.

      • The network is low-latency and high-bandwidth.

      • There are no significant memory or disk I/O bottlenecks.

• Handle collisions in case of duplicate keys.

d) Data Storage

• Choose a storage system based on scale:

  • Relational Databases: MySQL/PostgreSQL for small-scale systems.

  • NoSQL Databases: DynamoDB, Cassandra, or MongoDB for large-scale systems.

  • In-memory caching (Redis or Memcached) for frequently accessed data.

e) Redirection

• Use HTTP 301 (Moved Permanently) or 302 (Found) for redirection.

---

Scaling the System

a) Read/Write Patterns

• Reads will dominate writes (many more redirections than shortenings).

• Optimize for high-read throughput using caching.

b) Partitioning and Replication

• Use database replication for durability, fault tolerance and to allow scaling reads horizontally.

• Partition data by the short key to distribute load (consistent hashing).

c) Caching

• Use Redis or Memcached to cache mappings of frequently accessed short_key -> original_url.

d) Rate Limiting

• Implement rate limiting to prevent abuse (e.g., spamming the shorten API).

---

High-Level Architecture

---

Trade-offs and Challenges

• Key Length: Shorter keys are user-friendly but increase the chance of collisions.

• Consistency: Balancing consistency and availability (CAP theorem).

• Redundancy: Ensure data is not lost due to server failures.

• Performance: Optimize key lookup and redirection latency.