Design a URL Shortening Service at Scale

High-level architecture (textual diagram and components) - Clients: web browsers, mobile apps. They access short URLs (short.example/abc1234) and the write API for creating short URLs. - CDN / Edge (CloudFront, Fastly): Edge layer that receives incoming short-URL requests. Edge will cache redirect responses (HTTP 301/302) and serve them without touching origin where possible to meet latency SLA. - Edge routing / Global DNS (Route53, anycast): Routes write API calls to nearest region and short-URL hits to the nearest edge/region. Health checks and failover are configured. - Regional API Gateway + Load Balancer (API Gateway / ALB): Accepts client writes and management calls. Routes to Write Services deployed in containers (ECS/Kubernetes) across availability zones. - Write Service (stateless microservice): Validates input, generates a short token via ID generator module, writes mapping into primary DB, publishes events to stream, updates caches, and returns short URL. - Read Path Services / Redirect Service (stateless): Receives cache misses from edge or direct hits, queries local cache (Redis cluster), falls back to DB, returns redirect with appropriate cache headers. - Distributed Cache (Redis clusters per region, clustered/replicated): Hot lookups stored here for microsecond responses. Each region has its own Redis cluster with replication across AZs. - Primary Storage (DynamoDB or Cassandra/Scylla alternative): Stores mapping short_id -> long_url, metadata, expiry, owner, creation_ts. Chosen for high read/write throughput, TTL support, and multi-region replication. - Event Stream (Kinesis / Kafka): All writes produce events for analytics, index updates, cache invalidation messages, and async processing. - Background Workers (containerized): Handle TTL cleanup, reclamation queue, analytics, and async replication checks. - Monitoring & Ops: Prometheus/Grafana, CloudWatch, alerting, automated runbooks. Component interactions (read): User hits short URL -> Edge cache checks for cached redirect -> if hit, return cached redirect (<5ms). If miss, Edge forwards to regional LB -> Redirect Service queries Redis cache -> if hit, return redirect and Edge caches; if miss, Redirect Service queries primary DB -> returns redirect -> Redis set and Edge caches redirect. Component interactions (write): Client calls API -> API Gateway -> Write Service -> ID generator produces token -> Write Service writes mapping into primary DB with TTL -> Write Service publishes event to stream -> Write Service writes to Redis cache and returns short URL. Background workers asynchronously replicate events to analytics and other regions where necessary. URL shortening algorithm and key generation strategy Goals: 7-character max alphanumeric token, non-guessable (no sequential tokens), low collision probability, reproducible failure/ retry behavior. Space and constraints: 62^7 ~= 3.52e12 possible tokens. Monthly new tokens target 100 million is tiny relative to space, but we must ensure no easy enumeration. Strategy chosen (primary): - Use cryptographically secure random generation per new short URL. Generate a 64-bit cryptographically secure random integer, apply rejection sampling to map into range [0, 62^7 - 1] without modulo bias, then base62-encode into exactly 7 characters. This yields uniformly random tokens across the 7-char space and no sequentiality. - Before committing, attempt an atomic insert into the DB with short_id as primary key and uniqueness enforced. If insert fails due to rare collision, retry with a new random token (expected collision probability negligible; expected retries << 1). Why not sequential IDs or bijective encoding of an increasing counter: sequential or timestamp-derived IDs are guessable and allow enumeration and scraping. We reject them to meet non-guessability. Alternative considered and rejected: truncated cryptographic hashes of the long URL (e.g., first 7 base62 chars of SHA256). Rejected because deterministic mapping makes tokens guessable if attacker can hash popular URLs; also collisions more frequent when truncating. We could have used HMAC(longURL, secret) to be deterministic and non-guessable, but deterministic mapping prevents reusing short tokens across multiple input variations and complicates TTL/revocation. Database schema and storage tech (with justification) Chosen primary store: DynamoDB (AWS) or managed Cassandra/Scylla if self-hosted. Primary reason: managed, horizontally scalable, high read/write throughput, built-in TTL support, multi-region replication (DynamoDB Global Tables) and single-digit millisecond access if provisioned appropriately. This is important for a 99.9% uptime and simple ops. Schema (logical, DynamoDB style): - Table: url_map - Partition Key: short_id (string, 7 chars) - Attributes: long_url (string), created_at (timestamp), expires_at (timestamp), owner_id (string), metadata (JSON blob), version (int), deleted (boolean), deletion_marked_at (timestamp), click_count (numeric, optional), analytics_shard_id (for click sharding) - TTL attribute: expires_at for automatic expiry by DB TTL feature Indexes: no additional global secondary indexes required for redirect path. Optionally a GSI on owner_id for management and bulk deletion by user, and GSI on deletion_marked_at for reclamation processing. Justification: Key-value access pattern maps cleanly to DynamoDB. The short_id is the natural unique key. TTL is built-in. For other cloud providers, use Cosmos DB with TTL or Scylla/Cassandra with TTL per-row. Caching strategy and invalidation Goals: Achieve 95th percentile redirect < 10ms at scale, minimize DB load, support multi-region. Layers: - CDN (edge) caching of redirect responses. Edge caches 301/302 with cache TTL computed from mapping expiry; max cache TTL limited to remaining TTL. For newly created short URLs, set short cache TTL for first N seconds to allow consistency. - Regional Redis cluster (ElastiCache Redis Cluster with cluster-mode enabled). Redis stores mapping short_id -> serialized redirect response and expiry metadata. Redis set TTL equals mapping expiry. - Local in-process LRU cache (small) in redirect service for micro-hits. Cache hit assumptions and sizing: - Assume CDN hit rate 70% for short URLs (popular links); Redis hit rate for edge misses ~85% for regional access patterns. These are tunable based on usage. Cache population and invalidation: - On write: Write Service writes to DB and immediately writes to regional Redis and publishes cache invalidation event to event stream which all regions subscribe to. This ensures caches are warm and consistent in near real-time. - On update or deletion: Write Service updates DB and publishes invalidation event; subscribers delete keys from Redis and expire Edge caches via cache-control headers or by sending PURGE/Cache API to CDN (or set short cache TTL to 0 and let edge fetch fresh). Purge calls kept minimal; prefer TTL-based expiration and pub/sub invalidation. - For TTL expiry: rely on DB TTL to remove the row and background workers to publish an invalidation event to clean caches and add token to reclamation queue. Read path (detailed) and throughput calculations Traffic calculations (baseline monthly -> per-second): - Writes: 100,000,000 / 30 / 24 / 3600 ~= 38.6 writes/sec average. Peak factor 5 assumed for diurnal/spiky traffic -> ~193 writes/sec peak. - Reads (redirects): 10,000,000,000 / 30 / 24 / 3600 ~= 3,858 reads/sec average. Peak factor 5 -> ~19,290 reads/sec peak. - Read-to-write ratio: 100:1 as specified. Read path (optimized for latency): 1. Client requests short.example/abc1234 -> DNS resolves to CDN edge node. 2. Edge cache lookup: if cached redirect, immediately return HTTP 301/302. This covers the majority of requests for popular links. 3. If edge miss: request forwarded to regional LB -> Redirect Service. 4. Redirect Service consults in-process cache (tiny) -> Redis cluster get(short_id). Redis GET is sub-millisecond depending on network (generally <1ms in-region). If Redis hit, service returns redirect and edge caches it with appropriate TTL. 5. If Redis miss: service queries primary DB (DynamoDB GetItem) which is single-digit ms, typically 3-6ms. Service returns redirect and populates Redis and edge cache. Throughput capability and sizing examples: - Redis cluster: assume peak 20k reads/sec. Deploy 3-5 shards with replication to handle 50k+ ops/sec and provide headroom. Each shard sized for ~10k ops/sec (appropriate node type). Read replicas in each AZ for HA. - DynamoDB: need capacity for writes ~200 TPS peak and reads for cache misses. If cache hit rate is 90% overall, DB read load = 19,290 * 0.10 ~= 1,929 reads/sec at peak. With eventual peaks and safety factor 2, provision for 4k strongly consistent reads/sec (or use eventually consistent reads to halve RCU cost). Write path (detailed) and throughput Write path: 1. Client submits create request to API -> API Gateway -> regional LB -> Write Service. 2. Write Service validates the URL (sanitization, malware checks optionally), checks rate limits and quotas. 3. ID Generator: uses CSPRNG to create token; attempt to insert into DB with PutItem conditional that short_id does not exist (atomic). If PutItem fails due to existing key (rare), retry generation. Insert includes long_url, created_at, expires_at. 4. On successful insert, Write Service writes to Redis for immediate cache warm-up and publishes an event to stream for analytics and cross-region propagation. 5. Return short URL to client. Throughput sizing for writes: - Baseline 39 writes/sec average, provisioned peak ~200 writes/sec. DynamoDB easily supports thousands of writes/sec with appropriate capacity or on-demand mode. - Stateless Write Service horizontally scaled: assume each instance can handle 200-500 req/s; set autoscaling group to maintain headroom. At 200 writes/sec peak, 2-4 instances are sufficient; allocate 10-20 for redundancy and other processing like rate-limiting. Scaling strategy and handling 10x growth Scenario: 10x growth means 1 billion writes/month and 100 billion redirects/month. Strategies: - Autoscaling: All stateless services (Write/Redirect) auto-scale based on CPU/RPS and request latency. Use cluster autoscaler for containers. - Cache scaling: Add Redis shards and increase memory. Redis cluster-mode allows dynamic re-sharding. CDN handles edge scaling automatically. - DB scaling: DynamoDB supports on-demand scaling, or increase write/read capacity; for self-hosted Cassandra/Scylla, add nodes and rebalance tokens. - Partitioning: DynamoDB hash key already distributes across partitions. For Cassandra, ensure enough nodes to keep partitions small. - Rate-limiting and backpressure: For sudden spikes, enforce per-user and per-API key rate limits and queue background tasks for non-critical work (analytics). Implement graceful degradation (e.g., deny new creations for abusive clients) rather than impacting redirects. - Global traffic: Add more regions and replicate data. Add cross-region Redis read replicas or rely on local caching filled by on-demand reads. Estimate capacity after 10x: - Peak reads ~200k/sec. With 90% cache hit rate, DB reads at peak ~20k/sec. DynamoDB/DAX or managed caching in front of DB will be required. Redis cluster scale to hundreds of shards, and CDN remains primary for reducing global load. Multi-region deployment and consistency model Model chosen: Active-active multi-region with eventual consistency across regions for non-critical data. Use DynamoDB Global Tables or Cassandra multi-dc replication. Rationale and CAP trade-offs: - Requirement: 99.9% uptime and cross-region disaster recovery. Prioritize Availability and Partition Tolerance (AP) over strict Consistency (CP) because redirects must remain available even during region partitions. Slight delay in replication for newly created short URLs in another region is acceptable; user who created the URL usually uses it immediately in same region and will see it due to local write and cache warming. - Implementation: Write Service writes to local region DB (DynamoDB local or same-region table) then replication to other region(s) happens via global tables. Reads in a region preferentially read locally. For strong local read-after-write consistency, use DynamoDB strongly consistent read in same region immediately after write, or just rely on immediate cache warm-up to ensure the redirect works in the writer's region. Trade-offs: - Eventual consistency simplifies global availability and lowers latency for reads. It does permit a short window where a short URL created in region A may not be visible in region B until replication finishes. We accept this because the main SLA concerns redirects' availability and latency. - If strict cross-region consistency were required, we would have to implement a CP model with cross-region synchronous replication, which would significantly increase write latency and reduce availability during partitions; thus rejected. TTL expiration and URL reclamation mechanism Requirements: configurable TTL per short URL (default 5 years), expired URLs should be reclaimable. Mechanism: - Use DB TTL attribute (expires_at). DynamoDB auto-deletes items after TTL passes, but deletion is eventually consistent and may not be immediate (can take up to 48 hours in some systems). Therefore we implement an active reclamation pipeline. - When expires_at approaches (e.g., within 24 hours), background workers mark the URL as expiring and push an event through the stream. This allows caches to set short TTLs and prepare purge. - On actual expiry, background workers scan for expired rows (using GSI on deletion_marked_at or table TTL events) and move the key into a Reclamation Queue with metadata: short_id, deletion_marked_at, original_expires_at. - Reclamation policy: Introduce a configurable grace period (e.g., 30 days) after expiry during which the short_id is tombstoned (deleted flag and tombstone record retained) to prevent immediate reuse and to protect against replication lag and user disputes. During tombstone period, the short_id resolves to 404 or a “this link expired” page; clicks are logged for audit. - After grace period, the reclamation worker moves short_id into a Reclaimable Token Pool (Kafka topic or DynamoDB token pool table). Tokens in pool can be recycled; Reclaimed tokens include a cooldown and are never immediately reissued to the same owner unless explicitly requested. - To avoid reuse collisions and abuse, maintain a tombstone index for recently used tokens (size bounded, e.g., retain for 1 year in a separate table) and check before reuse. Alternatively, instead of reusing tokens, prefer to keep recycling rate extremely low since the 7-char space is large. Failure modes and recovery 1) CDN / Edge outage in a region or a global edge provider disruption - Impact: Edge caching stopped; more requests hit regional redirect services and backend caches, increasing load and latency. - Recovery: Traffic is rerouted by DNS/anycast to other edges or fallback origin. Autoscale redirect fleet and increase instance counts. Use origin Shield and configure origin failover. Serve redirects directly from origin until edge recovers. 2) Primary DB region failure (full AZ/region outage) - Impact: Local DB unavailable; writes and reads cannot be served from that region. - Recovery: Failover to another region via global tables. Route DNS and API Gateway to healthy region(s). Because data is replicated asynchronously, recent writes in failed region may be lost for short time unless writes were replicated prior. The system accepts this in exchange for high availability. Background reconciliation tries to repair conflicts once region returns. 3) Redis cluster failure or partition - Impact: Cache misses increase leading to higher DB load and increased latency. - Recovery: Clients fallback to DB reads; scale up DB read capacity or enable DAX (DynamoDB Accelerator) or additional Redis nodes. Rebuild Redis cluster from DB snapshots or warm caches via prefetch of hottest keys using analytics/hot key lists. Use Redis Sentinel or managed Redis cluster with automatic failover to ensure node-level redundancy. 4) ID generator service bug causing collisions or rate limit exhaustion - Impact: Write failures, duplicate token errors, or inability to create new tokens. - Recovery: Design generator as stateless CSPRNG-based; if a bug is detected, roll back to a previous stable version and route requests to a fallback generator implementation (e.g., a different RNG library or a short-lived backed counter combined with HMAC salt). Add monitoring on collision rate; if collision rate > trivial threshold, stop issuing new tokens and return 5xx until fixed. 5) Event stream consumer backlog or worker failure - Impact: Cache invalidations, analytics processing, and reclamation are delayed. - Recovery: Autoscale consumers, prioritize invalidation and reclamation topics, and set retention so new consumers can catch up. Rebuild state from DB if necessary. Key trade-offs and alternatives considered 1) Storage choice: DynamoDB (managed NoSQL) vs. RDBMS vs. Cassandra/Scylla - Chosen: DynamoDB (or managed Cassandra). Reason: horizontal scale, TTL, managed service, global tables for multi-region. RDBMS rejected due to scaling complexity, sharding, and slower single-row latency at extreme scale. 2) Token generation: Random token vs sequential counter vs hash of long URL - Chosen: Cryptographically secure random tokens mapped into 7-character base62. Reason: non-guessable, uniform distribution, trivial to scale, small collision probability resolved by DB conditional insert. Sequential counters rejected because they are guessable. Deterministic hash rejected because of higher collision risk and predictability. 3) Active-active multi-region vs active-passive failover - Chosen: Active-active with eventual consistency. Reason: better availability and simpler client routing to nearest region with low latency. Active-passive provides stronger consistency but increases failover time and might violate latency/availability requirements. 4) Reclaiming tokens vs never reusing tokens - Chosen: Reclaimable with grace/tombstone period. Reason: token space is large so reuse is not necessary often, but reclamation required by spec. Safety increased by tombstone retention and cooldown before reissue. Never reuse rejected because after many years there might be need to conserve namespace if tokens are exhausted in pathological scenarios. 5) Caching at edge vs direct origin-only - Chosen: heavy edge caching with short TTLs. Reason: meet 95th percentile latency < 10ms for global users. Direct origin-only rejected because origin latency and cross-region hops would exceed latency SLA. Operational considerations and numbers - SLOs: 99.9% uptime; monitor health and latency at edge, redis, DB, and write service. Set alert thresholds for error rates and 95th percentile latency. - Capacity planning examples: for baseline traffic, provision DB for ~4k reads/sec and ~200 writes/sec peak; Redis cluster sized for ~30k ops/sec. For 10x scale, provision DB for ~40k reads/sec and Redis for ~300k ops/sec with autoscaling shards. - Security & abuse mitigation: rate limiting per API key/IP, URL scanning for malware (optional async), quota enforcement per account. Protect endpoints with WAF and API keys. - Data retention and privacy: Provide management APIs for users to delete/extend TTL; soft-delete semantics for auditability and tombstone retention. Summary This design uses a multi-layer caching approach (CDN edge + regional Redis) backed by a horizontally scalable NoSQL store (DynamoDB or Cassandra) and stateless microservices to meet throughput and latency requirements. Token generation uses CSPRNG-based base62 7-character tokens with DB-backed collision resolution to ensure non-guessability. The system favors availability and partition tolerance (active-active multi-region eventual consistency) to meet the uptime and latency SLAs, while reclamation and TTL are handled by DB TTL plus a reclamation pipeline with a tombstone grace window to avoid accidental reuse. The architecture scales horizontally with autoscaling and sharding to accommodate 10x growth, and includes recovery paths for common failure modes to meet the 99.9% uptime target.

This system design outlines a robust, scalable, and highly available URL shortening service capable of handling 100 million new shortenings and 10 billion redirects per month, with stringent latency and uptime requirements. High-level Architecture Description: The architecture is designed for high availability, scalability, and low latency, leveraging a microservices approach. Key components include: 1. **Load Balancers (e.g., AWS ELB/GCP Load Balancer/Nginx)**: Distribute incoming traffic across service instances. 2. **API Gateway (e.g., AWS API Gateway/Kong)**: Handles API requests, authentication, rate limiting, and routes traffic to the appropriate backend services. 3. **Shortening Service (Write Path)**: A stateless microservice responsible for processing requests to create new short URLs. It interacts with the Key Generation Service and the Database. 4. **Redirect Service (Read Path)**: A highly optimized, stateless microservice responsible for resolving short URLs to long URLs and performing the HTTP 301/302 redirect. It heavily relies on caching. 5. **Key Generation Service**: A dedicated service responsible for pre-generating and managing a pool of unique, random short URL keys. It ensures non-guessability and avoids collisions. 6. **Database (e.g., Apache Cassandra)**: The primary persistent storage for short URL mappings. Chosen for its high write/read throughput, horizontal scalability, and multi-region replication capabilities. 7. **Distributed Cache (e.g., Redis Cluster)**: Stores frequently accessed short URL mappings to reduce database load and achieve low redirect latency. 8. **Message Queue (e.g., Apache Kafka/AWS SQS)**: Used for asynchronous communication between services, such as publishing events for analytics, cache invalidation, and URL expiration. 9. **Analytics Service**: Consumes events from the message queue to track click counts, generate reports, and monitor usage patterns. 10. **Expiration & Reclamation Service**: A background worker service responsible for identifying expired URLs, marking them, and returning their keys to the Key Generation Service's pool for reuse. 11. **CDN (Content Delivery Network, e.g., Cloudflare/Akamai)**: Optional but highly recommended for caching redirects at the edge, further reducing latency and origin server load for global users. Interactions: * **Write Path**: User -> Load Balancer -> API Gateway -> Shortening Service -> Key Generation Service (gets key) -> Database (writes mapping) -> Message Queue (publishes 'new_url' event) -> Cache (updates/writes through). * **Read Path**: User -> Load Balancer -> CDN (if hit, redirects) -> Redirect Service (checks local cache -> distributed cache -> database) -> Redirect. URL Shortening Algorithm and Key Generation Strategy: To ensure non-guessability, uniqueness, and meet the 7-character limit, a pre-generation strategy is employed: 1. **Key Generation Service**: This service continuously generates random alphanumeric strings of 7 characters (e.g., using a cryptographically secure pseudo-random number generator). The character set includes `a-z`, `A-Z`, `0-9`, totaling 62 characters. A 7-character string allows for 62^7 unique keys, which is approximately 3.5 trillion, far exceeding the 100 million URLs/month requirement. 2. **Uniqueness Check**: Before adding to the pool, each generated key is checked for uniqueness against the database (or a dedicated unique key store). This is a one-time check during generation, not during shortening requests. 3. **Key Pool**: Unique keys are stored in a highly available, fast-access pool (e.g., a Redis Set or a dedicated table in Cassandra with a 'status' field like 'available'). The Key Generation Service maintains a large buffer (e.g., several billion keys) to ensure keys are always readily available. 4. **Shortening Process**: When a user requests a new short URL, the Shortening Service requests a key from the Key Generation Service. The Key Generation Service atomically pops an available key from its pool, marks it as 'in-use', and returns it. This avoids contention during high write loads. 5. **Collision Avoidance**: By pre-generating and atomically assigning unique keys, collisions during the actual shortening request are virtually eliminated. The database also enforces a unique constraint on the `short_url_key` as a final safeguard. Database Schema and Choice of Storage Technology: Database Choice: **Apache Cassandra** (or AWS DynamoDB as a managed alternative). Justification: * **High Write/Read Throughput**: Cassandra is designed for high-volume, low-latency operations, perfect for the 100:1 read-to-write ratio and billions of reads. * **Horizontal Scalability**: Easily scales by adding more nodes, distributing data and load across the cluster. * **High Availability & Fault Tolerance**: Data is replicated across multiple nodes and data centers, ensuring continuous operation even during node failures. * **Eventual Consistency**: Acceptable for this use case. While a new URL might take milliseconds to propagate across regions, it doesn't impact core functionality. * **Simple Key-Value Lookups**: The primary access pattern is `short_url_key` to `long_url`, which Cassandra excels at. Schema (Keyspace: `url_shortener`, Table: `short_urls`): ``` CREATE TABLE url_shortener.short_urls ( short_url_key text PRIMARY KEY, -- Partition Key, 7 alphanumeric characters long_url text, user_id text, -- Optional, for user-specific URLs created_at timestamp, expires_at timestamp, click_count counter, -- Cassandra counter type for atomic increments status text -- 'active', 'expired', 'reclaimed' ); ``` Caching Strategy and Cache Invalidation Approach: Caching is critical for achieving the <10ms redirect latency and handling 10 billion redirects/month. Strategy: 1. **Multi-tier Caching**: * **CDN (Edge Cache)**: Caches redirects at geographically distributed points of presence. This is the first line of defense for read requests. * **Distributed Cache (Redis Cluster)**: A central, high-performance cache storing `short_url_key` to `long_url` mappings. Each entry also stores `expires_at`. * **In-memory Cache**: Each Redirect Service instance maintains a small, fast in-memory cache for the hottest URLs. 2. **Read-Through**: When the Redirect Service receives a request, it first checks its in-memory cache, then the Redis Cluster. If not found, it fetches from Cassandra, stores the mapping in Redis and its local cache, and then redirects. 3. **Write-Through**: When a new URL is shortened, the Shortening Service writes the mapping to Cassandra and then immediately writes it to the Redis Cluster. Cache Invalidation: 1. **TTL-based Expiration**: Cache entries in Redis and in-memory caches have a configurable TTL (e.g., 5 minutes or aligned with the URL's `expires_at`). This handles eventual consistency and ensures stale data doesn't persist indefinitely. 2. **Explicit Invalidation**: When a URL expires or is reclaimed by the Expiration & Reclamation Service, an event is published to the Message Queue. Cache invalidation workers consume this event and explicitly delete the corresponding entry from the Redis Cluster. CDN caches are invalidated via API calls or by setting appropriate `Cache-Control` headers with short max-age for redirects. Read Path and Write Path with Throughput Calculations: Assumptions: 1 month = 2,592,000 seconds. Write Path (100 million new URL shortenings per month): * **Average Throughput**: 100,000,000 URLs / 2,592,000 seconds ≈ 38.6 writes/second. * **Peak Throughput**: Assuming peak is 3x average, design for ~120 writes/second. * **Flow**: Load Balancer -> API Gateway -> Shortening Service (requests key from Key Generation Service, writes to Cassandra, writes to Redis, publishes event to Kafka). * **Components**: Multiple instances of Shortening Service, Key Generation Service, Cassandra nodes, Redis nodes, Kafka brokers. * **Latency Target**: Under 100ms for writes (less critical than reads). Read Path (10 billion redirects per month): * **Average Throughput**: 10,000,000,000 redirects / 2,592,000 seconds ≈ 3,858 reads/second. * **Peak Throughput**: Assuming peak is 3x average, design for ~12,000 reads/second. * **Flow**: User -> CDN (if hit, redirects) -> Load Balancer -> Redirect Service (checks in-memory cache -> Redis Cluster -> Cassandra) -> Redirect. * **Cache Hit Ratio**: Aim for >95% cache hit ratio (CDN + Redis) to offload Cassandra. * **Effective DB Reads**: 12,000 reads/sec * 5% (cache miss) = 600 reads/second to Cassandra. * **Latency Target**: Under 10ms at 95th percentile. * **Components**: Numerous instances of Redirect Service, Redis Cluster nodes, Cassandra nodes. CDN plays a crucial role. Scaling Strategy: 1. **Horizontal Scaling (Stateless Services)**: All stateless services (API Gateway, Shortening Service, Redirect Service, Key Generation Service, Analytics Service, Expiration & Reclamation Service) are deployed as multiple instances behind load balancers. They can be scaled out by adding more instances based on CPU utilization, memory, or request queue depth (e.g., using Kubernetes HPA or AWS Auto Scaling Groups). 2. **Database Scaling (Cassandra)**: Cassandra scales horizontally by adding more nodes to the cluster. Data is automatically rebalanced. This allows for increased storage capacity and read/write throughput. 3. **Cache Scaling (Redis Cluster)**: Redis Cluster provides sharding and replication, allowing it to scale horizontally by adding more master and replica nodes. 4. **Message Queue Scaling (Kafka)**: Kafka is inherently scalable, allowing for increased throughput by adding more brokers and partitions. 5. **CDN**: Offloads a significant portion of read traffic from the origin servers, effectively scaling the read path globally. 6. **Microservices**: The modular architecture allows individual services to be scaled independently based on their specific load requirements. Multi-region Deployment and Data Consistency Model: To achieve 99.9% uptime and disaster recovery, the service will be deployed in an Active-Active configuration across at least two geographic regions (e.g., US-East and EU-West). Deployment: * Each region hosts a complete, independent stack of all services (Load Balancers, API Gateway, Shortening/Redirect Services, Key Generation Service, Cassandra cluster, Redis Cluster, Kafka cluster, etc.). * A Global Load Balancer (e.g., AWS Route 53 with latency-based routing or a global traffic manager) directs users to the closest healthy region. Data Consistency Model: * **Cassandra Multi-Datacenter Replication**: Cassandra's `NetworkTopologyStrategy` is used to replicate data asynchronously between the regional clusters. Each region maintains a full copy of the data. * **Writes**: Writes are typically performed with `LOCAL_QUORUM` consistency within the primary region for low latency. Cassandra's built-in replication ensures eventual consistency across regions. A new short URL created in Region A will eventually propagate to Region B. * **Reads**: Reads are also typically performed with `LOCAL_QUORUM` consistency for low latency, serving data from the local region's Cassandra cluster or cache. If a key is not found locally (e.g., due to replication lag for a very new URL), a fallback to a cross-region read could be implemented, but this would incur higher latency. Given the read-heavy nature and cache, this is rare. Trade-offs (CAP Theorem): * **Chosen**: Prioritize **Availability** and **Partition Tolerance** over strong **Consistency** across regions. * **Reasoning**: For a URL shortening service, it's more critical that the service is always available and performs quickly, even if a newly created URL takes a few milliseconds to be accessible globally. Strong consistency across geographically dispersed data centers would introduce unacceptable write latency and complexity. Eventual consistency is a suitable trade-off. TTL Expiration and URL Reclamation Mechanism: 1. **Expiration**: The `expires_at` timestamp in the `short_urls` table is used. The Expiration & Reclamation Service (a set of background workers) periodically scans the `short_urls` table for entries where `expires_at` is in the past and `status` is 'active'. * Upon identifying an expired URL, the service updates its `status` to 'expired' in Cassandra. * It then publishes an 'url_expired' event to the Message Queue, triggering cache invalidation for that `short_url_key` in Redis and CDN. 2. **Reclamation**: After a configurable grace period (e.g., 24-48 hours) following expiration (to ensure all caches are cleared and no in-flight redirects are affected), the Expiration & Reclamation Service identifies URLs with `status` 'expired' that are past their grace period. * It then updates their `status` to 'reclaimable'. * The `short_url_key` is then added back to the Key Generation Service's pool of available keys. This ensures that the 7-character key space is efficiently reused over time. * A final check for uniqueness before adding back to the pool can be done, though the Key Generation Service's design should prevent true collisions. Failure Modes and Recovery: 1. **Database Node Failure (e.g., Cassandra node crash)**: * **Detection**: Monitoring systems detect node unreachability or high error rates. * **Recovery**: Cassandra's distributed architecture with a replication factor (RF) of 3 (or higher) ensures data redundancy. If a node fails, other replicas serve the data. The cluster remains operational. The failed node can be automatically replaced or manually brought back online. No data loss, minimal service interruption. 2. **Key Generation Service Failure**: * **Detection**: Health checks and monitoring detect service unavailability or exhaustion of the key pool. * **Recovery**: The Key Generation Service is deployed with multiple instances. If one fails, others take over. If the entire service fails, new URL shortening requests will temporarily fail as they cannot obtain a unique key. However, existing redirects will continue to function normally. Auto-scaling groups will launch new instances. A large pre-generated key buffer (billions of keys) significantly reduces the impact of temporary outages. 3. **Cache Cluster Failure (e.g., Redis Cluster outage)**: * **Detection**: Monitoring detects Redis node or cluster unavailability. * **Recovery**: The Redirect Service is designed to fall back to the Cassandra database if the cache is unavailable. This will lead to increased redirect latency (from <10ms to potentially 50-100ms) and higher load on Cassandra, but the service remains fully functional (degraded performance). Redis Cluster with replication provides high availability, mitigating full cluster outages. 4. **Entire Region Outage**: * **Detection**: Global Load Balancer (e.g., Route 53 health checks) detects that all services in a region are unhealthy. * **Recovery**: The Global Load Balancer automatically routes all traffic to the healthy secondary region. Users might experience a brief spike in latency during the failover, but the service remains available. Data consistency might be slightly behind, but the system is designed to tolerate eventual consistency. Key Trade-offs Made and Alternatives Considered: 1. **Consistency vs. Availability/Latency (CAP Theorem)**: * **Chosen**: Eventual consistency for cross-region data replication and high availability/low latency reads. * **Rejected**: Strong consistency across regions. * **Reasoning**: Strong consistency would introduce significant latency for writes and cross-region reads, which is unacceptable for a high-throughput, low-latency redirect service. A few milliseconds of inconsistency for a new URL mapping is a minor trade-off compared to the benefits of high availability and performance. 2. **Key Generation Strategy (Pre-generated vs. On-the-fly Hashing/Sequential)**: * **Chosen**: Pre-generated random alphanumeric keys via a dedicated service. * **Rejected**: Hashing the long URL (e.g., MD5, SHA-256 truncated) or using a base-62 encoder on an auto-incrementing ID. * **Reasoning**: Hashing can lead to collisions (especially with a 7-char limit) requiring complex collision resolution logic, adding latency and complexity to the write path. Base-62 on auto-incrementing IDs makes URLs sequential and guessable, violating a key requirement. Pre-generation ensures uniqueness, non-guessability, and fast key retrieval during writes, simplifying the shortening process. 3. **Database Choice (NoSQL vs. Relational SQL)**: * **Chosen**: Apache Cassandra (NoSQL). * **Rejected**: PostgreSQL/MySQL (Relational SQL). * **Reasoning**: Relational databases struggle with the extreme read/write throughput and horizontal scalability requirements of this service without significant sharding complexity. NoSQL databases like Cassandra are purpose-built for this scale, high availability, and performance, especially for simple key-value lookups, which is the primary access pattern. 4. **TTL Implementation (Background Service vs. Database TTL)**: * **Chosen**: Dedicated Expiration & Reclamation Service scanning `expires_at`. * **Rejected**: Relying solely on database-level TTL (e.g., Cassandra's built-in TTL). * **Reasoning**: While database TTL can automatically expire data, it doesn't easily facilitate the controlled reclamation of the `short_url_key` back into a reusable pool or trigger explicit cache invalidation. A dedicated service provides more granular control over the entire lifecycle, including the grace period and safe key reuse.