Bird
Raised Fist0

Design a URL Shortener - Encoding, Redirect, Analytics, Custom Alias

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a URL Shortener - Encoding, Redirect, Analytics, Custom Alias
Design a scalable URL shortener with custom aliases, redirect, and analytics at 2B DAU scale
mediumInfrastructure and Platform SystemsFreq: high
Prerequisites:HashingKey-Value Stores
⚙️
Functional Requirements
  • Encode a long URL into a unique short URL alias
  • Redirect short URL requests to the original long URL with low latency
  • Support custom aliases chosen by users with collision detection
  • Collect and serve analytics on URL usage (click counts, geolocation, device info)
  • Expire or deactivate URLs after a configurable TTL or on user request
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating ~40 URL shorten requests per user per day
  • Support 99.99% availability for redirect requests
  • Ensure 100ms P99 latency for redirect and encoding APIs
  • Store and process analytics data with eventual consistency within 1 hour
  • Scale to 10x growth without major redesign
❓
Clarifying Questions to Ask
  • What is the expected average length of original URLs and short URLs?
  • Are short URLs case-sensitive or case-insensitive?
  • What is the expected retention period for analytics data?
  • Should the system support URL expiration or deletion?
  • Is there a requirement for global distribution or geo-redundancy?
  • What is the expected ratio of read (redirect) to write (encode) requests?
Out of Scope
✗ User authentication and authorization mechanisms
✗ Monetization or billing features
✗ Advanced fraud detection or spam filtering
✗ URL content validation or malware scanning
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user creates 40 short URLs per day on average
  • Average original URL size is 100 bytes
  • Read to write ratio is 10:1 (redirects dominate)
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qpsWrite QPS × 10 = 9,259,260 reads/sec
peak read qpsAssuming 2× peak factor → 18,518,520 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention days365
total storage8 TB × 365 = 2.92 PB
with replication2.92 PB × 3 replicas = 8.76 PB
🖥️
Server Estimate
write serversAssuming each write server handles 10K writes/sec → 1,851,852 / 10,000 ≈ 186 servers
read serversAssuming each read server handles 50K reads/sec → 18,518,520 / 50,000 ≈ 370 servers
🏗️
Architecture Diagram
Architecture Diagram
          +-------------+
          |  Client UI  |
          +------+------+
                 |
        +--------v---------+
        |  API Gateway     |
        +--------+---------+
                 |
    +------------+-------------+
    |                          |
 +--v---+                  +---v---+
 |Write |                  |Read   |
 |Service|                  |Service|
 +--+---+                  +---+---+
    |                          |
    |                          |
 +--v--------------------------v---+
 |          Cassandra Cluster       |
 +---------------------------------+
                 |
        +--------v---------+
        | Kafka (Analytics) |
        +--------+---------+
                 |
          +------v-------+
          | Analytics DB |
          +--------------+
🧩
Components
API Gateway
Entry point for all client requests, routes encode and redirect calls
Why thisEnvoy proxy supports high throughput, low latency routing with TLS termination and rate limiting
Why notNginx lacks native service discovery and dynamic routing at this scale
Write Service
Handles URL encoding, custom alias validation, and writes to Cassandra
Why thisStateless microservice in Go for concurrency and low latency; integrates with Cassandra for scalable writes
Why notMonolithic app would limit independent scaling and increase deployment risk
Read Service
Handles redirect requests by fetching original URL from Cassandra and returning HTTP 301
Why thisStateless service optimized for high QPS reads with Redis caching layer for hot keys
Why notDirect DB queries without caching cause high latency and overload Cassandra
Cassandra Cluster
Primary storage for URL mappings and metadata with high write and read throughput
Why thisCassandra's wide-column model supports high write QPS with tunable consistency and linear scalability
Why notPostgreSQL requires complex manual sharding at 1.8M writes/sec; B-tree writes don't scale linearly
Redis Cache
Caches frequently accessed short URL to long URL mappings to reduce DB load and latency
Why thisRedis TTL natively expires stale entries without cron jobs - sub-millisecond lookup for redirects
Why notMemcached lacks persistence and TTL management, increasing cache misses
Kafka (Analytics)
Asynchronous event streaming platform to collect click and usage analytics from redirect service
Why thisKafka supports high throughput, durable, ordered event streams with consumer groups for analytics processing
Why notRabbitMQ does not scale as well for high volume event streams and lacks strong ordering guarantees
Analytics DB
Stores aggregated analytics data for reporting and dashboard queries
Why thisClickHouse supports fast OLAP queries on large datasets with columnar storage and compression
Why notRelational DBs like MySQL are inefficient for large-scale analytics queries
🔄
Data Flow
1
Client UI → API Gateway
Send encode or redirect request
API Gateway routes based on request type
2
API Gateway → Write Service
Forward encode or custom alias request
Write Service validates and generates short URL
3
Write Service → Cassandra Cluster
Store short URL → long URL mapping
Use partition key on short URL for even data distribution
4
Client UI → API Gateway
Send redirect request with short URL
API Gateway routes to Read Service
5
Read Service → Redis Cache
Lookup short URL mapping
Cache hit returns original URL immediately
6
Read Service → Cassandra Cluster
Query original URL if cache miss
Populate Redis cache after DB fetch for future requests
7
Read Service → Client UI
Redirect user with HTTP 301 to original URL
Low latency redirect response
8
Read Service → Kafka (Analytics)
Send click event asynchronously
Analytics events streamed for processing
9
Kafka (Analytics) → Analytics DB
Consume and aggregate click events
Batch processing for analytics reporting

Practice

(1/5)
1. In a system using a Bloom filter to check key existence before disk read, at step 4 the Bloom filter component returns false positive for a key. What happens next?
easy
A. The system retries the Bloom filter check with a different hash function
B. The system performs a disk lookup to confirm key presence despite the Bloom filter result
C. The system immediately returns a key-not-found error without disk access
D. The system updates the Bloom filter to remove the false positive

Solution

  1. Step 1: Understand Bloom filter false positives

    Bloom filters can yield false positives, meaning they may indicate a key exists when it does not.

  2. Step 2: Trace system behavior at step 4

    Upon a positive Bloom filter result, the system must verify by disk lookup; however, the question states a false positive, so the system retries with a different hash function to reduce false positives before disk access.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    False positives trigger retries with alternate hashes before disk read [check]
Hint: False positive? Retry with different hash [check]
Common Mistakes:
2. A distributed messaging system processes millions of events per second. Some messages fail processing due to transient errors and must be retried without blocking the main queue. Which component best handles isolating these failed messages for later inspection and retry?
easy
A. A Dead Letter Queue (DLQ) configured to capture failed messages separately
B. A cache layer like Redis to temporarily store failed messages for retry
C. A high-throughput relational database with retry logic in application code
D. A load balancer that redirects failed messages to a backup server

Solution

  1. Step 1: Identify the role of Dead Letter Queues

    DLQs isolate failed messages from the main queue, enabling retries without blocking normal processing.

  2. Step 2: Evaluate alternatives

    Relational DBs (A) add latency and complexity; Redis (C) lacks durability guarantees; load balancers (D) do not handle message state or retries.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    DLQ isolates failures for retry without blocking main queue [check]
Hint: Dead Letter Queues isolate failures, not caches or DBs [OK]
Common Mistakes:
3. A messaging system must handle 925K message writes per second and fan-out delivery to millions of users with minimal latency. Which component best decouples message ingestion from fan-out delivery to ensure durability and scalability?
easy
A. Use a relational database with row-level locking for message storage and fan-out
B. Use HTTP polling from clients to fetch new messages periodically
C. Use Redis pub/sub for message delivery to all subscribers
D. Use a distributed log system like Kafka partitioned by conversation ID

Solution

  1. Step 1: Identify Kafka's role in decoupling ingestion and delivery

    Kafka partitions by conversation ID to guarantee ordering and durability, allowing high write throughput and asynchronous fan-out.

  2. Step 2: Eliminate other options

    Relational DB with locking can't handle high write concurrency; Redis pub/sub lacks durability and persistence; HTTP polling adds latency and load.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka partitions -> durable, ordered, scalable message ingestion [check]
Hint: Kafka partitions ensure durable, ordered, scalable ingestion [OK]
Common Mistakes:
4. In the message delivery trace, at Step 4 the Delivery Worker checks Bob's presence TTL in the presence service cache. What happens if Bob's presence TTL has expired at this step?
easy
A. The Delivery Worker queues the message for offline storage and does not send over WebSocket
B. The Delivery Worker immediately marks the message as delivered without sending
C. The Delivery Worker retries presence check indefinitely before sending
D. The Delivery Worker sends the message over WebSocket regardless of presence TTL

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- Bob's presence TTL

    If Bob's presence TTL expired, Delivery Worker treats Bob as offline and queues message for offline storage.

  2. Step 2: Eliminate other options

    Marking delivered without sending is incorrect; retrying indefinitely blocks delivery; sending regardless ignores offline status.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired presence TTL -> queue for offline delivery [check]
Hint: Expired presence TTL means offline -> queue message [check]
Common Mistakes:
5. In the DNS resolution chain, at step 4 the recursive DNS server receives a referral response from the root server pointing to a TLD server. What state does the recursive server enter immediately after receiving this referral?
easy
A. It caches the referral to the TLD server and initiates a query to the TLD server
B. It discards the referral and retries querying the root server
C. It caches the IP address of the root server and returns it to the client
D. It forwards the referral directly to the client without caching

Solution

  1. Step 1: Understand recursive server behavior on referral

    When the recursive DNS server receives a referral from the root server, it caches the referral information (the TLD server's IP) and then queries the TLD server itself.

  2. Step 2: Eliminate incorrect states

    It does not cache the root server IP (already known), nor does it discard the referral or forward it directly to the client. The recursive server handles the full resolution chain transparently.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Recursive server caches referral and queries next server [check]
Hint: Recursive server caches referrals and queries next hop [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard