Design a URL Shortening Service at Scale

### A. High-level Architecture The system is designed as a set of distributed, stateless microservices deployed across multiple geographic regions to ensure high availability and low latency. The main components are: 1. **Global Load Balancer (GLB)**: Distributes user traffic to the nearest and healthiest region using DNS-based routing (e.g., AWS Route 53, Google Cloud Load Balancing). 2. **Regional Load Balancers (RLB)**: Distribute traffic within a single region to the fleet of web servers. 3. **API Gateway / Web Servers**: A layer of stateless servers that terminate TLS and handle incoming HTTP requests for both writes (shortening) and reads (redirection). 4. **Redirect Service (Read Path)**: A highly optimized service responsible for looking up short codes and issuing HTTP 301/302 redirects. It interacts primarily with the caching layer. 5. **URL Shortening Service (Write Path)**: A service that handles the creation of new short URLs. It coordinates with the Key Generation Service and the primary database. 6. **Distributed Cache**: An in-memory cache (e.g., Redis Cluster) in each region that stores hot URL mappings to meet the strict low-latency requirement for redirects. 7. **Primary Database**: A distributed NoSQL database (e.g., Apache Cassandra, Amazon DynamoDB) that serves as the persistent source of truth for all URL mappings, replicated across all regions. 8. **Key Generation Service (KGS)**: A dedicated, highly available service that pre-generates batches of unique, 7-character short codes to eliminate write-time collisions and latency. 9. **Analytics Pipeline**: An asynchronous data pipeline starting with a message queue (e.g., Apache Kafka) to ingest clickstream data without impacting the performance of the redirect service. This data is then processed and stored in a separate analytics database. ### B. URL Generation Strategy **Approach**: We will use a dedicated Key Generation Service (KGS) to pre-generate unique keys. **Mechanism**: 1. The KGS maintains a counter in a distributed, fault-tolerant manner (e.g., using ZooKeeper or an atomic counter in a database like Redis). 2. It generates large, sequential numeric IDs. To ensure high availability, multiple KGS instances can be run, each responsible for a different range of IDs (e.g., Server 1 handles 1 to 1,000,000, Server 2 handles 1,000,001 to 2,000,000). 3. Each numeric ID is then converted to a base-62 string ([a-z, A-Z, 0-9]) to produce the 7-character short code. A 62^7 space provides ~3.5 trillion unique codes, which is more than sufficient. 4. The KGS generates these codes in batches and places them into a queue (e.g., a Redis list) for the URL Shortening Service to consume. **Justification**: This approach avoids the need to check for collisions in the main database during a write operation, which would be slow and a point of contention. It makes the write path extremely fast and predictable, as the Shortening Service simply needs to fetch a guaranteed-unique key from the KGS. ### C. Data Model and Storage **Primary Storage (URL Mappings)**: * **Technology**: Apache Cassandra or Amazon DynamoDB. * **Why**: These NoSQL databases offer excellent horizontal scalability, native multi-region replication, high availability, and low-latency key-value lookups, which perfectly match our requirements for both scale and fault tolerance. * **Schema**: * Table Name: `url_mappings` * Partition Key: `short_code` (string) * Columns: * `long_url` (string) * `user_id` (string, for ownership) * `created_at` (timestamp) **Cache Storage**: * **Technology**: Redis Cluster. * **Why**: Redis provides extremely low-latency (sub-millisecond) in-memory data access, which is essential for meeting the <10ms redirect requirement. It can be clustered for scalability and high availability. **Analytics Storage**: * **Technology**: A column-oriented database like Apache Druid, ClickHouse, or a cloud data warehouse like Google BigQuery. * **Why**: These systems are optimized for fast aggregations and analytical queries over massive datasets, which is ideal for powering the analytics dashboard. ### D. Read Path Optimization The read path is heavily optimized for latency using a multi-layered caching strategy to handle the 40,000 peak QPS. 1. **CDN/Edge Cache**: For extremely popular URLs, a CDN can cache the 301/302 redirect response at edge locations, serving users from the closest point of presence without hitting our core infrastructure. 2. **Distributed In-Memory Cache (Redis)**: This is the primary workhorse for low latency. The Redirect Service first queries the regional Redis cluster. A cache hit results in an immediate redirect. * **Cache Size Estimate**: To cache 20% of 5 years of URLs (100M/month * 12 * 5 * 0.2 = 1.2B URLs). At ~600 bytes per entry (short code, long URL, overhead), this requires approximately 720 GB of RAM per region, which is feasible for a Redis cluster. 3. **Database Lookup**: On a cache miss, the service queries the primary Cassandra/DynamoDB database. The result is then written back to the Redis cache with a Time-To-Live (TTL) to ensure the cache remains filled with frequently accessed items. This architecture ensures that the vast majority of requests are served from memory, easily meeting the <10ms p99 latency goal. ### E. Write Path The write path is designed for reliability and throughput (~400 peak writes/sec). 1. A user sends a POST request with the long URL to the API Gateway. 2. The request is routed to an instance of the URL Shortening Service. 3. The service validates the long URL. 4. It requests a unique short code from the Key Generation Service (KGS). 5. The service writes the new mapping (`short_code`, `long_url`) to the primary database (Cassandra/DynamoDB) with a high consistency level for the local region. 6. The database asynchronously replicates this write to other regions. 7. Upon successful database write, the service returns the new short URL to the user. ### F. Scaling Strategy The system is designed to scale horizontally at every layer: * **Stateless Services**: The API Gateway, Redirect Service, and Shortening Service are stateless. We can scale them by adding more virtual machines or containers behind the load balancers. * **Database**: Cassandra and DynamoDB are designed to scale horizontally by adding more nodes to the cluster. The data and load are automatically rebalanced. * **Cache**: Redis Cluster can be scaled by adding more nodes and re-sharding the keyspace. * **Analytics Pipeline**: Kafka scales by adding more brokers and partitions. The consumer services that process the data can also be scaled horizontally. ### G. Reliability and Fault Tolerance High availability is achieved through redundancy across multiple geographic regions (e.g., US-East, US-West, EU-West). * **Multi-Region Deployment**: The entire stack is deployed in at least two independent regions. * **Global Failover**: The Global Load Balancer continuously monitors the health of each region. If an entire region becomes unavailable, the GLB automatically redirects all traffic to the healthy regions. * **Data Replication**: The primary database (Cassandra/DynamoDB) is configured for multi-region replication. This ensures that if one regional database is lost, the data is preserved in other regions. Writes can continue to be served in the remaining active regions. * **No Single Point of Failure**: Every component, from the load balancers to the KGS and databases, is deployed in a clustered, fault-tolerant configuration. ### H. Analytics Pipeline The analytics pipeline is designed to be completely decoupled from the critical redirect path to prevent any performance degradation. 1. **Data Ingestion**: After successfully serving a redirect, the Redirect Service publishes a message to a Kafka topic. This message contains event data like `short_code`, `timestamp`, `IP address`, `User-Agent`, and `Referrer`. This is an asynchronous, non-blocking operation. 2. **Data Processing**: A separate fleet of stream processing workers (e.g., using Spark Streaming, Flink, or custom consumers) reads messages from the Kafka topic in batches. 3. **Data Enrichment & Aggregation**: These workers enrich the data (e.g., converting IP to geo-location) and perform real-time aggregations (e.g., incrementing click counts per hour, per country). 4. **Data Storage**: The processed and aggregated data is loaded into the analytics database (ClickHouse/Druid), which is optimized to power the user-facing dashboard queries efficiently. This asynchronous architecture ensures that even a massive spike in traffic or a failure in the analytics pipeline will have zero impact on the speed and availability of URL redirections. ### I. Key Trade-offs 1. **Eventual Consistency vs. Strong Consistency**: We chose an eventually consistent data replication model across regions. A URL created in one region might take milliseconds to be available in another. This trade-off significantly improves write latency and system availability, which are more critical for this application than immediate global consistency. 2. **Cost vs. Performance**: We are using a large, expensive in-memory Redis cache to meet the strict <10ms p99 latency requirement. A cheaper, disk-based solution would not be able to satisfy this core performance SLA. We are trading higher operational cost for guaranteed low latency on the critical read path. 3. **Complexity vs. Scalability (KGS)**: We introduced a separate Key Generation Service (KGS) instead of generating hashes or random strings on the fly. This adds an extra component to build and maintain, increasing system complexity. However, it completely eliminates database hotspots and collision-checking logic on the write path, which is a crucial trade-off to ensure high throughput and low-latency writes at scale.

Summary I propose a globally distributed, cache-first URL shortener with: a lightweight edge redirect path (CDN + edge function + local cache) to meet the <10 ms p99 redirect latency requirement; a durable, multi-region primary store for canonical mappings; a distributed ID allocator to generate unique short codes encoded in base62 (<=7 chars); an async analytics pipeline (Kafka/Kinesis → stream processors → OLAP store) that is strictly decoupled from the redirect path; and multi-region replication and failover for availability during a full data center outage. A. High-level architecture (components and interactions) - Edge layer (CDN): Cloud CDN (e.g., Amazon CloudFront, Fastly) fronts all GET /{code} redirect requests. Most requests are served from CDN edge cache with a cached 301/302 response. - Edge function (CloudFront Function / Fastly Compute / Lambda@Edge): if cache miss, a tiny edge function invokes a regional Redirect API (via a short RPC/HTTP) to fetch the canonical destination URL and return a 301/302. The edge function adds minimal logic to choose correct cache TTL and handle deleted/missing codes. - Regional Redirect API / Read Cache tier: stateless read servers in each region that first consult a regional in-memory cache (Redis cluster / ElastiCache or Memcached) then fall back to the durable key-value store if needed. - Durable key-value store (Primary DB): DynamoDB Global Tables or Cassandra (multi-region) that store short_code -> long_url and metadata as the canonical source of truth. - ID Allocation service (Range allocator): a small service that hands out ID blocks to Write API servers for local short code generation (ensures uniqueness without per-write central lock). - Write API: service that handles creation requests, reserves/generates the short_code (via ID block), persists to primary DB, and propagates an invalidation to caches and CDN. Writes are synchronous to primary DB for durability. - Cache invalidation & propagation: on create/update/delete, Write API updates regional caches and invalidates CDN edge entries via CDN invalidation API or by writing cache-control headers and using a version token in URL if necessary. - Analytics pipeline (async): redirect events are recorded asynchronously (not in the synchronous redirect path). Edge loggers or regional read servers push lightweight click events to a message bus (Kafka / Kinesis). Stream processing (Flink / Spark Streaming) aggregates and writes to an analytics store (ClickHouse / BigQuery) and to pre-aggregated counters in a read-optimized store for dashboards. - Dashboard API & UI: reads aggregated analytics from OLAP/aggregates stores and serves user dashboards. Dashboard queries never hit the redirect path. B. URL generation strategy Goals: uniqueness, compactness (<=7 alphanumeric chars), high throughput, low contention. Chosen approach: sequential numeric IDs allocated in distributed ID blocks, base62-encoded to produce the short code. - Why base62 sequential IDs: base62 (a–z, A–Z, 0–9) gives 62^7 ≈ 3.52 × 10^12 possible codes with up-to-7-char strings — far more than expected lifetime needs. Sequential IDs encode compactly and are easy to reverse to numeric values if needed. Deterministic mapping avoids hashing collisions. - ID allocation implementation: a central allocator hands out monotonically increasing ID ranges (e.g., blocks of 1M) to each write-server cluster. Each write server issues local IDs from its block without remote coordination, ensuring uniqueness and very low latency. The allocator itself is small and can be backed by a highly-available store (RDS or a lightweight ZooKeeper/etcd based counter) and only used for block refills (low QPS). - Encoding: numeric ID -> base62 string. If numeric ID < 62^7, encoding length is <=7. With 100M new shortenings/month (1.2B/year), 62^7 capacity gives >2,900 years of space. - Handling collisions: none expected because numeric IDs are unique. Still, the Write API uses a conditional insert against the primary DB (PUT with primary key == short_code) and retry on rare primary DB conflict (shouldn't happen if allocator is correct). For user-requested custom aliases, check and return error if already taken. - Optional deduplication: optionally maintain a secondary hash index (e.g., SHA-256 of long_url) to return an existing short code if the same URL was shortened before by same user; this is application-level behavior and is optional. C. Data model and storage Primary data store choices: DynamoDB Global Tables (managed, multi-region, single-digit ms read/write), or Apache Cassandra / ScyllaDB (self-managed multi-region) as the canonical choices. I recommend DynamoDB Global Tables for faster ops and simpler multi-region replication unless you must be cloud-agnostic. Primary mapping table schema (key-value optimized): - Table name: URL_Mapping - Primary key: short_code (string, PK) - Attributes: long_url (text), user_id (string), created_at (timestamp), custom_alias_flag (bool), deleted_flag (bool), metadata (JSON/Sparse map), analytics_enabled (bool), version (int) - Secondary indexes (optional): user_id -> list of short_codes (GSI) for management UI; long_hash -> short_code (for de-duplication if desired) Storage estimates: assume each record stores 200 bytes on average (short_code ~7 bytes, URL avg 200? but we can compress; assume 200–400 bytes conservative). At 100M/month new rows: 100M * 200 B = 20 GB/month. Yearly ≈ 240 GB. Ten-year ≈ 2.4 TB. DynamoDB/Cassandra can easily handle this scale. Analytics stores: raw click events go into append-only systems (Kafka/Kinesis) then into a long-term analytics store (ClickHouse or BigQuery) for aggregation and dashboards. Pre-aggregated counters (per short_code per timebucket) can be stored in ClickHouse and hot counters cached in Redis for dashboard queries. D. Read path optimization (achieving <10 ms p99 redirects) Objective is to serve 99th percentile redirects under 10 ms from request arrival to issuing 301/302. Techniques used: 1) CDN + Edge Cache (primary optimization): cache full 301 responses at CDN edges for nearly all requests. Set very long TTLs (effectively non-expiring) because mappings do not expire, but support immediate invalidation when a mapping is updated/deleted. - With CDN edge hit, latency to client typically <10 ms globally. 2) Very small edge function for cache-miss lookup: CloudFront Function or Fastly’s edge compute to minimize runtime overhead (~sub-ms). If cache miss, the edge function calls a regional Redirect API via a short TCP connection (keepalive) and returns 301 to CDN. 3) Regional read cache (Redis in each region): Regional cache is a memory-first store for mapping lookups; typical Redis GET <1 ms. Cache hit rate target: >=99% for hot codes. Use LFU/LRU eviction and size to hold working set. - Cache sizing example: assume peak global RPS = 40k reads/sec; working set of top 50M codes (hot tail) — store short_code->long_url pairs (avg 200 bytes). Memory = 50M * 200 B ≈ 10 GB. A modest multi-shard Redis cluster (e.g., 4-8 nodes of 32 GB each) per region can handle this. 4) Origin DB access only on cache miss: DynamoDB single-row GetItem is typically low ms (1–10 ms) but we design to avoid being in critical path for p99 by caching heavily. 5) Keep the edge function + HTTP path minimal: use HTTP/2 or HTTP/3 between CDN and origin to reduce handshake latency and enable connection reuse. 6) Local anycast + geo-aware routing: send client to nearest edge/region to keep RTT low. Measurement and SLA: test with synthetic traffic and 99th percentile latency budgets allocated: CDN hit (target <5 ms), edge function + Redis <10 ms, origin fallback acceptable for low percentiles but will be monitored and tuned. E. Write path: creation and persistence 1) Client makes POST /create (or via UI) to Write API (region-aware endpoint). Write API layer is stateless and autoscaling. 2) Write API obtains a numeric ID from its locally allocated block (range allocator). If block exhausted, requests a new block from the allocator. 3) Encode numeric ID to base62 short_code. 4) Persist to primary DB with a conditional insert: PutItem(short_code, long_url, metadata) with conditional expression that short_code does not exist (prevents accidental overwrite of custom alias). Ensure atomic write for durability. 5) Upon successful write: - Update regional read cache (write-through) so subsequent redirects hit the cache. - Send a CDN cache pre-warm request or publish an invalidation for this short_code to the CDN so the new mapping is immediately cached at edges (or leverage the CDN’s cache-control + versioning to make it effective). 6) Return created short_code to user. Durability and consistency: synchronous write to primary DB with replication across regions (DynamoDB global tables or Cassandra with multi-DC replication). If using DynamoDB, consistency model can be eventually consistent for reads but writes are durable and replicated. Operational numbers: writes QPS average ~40 writes/sec (100M/month ≈ 38.6/s). Peak bursts possible; the write pipeline is easy to scale horizontally. F. Scaling strategy (horizontal scaling) - Stateless API / Redirect servers: autoscale horizontally behind a global load balancer (ALB / GCLB). Keep servers stateless so they are easy to scale. - ID allocator: low QPS—scale by making it fault-tolerant (active/passive + persisted counter or delegated range allocation). Allocate larger blocks to reduce allocator load. - Caches: Redis/ElastiCache clusters per region, sharded (consistent hashing). Add shards to grow memory throughput. - Primary DB: DynamoDB auto-scaling or Cassandra cluster that can add nodes and grow throughput. Choose instance sizes and replication factor to meet read/write capacity. - Message bus (Kafka/Kinesis): partition the click stream by short_code hash to scale ingestion. Use enough partitions to meet peak throughput (e.g., if peak redirects 38k RPS generating 38k events/sec, provision Kafka partitions and brokers to handle ~50–100k events/s with replication factor 3). - Analytics compute: scale Flink / Spark clusters horizontally based on event volume. - CDN scales automatically; CDN config should be tuned for request rates. G. Reliability and fault tolerance Goals: survive an entire data center going offline, ensure no data loss. - Multi-region deployment: deploy at least two active regions (multi-active) with global routing. Use global load balancing + health checks to route around failed region. - Primary DB replication: DynamoDB Global Tables provide active-active replication across regions; Cassandra/Scylla can be configured with replication factor across data centers. This provides durability if one DC is lost. - Regional caches are warm on failure: when a region fails, traffic routed to next region which will have its own cache. Cold-fronting a region after failover may cause more origin reads until caches warm but availability is preserved. - ID allocator fault tolerance: allocator state persisted in a highly-available store; allocate large blocks to reduce need to access allocator under failover. - Message bus replication: Kafka with replication factor >=3 across racks/regions or managed Kinesis with cross-region replication for durability. - Health checks and automated failover: active monitoring, circuit breakers, rate-limiting to prevent overload during failover. - Backups: periodic snapshots of primary DB and exports of metadata. For DynamoDB, enable point-in-time recovery; for Cassandra, scheduled snapshots. H. Analytics pipeline (collect/process/serve without impacting redirects) Design principle: analytics writes must be asynchronous and never block redirects. 1) Lightweight event generation: edge (CDN/edge function) emits a small event for each redirect (short_code, timestamp, client_ip or geo tag, referrer, user-agent). To minimize redirect latency, emitting is done via a very fast UDP-like push to a local proxy or via batching in memory in the read server and sent asynchronously. 2) Message bus: events are pushed to Kafka or Kinesis topics partitioned by short_code (or hashed) to support scalable parallel processing. The producer must be asynchronous and non-blocking; if the local Kafka buffer is full, fall back to sampling or drop low-value fields to ensure redirect latency is not affected. Producers use local buffering and backpressure policies. 3) Stream processing: Flink / Kafka Streams / Spark Streaming consumes events, enriches (geo-IP lookup, UA parsing), and computes real-time aggregates (click counts, geo distribution, referrers) at minute/hour granularity. Pre-aggregate per short_code per time window. 4) OLAP store & aggregates: write aggregated data to ClickHouse or BigQuery for fast analytical queries and long-term storage. For serving dashboards, store recent aggregates in a fast read store (Redis or Druid) for interactive queries. 5) Dashboard API: reads only from aggregates/OLAP store; no direct query from analytics store to redirect path. Implement rate limits and per-user quotas for dashboard queries. 6) Sampling and tiered logging: for extremely high-traffic short_codes, optionally sample events to reduce pipeline load while preserving representative analytics. Performance example: peak redirects ~40k/s -> events 40k/s -> Kafka ingest easily manageable with 100 partitions and a few brokers. Stream processors scale horizontally to handle this volume and write summarized aggregates every minute to ClickHouse. I. Key trade-offs (at least three) with justification 1) CDN edge-caching vs immediate consistency for deletes/updates - Trade-off: Using long-lived CDN edge cache yields very low redirect latency but makes update/delete propagation slightly more complex and not instant everywhere. - Justification: Redirect latency SLA is strict (<10 ms p99). Typical operations to modify/delete a short URL are rare compared to redirects. We prefer ultra-low latency for redirects and accept slightly delayed cache invalidation (we provide immediate invalidation APIs for important cases). We also include a version token or short TTL invalidation strategy for critical updates. 2) Sequential ID allocation (range blocks + base62) vs fully random/hashing scheme - Trade-off: Sequential allocation with blocks requires a small allocator service and careful handling during cross-region failover, while hashing/random generation can be fully stateless but requires collision resolution or larger code length to reduce collisions. - Justification: Sequential IDs produce compact, very short codes deterministically and avoid collision handling at write time. With block allocation, allocator load is minimal and scale-friendly. Given the extremely large keyspace (62^7) we don’t need randomness to avoid collisions. 3) DynamoDB (managed, multi-region) vs self-hosted Cassandra - Trade-off: DynamoDB simplifies operational burden and gives managed multi-region replication, but may be more expensive and somewhat less flexible in query patterns compared to self-hosted Cassandra/Scylla. - Justification: The system’s access pattern is simple primary-key reads/writes; we value operational simplicity, reliability, and automatic scaling and therefore recommend DynamoDB Global Tables unless cost constraints force Cassandra. 4) Synchronous write-through caching vs eventual propagation to caches - Trade-off: Synchronous write-through to caches increases write latency slightly but ensures immediate availability at read caches; eventual propagation lowers write latency but may cause short window where redirects miss. - Justification: Writes are low QPS (≈40/s), so performing a cache write on creation is acceptable to ensure newly created links are immediately available for redirects and avoid cold cache misses for newly created short codes. Operational considerations and telemetry - Monitoring: p99 redirect latency, cache hit ratio, origin RPS, write latency, message bus lag, analytic pipeline lag. Alerting for cross-DC replication lag. - Capacity planning: plan for 10x peak safety. Example numbers: - Read QPS (avg): 3,858 RPS = 10B/month. Peak assumption 10x => ~38.6k RPS. - CDN edge hit target: 99% → origin RPS ≈ 386 RPS. Regional caches sized to keep hot working set. - Cache sizing: to hold top 50M keys at 200 B each → 10 GB; use multiple shards per region. - Kafka throughput: at peak 40k events/s, with average event size 500 B => ~20 MB/s ingest; with replication factor 3 and overhead plan for ~60 MB/s cluster throughput. - Primary DB throughput: writes ~40/s, reads from origin after cache misses ~386/s aggregate (or per-region splits). DynamoDB capacity auto-scaling easily supports these levels. Security and operational features - Rate limiting and abuse detection at edge to mitigate spam or bots. - Throttling of analytics writes during overload, sampling for extremely hot codes. - Access controls (OAuth/API tokens) for creating and managing short URLs. - Audit logs for deletions to meet the non-expiry guarantee unless explicitly deleted. Conclusion This design prioritizes redirect latency and availability via CDN edge caching + minimal edge logic, durable multi-region storage for permanent mappings, a simple and robust ID allocation and base62 encoding scheme (guaranteeing no collisions and <=7 chars), and a completely asynchronous analytics pipeline so that analytics never degrade redirect performance. The architecture scales horizontally, survives full DC outages via multi-region replication, and provides operational levers (cache sizing, CDN invalidation, sampling) to balance costs versus performance.