Design a URL Shortening Service for Global Read Traffic

## URL Shortening Service Design ### 1. High-Level Architecture and Main Components The system will be composed of several microservices, deployed across multiple availability zones and regions for high availability and low latency. * **API Gateway:** Handles incoming requests, authentication, rate limiting, and routes requests to appropriate services. * **Link Creation Service:** Responsible for generating short URLs, storing them, and handling custom aliases. It interacts with the ID Generation Service and the Metadata Database. * **Link Resolution Service:** Handles incoming redirect requests. It fetches the long URL from the cache or database and performs the redirect. It also logs click events. * **Analytics Service:** Processes click logs, aggregates data, and provides analytics reports. * **ID Generation Service:** Generates unique short IDs for URLs. This can be a separate, highly available service. * **Click Logging Service:** A high-throughput service responsible for ingesting raw click events. * **Web UI/Admin Panel:** For users to create links, manage them, and view analytics. **Architecture Diagram (Conceptual):** ``` +-----------------+ +-----------------+ +-----------------------+ | Load Balancer |----->| API Gateway |----->| Link Creation Service | +-----------------+ +-----------------+ +-----------------------+ | | (Redirects) v +-----------------+ +-----------------+ +-----------------------+ | Load Balancer |----->| Link Resolution | +-----------------+ | Service | +-----------------+ | | (Click Events) v +-----------------------+ | Click Logging Service | +-----------------------+ | | (Raw Logs) v +-----------------------+ | Message Queue | +-----------------------+ | | (Processed Data) v +-----------------------+ | Analytics Service | +-----------------------+ | | (Analytics Data) v +-----------------------+ | Analytics Database | +-----------------------+ **Databases:** * **Metadata Database:** Stores short URL to long URL mappings, custom aliases, creation timestamps, expiration times, and user information. * **Analytics Database:** Stores aggregated click data per link. * **ID Generation Database/Service:** For generating unique IDs. **Caching:** * **Read Cache:** For frequently accessed short URLs to speed up redirects. **Message Queue/Stream:** * For decoupling click logging from the redirect path and enabling asynchronous processing for analytics. ``` ### 2. Core Data Model and Storage Choices **Metadata Database:** * **Choice:** A distributed NoSQL database like Cassandra or a sharded relational database (e.g., PostgreSQL with Citus) for scalability and availability. * **Schema:** * `links` table/collection: * `short_id` (string, primary key): The unique short identifier. * `long_url` (string): The original long URL. * `user_id` (string, optional): Identifier for the user who created the link. * `created_at` (timestamp): When the link was created. * `expires_at` (timestamp, optional): When the link expires. * `custom_alias` (string, optional, unique index): User-defined alias. * `updated_at` (timestamp, optional): Last update time (for the 10-minute update window). * `destination_updated_at` (timestamp, optional): Timestamp of the last destination URL update. **Analytics Database:** * **Choice:** A time-series database (e.g., InfluxDB, TimescaleDB) or a data warehouse (e.g., Snowflake, BigQuery) for efficient aggregation and querying of time-based data. * **Schema:** * `click_analytics` table/collection: * `short_id` (string, indexed). * `timestamp` (timestamp, indexed). * `country_code` (string, optional). * `device_type` (string, optional). * `aggregated_count` (integer): For pre-aggregated data. **ID Generation:** * **Choice:** A dedicated distributed ID generation service (e.g., using Snowflake algorithm or a database sequence with a dedicated service). This ensures uniqueness and high availability. **Click Logs:** * **Choice:** A high-throughput message queue (e.g., Kafka, AWS Kinesis) to buffer raw click events before they are processed by the Analytics Service. ### 3. API Design **Base URL:** `https://short.url/api/v1` **1. Create Link:** * **Endpoint:** `POST /links` * **Request Body:** ```json { "long_url": "https://example.com/very/long/url", "custom_alias": "my-custom-alias" // Optional "expires_at": "2023-12-31T23:59:59Z" // Optional } ``` * **Response Body:** ```json { "short_url": "https://short.url/xyz123", "long_url": "https://example.com/very/long/url", "custom_alias": "my-custom-alias" // If provided } ``` **2. Resolve Link (Redirect):** * **Endpoint:** `GET /{short_id}` or `GET /{custom_alias}` * **Logic:** The Link Resolution Service will handle this. It will look up the `short_id` or `custom_alias` in the cache first. If not found, it queries the Metadata Database. After fetching the `long_url`, it logs the click event and returns a 301 (Permanent Redirect) or 302 (Temporary Redirect) to the `long_url`. * **Abuse Prevention:** Basic checks for known malicious patterns or blacklisted URLs can be performed here. **3. Get Link Analytics:** * **Endpoint:** `GET /links/{short_id}/analytics` * **Query Parameters:** * `start_time` (timestamp, required) * `end_time` (timestamp, required) * `group_by` (string, optional, e.g., "day", "country") * **Response Body:** ```json { "short_id": "xyz123", "total_clicks": 1500, "clicks_over_time": [ {"timestamp": "2023-10-27T10:00:00Z", "count": 50}, {"timestamp": "2023-10-27T11:00:00Z", "count": 75} ], "clicks_by_country": [ {"country": "US", "count": 1000}, {"country": "EU", "count": 500} ] } ``` **4. Update Link Destination (within 10 mins of creation):** * **Endpoint:** `PUT /links/{short_id}` * **Request Body:** ```json { "long_url": "https://new.example.com/updated/url" } ``` * **Response:** 200 OK or error. ### 4. Scaling Strategy * **Read Traffic (Redirects):** * **Caching:** Aggressively cache `short_id` to `long_url` mappings in a distributed cache (e.g., Redis, Memcached) with a short TTL (e.g., 5-10 minutes) to handle bursts. Cache misses will hit the database. * **Database Sharding:** The Metadata Database will be sharded by `short_id` or a hash of it to distribute load. * **Read Replicas:** Use read replicas for the Metadata Database to offload read traffic. * **Global Distribution:** Deploy Link Resolution Service instances in multiple regions close to users. Use GeoDNS to route users to the nearest region. * **Write Traffic (Link Creation):** * **Stateless Services:** Link Creation Service instances should be stateless, allowing easy horizontal scaling. * **ID Generation Service:** Must be highly available and scalable to handle the rate of new link creations. * **Analytics Traffic:** * **Asynchronous Processing:** Use a message queue (Kafka, Kinesis) to buffer click events. This decouples the redirect path from analytics processing. * **Scalable Analytics Pipeline:** The Analytics Service can scale horizontally to process messages from the queue and update the Analytics Database. * **Data Warehousing:** For large-scale analytics, a data warehouse is more suitable than a traditional RDBMS. ### 5. Reliability and Disaster Recovery * **Multi-AZ Deployment:** All services and databases will be deployed across multiple Availability Zones within a region. * **Multi-Region Deployment:** For critical services (Link Resolution, API Gateway), deploy across multiple geographic regions. Use GeoDNS for failover. * **Data Replication:** Databases will have replication enabled (e.g., multi-master or primary-replica with automatic failover). * **Idempotency:** Ensure critical operations (like link creation) are idempotent to handle retries safely. * **Graceful Degradation:** If the Analytics Service is down, redirects should continue to function. If the Metadata Database is slow, cache performance might degrade, but redirects should still work if cached. * **Backups:** Regular automated backups of all persistent data. ### 6. Key Trade-offs * **ID Generation:** * **Centralized (e.g., Snowflake):** Guarantees uniqueness, good performance, but introduces a dependency on the ID service. Can be a single point of failure if not highly available. * **Database Auto-increment:** Simple, but can be a bottleneck and harder to scale across shards/regions. * **Random Hash:** Simpler to generate, but requires collision detection and might lead to longer IDs if not carefully designed. * **Chosen:** Distributed ID generation service (e.g., Snowflake-like) for balance of uniqueness, performance, and availability. * **Database Selection:** * **NoSQL (Cassandra):** Excellent for high write throughput and horizontal scalability, good for availability. Schema flexibility. Can be complex to manage. * **Relational (Sharded PostgreSQL):** Strong consistency, familiar SQL interface. Sharding adds complexity. * **Chosen:** Cassandra for Metadata (high write/read, availability) and a Time-Series DB/Data Warehouse for Analytics (query performance). * **Caching:** * **Cache Invalidation Strategy:** Cache-aside with TTL is common. For updates (within 10 mins), explicit invalidation is needed. For expiration, TTL handles it. * **Consistency vs. Availability:** Aggressive caching improves availability and latency but can lead to stale data if not invalidated properly. * **Chosen:** Cache-aside with short TTLs for `short_id` to `long_url` mappings. Invalidate on updates. * **Consistency:** * **Eventual Consistency:** Acceptable for analytics. For link resolution, strong consistency is preferred but can be relaxed with caching. * **Link Creation:** Strong consistency for `short_id` uniqueness. Custom aliases might have a slight delay in propagation across replicas. * **Chosen:** Eventual consistency for analytics. Strong consistency for ID generation and link creation uniqueness. Relaxed consistency for link resolution via caching. * **Analytics Pipeline:** * **Real-time vs. Near Real-time:** The requirement is ~5 mins. This is achievable with stream processing (e.g., Kafka Streams, Flink) or micro-batching. * **Complexity:** A full real-time pipeline is complex. A batch processing approach (e.g., daily aggregation) is simpler but doesn't meet the 5-minute requirement. * **Chosen:** Kafka + stream processing (e.g., Flink or Spark Streaming) for near real-time aggregation into the Analytics Database. ### 7. Monitoring and Failure Detection * **Key Metrics:** * **Latency:** P95/P99 latency for API Gateway, Link Creation, Link Resolution, and Analytics APIs. * **Error Rates:** HTTP 5xx and 4xx error rates for all services. * **Throughput:** Requests per second for link creation and resolution. * **Resource Utilization:** CPU, memory, network I/O, disk I/O for all services and databases. * **Cache Hit Rate:** For the read cache. * **Queue Depth:** For the message queue. * **Database Performance:** Query latency, connection counts, replication lag. * **Tools:** * **Metrics Collection:** Prometheus, Datadog, CloudWatch. * **Logging:** Centralized logging system (e.g., ELK stack, Splunk, CloudWatch Logs). * **Tracing:** Distributed tracing (e.g., Jaeger, Zipkin) to track requests across services. * **Alerting:** Alertmanager, PagerDuty for critical issues. * **Failure Detection:** * **Health Checks:** Implement deep health checks for all services and dependencies. * **Synthetic Monitoring:** Regularly ping critical endpoints (e.g., create link, resolve a known link) from external locations. * **Anomaly Detection:** Monitor metrics for sudden spikes or drops that deviate from normal patterns. * **Automated Rollbacks:** Configure CI/CD pipelines to automatically roll back deployments if critical alerts are triggered. * **Chaos Engineering:** Periodically inject failures (e.g., network latency, service outages) in a controlled environment to test resilience.

High-Level Architecture and Main Components The system is organized into several layers deployed across at least two geographic regions (US-East and EU-West) behind a global anycast DNS or a global load balancer such as AWS Global Accelerator or Cloudflare. 1. Edge and CDN Layer: A global load balancer routes users to the nearest regional cluster. A CDN or edge cache (Cloudflare Workers, CloudFront) caches popular redirect mappings at the edge to achieve sub-80ms P95 latency. 2. API Gateway and Rate Limiter: Each region runs an API gateway that handles authentication, rate limiting, and request routing. Rate limiting uses a sliding-window counter backed by Redis to throttle abusive creation patterns. 3. Link Creation Service: Stateless service behind the API gateway. Accepts long URLs, optional custom aliases, optional expiry, and returns a short code. Writes to the primary database and invalidates or warms the cache. 4. Redirect Service: The hottest path. Receives GET requests on short codes, looks up the destination URL (cache first, then database), issues an HTTP 301 or 302 redirect, and emits a click event to the analytics pipeline. Uses 302 redirects so the service always sees the request for analytics, but returns a Cache-Control header with a short TTL (e.g., 60s) so browsers and CDN edges can cache. 5. Analytics Pipeline: Click events are published to a distributed stream (Kafka or AWS Kinesis). A stream processor (Flink or Kafka Streams) aggregates clicks per link in tumbling windows of one minute and writes rollups to an analytics store. A simple API serves aggregated analytics. 6. Abuse Prevention Service: On link creation, the destination URL is checked against Google Safe Browsing API and an internal blocklist. A lightweight ML scorer flags suspicious patterns (bulk creation, known spam domains). Flagged links are held for review or rejected. 7. Expiry and Cleanup Worker: A periodic job (cron or scheduled Lambda) scans for expired links and soft-deletes them, removing them from the cache. Core Data Model and Storage Choices Primary Link Store: A distributed NoSQL database such as Amazon DynamoDB or Apache Cassandra. The table is keyed by short_code (partition key). Schema fields: short_code (string, primary key), long_url (string), user_id (string), created_at (timestamp), expires_at (timestamp, nullable), custom_alias (boolean), updated_at (timestamp). DynamoDB is chosen for its single-digit-millisecond reads, automatic multi-region replication via Global Tables, and managed scaling. Cassandra is an alternative for teams wanting to avoid vendor lock-in. Cache Layer: Redis Cluster (or ElastiCache) in each region. Cache entry: short_code -> long_url with a TTL matching the link expiry or a default of 24 hours. Cache-aside pattern: redirect service checks Redis first; on miss, reads from DynamoDB and populates Redis. Analytics Store: A time-series or columnar store. ClickHouse or Amazon Timestream stores per-link click aggregates with dimensions: short_code, timestamp_bucket, country, referrer, device_type. Pre-aggregated rollups at 1-minute, 1-hour, and 1-day granularity. User and Account Store: A relational database (PostgreSQL via RDS) stores user accounts, API keys, billing, and link ownership metadata. This is lower traffic and benefits from strong consistency and relational queries. API Design Create Short Link: POST /api/v1/links. Request body: long_url (required), custom_alias (optional), expires_at (optional). Response: 201 Created with short_code, short_url, created_at, expires_at. Errors: 409 Conflict if custom alias taken, 400 if URL invalid, 403 if abuse detected. Update Destination URL: PATCH /api/v1/links/{short_code}. Request body: long_url. Allowed only within 10 minutes of created_at. Response: 200 OK with updated record. Error: 403 if outside the 10-minute window or not the owner. Resolve (Redirect): GET /{short_code}. Response: 302 Found with Location header set to long_url. If expired or not found: 404. The redirect service also sets response headers for cache control. Read Analytics: GET /api/v1/links/{short_code}/analytics?start=...&end=...&granularity=hour. Response: 200 OK with array of time-bucketed click counts, top countries, top referrers. Delete Link: DELETE /api/v1/links/{short_code}. Soft-deletes the link and invalidates cache. ID Generation Strategy Short codes are 7 characters from a base-62 alphabet (a-z, A-Z, 0-9), giving roughly 3.5 trillion possible codes, far exceeding the expected link volume over many years. Generation approach: Each service instance is assigned a unique worker ID (from a coordination service or configuration). A Snowflake-like ID generator produces a 64-bit unique integer combining a timestamp component, worker ID, and sequence number. The integer is then base-62 encoded and truncated or padded to 7 characters. This avoids coordination on every write and guarantees uniqueness. For custom aliases, the service attempts an insert with a uniqueness constraint; on conflict it returns 409. Scaling Strategy for Traffic Growth and Burst Handling Steady-state math: 1.5 billion redirects per month is roughly 580 requests per second average, with peaks during news events potentially reaching 10-50x, so the redirect path must handle at least 30,000 RPS per region. Link creation at 120 million per month is about 46 RPS average. Redirect path scaling: The redirect service is stateless and horizontally scalable behind an auto-scaling group. Redis handles the vast majority of reads; DynamoDB on-demand capacity handles cache misses. The CDN edge cache absorbs a large fraction of repeat requests for viral links, reducing origin load. Burst handling: Auto-scaling policies based on CPU and request count with aggressive scale-out (add 50 percent capacity in 60 seconds). Redis cluster can be pre-scaled with read replicas. DynamoDB on-demand mode absorbs burst writes and reads without pre-provisioning. The CDN naturally absorbs burst read traffic for hot links. Creation path scaling: Less bursty but still auto-scaled. Writes go to the regional DynamoDB Global Table, which replicates asynchronously to other regions. Analytics pipeline scaling: Kafka partitions are keyed by short_code for parallelism. Flink consumer group scales horizontally. ClickHouse cluster can add shards for query throughput. Reliability and Disaster Recovery Multi-region active-active: DynamoDB Global Tables replicate data across US-East and EU-West with last-writer-wins conflict resolution. Both regions serve reads and writes. If one region fails, DNS health checks (Route 53 or equivalent) route all traffic to the surviving region within seconds. Redis replication: Each region has its own Redis cluster populated from the local DynamoDB replica. If Redis fails, the redirect service falls back to DynamoDB reads with slightly higher latency. Kafka durability: Kafka topics have replication factor 3 with min.insync.replicas=2. If the analytics pipeline lags, click events are retained in Kafka for at least 72 hours for replay. Backups: DynamoDB point-in-time recovery is enabled. PostgreSQL has automated daily snapshots with cross-region replication. ClickHouse data is backed up to S3 daily. Graceful degradation: If the abuse checking service is slow, creation requests proceed with a flag for async review rather than blocking. If the analytics pipeline is down, redirects continue unaffected; click events queue in Kafka. Key Trade-offs ID generation: Snowflake-style IDs avoid a centralized counter bottleneck but require worker ID coordination. Base-62 encoding of 64-bit IDs yields short, URL-safe codes. Trade-off: slightly longer codes (7 chars) than strictly necessary to avoid collisions and allow future growth. Database selection: DynamoDB chosen for managed scaling, low-latency reads, and built-in global replication. Trade-off: eventual consistency across regions (acceptable since link creation is not latency-critical across regions, and redirects in the same region are consistent). Cassandra would offer similar properties with more operational burden but no vendor lock-in. Caching: Cache-aside with Redis provides sub-millisecond reads for hot links. Trade-off: cache invalidation on URL updates within the 10-minute window requires explicit invalidation across regions, introducing a brief window of stale data (mitigated by short cache TTLs for recently created links, e.g., 30 seconds for links less than 10 minutes old). Consistency: The system favors availability and partition tolerance (AP in CAP terms). Redirect reads are eventually consistent, which is acceptable. The 10-minute update window is enforced at the application layer; in rare split-brain scenarios, a stale redirect could occur briefly. Analytics pipeline: Kafka plus Flink plus ClickHouse provides near-real-time analytics within the 5-minute SLA. Trade-off: this adds operational complexity. A simpler alternative would be writing click logs to S3 and querying with Athena, but that would not meet the 5-minute freshness requirement. 302 vs 301 redirects: 302 (temporary) is used so the service sees every click for analytics. Trade-off: slightly higher latency for repeat visitors compared to 301, but the CDN edge cache with a 60-second TTL mitigates this while still capturing most clicks. Monitoring and Failure Detection Metrics: Every service emits metrics to a time-series monitoring system (Prometheus plus Grafana, or CloudWatch). Key metrics include redirect P50, P95, and P99 latency; cache hit ratio (target above 95 percent); DynamoDB read and write consumed capacity; Kafka consumer lag; error rates by endpoint; link creation rate. Alerting: PagerDuty alerts on redirect P95 latency exceeding 80ms, cache hit ratio dropping below 90 percent, Kafka consumer lag exceeding 5 minutes (analytics SLA), error rate above 1 percent on any endpoint, and any region health check failure. Distributed tracing: OpenTelemetry traces across the redirect path (edge to cache to database to response) to diagnose latency regressions. Synthetic monitoring: Canary requests from multiple geographic locations continuously create and resolve short links, alerting if end-to-end latency or correctness degrades. Log aggregation: Structured logs shipped to a centralized system (ELK or CloudWatch Logs) for debugging and audit trails. Health checks: Each service exposes a health endpoint. The load balancer removes unhealthy instances. Cross-region health checks trigger DNS failover. Additional Assumptions: Users authenticate via API keys for link creation and analytics. Anonymous link creation is rate-limited by IP. The system runs on AWS but the design is portable. Short codes are case-sensitive. The service does not need to support billions of concurrent active links in the near term, but the 7-character code space allows growth to trillions.