Design a URL Shortening Service

## System Design: URL Shortening Service ### A. High-Level Architecture The system will consist of the following major components: 1. **Load Balancers (LBs):** Distribute incoming traffic (both API requests for shortening and redirection requests) across multiple API servers. We'll use multiple layers of LBs, starting with a global LB (e.g., AWS Route 53) for DNS-based routing and then regional LBs (e.g., AWS ELB/ALB) for distributing traffic within a region. 2. **API Servers (Web Servers):** Handle incoming requests for both creating short URLs (POST /shorten) and redirecting short URLs (GET /{short_code}). These servers will be stateless. 3. **URL Shortening Service (Business Logic):** A microservice responsible for generating short codes, interacting with the database, and potentially caching. 4. **Database:** Stores the mapping between short codes and original URLs. We'll discuss the choice in detail in section C. 5. **Cache:** Stores frequently accessed short URL mappings to reduce database load and latency for redirects. Redis or Memcached will be used. 6. **Message Queue (Optional but recommended for scale):** For asynchronous processing of tasks like updating analytics or handling potential retries, though not strictly necessary for core functionality. **Request Flow:** * **URL Creation (POST /shorten):** 1. Client sends a POST request with the original URL to the API Gateway/Load Balancer. 2. The LB forwards the request to an available API Server. 3. The API Server calls the URL Shortening Service. 4. The URL Shortening Service generates a unique short code (see section B). 5. The service stores the mapping (short_code -> original_url) in the Database. 6. The service might also write the mapping to the Cache. 7. The API Server returns the shortened URL (e.g., `https://short.url/{short_code}`) to the client. * **URL Redirection (GET /{short_code}):** 1. User enters a shortened URL in their browser. 2. The request hits the Load Balancer. 3. The LB forwards the request to an available API Server. 4. The API Server (or a dedicated Redirect Service) first checks the Cache for the `short_code`. 5. **Cache Hit:** If found, the original URL is retrieved from the cache, and the API Server issues an HTTP 301 (Permanent Redirect) or 302 (Temporary Redirect) response to the client with the original URL. 6. **Cache Miss:** If not found in the cache, the API Server queries the Database for the `short_code`. 7. The Database returns the original URL. 8. The API Server adds the mapping to the Cache for future requests. 9. The API Server issues the HTTP redirect response. ### B. Short URL Generation Strategy We need a strategy that generates unique, short, and preferably somewhat random-looking codes. The primary goal is uniqueness and efficiency. * **Hashing (e.g., MD5, SHA-1):** * *Pros:* Deterministic, can generate unique codes. Can be truncated. * *Cons:* Collisions are possible (though rare with good hashing and truncation). Codes might not be uniformly distributed, leading to hot spots. Not easily human-readable or memorable. * **Counter-Based (e.g., Auto-incrementing ID):** * *Pros:* Guarantees uniqueness. Simple to implement. * *Cons:* Centralized counter can become a bottleneck. Sequential IDs are predictable and can reveal usage patterns. Requires a distributed counter system for high availability and scale. * **Pre-generated Key Pools:** * *Pros:* Distributes the generation load. Can pre-generate a large pool of unique codes. * *Cons:* Requires managing the pool, ensuring no overlap, and potentially pre-generating a massive number of keys. * **Base-62/Base-64 Encoding of a Counter:** * *Pros:* Generates short, unique codes by encoding a monotonically increasing counter (e.g., a 64-bit integer) into a base-62 (0-9, a-z, A-Z) or base-64 alphabet. This is efficient and produces relatively short strings. Guarantees uniqueness if the counter is managed properly. * *Cons:* Requires a distributed counter service to avoid bottlenecks and ensure uniqueness across multiple API servers. **Chosen Strategy: Base-62 Encoding of a Distributed Counter** This approach offers the best balance of uniqueness, shortness, and scalability. We'll use a distributed ID generation service (like Twitter's Snowflake or Apache ZooKeeper) to generate unique, sequential 64-bit IDs. Each ID will then be encoded into a base-62 string. This provides short, unique codes. The sequential nature of IDs can be managed to avoid predictable patterns by using a random component in the ID generation or by shuffling the mapping later. ### C. Data Storage **Database Technology:** A NoSQL database like **Cassandra** or **ScyllaDB** (a high-performance Cassandra-compatible database) is a strong candidate due to its distributed nature, high availability, and excellent write performance, which is crucial for URL creation. Alternatively, a sharded relational database (like PostgreSQL with Citus or MySQL with Vitess) could work, but NoSQL often simplifies scaling for this type of key-value lookup. Let's assume **Cassandra** for its linear scalability and fault tolerance. **Schema:** We'll use a simple schema in a keyspace optimized for reads: ```cql CREATE TABLE url_mappings ( short_code text PRIMARY KEY, original_url text, created_at timestamp ); ``` * `short_code`: The unique short code generated (e.g., `aBcDeF`). This is the primary key. * `original_url`: The long URL to redirect to. * `created_at`: Timestamp for when the URL was shortened. **Storage Requirements Estimation (over 5 years):** * **New URLs per month:** 100 million * **Total URLs over 5 years:** 100 million/month * 12 months/year * 5 years = 6 billion URLs * **Average short code length:** Base-62 encoding of a 64-bit integer results in ~11 characters. Let's assume 15 bytes for the `short_code` (including overhead). * **Average original URL length:** Let's assume 2000 bytes (URLs can be very long). * **Overhead:** Assume 10% overhead for database storage (replication, indexes, etc.). **Total Storage:** (6 billion URLs) * (15 bytes/short_code + 2000 bytes/original_url) * 1.10 (overhead) = 6 * 10^9 * 2015 bytes * 1.10 ≈ 13.3 * 10^12 bytes ≈ 13.3 Terabytes (TB) This is a manageable amount for a distributed NoSQL database like Cassandra, which can scale horizontally by adding more nodes. **Why Cassandra?** * **Scalability:** Scales linearly by adding more nodes, handling massive amounts of data and traffic. * **Availability:** Designed for high availability with no single point of failure. Data is replicated across multiple nodes and data centers. * **Write Performance:** Excellent write throughput, crucial for the URL creation part. * **Read Performance:** Can be optimized for fast key-value lookups, which is what redirection requires. ### D. Scaling Strategy **1. Caching Strategy:** * **Level 1 Cache (Distributed Cache):** Use Redis or Memcached cluster. Store `short_code -> original_url` mappings. This will serve the vast majority of read requests (99% of traffic, given the 100:1 read-to-write ratio). * **Cache Invalidation/Expiration:** For simplicity and given the 5-year lifespan, we can use a Time-To-Live (TTL) slightly longer than the expected access pattern, or simply rely on the fact that once a short URL is created, its mapping rarely changes. A common strategy is to cache indefinitely until the application restarts or a manual invalidation is triggered (though this is less common for URL shorteners). * **Cache Population:** When a redirect request misses the cache, the original URL is fetched from the database, and then written into the cache before returning the redirect. **2. Database Partitioning/Sharding:** * **Cassandra:** Cassandra handles partitioning automatically based on the primary key (`short_code`). Data is distributed across nodes using a consistent hashing algorithm. This inherently shards the data. * **Relational DB (if chosen):** Shard the database based on the `short_code` (e.g., using a hash of the `short_code` to determine the shard). This distributes the load and data across multiple database instances. **3. Handling Hot Keys (Viral URLs):** * **Caching:** The primary defense against hot keys is aggressive caching. A viral URL will be heavily cached in Redis/Memcached, meaning subsequent requests will be served directly from memory, bypassing the database entirely. * **Database Read Replicas (if using RDBMS):** If the database becomes a bottleneck even with caching, read replicas can be employed, though Cassandra's distributed nature already handles this well. * **Content Delivery Network (CDN):** For extremely high traffic, the redirect responses themselves could potentially be cached at the edge using a CDN, though this adds complexity and might not be suitable for all redirect types (e.g., 302). However, the API servers themselves could be placed behind a CDN for faster global access. * **Dedicated Read Path:** For extreme cases, a separate read-optimized data store or cache layer could be considered, but the primary cache should handle most hot key scenarios. ### E. Reliability and Fault Tolerance **1. High Availability (99.9% Uptime):** * **Redundancy:** Deploy multiple instances of each component (API servers, cache nodes, database nodes) across multiple Availability Zones (AZs) or even regions. * **Load Balancers:** LBs will automatically route traffic away from unhealthy instances. * **Stateless API Servers:** API servers are stateless, so any server can handle any request. If one fails, others take over seamlessly. * **Database Replication:** Cassandra provides built-in data replication. We'll configure a replication factor (e.g., 3) across different nodes and racks/AZs. If a node fails, replicas on other nodes serve the data. * **Cache Replication/Clustering:** Redis Sentinel or Redis Cluster can provide high availability for the cache. **2. Component Failure Handling:** * **API Server Failure:** LBs detect failure and stop sending traffic to the unhealthy instance. Other instances continue to serve requests. * **Cache Node Failure:** If using Redis Cluster or Sentinel, the system automatically promotes a replica or reconfigures the cluster. If a single node fails, some cached data might be temporarily unavailable, but the system will fall back to the database. * **Database Node Failure:** Cassandra automatically handles node failures. Data is available from replicas on other nodes. If a whole AZ fails, data is still available from nodes in other AZs (if multi-AZ deployment). **3. Data Replication and Failover:** * **Database:** Cassandra's replication strategy ensures data durability and availability. We'll use a replication factor of 3, with replicas spread across different physical locations (racks/AZs). If a node fails, reads and writes can still be served by other replicas. * **Cache:** Redis Sentinel or Cluster provides automatic failover for cache nodes. * **Application Level:** Implement retry mechanisms for transient network issues when communicating between services. ### F. Key Trade-offs 1. **Consistency vs. Availability (CAP Theorem):** * **Choice:** We prioritize **Availability** and **Partition Tolerance** over strong Consistency for the redirect service. For URL creation, we need strong consistency to ensure unique short codes. For redirection, if a database replica is temporarily unavailable, we'd rather serve a stale entry from cache or return an error than block requests. * **Justification:** The core function of a URL shortener is to redirect users quickly and reliably. Occasional stale cache entries or temporary unavailability of a specific short URL mapping (which would be rare with proper replication) is more acceptable than widespread service outages. For URL creation, a distributed ID generator with strong consistency guarantees is used to ensure uniqueness. 2. **Latency vs. Cost/Complexity (Caching Strategy):** * **Choice:** We chose an aggressive, multi-layered caching strategy (in-memory cache like Redis/Memcached) to achieve the sub-50ms latency requirement for redirects. * **Justification:** The 100:1 read-to-write ratio and the strict latency requirement (99.9% uptime, <50ms latency at 95th percentile) make caching essential. Serving most requests directly from RAM significantly reduces database load and response times. While caching adds complexity (cache invalidation, consistency concerns, additional infrastructure cost), it's a necessary trade-off to meet the performance and availability goals. Without it, the database would be overwhelmed by read traffic, leading to higher latency and potential outages.

A) High-level architecture Components 1) Edge - DNS + CDN/Anycast edge (optional but strongly recommended for <50ms p95 globally) - WAF + DDoS protection - Global load balancers (GSLB) routing to nearest region 2) Regional stack (at least 2 regions, active-active) - L7 load balancer (ALB/Envoy) - Stateless API service (URL Shortener) - Create API (write path) - Redirect API (read path) - Cache tier - L1 in-process cache (tiny, per instance, very hot keys) - L2 distributed cache (Redis/Memcached cluster) - Persistent storage - Primary KV store (DynamoDB/Cassandra/ScyllaDB-style) for short_code -> long_url mapping - Optional relational store (Postgres/MySQL) for analytics, user accounts, custom aliases (not in critical redirect path) - Async pipeline (non-critical) - Kafka/Kinesis/PubSub for click events, logs, abuse signals - Stream processors / OLAP sink (ClickHouse/BigQuery/S3) Request flow: URL creation (write) 1) Client calls POST /api/shorten with long_url (+ optional custom alias, TTL policy, user auth). 2) Request hits GSLB -> regional LB -> API server. 3) API validates URL (format, allow/deny lists, safe browsing), normalizes it, enforces rate limits. 4) Short code generation service allocates a unique code (details in section B). 5) API writes mapping to KV store (short_code as partition key). - Write includes created_at, expire_at (>=5 years), long_url, owner_id, flags. - Use quorum write (or strongly consistent write depending on store). 6) API populates L2 cache with short_code -> long_url (write-through) and returns short URL. 7) Emit asynchronous events (created, user, spam scoring) to stream; not required for success response. Request flow: URL redirection (read) 1) Browser requests GET /{code}. 2) Edge routes to nearest region; optional CDN can cache 301/302 responses if policy allows. 3) API server parses code. 4) Lookup order: a) L1 in-process cache b) L2 Redis/Memcached c) KV store (if cache miss) 5) If found and not expired/blocked: return HTTP 301/302 redirect with Location: long_url. - Cache fill on miss (set in L2; optionally L1). 6) Emit click event asynchronously (fire-and-forget). 7) If not found: 404 (optionally fallback to origin region if using regional isolation). Latency targets - L2 cache hit should dominate (sub-millisecond to a few ms within region). With edge routing + high cache hit rate, <50ms p95 is feasible. B) Short URL generation strategy Requirements - 100M new shortenings/month ~ 3.3M/day ~ ~38.6 writes/sec average (peaks higher). - Must generate unique, short, URL-safe codes with low collision risk and no coordination bottleneck. Options 1) Hash(long_url) - Pros: deterministic; dedup possible. - Cons: collisions require handling; reveals patterns; hard to support multiple identical long URLs for different users; changing normalization affects stability. 2) Central counter (autoincrement) + base62 encoding - Pros: compact; no collisions; simple. - Cons: single logical bottleneck unless sharded; sequential codes are guessable (security/abuse). 3) Distributed ID (Snowflake-like: time + worker + sequence) then base62 - Pros: no central coordinator; scalable; unique; bounded size. - Cons: slightly longer codes; time-based ordering leaks some info. 4) Pre-generated key pool - Pros: fastest allocation; decouples creation from ID generation. - Cons: requires managing pool, storage, and avoiding reuse; operational complexity. Chosen approach - Use a Snowflake-style 64-bit unique ID generated by each API node (or dedicated ID service) and encode to base62/base64url. - 64 bits in base62 yields up to 11 characters worst-case; typically 10–11 chars, acceptable. - If shorter codes are required, use 56–60 bits (still plenty) with careful epoch/time window and worker bits. - To reduce predictability, optionally apply a reversible permutation (e.g., Feistel network) to the 64-bit ID before base62 encoding; keeps uniqueness but makes codes non-sequential. Why this choice - Eliminates single counter bottleneck. - No collision handling needed. - Works well with multi-region active-active. - Predictability mitigated via permutation. Custom aliases - If user requests custom code, validate availability with a conditional write (put-if-absent) in KV store; if conflict, reject. C) Data storage Database choice - Primary store: a highly available, horizontally scalable KV database (DynamoDB or Cassandra/ScyllaDB). - Reasoning: - Access pattern is key-based reads by short_code. - Read-heavy at high QPS; KV stores excel at low-latency point lookups. - Built-in replication, partitioning, and operational maturity. Schema (single table) Table: url_mapping - Partition key: short_code (string) - Attributes: - long_url (string) - created_at (timestamp) - expire_at (timestamp, must be >= created_at + 5 years; can be null for “never”, but requirement says at least 5 years) - owner_id (string, optional) - status (active/disabled/malicious) - meta (optional: title, campaign, etc.) Indexes (optional) - GSI/secondary index on owner_id + created_at for listing user links (not on redirect path). Storage estimation (5 years) - New URLs: 100M/month * 12 * 5 = 6 billion mappings. - Per record size rough estimate: - short_code: 10–11 bytes (store as ~16 bytes with overhead) - long_url: assume average 100 bytes (could be 50–200; use 120 including overhead) - timestamps/status/owner_id: ~40 bytes average (owner_id optional) - DB overhead (keys, replication metadata, compression): varies; assume ~100 bytes overhead - Total logical per item ~250 bytes (conservative) - Raw logical storage: 6e9 * 250B = 1.5 TB. - With replication factor 3 (common in Cassandra/Scylla): ~4.5 TB. - Add indexes + headroom: plan ~6–10 TB across the cluster over 5 years. Notes - Long URLs can be compressed (dictionary/deflate) at application layer to reduce size; but only if it doesn’t add latency. Many KV stores also compress SSTables. D) Scaling strategy Traffic estimation - Writes: ~38.6/s average; assume peak 10x => ~400/s. - Reads: 100:1 => average ~3,860 reads/s; peak potentially much higher (e.g., 50k–200k/s depending on usage spikes). Scaling reads 1) Caching - L1 in-process cache: tiny (e.g., 10k–100k entries) with short TTL (30–120s) to absorb micro-hotspots and reduce Redis QPS. - L2 Redis/Memcached: - Cache value: long_url + status + expire_at. - TTL strategy: - If links are immutable (common), set long TTL (hours to days). - Still respect expire_at by setting TTL = min(configured_max_ttl, expire_at - now). - Use cache-aside with negative caching: - Cache “not found” for a short TTL (e.g., 30–60s) to reduce DB hits from scanners. - Aim for >95–99% cache hit rate for redirects. 2) CDN caching (optional but powerful) - For 301 redirects that are stable, CDN can cache the redirect response for popular codes. - Must consider ability to disable links quickly; mitigate by: - Short CDN TTL (e.g., 60–300s) + purge on disable - Or keep redirect logic at origin but cache mapping at edge KV (advanced). Database partitioning/sharding - Partition by short_code (consistent hashing / token ring). - Even distribution expected because codes are pseudo-random (post-permutation). - Add nodes to scale linearly. Handling hot keys (viral URLs) - Multi-layer approach: 1) Edge/CDN caches the redirect response for hottest keys with short TTL. 2) L1 + L2 caches reduce origin DB load. 3) Redis cluster scaling: shard by key; enable client-side hashing. 4) Request coalescing / single-flight on cache miss: if many requests miss simultaneously for same key, one request populates cache while others wait briefly. 5) For extreme cases, allow “hot key replication” in cache (store same key in multiple shards) or use a dedicated “hot cache” tier. Write scaling - Writes are modest; ensure conditional writes for uniqueness and idempotency. - Use rate limiting and abuse prevention to avoid write amplification from bots. E) Reliability and fault tolerance (99.9% uptime) Multi-region - Active-active in at least 2 regions. - GSLB health checks route traffic away from unhealthy region. Stateless services - API servers are stateless; scale horizontally; deploy across multiple AZs. Cache tier - Redis/Memcached deployed as a sharded cluster with replicas per shard (or Redis Cluster with replicas). - If cache fails: system falls back to DB; increased latency but still functional. - Protect DB with circuit breakers and adaptive rate limiting if cache outage causes thundering herd. Database replication and failover - DynamoDB option: - Use Global Tables for multi-region active-active replication. - Configure on-demand or provisioned capacity with autoscaling. - Cassandra/Scylla option: - Multi-AZ replication within region (RF=3). - Multi-region replication via NetworkTopologyStrategy; tune consistency (e.g., LOCAL_QUORUM for reads/writes) to keep latency low. - Failure modes: - Single node failure: replica reads/writes continue. - AZ failure: remaining AZs serve traffic (RF across AZs). - Region failure: GSLB shifts to healthy region; data available via replicated store. Data durability - Regular backups/snapshots to object storage (S3/GCS) + point-in-time recovery. - Disaster recovery drills and restore testing. Deployment safety - Rolling deployments + canary releases. - Feature flags. - Automated rollback on error budget burn. Operational controls - SLIs: redirect p95 latency, cache hit rate, DB p95, error rate, replication lag. - SLO: 99.9% availability; design for graceful degradation (e.g., temporarily disable analytics writes). F) Key trade-offs 1) Shortness of code vs distributed generation - Trade-off: A centralized counter can yield very short codes (often 6–8 chars early on), but adds coordination and is harder in multi-region. - Choice: distributed Snowflake-like IDs + base62 (10–11 chars) to ensure scalability, uniqueness, and multi-region compatibility while meeting latency/availability requirements. 2) Strong consistency vs low latency/high availability - Trade-off: Strongly consistent global reads increase latency and reduce availability during partitions. - Choice: use local-quorum/region-local consistency for redirect lookups (fast) with multi-region replication. For create operations, ensure uniqueness with conditional writes and accept eventual cross-region propagation; redirects remain correct because the authoritative mapping exists in at least one region and is quickly replicated. 3) Aggressive caching vs rapid disable/abuse response - Trade-off: Long cache TTLs improve latency and reduce DB load, but make it harder to immediately disable malicious links. - Choice: moderate TTLs + purge mechanisms, plus status checks in cached value and short TTL for CDN; allow “kill switch” by caching disabled status with high priority. Summary - Use edge routing + heavy caching to keep redirects under 50ms p95. - Use distributed unique ID generation (Snowflake + permutation) for scalable code generation. - Store mappings in a replicated KV store with sharding by short_code and multi-region failover. - Maintain 99.9% uptime via multi-AZ + multi-region, stateless services, replicated storage, and graceful degradation paths.