Design a Global URL Shortening Service

1. High-Level Architecture and Request Flows: **Main Components:** * **API Gateway/Load Balancers:** Entry point for all user requests, handles routing, authentication, and rate limiting. * **Shorten Service:** Microservice responsible for creating, updating, and deleting short links. Handles custom alias validation and expiration logic. * **Redirect Service:** Microservice optimized for high-throughput, low-latency redirection. Records click events. * **Distributed Cache (e.g., Redis Cluster):** Primary storage for `short_code` to `long_url` mappings to serve redirects with minimal latency. * **Distributed SQL Database (e.g., CockroachDB, Google Spanner):** Stores the authoritative source of truth for all link metadata, ensuring global uniqueness and strong consistency. * **Message Queue (e.g., Apache Kafka):** Ingests high-volume click events from the Redirect Service, decoupling it from analytics processing. * **Analytics Processor (e.g., Apache Flink/Spark Streaming):** Consumes click events from the Message Queue, performs real-time aggregation, and stores data. * **Data Warehouse (e.g., ClickHouse, Snowflake, BigQuery):** Stores raw and aggregated analytics data for reporting and analysis. * **CDN (e.g., Cloudflare, Akamai):** Distributes static assets, provides global DNS resolution, and can offer geo-routing to the nearest data center. **Request Flows:** * **Short Link Creation:** 1. User/Client sends a request to the API Gateway. 2. API Gateway routes to a Load Balancer, then to the Shorten Service. 3. Shorten Service generates a unique `short_code` (or validates a custom alias). 4. It stores the `short_code`, `long_url`, `expires_at`, and other metadata in the Distributed SQL Database. 5. It pushes the new `short_code` -> `long_url` mapping to the Distributed Cache. 6. Shorten Service returns the `short_code` to the user. * **Short Link Redirection:** 1. User/Client accesses a short URL, which is routed via CDN/GeoDNS to the nearest data center's Load Balancer. 2. Load Balancer directs to the Redirect Service. 3. Redirect Service first checks the Distributed Cache for the `short_code` -> `long_url` mapping. 4. *Cache Hit:* If found and active, it immediately issues an HTTP 301/302 redirect to the `long_url`. 5. *Cache Miss:* If not found, it queries the Distributed SQL Database. If found and active, it populates the cache and then redirects. If not found, expired, or deleted, it returns a 404 error. 6. Asynchronously, the Redirect Service publishes a click event (containing `short_code`, `timestamp`, `country`, `device_type`, `referrer_domain`) to the Message Queue. * **Analytics Processing:** 1. Analytics Processor consumes click events from the Message Queue. 2. It performs real-time processing (e.g., aggregation, enrichment). 3. Raw and aggregated data are stored in the Data Warehouse for reporting. 2. Data Model and Storage Choices: * **Links & Aliases (Distributed SQL Database - CockroachDB/Google Spanner):** * **`links` table:** * `short_code` (VARCHAR, Primary Key): The unique short identifier. * `long_url` (VARCHAR): The original URL (up to 500 bytes). * `user_id` (UUID, Indexed, FK): Optional, for link ownership. * `created_at` (TIMESTAMP): When the link was created. * `expires_at` (TIMESTAMP, Nullable, Indexed): When the link should expire. * `status` (ENUM: 'active', 'expired', 'deleted', Indexed): Current state of the link. * `is_custom_alias` (BOOLEAN): True if it's a user-defined alias. * `click_count` (BIGINT): Denormalized, eventually consistent count of clicks (updated by analytics). * *Justification:* Chosen for strong consistency guarantees (critical for `short_code` and `custom_alias` uniqueness globally), ACID properties, and native multi-region replication capabilities. This simplifies global data management and ensures data integrity. * **Analytics Events (Message Queue - Apache Kafka, Data Warehouse - ClickHouse/Snowflake):** * **Kafka Topic (`click_events`):** Stores raw click event messages (e.g., JSON/Protobuf). * **Data Warehouse (`raw_clicks` table):** * `event_id` (UUID, Primary Key) * `short_code` (VARCHAR, Indexed) * `timestamp` (TIMESTAMP, Indexed) * `country` (VARCHAR, Indexed) * `device_type` (VARCHAR) * `referrer_domain` (VARCHAR) * **Data Warehouse (`aggregated_clicks` table):** (e.g., hourly/daily aggregates) * `short_code` (VARCHAR, PK) * `aggregation_time` (TIMESTAMP, PK) * `country` (VARCHAR, PK) * `total_clicks` (BIGINT) * *Justification:* Kafka provides high-throughput, fault-tolerant ingestion and decoupling. ClickHouse/Snowflake are optimized for analytical queries over massive datasets, supporting the eventual consistency requirement for analytics. 3. Scaling Strategy for Read-Heavy Traffic: * **Distributed Cache (Redis Cluster):** This is the primary scaling layer for redirects. It will store `short_code` to `long_url` mappings in memory, handling the vast majority of 4 billion daily redirects. Redis Cluster offers horizontal scaling and high availability through sharding and replication. * **Global CDN and Geo-Routing:** A CDN (e.g., Cloudflare) will serve static assets and provide intelligent DNS-based routing (GeoDNS) to direct users to the geographically closest data center, minimizing redirect latency. * **Stateless Services:** Both Shorten and Redirect services are designed to be stateless, allowing for easy horizontal scaling by adding more instances behind load balancers in each region. Auto-scaling groups will dynamically adjust capacity based on traffic. * **Database Read Replicas/Distributed Reads:** The Distributed SQL Database will inherently handle distributed reads across its nodes. If cache hit rates are lower than expected, or for less popular links, the database's ability to scale reads across its cluster will be crucial. * **Short Code Generation:** For high-volume link creation, short codes can be pre-generated in batches and stored, or a distributed ID generation service (e.g., inspired by Twitter Snowflake) can be used to ensure unique, non-sequential codes, preventing database hotspots. 4. Reliability Strategy: * **Failover:** * **Multi-Region Deployment:** All critical services (Shorten, Redirect, Database, Cache, Message Queue) are deployed in an active-active configuration across at least three geographically distinct regions (e.g., North America, Europe, Asia). * **Service-Level Failover:** Services are deployed in auto-scaling groups across multiple Availability Zones within each region. Load balancers automatically detect and route traffic away from unhealthy instances. * **Database Failover:** The Distributed SQL Database provides built-in multi-region replication and automatic failover mechanisms (e.g., Raft consensus in CockroachDB) to ensure continuous operation even if nodes or entire zones fail. * **Cache Failover:** Redis Cluster provides replication for data redundancy and automatic failover of master nodes. * **Message Queue Failover:** Kafka clusters are deployed with replication (e.g., 3 brokers, replication factor 3) across multiple Availability Zones to tolerate broker failures. * **Consistency Decisions:** * **Strong Consistency (Link Creation/Aliases):** The Distributed SQL Database ensures strong consistency for `short_code` and `custom_alias` uniqueness. This is critical to prevent collisions and maintain data integrity. * **Eventual Consistency (Redirects):** The Distributed Cache operates with eventual consistency. When a link is created, updated (e.g., `expires_at` changes), or deleted, an event is published to a cache invalidation topic (e.g., Kafka). Cache nodes subscribe to this topic and invalidate/update their entries. A short TTL (e.g., 1-5 minutes) on cache entries acts as a fallback to prevent indefinite staleness. * **Eventual Consistency (Analytics):** Analytics data is eventually consistent within 5 minutes, handled by the asynchronous Message Queue and stream processing. This prioritizes redirect performance over immediate analytics updates. * **Handling Regional Outages:** * **Global Load Balancing/DNS:** Intelligent DNS services (e.g., GeoDNS) and global load balancers automatically detect regional failures and reroute traffic to healthy, active regions. * **Data Replication:** The Distributed SQL Database replicates all link data across active regions. If one region becomes unavailable, other regions can continue to serve requests with minimal data loss and latency impact. * **Graceful Degradation:** If the Analytics Service or Message Queue experiences issues, the Redirect Service is designed to continue functioning by buffering events locally or, in extreme cases, dropping them, prioritizing the core redirect functionality. 5. Key Trade-offs, Bottlenecks, and Risks: * **Key Trade-offs:** * **Consistency vs. Latency:** Strong consistency for link creation (via Distributed SQL) ensures data integrity but might incur slightly higher write latency. For redirects, eventual consistency via a highly optimized cache is chosen to achieve sub-80ms latency. * **Cache Size vs. Cost:** Extensive caching is vital for redirect performance but requires significant memory resources, leading to higher infrastructure costs. A balance must be struck between cache hit ratio and operational expense. * **Short Code Length vs. Namespace Size:** Shorter codes are more user-friendly but increase the probability of collisions and limit the total number of unique links. A 7-10 character base62 code provides a vast, practical namespace. * **Bottlenecks:** * **Distributed Cache Capacity:** If the cache cannot handle the peak read throughput or if the active working set of links exceeds its memory capacity, redirects will fall back to the database, increasing latency and database load. * **Database Write Throughput:** While link creation is lower volume than redirects, 120 million links/day is substantial. The Distributed SQL Database must be able to handle this write load across regions without becoming a bottleneck. * **Network Latency between Regions:** Cross-region data replication and consistency checks, especially for write operations in a globally distributed system, can introduce inherent latency. * **Risks & Mitigations:** * **Risk 1: Short Code Collisions (especially for random generation):** * *Mitigation:* Use a sufficiently long `short_code` (e.g., 7-10 characters using base62: a-z, A-Z, 0-9). Implement a robust generation strategy: pre-generate a large pool of unique codes, use a distributed ID generator (e.g., Snowflake-like) to generate unique IDs then convert to base62, or for custom aliases, perform a direct uniqueness check in the database with optimistic locking and retries. * **Risk 2: Cache Staleness for Expired/Deleted Links:** * *Mitigation:* Implement a real-time cache invalidation mechanism. When a link's status changes (e.g., `expires_at` reached, `status` set to 'deleted'), the Shorten Service (or a dedicated background job) publishes an event to a Kafka topic. All Redirect Service instances and cache nodes subscribe to this topic and immediately invalidate the corresponding `short_code` entry. A short TTL (e.g., 1-5 minutes) on cache entries acts as a fallback. * **Risk 3: Database Hotspots due to uneven `short_code` distribution:** * *Mitigation:* For Distributed SQL databases, rely on their internal sharding and rebalancing capabilities. For custom aliases, the alias itself serves as the primary key, which should distribute well. For randomly generated short codes, ensure the generation algorithm produces sufficiently random codes to avoid sequential keys that could lead to hotspots. Monitor database partitions and rebalance as needed. 6. Capacity Estimate: * **Throughput:** * **Redirects:** 4 billion/day = ~46,300 requests/second (average), peak ~138,900 requests/second (3x average). * **Link Creation:** 120 million/day = ~1,389 requests/second (average), peak ~4,167 requests/second (3x average). * **Analytics Events Ingestion:** ~46,300 events/second (average), peak ~138,900 events/second. * **Storage:** * **Links Data (Distributed SQL Database):** * Average record size: ~100 bytes (short_code, long_url, timestamps, status, etc.). * Daily new links: 120 million * 100 bytes = 12 GB. * Total over 5 years: 12 GB/day * 365 days/year * 5 years = ~21.9 TB. * With 3x replication factor for high availability/multi-region: ~65.7 TB. * **Analytics Data (Data Warehouse):** * Average event size: ~100 bytes (short_code, timestamp, country, device, referrer). * Daily events: 4 billion * 100 bytes = 400 GB. * Total over 1 year retention: 400 GB/day * 365 days/year = ~146 TB. * With 3x replication factor: ~438 TB. * **Distributed Cache (Redis Cluster):** * Each cached entry: `short_code` (e.g., 10 bytes) + `long_url` (average 500 bytes) = ~510 bytes. * To cache 1 billion active links (a reasonable working set for popular links): 1 billion links * 510 bytes/link = 510 GB of cache memory. This is a significant but manageable size for a large, sharded Redis Cluster.

## Global URL Shortening Service - System Design ### 1. High-Level Architecture **Main Components:** - **API Gateway & Load Balancer**: Global entry point with regional routing (North America, Europe, Asia) - **Short Link Service**: Handles creation, validation, and alias management - **Redirect Service**: Optimized for high-throughput redirects with minimal latency - **Cache Layer**: Multi-tier caching (edge CDN, regional Redis, local in-memory) - **Primary Data Store**: Distributed SQL database (PostgreSQL with sharding) for link metadata - **Analytics Pipeline**: Event streaming (Kafka) → Stream processor (Flink/Spark) → Analytics DB (ClickHouse/Druid) - **CDN**: Global content delivery for redirect responses - **Message Queue**: For async operations (expiration, deletion, analytics) - **Monitoring & Observability**: Distributed tracing, metrics, alerting **Request Flows:** *Create Short Link:* 1. Client → API Gateway (regional) 2. Short Link Service validates input, generates short code or validates custom alias 3. Check alias uniqueness in distributed cache + primary DB 4. Write to primary DB (with replication) 5. Invalidate cache, publish event to Kafka 6. Return short link (p95 < 300ms) *Redirect (Read):* 1. Client → Nearest CDN edge location 2. CDN checks local cache; if miss, routes to regional cache (Redis) 3. Regional cache miss → Query primary DB with read replica 4. Response cached at CDN edge and regional Redis 5. Return 301/302 redirect (p95 < 80ms) 6. Async: publish click event to Kafka *Analytics:* 1. Click events → Kafka topic 2. Stream processor aggregates by link_id, country, device, referrer 3. Write aggregated metrics to analytics DB every 1-5 minutes 4. Dashboard queries analytics DB for reports --- ### 2. Data Model and Storage Choices **Link Metadata Table (Primary DB - PostgreSQL):** ``` links: - link_id (UUID, primary key) - short_code (VARCHAR(10), unique index) - long_url (TEXT, max 500 bytes) - user_id (UUID, indexed) - custom_alias (VARCHAR(100), unique global index, nullable) - created_at (TIMESTAMP) - expires_at (TIMESTAMP, nullable, indexed) - is_deleted (BOOLEAN, indexed) - is_custom (BOOLEAN) - created_region (VARCHAR(10)) - metadata (JSONB: title, description, tags) ``` **Analytics Events Table (Time-series DB - ClickHouse):** ``` click_events: - event_id (UUID) - link_id (UUID, indexed) - timestamp (DateTime) - country (VARCHAR(2)) - device_type (VARCHAR(20)) - referrer_domain (VARCHAR(255)) - user_agent (VARCHAR(500)) - ip_hash (VARCHAR(64)) ``` **Storage Choices Justification:** - **PostgreSQL (Primary)**: ACID guarantees for link creation, strong consistency for alias uniqueness, proven at scale with proper sharding - **Redis (Regional Cache)**: Sub-millisecond latency for hot links, supports TTL for automatic expiration, distributed across regions - **ClickHouse (Analytics)**: Optimized for time-series analytics, columnar storage reduces storage by 10-100x, fast aggregations - **CDN (Cloudflare/Akamai)**: Global edge caching, reduces latency to <80ms p95, offloads origin traffic - **Kafka (Event Stream)**: Decouples analytics from redirect path, enables replay, supports multiple consumers --- ### 3. Scaling Strategy for Read-Heavy Traffic **Caching Architecture (Multi-Tier):** 1. **Edge CDN Cache** (Tier 1): - Cache redirect responses globally - TTL: 24 hours for active links, 5 minutes for expired links - Cache key: short_code - Hit ratio target: 95%+ - Reduces origin traffic by 95% 2. **Regional Redis Cluster** (Tier 2): - 3 regions: us-east, eu-west, ap-southeast - Each region: Redis cluster with 6 nodes (3 primary, 3 replica) - Replication across availability zones - TTL: 1 hour for links, 5 minutes for expired links - Capacity: 500GB per region (hot links only) 3. **Local In-Memory Cache** (Tier 3): - Per-service instance LRU cache (100MB) - Reduces Redis round-trips for hottest 1% of links **Read Replica Strategy:** - Primary DB in us-east (write master) - Read replicas in eu-west, ap-southeast (async replication, ~100ms lag) - Route reads to nearest replica - Fallback to primary if replica unavailable **Horizontal Scaling:** - Redirect Service: Auto-scale to 1000+ instances across regions - Each instance handles ~4M redirects/day (4B / 1000) - Load balancer distributes based on latency and capacity **Short Code Generation:** - Base62 encoding (0-9, a-z, A-Z) for 6-character codes - 62^6 = 56 billion possible codes (sufficient for 120M/day for 400+ years) - Distributed ID generator (Snowflake-like) with region prefix to avoid collisions - Batch allocation: each service instance pre-allocates 10K codes --- ### 4. Reliability Strategy **Failover & High Availability:** - **Multi-region deployment**: Active-active in 3 regions - **Database replication**: PostgreSQL streaming replication with automatic failover (Patroni) - **Circuit breakers**: Prevent cascading failures when cache/DB unavailable - **Graceful degradation**: If analytics DB down, still serve redirects; queue events locally **Consistency Decisions:** - **Strong consistency for writes**: Link creation uses distributed locks (Redis/Zookeeper) for alias uniqueness - **Eventual consistency for reads**: Redirect responses may be stale by ~100ms (acceptable) - **Eventual consistency for analytics**: 5-minute window acceptable per requirements - **Expiration handling**: Lazy deletion (check expires_at on read) + background job (scan every hour) **Regional Outage Handling:** 1. **Detect outage**: Health checks fail for 30 seconds 2. **Failover**: Route traffic to other regions 3. **Write operations**: Redirect to primary region (us-east) with fallback to local region 4. **Read operations**: Use read replicas in other regions 5. **Recovery**: Sync data from primary when region recovers 6. **Monitoring**: Alert on region unavailability, track failover events **Specific Mitigations:** - **Database failure**: Patroni auto-failover to replica (RTO < 30s) - **Cache failure**: Bypass to DB with rate limiting to prevent thundering herd - **CDN failure**: Direct traffic to regional cache - **Network partition**: Assume partition heals; use quorum-based decisions - **Data corruption**: Point-in-time recovery from backups (daily snapshots) --- ### 5. Key Trade-offs, Bottlenecks, and Risks **Trade-offs:** 1. **Consistency vs. Latency**: Chose eventual consistency for analytics to keep redirect latency <80ms. Strong consistency for alias uniqueness adds ~50ms but necessary for correctness. 2. **Cache TTL vs. Freshness**: 24-hour CDN TTL reduces origin load but means expired links may redirect for up to 24 hours. Mitigated by 5-minute TTL for links marked deleted. 3. **Storage vs. Query Speed**: Denormalize analytics data (store country, device in events table) to enable fast aggregations, accepting 2-3x storage overhead. 4. **Regional Autonomy vs. Global Consistency**: Each region can serve reads independently but writes must coordinate for alias uniqueness, adding latency. **Bottlenecks:** 1. **Alias Uniqueness Check**: Global distributed lock required; can become contention point during peak writes. Mitigation: Use Redis with Lua scripts for atomic check-and-set; shard by first character of alias. 2. **Database Write Throughput**: 120M new links/day = ~1,400 writes/sec. PostgreSQL can handle ~10K writes/sec per instance, so need 1-2 primary instances. Mitigation: Batch writes, use connection pooling (PgBouncer). 3. **Analytics Pipeline**: 4B clicks/day = ~46K events/sec. Kafka can handle this, but aggregation may lag. Mitigation: Use stream processor (Flink) for real-time aggregation; write to analytics DB every 1 minute. **Three Major Risks & Mitigations:** **Risk 1: Cache Stampede on Popular Link Expiration** - *Scenario*: Viral link with 1M clicks/hour expires; all cache entries invalidate simultaneously; 1M requests hit DB - *Impact*: DB overload, redirect latency spikes to seconds, SLA breach - *Mitigation*: - Use probabilistic early expiration: refresh cache 5 minutes before actual expiration - Implement request coalescing: if multiple requests hit expired link, only first queries DB - Set max DB query rate with circuit breaker; return 404 if exceeded - Pre-warm cache for known expiring links **Risk 2: Distributed Alias Collision Under Network Partition** - *Scenario*: Network partition between regions; two users create same custom alias in different regions; partition heals; data conflict - *Impact*: Alias uniqueness violated; one link becomes unreachable; data inconsistency - *Mitigation*: - Use global distributed lock (Zookeeper/etcd) for alias writes; fail if lock unavailable - Implement conflict resolution: timestamp-based winner (earlier write wins) - Audit job: scan for duplicate aliases daily; alert on conflicts - Require alias writes to go through primary region only (accept higher latency) **Risk 3: Analytics Data Loss During Stream Processing Failure** - *Scenario*: Kafka consumer crashes; events not processed; analytics lag grows; memory fills; events dropped - *Impact*: Inaccurate click counts; business metrics unreliable; customer trust loss - *Mitigation*: - Use Kafka consumer groups with offset management; resume from last committed offset - Implement dead-letter queue for failed events; replay manually - Set memory limits on local event buffer; drop oldest events if full (with alerting) - Dual-write analytics: Kafka → Stream processor AND direct DB writes (with deduplication) - Monitor consumer lag; alert if lag > 5 minutes --- ### 6. Capacity Estimates **Storage:** *Link Metadata (PostgreSQL):* - 120M new links/day × 365 days = 43.8B links/year - Per link: 50 bytes (IDs, timestamps, flags) + 500 bytes (long URL) + 100 bytes (metadata) = 650 bytes - Year 1: 43.8B × 650B = 28.5 TB - With 3-year retention: 85.5 TB - With replication (3x): 256.5 TB - Sharded across 10 instances: 25.6 TB per instance (manageable) *Analytics Events (ClickHouse):* - 4B clicks/day × 365 days = 1.46T events/year - Per event: 50 bytes (IDs, timestamps) + 100 bytes (country, device, referrer) = 150 bytes - Year 1: 1.46T × 150B = 219 TB (uncompressed) - ClickHouse compression: 10-20x → 11-22 TB/year - 3-year retention: 33-66 TB (acceptable) *Cache (Redis):* - Hot links (1% of total): 438M links - Per link in cache: 50 bytes (short_code, long_url pointer) = 50 bytes - 438M × 50B = 22 GB per region - 3 regions: 66 GB total (fits in 500GB per region allocation) **Throughput:** *Write Throughput:* - 120M links/day ÷ 86,400 seconds = 1,389 writes/sec - PostgreSQL: 1 primary instance handles 10K writes/sec → 1 instance sufficient - Kafka: 1,389 events/sec → 1 partition sufficient (Kafka handles 100K+ msgs/sec per partition) *Read Throughput:* - 4B redirects/day ÷ 86,400 seconds = 46,296 reads/sec - Peak (3x): 138,888 reads/sec - CDN cache hit rate: 95% → 6,944 reads/sec to origin - Redis hit rate: 99% of misses → 70 reads/sec to DB - PostgreSQL: 1 read replica per region handles 10K reads/sec → 1 replica per region sufficient - Redirect Service instances: 46K reads/sec ÷ 100 reads/sec per instance = 460 instances (baseline); 1,389 instances at peak *Analytics Throughput:* - 4B clicks/day = 46,296 events/sec - Kafka: 1 topic, 10 partitions (parallelism) - Stream processor: 10 instances, each handles 4,630 events/sec - ClickHouse: Batch inserts every 1 minute; 46K events/min = manageable **Network Bandwidth:** *Redirect responses:* - 46K redirects/sec × 300 bytes (HTTP response) = 13.8 MB/sec - Peak: 41.4 MB/sec - CDN absorbs 95% → 2.1 MB/sec to origin at peak - Easily handled by 1 Gbps connection *Analytics events:* - 46K events/sec × 500 bytes = 23 MB/sec - Kafka cluster: 10 Gbps capacity → sufficient **Summary Table:** | Component | Capacity | Instances | Notes | |-----------|----------|-----------|-------| | PostgreSQL Primary | 10K writes/sec | 1 | Sharded for future growth | | PostgreSQL Read Replicas | 10K reads/sec | 3 (1 per region) | Async replication | | Redis Clusters | 100K ops/sec | 3 (1 per region) | 6 nodes each | | Redirect Service | 100 redirects/sec | 460 (baseline), 1,389 (peak) | Auto-scaling | | Kafka Brokers | 100K msgs/sec | 3 | Replication factor 3 | | Stream Processors | 4,630 events/sec | 10 | Flink/Spark | | ClickHouse Nodes | 1M inserts/sec | 3 | Distributed cluster | | CDN Edge Locations | Global | 200+ | Cloudflare/Akamai | --- ### Implementation Priorities 1. **Phase 1** (MVP): Single region, PostgreSQL + Redis + CDN, basic analytics 2. **Phase 2** (Scale): Multi-region, read replicas, Kafka analytics pipeline 3. **Phase 3** (Optimize): Distributed ID generation, advanced caching, ClickHouse analytics 4. **Phase 4** (Harden): Circuit breakers, chaos engineering, disaster recovery drills