Design a URL Shortening Service

URL Shortening Service — High-Level Design FUNCTIONAL REQUIREMENTS Users can submit a long URL and receive a unique short code (e.g., https://short.ly/aB3xYz). Visiting the short URL redirects the browser to the original destination. Short links optionally expire after a configurable TTL. Users may optionally request a custom alias. A basic click counter is maintained per link. NON-FUNCTIONAL REQUIREMENTS The system must handle roughly 20 million writes and 200 million reads per month, translating to about 8 writes/second and 80 reads/second on average, with peaks several times higher. Redirect latency should be under 50 ms at the 95th percentile. The service must be highly available (target 99.9% uptime). Short codes must be globally unique. The system should be horizontally scalable and tolerate single-node failures gracefully. API ENDPOINTS POST /api/links accepts a JSON body with fields: longUrl (required), customAlias (optional), ttlDays (optional). It returns a JSON response containing shortCode and shortUrl. This is the write path. GET /{shortCode} is the redirect endpoint. The server looks up the code and responds with HTTP 301 (permanent) or 302 (temporary, preferred for analytics) to the original URL. GET /api/links/{shortCode} returns metadata: original URL, creation time, expiry, click count. DELETE /api/links/{shortCode} marks a link as deleted (soft delete). DATA MODEL A single primary table, links, holds the core data. Key columns: short_code (varchar, primary key), long_url (text, not null), created_at (timestamp), expires_at (timestamp, nullable), is_deleted (boolean, default false), click_count (integer, default 0), owner_id (varchar, nullable for anonymous links). An index on expires_at supports efficient expiry sweeps. If custom aliases are supported, short_code is simply set to the user-supplied value after a uniqueness check. SHORT CODE GENERATION The default approach uses a base-62 encoding (characters a-z, A-Z, 0-9) of a unique integer ID. A 7-character base-62 code gives 62^7 ≈ 3.5 trillion possible codes, far exceeding foreseeable demand. The integer ID is produced by a distributed ID generator such as a Snowflake-style service or a database sequence. This guarantees uniqueness without coordination overhead at the application layer. On write, the application encodes the generated ID to produce the short code and stores both. For custom aliases, the application checks for an existing row with that short_code before inserting; if taken, it returns a conflict error to the caller. READ AND WRITE FLOW Write path: The client POSTs to the API service. The service validates the URL (basic format check, optional blocklist check). It obtains a new unique ID from the ID generator, encodes it to a short code, and inserts a row into the primary database. The new mapping is optionally pre-warmed into the cache. The short URL is returned to the client. Read path: The client issues GET /{shortCode}. The API service first checks the distributed cache (Redis). On a cache hit, it returns the 302 redirect immediately and asynchronously increments the click counter. On a cache miss, it queries the primary database, writes the result to the cache with a TTL (e.g., 24 hours), then redirects. If the code is not found, expired, or deleted, it returns 404. STORAGE AND CACHING Primary storage is a relational database (PostgreSQL or MySQL) for its strong consistency, ACID guarantees, and straightforward unique-key enforcement. At 20 million links per month and a modest row size (~500 bytes), one year of data is roughly 120 GB — easily manageable on a single primary with read replicas. A distributed in-memory cache (Redis) sits in front of the database for the read path. Given that a small fraction of links account for most traffic (power-law distribution), a cache with an LRU eviction policy and a 24-hour TTL will achieve a high hit rate with modest memory. Estimating 10 million hot links at ~200 bytes each requires only about 2 GB of cache memory. Click counts are buffered in Redis (INCR) and flushed to the database periodically to avoid write amplification. SCALING FOR HEAVY READ TRAFFIC The API tier is stateless and scales horizontally behind a load balancer. Read replicas of the database absorb read queries that miss the cache. The cache cluster (Redis Cluster) can be sharded by short_code. A CDN can be placed in front of the redirect endpoint for the most popular links, serving the 302 response from edge nodes without hitting the origin at all. Because 302 responses are not cached by browsers by default, the CDN must be configured to cache them for a short duration (e.g., 60 seconds) to be effective. HANDLING EXPIRED OR DELETED LINKS Expiry is checked at read time: if expires_at is in the past or is_deleted is true, the service returns 404 and removes the entry from the cache. A background job runs periodically (e.g., nightly) to hard-delete or archive rows where expires_at has passed, keeping the active dataset small and index scans fast. Soft deletes (is_deleted flag) allow for audit trails and potential recovery before permanent removal. ABUSE PREVENTION AND RATE LIMITING Rate limiting is enforced at the API gateway layer using a token bucket or sliding window algorithm keyed on IP address and, for authenticated users, on user ID. Reasonable defaults: 10 writes per minute per IP for anonymous users, higher limits for authenticated accounts. On the write path, submitted URLs are checked against a blocklist of known malicious or phishing domains (maintained as a Redis set or a small in-memory trie). CAPTCHA or email verification can be required for bulk or suspicious submission patterns. Short codes that receive an unusual spike of 404 responses (e.g., enumeration attacks) can trigger temporary IP blocks. RELIABILITY AND BOTTLENECKS The primary database is the most critical single point of failure. Mitigation: synchronous replication to at least one standby with automatic failover (e.g., using a tool like Patroni). The cache layer improves availability by serving reads even during brief database degradation. The ID generator must itself be highly available; a Snowflake-style generator embedded in each API node (using node ID + timestamp + sequence) eliminates this as a separate dependency. Likely bottlenecks: the database write path during traffic spikes (mitigated by connection pooling and write batching where possible), and cache eviction under a sudden surge of unique short codes (mitigated by pre-warming popular links and tuning cache size). TRADE-OFFS AND ASSUMPTIONS Using 302 (temporary) redirects instead of 301 (permanent) means browsers do not cache the redirect, so every visit hits the service. This is intentional: it enables accurate click counting and allows links to be updated or deleted. The trade-off is slightly higher latency and load compared to 301. Base-62 encoding of a sequential ID leaks approximate creation order; if that is a concern, the ID can be hashed or a random code can be generated with a uniqueness check (retry on collision). The design assumes anonymous link creation is allowed; adding authentication would improve abuse control but reduces accessibility. Click counts use eventual consistency (buffered in Redis, flushed asynchronously) rather than strict transactional increments, accepting minor inaccuracies in exchange for much lower write load on the database. Custom aliases are supported but treated as a minority use case; they do not affect the core generation pipeline.

## URL Shortening Service Design This document outlines a high-level design for a public URL shortening service. ### Core Functional Requirements: 1. **Shorten URL**: Users can submit a long URL and receive a unique short code. 2. **Redirect**: Visitors accessing a short URL are redirected to the original long URL. 3. **Custom Aliases (Optional)**: Users can optionally specify a custom alias for their short code. ### Key Non-Functional Requirements: 1. **High Availability**: The service must be available with minimal downtime. 2. **Low Latency**: Both shortening and redirection should be fast. 3. **Scalability**: The system must handle a large and growing number of requests (20M new links/month, 200M redirects/month). 4. **Durability**: Shortened URLs and their mappings should not be lost. 5. **Consistency**: While strong consistency for writes is ideal, eventual consistency might be acceptable for reads in some scenarios. ### Main API Endpoints: * **POST /shorten** * **Request Body**: `{"url": "<long_url>", "alias": "<custom_alias_optional>"}` * **Response Body**: `{"short_code": "<short_code>", "short_url": "<short_url>"}` * **Description**: Creates a new short URL. If an alias is provided and available, it's used; otherwise, a unique short code is generated. * **GET /{short_code}** * **Response**: HTTP 301 (Permanent Redirect) or 302 (Temporary Redirect) to the original URL. * **Description**: Redirects the user to the original long URL associated with the `short_code`. * **DELETE /{short_code}** (Optional, for management) * **Description**: Deletes a short URL mapping. ### Data Model: We can use a NoSQL database like Cassandra or DynamoDB for its scalability and availability. The schema would be: * **Table: `urls`** * `short_code` (Primary Key, String) * `long_url` (String) * `created_at` (Timestamp) * `user_id` (String, optional, for tracking ownership) * `is_active` (Boolean, for handling deletions) * `alias` (String, optional, indexed if used for lookup) ### Short Code Generation and Uniqueness: Generating unique short codes is crucial. Several approaches: 1. **Base-62 Encoding of Incremental IDs**: A common and efficient method. We can use a distributed counter service (e.g., Apache ZooKeeper or a custom-built service using Redis or a database) to generate unique, ever-increasing 64-bit integers. These integers are then encoded into a base-62 string (0-9, a-z, A-Z). This guarantees uniqueness and provides short codes of a predictable length (e.g., 7-8 characters for billions of IDs). 2. **Hashing**: Hashing the `long_url` (e.g., using MD5 or SHA-1) and taking the first few characters. Collisions must be handled by checking for existing entries. If a collision occurs, append a unique suffix or try a different hash. For this design, **Base-62 encoding of incremental IDs** is preferred for its simplicity in guaranteeing uniqueness and predictable length. A distributed ID generation service will be essential. ### Read and Write Request Flow: * **Write Request (Shorten URL):** 1. User sends a POST request to `/shorten` with a `long_url` and optional `alias`. 2. The API gateway routes the request to a **Write Service**. 3. **Short Code Generation**: If no alias is provided, the Write Service requests a unique ID from the ID generation service, which is then Base-62 encoded. 4. **Alias Check (if applicable)**: If an alias is provided, check if it's already in use. If so, return an error. Otherwise, use the alias as the `short_code`. 5. **Database Write**: Store the mapping (`short_code`, `long_url`, `created_at`, etc.) in the `urls` database. If the alias is used, an additional entry or index might be needed for alias-based lookups. 6. The Write Service returns the `short_code` and `short_url` to the user. * **Read Request (Redirect):** 1. User enters a `short_url` (e.g., `short.domain/abcd123`). 2. The request hits the API gateway and is routed to a **Read Service** (or Redirector Service). 3. **Cache Check**: The Read Service first checks a distributed cache (e.g., Redis) for the `short_code` to `long_url` mapping. 4. **Database Lookup**: If not found in the cache, the Read Service queries the `urls` database using the `short_code`. 5. **Cache Update**: Once retrieved from the database, the mapping is added to the cache for subsequent requests. 6. **Redirect**: The Read Service returns an HTTP redirect (301 or 302) to the user's browser with the original `long_url`. ### Storage Choices and Caching Strategy: * **Primary Storage**: A distributed NoSQL database like **Cassandra** or **DynamoDB**. These offer high availability, fault tolerance, and horizontal scalability, well-suited for the read-heavy nature of the service. * **Caching**: A distributed in-memory cache like **Redis** or **Memcached** is crucial for the read-heavy traffic. It will store frequently accessed `short_code` to `long_url` mappings. This dramatically reduces database load and improves redirect latency. A TTL (Time-To-Live) can be set on cache entries, or they can be invalidated on writes (though this adds complexity). ### Scaling Approach for Heavy Read Traffic: 1. **Read Replicas**: For relational databases, use read replicas. For NoSQL, their distributed nature inherently handles scaling reads. 2. **Caching Layer**: A robust distributed cache is the primary mechanism. Scale out Redis/Memcached horizontally. 3. **Stateless Services**: Ensure the Read Service and Write Service are stateless. This allows easy horizontal scaling by adding more instances behind a load balancer. 4. **Load Balancing**: Use a robust load balancer (e.g., AWS ELB, Nginx) to distribute traffic across service instances. 5. **CDN**: For the static parts of the web interface (if any) and potentially for serving redirects from edge locations, a Content Delivery Network (CDN) can be employed. ### Handling Expired or Deleted Links: * **Deletion**: The `is_active` flag in the database can be used. When a link is deleted, update `is_active` to `false`. The Read Service would check this flag during database lookups. The entry can also be removed from the cache. * **Expiration**: Add an `expires_at` timestamp to the `urls` table. The Read Service would check this timestamp. An automated background job can periodically clean up expired entries from the database. ### Basic Abuse Prevention and Rate Limiting: * **Rate Limiting**: Implement rate limiting at the API gateway or within the Write Service. This can be based on IP address, user ID (if authenticated), or API keys. Common algorithms include Token Bucket or Leaky Bucket. * **URL Validation**: Before shortening, validate the input `long_url` to prevent obviously malicious or malformed URLs. * **Abusive Content Detection**: Monitor for URLs pointing to phishing sites, malware, or spam. This can involve integrating with third-party blacklists or using machine learning models. * **Custom Alias Restrictions**: Limit the use of custom aliases to registered/verified users to prevent abuse. ### Reliability Considerations and Likely Bottlenecks: * **Likely Bottlenecks**: * **ID Generation Service**: If not designed for high throughput and availability, it can become a bottleneck for writes. * **Database**: High write volume or complex read queries (e.g., unindexed alias lookups) can strain the database. * **Cache**: Cache misses at very high read volumes can overwhelm the database. Cache eviction policies and scaling are critical. * **Network Latency**: Between services, especially across availability zones. * **Reliability**: * **Redundancy**: Deploy services and databases across multiple availability zones. * **Failover**: Implement automatic failover for critical components. * **Monitoring & Alerting**: Comprehensive monitoring of system health, performance metrics, and error rates, with alerts for anomalies. * **Graceful Degradation**: If the cache fails, the system should still function (albeit slower) by reading directly from the database. ### Trade-offs and Assumptions: * **Assumptions**: * We have a reliable mechanism for generating unique, sequential IDs in a distributed environment. * The majority of requests are reads (redirects), justifying heavy investment in caching and read scaling. * Strong consistency for link creation is desirable, but eventual consistency for redirect lookups after a short propagation delay is acceptable. * **Trade-offs**: * **Cache vs. Consistency**: A highly aggressive caching strategy can lead to stale data for a short period after a write, requiring careful cache invalidation or TTL management. * **ID Generation Complexity**: Using incremental IDs is simple for uniqueness but requires a dedicated, highly available ID generation service. Hashing is simpler to implement initially but requires robust collision handling. * **Custom Aliases**: Support for custom aliases adds complexity to the data model (secondary indexes, conflict resolution) and write path. * **Durable vs. Temporary Redirects**: Using HTTP 301 (Permanent) assumes the short URL will always map to the same long URL. Using 302 (Temporary) is more flexible if mappings can change but might have slight SEO implications or browser caching behaviors. This design provides a scalable, reliable, and performant foundation for a URL shortening service.