Design a Global URL Shortening Service

### 1. High-Level Architecture The system is designed as a globally distributed, multi-region service to ensure low latency and high availability. Each major region (e.g., US-East, EU-West, AP-Southeast) hosts a complete Point of Presence (PoP). **Components:** 1. **Global Load Balancer (GLB):** Uses latency-based DNS routing to direct users to the nearest healthy regional PoP. 2. **Regional PoP Stack:** * **API Gateway:** Terminates TLS, authenticates requests, and routes them to the appropriate backend service. * **Redirect Service:** A lightweight, highly-scaled service that handles `GET /{short_alias}` requests. It is optimized for speed. * **Write Service:** Handles link creation (`POST /api/v1/links`), including custom alias validation and unique ID generation. * **Analytics Service:** Provides access to link statistics via `GET /api/v1/links/{short_alias}/stats`. 3. **Data Infrastructure:** * **Global Database:** A strongly consistent, distributed database for the core link mapping. * **Regional Cache:** An in-memory cache in each region for hot links. * **Analytics Pipeline:** A message queue for event ingestion, a stream processor for aggregation, and a NoSQL database for storing and serving analytics data. **Data Flow:** * **Link Creation:** A user's `POST` request is routed to the nearest Write Service. The service generates or validates an alias and writes the `short_alias -> long_URL` mapping to the Global Database. The write is synchronously replicated across all regions within 2 seconds. * **Redirection:** A `GET` request is routed to the nearest Redirect Service. It first checks the Regional Cache. On a cache hit, it immediately issues a 301 redirect and asynchronously sends a click event to the analytics queue. On a miss, it queries the Global Database's local replica, populates the cache, then performs the redirect and event logging. * **Analytics:** Click events from all regions are published to a central message queue. A stream processor consumes these events, aggregates them into time-windowed statistics (total clicks, 24h clicks, country counts), and writes the results to the Analytics Database. ### 2. Storage Choices * **Link Mappings (Primary Storage):** * **Technology:** A globally distributed SQL database like Google Cloud Spanner or CockroachDB. * **Justification:** This choice is driven by the need for strong consistency on redirects and the <2 second global write propagation requirement. These databases provide synchronous replication and low-latency regional reads, justifying their higher cost for the core business function. The `short_alias` serves as the primary key for fast lookups. * **Cached Hot Links:** * **Technology:** A regional in-memory distributed cache like Redis Cluster. * **Justification:** With 8 billion daily reads and heavy traffic skew, a cache is essential for meeting the <80ms P95 latency target and protecting the database. Each region maintains its own cache using a cache-aside pattern. * **Analytics Data:** * **Ingestion Queue:** Apache Kafka or AWS Kinesis. This decouples the high-throughput redirect path from analytics processing and provides a durable buffer for click events. * **Serving Database:** A wide-column NoSQL store like Apache Cassandra or ScyllaDB. It is optimized for the high-write, time-series aggregation workload of analytics and is more cost-effective at scale for these query patterns than a relational database. ### 3. ID Generation and Alias Strategy We will use a 7-character alias from the alphabet `[a-zA-Z0-9]`, providing `62^7` (over 3.5 trillion) unique combinations. * **ID Generation:** A background service pre-generates a large pool of unique random IDs and stores them in a dedicated queue (e.g., a Redis list). The Write Service simply fetches a pre-generated ID from this pool when a new link is created. This approach is fast, scalable, and avoids on-the-fly collision checks during a user request. * **Custom Alias Handling:** When a user submits a custom alias, the Write Service attempts to `INSERT` it into the Global Database. The `short_alias` column is the primary key with a unique constraint. This atomically handles the check-and-set operation; if the alias is taken, the database rejects the write, and the service returns a `409 Conflict` error to the user. ### 4. API Design * **Create Link:** `POST /api/v1/links` * **Body:** `{ "long_url": "...", "custom_alias": "..." (optional), "expires_at": "..." (optional) }` * **Response:** `201 Created` with `{ "short_url": "...", "long_url": "..." }` * **Redirect:** `GET /{short_alias}` * **Response:** `301 Moved Permanently` with `Location: {long_url}` header for permanent links. `404 Not Found` if the alias doesn't exist or is expired. * **Get Analytics:** `GET /api/v1/links/{short_alias}/stats` * **Response:** `200 OK` with `{ "total_clicks": ..., "clicks_last_24h": ..., "top_countries": [...] }` ### 5. Scaling Approach * **Hot Keys:** A multi-layer caching strategy is employed. For extremely viral links, the `301` redirect response can be cached at the CDN layer. The primary defense is the regional Redis cache, which will absorb the majority of the skewed traffic. * **Partitioning:** The Global Database (Spanner/CockroachDB) automatically handles partitioning of link data by its primary key (`short_alias`). The Analytics Database (Cassandra) will be partitioned by `short_alias` to co-locate all stats for a given link, enabling efficient queries. * **Multi-Region Traffic:** The GLB ensures users are routed to their nearest PoP for low latency. The architecture is active-active, as writes can be handled by any region and are globally replicated by the database. This design maximizes resource utilization and availability. ### 6. Reliability Strategy * **Failover:** The GLB performs health checks and will automatically route traffic away from any unhealthy region. Within a region, load balancers will route around failed service instances. * **Data Replication:** The Global Database is configured to replicate data across multiple availability zones and regions, providing resilience against both instance and regional failures. The Cassandra cluster for analytics will also be deployed across multiple regions. * **Backup:** Automated, periodic snapshots of both the primary and analytics databases are taken and stored in durable object storage (e.g., AWS S3) for disaster recovery. * **Graceful Degradation:** The system is designed so that a failure in the non-critical analytics pipeline will not impact the core redirect functionality. The Redirect Service will continue to serve requests even if it cannot publish events to the message queue. ### 7. Trade-offs and Alternatives Rejected * **Alternative 1: Hash-based ID Generation (Rejected).** * **Concept:** Generate a short ID by hashing the long URL. If a collision occurs, add a salt and re-hash. * **Reason for Rejection:** This adds unpredictable latency and complexity to the write path. At 120 million writes per day, collision probability becomes significant, requiring multiple database lookups to find a unique ID. The chosen pre-generation strategy provides constant-time performance for ID acquisition during a user request. * **Alternative 2: Single-Master Relational Database (Rejected).** * **Concept:** Use a traditional database like PostgreSQL in a single primary region with read replicas in other regions. * **Reason for Rejection:** This design cannot meet the strict `<2 second` global write propagation requirement. Replication lag to distant read replicas would frequently exceed this threshold, meaning a newly created link would not be immediately available to all global users. The higher cost of a globally distributed database is justified to meet this core functional requirement.

GLOBAL URL SHORTENING SERVICE — SYSTEM DESIGN ───────────────────────────────────────── 1. HIGH-LEVEL ARCHITECTURE AND DATA FLOW ───────────────────────────────────────── The system is organized into three planes: the Write Path (link creation), the Read Path (redirect), and the Analytics Path (event ingestion and querying). Major components: - Global Anycast Load Balancer / CDN Edge (e.g., Cloudflare or AWS CloudFront with Lambda@Edge) - API Gateway + Auth layer (rate limiting, abuse prevention) - Link Creation Service (stateless, horizontally scalable) - Redirect Service (stateless, extremely latency-sensitive) - ID Generation Service (distributed, unique short-code producer) - Primary Link Store (globally replicated relational DB, e.g., CockroachDB or AWS Aurora Global) - Hot-Link Cache (Redis Cluster, per-region) - Analytics Ingest Queue (Kafka or AWS Kinesis, per-region) - Analytics Aggregation Workers (stream processors, e.g., Flink or Kafka Streams) - Analytics Store (columnar store, e.g., ClickHouse or Apache Druid) - Analytics Query Service (read-only API) - Object Storage for cold backups (S3-compatible) Write Path (link creation): 1. Client POSTs to the nearest regional API Gateway. 2. API Gateway authenticates and rate-limits the request, then forwards to the Link Creation Service. 3. Link Creation Service calls the ID Generation Service to obtain a unique short code (or validates a custom alias). 4. The record is written to the Primary Link Store with strong consistency in the local region; the global DB replication propagates the record to other regions within ~1–2 seconds, satisfying the "usable within 2 seconds globally" SLA. 5. Simultaneously, the new mapping is pushed to the regional Redis cache (write-through or pub/sub invalidation) so the first redirect in that region does not miss cache. 6. A 201 response with the short URL is returned to the client. Read Path (redirect): 1. Client issues GET /{shortCode} to the nearest edge node. 2. Edge node checks its own CDN cache (for extremely hot links, TTL ~5–10 seconds to respect expiration semantics). 3. On CDN miss, the request hits the regional Redirect Service. 4. Redirect Service checks the regional Redis cache (expected hit rate > 99% for hot links). 5. On Redis miss, the Redirect Service queries the local read replica of the Primary Link Store. 6. If the link is expired or not found, return 404/410. 7. Otherwise, issue HTTP 301 (permanent) or 302 (temporary) redirect. Use 302 by default so browsers do not cache indefinitely, preserving analytics accuracy. 8. Asynchronously emit a click event (shortCode, timestamp, country derived from IP, user-agent) to the regional Analytics Ingest Queue. This is fire-and-forget; it does not block the redirect response. Analytics Path: 1. Regional Kafka topics receive click events. 2. Flink/Kafka Streams jobs consume events and maintain rolling aggregates: total clicks (counter), clicks in last 24 hours (sliding window), and top-5 countries (approximate heavy-hitter sketch, e.g., Count-Min Sketch or SpaceSaving). 3. Aggregated results are written to ClickHouse (append-optimized columnar store) every 30–60 seconds. 4. The Analytics Query Service reads from ClickHouse and returns pre-aggregated results. Raw events are also retained in ClickHouse for ad-hoc queries. 5. Cross-region analytics aggregation: each region's Kafka cluster mirrors events to a central analytics region via Kafka MirrorMaker 2 or Kinesis cross-region replication. The central ClickHouse cluster holds the global view. ───────────────────────────────────────── 2. STORAGE CHOICES ───────────────────────────────────────── Link Mappings — CockroachDB (or Aurora Global DB): Rationale: We need strong consistency for writes (to prevent duplicate aliases) and low-latency reads globally. CockroachDB is a distributed SQL database with multi-region active-active support, serializable isolation, and automatic failover. Aurora Global DB is an alternative with a single primary writer and up to 5 read replicas in different regions with ~1 s replication lag. Either satisfies the 2-second global propagation SLA. Schema (simplified): links(short_code VARCHAR(12) PK, long_url TEXT NOT NULL, owner_id BIGINT, created_at TIMESTAMPTZ, expires_at TIMESTAMPTZ, is_custom BOOLEAN) Indexes: short_code (PK, clustered), owner_id + created_at (for user dashboards). Estimated size: 120M links/day × 365 days × ~300 bytes/row ≈ ~13 TB/year. Manageable with partitioning by created_at. Hot-Link Cache — Redis Cluster (per region): Each region runs a Redis Cluster with 3–6 shards and replicas. Cache entries: short_code → {long_url, expires_at}. TTL set to min(link expiration, 24 hours). Expected working set: the top 1% of links (~1.2M) account for ~80% of traffic. At ~500 bytes per entry, 1.2M entries ≈ 600 MB per region — very affordable. We use a write-through strategy on link creation and lazy population on first redirect miss. Analytics Events — Kafka + ClickHouse: Kafka retains raw click events for 7 days (replayability). ClickHouse stores both raw events (partitioned by date, sharded by short_code) and pre-aggregated materialized views. ClickHouse's columnar storage and vectorized execution make it ideal for the aggregation queries needed (SUM, COUNT, GROUP BY country, sliding window). Cold Backups — S3-compatible object storage: Daily snapshots of the link store and weekly ClickHouse exports are stored in object storage with versioning and cross-region replication for disaster recovery. ───────────────────────────────────────── 3. ID GENERATION AND ALIAS STRATEGY ───────────────────────────────────────── Short Code Format: Use 7 characters from a Base62 alphabet (a-z, A-Z, 0-9). Base62^7 = ~3.5 trillion combinations, far exceeding any foreseeable need (120M/day × 10 years = ~438B links). ID Generation Strategy — Distributed Counter + Encoding: We use a distributed counter approach rather than random generation to avoid collision storms at scale. Step 1: Each Link Creation Service instance acquires a block of IDs from a lightweight coordination service (e.g., a Redis INCRBY or a dedicated ID service backed by ZooKeeper). Each instance claims a block of 10,000 IDs at a time, reducing coordination overhead. Step 2: The numeric ID is Base62-encoded to produce the short code. A 7-character Base62 code can represent IDs up to ~3.5 trillion. Step 3: To prevent enumeration attacks and add unpredictability, XOR the numeric ID with a secret salt before encoding, or use a bijective scrambling function (Feistel cipher over the ID space). Custom Aliases: 1. Client submits desired alias (3–20 alphanumeric characters). 2. Link Creation Service attempts an INSERT with the custom alias as the short_code using a unique constraint in the DB. 3. If the INSERT fails due to a unique constraint violation, return HTTP 409 Conflict with a suggestion to try another alias. 4. Custom aliases bypass the ID generation service entirely. 5. Custom aliases are reserved in a separate namespace check (profanity list, reserved words like "api", "admin", "health") before the DB write. Collision Handling for Generated Codes: Because we use a monotonically increasing counter with bijective encoding, collisions are structurally impossible for generated codes. Collisions can only occur if a generated code happens to match a custom alias — this is handled by the unique constraint; the ID generation service simply increments to the next ID and retries (extremely rare). ───────────────────────────────────────── 4. API DESIGN ───────────────────────────────────────── All APIs are RESTful over HTTPS. Rate limiting is enforced at the API Gateway layer (e.g., 100 creates/minute per authenticated user, 10 creates/minute for anonymous users). POST /v1/links — Create Short Link Request body (JSON): long_url: string (required, must be a valid URL, max 2048 chars) custom_alias: string (optional, 3–20 alphanumeric chars) expires_at: ISO 8601 datetime (optional) owner_id: string (optional, from auth token) Response 201 Created: short_code: string short_url: string (e.g., "https://sho.rt/aB3xY7z") long_url: string expires_at: string or null created_at: string Response 400: invalid URL or alias format Response 409: custom alias already taken Response 429: rate limit exceeded GET /{shortCode} — Redirect No request body. Path parameter: shortCode. Response 302 Found with Location header set to long_url. Response 404: short code not found. Response 410 Gone: link has expired. This endpoint is served at the apex domain (e.g., sho.rt/{shortCode}) for minimal URL length. GET /v1/links/{shortCode}/analytics — Retrieve Analytics Auth required (owner or admin). Query parameters: none required (returns default summary) Response 200: short_code: string total_clicks: integer clicks_last_24h: integer top_countries: array of objects, each with country_code (ISO 3166-1 alpha-2) and click_count, sorted descending, max 5 entries last_updated: ISO 8601 datetime (indicates analytics freshness) Response 404: link not found. Response 403: not authorized. GET /v1/links/{shortCode} — Get Link Metadata (optional utility endpoint) Auth required. Response 200: full link object including long_url, created_at, expires_at, is_custom. DELETE /v1/links/{shortCode} — Delete / Deactivate Link Auth required (owner or admin). Response 204 No Content. Soft-deletes the record (sets a deleted_at timestamp) and invalidates the cache entry via pub/sub. ───────────────────────────────────────── 5. SCALING APPROACH ───────────────────────────────────────── Hot Key Problem: A small fraction of links (viral URLs, marketing campaigns) will receive millions of redirects per minute. Naive Redis sharding puts all traffic for one key on one shard. Mitigation: - Local in-process cache in each Redirect Service instance (e.g., Caffeine with a 10,000-entry LRU, TTL 5 seconds). This absorbs the hottest keys entirely within the process, eliminating Redis round-trips for the top ~0.1% of links. - CDN edge caching with a short TTL (5–10 seconds) for the redirect response itself. At 8B redirects/day, even a 90% CDN hit rate offloads 7.2B requests from origin. - Redis read replicas: promote hot-key shards to have more replicas and route reads round-robin. Caching Strategy: Three-tier cache: CDN edge → in-process LRU → Redis Cluster → DB read replica. Cache population: write-through on creation, lazy on first miss. Cache invalidation: on link deletion or expiration, publish an invalidation message to a Redis pub/sub channel; all Redirect Service instances subscribe and evict the key from their local LRU. CDN entries expire naturally via TTL. Partitioning: - Link Store: partition by short_code hash (CockroachDB handles this automatically via range-based sharding). No hot partitions because short codes are uniformly distributed after bijective scrambling. - Kafka: partition click events by short_code hash. This ensures all events for a given link go to the same partition, enabling stateful per-link aggregation without shuffles. - ClickHouse: shard by short_code, partition by date. Queries for a single link's analytics hit one shard; time-range queries benefit from partition pruning. Multi-Region Traffic: Deploy in three regions: US-East, EU-West, AP-Southeast (covers North America, Europe, Asia). - DNS-based GeoDNS or Anycast routes users to the nearest region. - Each region is fully independent for reads (Redirect Service + Redis + DB read replica). - Writes (link creation) go to the nearest region's Link Creation Service, which writes to the local node of the globally distributed DB. CockroachDB replicates to other regions within ~1–2 seconds. - Analytics events are processed regionally and mirrored to a central analytics cluster for global aggregation. Capacity Sketch: - 8B redirects/day = ~92,500 req/s average, ~300,000 req/s at peak (3x factor). - With 90% CDN hit rate: ~30,000 req/s to origin across 3 regions = ~10,000 req/s per region. - Each Redirect Service instance can handle ~5,000 req/s (mostly cache hits, minimal CPU). ~2–4 instances per region at average load, auto-scaling to 20+ at peak. - 120M writes/day = ~1,400 writes/s average. Link Creation Service is not the bottleneck. ───────────────────────────────────────── 6. RELIABILITY STRATEGY ───────────────────────────────────────── Availability Target: 99.99% = ~52 minutes downtime/year. Failover: - Each region runs multiple instances of every stateless service behind a regional load balancer with health checks (fail open: remove unhealthy instances within 10 seconds). - Redis Cluster uses automatic failover: if a primary shard fails, a replica is promoted within ~15 seconds. During this window, Redirect Service falls back to the DB read replica (slightly higher latency but correct). - If an entire region fails, GeoDNS detects the failure via health probes and reroutes traffic to the next-nearest region within ~30–60 seconds. The remaining regions must absorb the load; auto-scaling handles this. - CockroachDB / Aurora Global DB: automatic failover to another region's node if the primary region is unavailable. For Aurora, this involves a manual or automated promotion of a read replica to primary (RTO ~1 minute with automation). Data Replication: - Link Store: synchronous replication within a region (at least 2 nodes), asynchronous cross-region replication (CockroachDB consensus across regions, or Aurora Global DB ~1 s lag). We accept eventual consistency for cross-region reads because the 2-second propagation SLA is met. - Redis: each shard has at least one replica in the same region. No cross-region Redis replication (Redis is a cache; the DB is the source of truth). - Kafka: replication factor 3 within each region. Cross-region mirroring for analytics only (not for redirect correctness). - ClickHouse: replicated within the analytics region using ClickHouse Keeper (ZooKeeper replacement). No multi-region ClickHouse replication needed since analytics are eventually consistent. Backup: - Daily logical backups of the Link Store to object storage (S3), retained for 30 days. - Weekly full ClickHouse exports to object storage, retained for 90 days. - Kafka topic data retained for 7 days (acts as a replay buffer for analytics recovery). - Backup restoration is tested monthly via automated restore drills in a staging environment. Degradation Behavior: - If Redis is unavailable: Redirect Service falls back to DB read replicas. Latency increases but correctness is maintained. Alert and auto-scale DB read replicas. - If the Analytics Queue is unavailable: click events are dropped (analytics are eventually consistent; we accept this loss). Redirects are never blocked by analytics failures. A circuit breaker in the Redirect Service disables event emission if the queue is unhealthy. - If the Link Store primary is unavailable: new link creation fails (return 503). Redirects continue using cached data and read replicas. This is acceptable because creation is less critical than redirect availability. - If a region is fully down: GeoDNS failover to adjacent region. Users experience higher latency but the service remains available. - Rate limiting and abuse detection at the API Gateway prevent DDoS from overwhelming the system. ───────────────────────────────────────── 7. KEY TRADE-OFFS AND REJECTED ALTERNATIVES ───────────────────────────────────────── Trade-off 1: 302 vs. 301 Redirects We chose 302 (temporary redirect) as the default. 301 (permanent) would allow browsers to cache the redirect indefinitely, reducing origin load. However, 301 makes it impossible to track repeat clicks from the same browser, breaks analytics, and prevents us from updating or expiring links (the browser would serve the cached redirect forever). The cost of 302 is higher origin traffic, which we mitigate with CDN and in-process caching. For links explicitly marked as permanent by the owner (and with no expiration), we could offer 301 as an opt-in, but the default is 302. Trade-off 2: Random Short Codes vs. Counter-Based Encoding Rejected: Generating random 7-character Base62 strings and checking for collisions in the DB. Reason for rejection: At 120M links/day and a 3.5T code space, the collision probability starts low but grows over time. More importantly, each creation requires a DB read to check for collision, then a write — two round-trips under contention. With a counter-based approach, the ID is guaranteed unique by construction; no collision check is needed. The counter service is a minor coordination overhead but is far cheaper than DB collision checks at scale. The bijective scrambling step preserves the unpredictability benefit of random codes. Trade-off 3: Synchronous Analytics vs. Asynchronous Queue Rejected: Writing click events synchronously to the analytics DB during the redirect request. Reason for rejection: This would add 10–50 ms of latency to every redirect (a ClickHouse or analytics DB write in the critical path), violating the P95 < 80 ms SLA. It also creates a hard dependency between redirect availability and analytics availability. The asynchronous queue approach decouples these concerns entirely. The cost is that analytics are eventually consistent (30–60 second lag), which is explicitly acceptable per the requirements. Trade-off 4: Single Global DB vs. Multi-Region Active-Active DB We chose a globally distributed DB (CockroachDB or Aurora Global) over a single-region primary with read replicas everywhere. A single-region primary would give us simpler consistency semantics but would make all writes go to one region (high latency for users in other regions creating links, and a single point of failure for writes). The globally distributed DB costs more and adds operational complexity, but it is justified because link creation latency and write availability are important for the user experience and the 99.99% availability target. Trade-off 5: ClickHouse vs. a Time-Series DB (e.g., InfluxDB) for Analytics Rejected: InfluxDB or TimescaleDB for analytics storage. Reason for rejection: Time-series databases are optimized for metrics with a fixed tag set. Our analytics queries require flexible GROUP BY country, arbitrary time windows, and potentially joining with link metadata. ClickHouse's columnar storage, SQL interface, and materialized views handle these patterns more naturally and at higher scale. ClickHouse also supports approximate aggregations (quantiles, heavy-hitters) natively, which is useful for the top-5-countries query at scale. ───────────────────────────────────────── SUMMARY OF BUDGET JUSTIFICATION ───────────────────────────────────────── Spend more on: - Multi-region Redis clusters: redirect latency is the core SLA; cache misses are expensive. - Globally distributed Link Store (CockroachDB / Aurora Global): correctness of redirects and 2-second global propagation require this. - CDN edge capacity: the single highest-leverage investment for redirect latency and availability. - Auto-scaling for Redirect Service: traffic is highly variable and spiky. Spend less on: - Analytics infrastructure: eventual consistency is acceptable; a single central ClickHouse cluster with replication is sufficient. No need for multi-region analytics replication. - Link Creation Service: write volume is ~1,400/s, trivially handled by a few instances. - Cold storage / backups: object storage is cheap; over-provision retention rather than under-provision. - Cross-region Redis replication: Redis is a cache backed by the DB; cross-region replication adds cost and complexity with minimal benefit since the DB already replicates.