Design a URL Shortening Service

A) API Design 1) Create short URL - Endpoint: POST /v1/urls - Request JSON: - long_url (string, required, max e.g. 8KB) - custom_alias (string, optional; if provided must be unique and pass allowed charset/length) - expire_at (timestamp, optional) - metadata (object, optional: e.g., campaign, user_id) - Response (201): - code (string) - short_url (string) - long_url (string) - created_at (timestamp) - expire_at (timestamp|null) - Errors: - 400 invalid URL/alias - 409 alias already exists - 429 rate limited 2) Resolve/redirect - Endpoint: GET /{code} - Behavior: - 301 Moved Permanently by default (or 302 if tracking/experimentation requires) - Location header = long_url - Optional: GET /v1/urls/{code} returns JSON instead of redirect (for API clients) - Errors: - 404 not found/expired 3) Delete/disable (optional, for abuse/user control) - Endpoint: DELETE /v1/urls/{code} - Auth required - Response: 204 4) Analytics (optional, can be async/approx) - Endpoint: GET /v1/urls/{code}/stats?from=&to= - Returns aggregated counters (clicks by day, referrer, geo, etc.) Notes: - Auth: API keys/OAuth for creation and management; redirects remain public. - Idempotency: support Idempotency-Key header on POST to avoid duplicates on retries. B) Data Model and Storage Workload - Writes: 100M new/month ≈ 3.33M/day ≈ 38.6 writes/sec average (higher peak). - Reads: 100:1 => 10B redirects/month ≈ 3.86K reads/sec average (peaks much higher). Storage choice - Primary store: distributed key-value / wide-column store (e.g., DynamoDB/Cassandra/ScyllaDB) optimized for very high read QPS, low latency, horizontal scaling, and multi-DC replication. - Rationale: access pattern is primarily key lookup by short code; value is small; strong need for high availability and predictable latency. - Secondary systems: - Cache: Redis/Memcached clusters per region. - Analytics pipeline: Kafka/PubSub + stream processing + OLAP store (not on critical path). Schema 1) url_mapping (primary) - Partition key: code (string) - Columns: - long_url (string) - created_at (timestamp) - expire_at (timestamp|null) - user_id (string|null) - status (active/deleted) - checksum (optional for integrity) - TTL: if expire_at set, use native TTL so expired entries auto-remove. 2) alias_reservation (optional if supporting custom aliases with uniqueness) - key: custom_alias - value: code / ownership metadata 3) idempotency (optional) - key: (user_id, idempotency_key) - value: code - TTL: e.g., 24h Storage estimate (10 years) - New URLs in 10 years: 100M/month * 12 * 10 = 12B mappings. - Per record size rough order: - code: ~8 bytes (or up to ~10 chars) - long_url: assume avg 200 bytes (conservative), plus overhead - metadata/columns/index overhead: assume ~100–200 bytes depending on store - Total effective (including replication overhead not counted yet): ~400 bytes/record (reasonable planning figure). - Raw data: 12B * 400B = 4.8TB. - With storage engine overhead + compaction + secondary indexes: plan ~2–3x => ~10–15TB. - Replication: - Within region (RF=3): ~30–45TB. - Multi-region (e.g., 2 regions active-active): double => ~60–90TB total across all regions. (These are planning numbers; exact depends on average URL length and DB overhead.) C) Short URL Generation Goals - Short as possible - Collision-free at high scale - Supports at least 10 years of growth Keyspace math - Total codes needed in 10 years: 12B. - Use Base62 charset: [0-9][a-z][A-Z] => 62 symbols. - Length L capacity: 62^L. - 62^6 ≈ 56.8B (sufficient for 12B) - 62^7 ≈ 3.52T (more headroom) Choice - Use variable length with a floor of 6 characters. - Start at 6 chars for first ~56.8B codes; that already covers 10-year requirement with significant margin (56.8B/12B ≈ 4.7x). - Keep ability to move to 7 chars in the future without breaking existing links. Generation algorithm (no collisions) Option selected: globally unique numeric IDs + Base62 encoding. - Maintain a monotonically increasing 64-bit ID space. - Encode ID in Base62 to produce the code. - Collision avoidance: none needed because IDs are unique by construction. How to generate IDs at scale - Use a distributed ID allocator similar to Snowflake, or a central “ID service” with range leasing: 1) ID service stores a counter in strongly consistent store (e.g., etcd/Spanner) per region. 2) Each app server leases an ID block (e.g., 1M IDs) to generate locally. 3) When block exhausted, request a new block. - This avoids per-write contention while ensuring uniqueness. Handling custom aliases - If custom_alias provided: - Validate charset/length - Conditional write (compare-and-set) on url_mapping with key=alias; if exists return 409. D) Scaling and Performance High-level architecture - Anycast/GeoDNS -> Global Load Balancer -> Regional L7 load balancers -> stateless API/redirect servers. - Separate services: - Write path: URL creation service - Read path: Redirect service - Shared storage + cache Scaling reads and writes independently - Redirect service scaled horizontally based on QPS/latency (likely dominant cost). - Create service scaled based on write throughput. - Use separate autoscaling groups and independent deployment pipelines. Data partitioning - Partition by code hash (or by code itself) across DB nodes. - Even distribution because codes are effectively uniform over ID space when Base62-encoded. Caching strategy - Primary: CDN/edge caching for redirects + regional in-memory cache. 1) CDN: - Cache 301/302 responses keyed by path (code) with TTL (e.g., 5–60 minutes, or respect expire_at). - For extremely hot links, CDN can absorb most traffic globally. 2) Regional cache (Redis/Memcached): - Key: code - Value: long_url + expire_at + status - TTL: min(default_ttl, expire_at-now) - Eviction: LRU or LFU (prefer LFU for skewed popularity). Expected hit rate - URL accesses are typically highly skewed (Zipf). With CDN + regional cache, 95–99% hit rate is feasible for redirects; even 90% is helpful. - Cache warming: on write, push mapping to cache; also negative caching for misses (short TTL) to reduce repeated DB hits for invalid codes. Meeting <50ms p95 redirect latency - Critical path for cached hit: - Edge/CDN hit: often <20ms. - Regional cache hit: LB + app + Redis lookup + response: typically 5–15ms within region. - For cache miss: - Single DB read from local region replica: target 5–20ms. - Keep redirect servers close to users via multi-region + edge. - Use keep-alive, HTTP/2 between components, connection pooling to Redis/DB. - Avoid synchronous analytics; emit click events asynchronously to a queue. Write performance - Writes are low compared to reads; still handle bursts. - Write flow: 1) Generate ID/code 2) Write to DB (quorum/majority within region) 3) Write-through to cache 4) Return response - Optional: dedupe identical long_url by storing a hash->code index (trade-off; see F). E) Reliability and Fault Tolerance Availability target: 99.9% - Multi-AZ within each region for all stateful components. - At least two regions active-active for redirect traffic. Replication strategy - Within region: replication factor 3 across AZs. - Cross-region: - Asynchronous replication for url_mapping to keep write latency low and availability high. - Redirects served from local region; if local mapping missing due to replication lag, fallback to another region (see below). Data center/region failure handling (graceful degradation) - Use Global Load Balancer health checks: - If a region is unhealthy, route traffic to next closest healthy region. - For redirect requests: - If regional cache/DB is degraded, redirect service can: 1) Try cache 2) Try local DB 3) If local DB unavailable, query a remote region read endpoint (with strict timeout) or use cross-region read replica. 4) If all fail, return a fast 503 with Retry-After (graceful failure). - For write requests: - Prefer local region writes; if region down, failover to another region. - ID allocation: each region has its own ID block namespace (or uses region bits in Snowflake) to avoid conflicts during failover. CAP theorem trade-off - Choose Availability over strong Consistency for global operations: - Redirects must be highly available; stale reads are acceptable briefly. - Cross-region replication is async: a newly created short URL might not resolve in a different region for a short window. Mitigations: - After creation, return a short URL hosted on same region domain (or use edge that routes to origin region for the first few minutes). - On create, optionally do a synchronous write to two regions for premium/enterprise tier (higher latency/cost). Backups and disaster recovery - Periodic snapshots + incremental backups to object storage. - Regular restore drills. F) Trade-off Discussion 1) ID-based code generation vs random tokens - Chosen: ID-based (range leased/Snowflake) + Base62. - Gains: - No collisions, no need for retry loops. - Predictable capacity planning and simpler DB constraints. - Faster writes. - Sacrifices: - Codes are guessable/sequential (security through obscurity not provided). Mitigation: - Add optional “salted permutation” (e.g., Feistel network) over the numeric ID before Base62 encoding to make codes non-sequential while preserving uniqueness. 2) Async cross-region replication (AP) vs synchronous multi-region (CP) - Chosen: async cross-region replication. - Gains: - Lower write latency, higher availability during partial failures. - Better ability to continue serving redirects even if a region is impaired. - Sacrifices: - Eventual consistency: brief window where a newly created URL may not be readable in another region. Mitigation: - Read-repair/fallback to origin region for fresh links; optional dual-write for high-SLA customers. 3) Heavy caching/CDN vs always hitting DB - Chosen: CDN + regional cache. - Gains: - Easily meets <50ms p95 and reduces DB load drastically. - Handles traffic spikes for viral links. - Sacrifices: - Cache invalidation complexity (e.g., deleted/expired links). Mitigation: - Short TTLs, respect expire_at, and explicit purge on delete for CDN where supported; use status flags and negative caching carefully.

A) API Design: 1. **Shorten URL Endpoint:** * **Method:** `POST` * **Path:** `/shorten` * **Request Body (JSON):** ```json { "long_url": "string", "custom_short_code": "string" (optional), "expires_at": "ISO 8601 datetime string" (optional) } ``` * **Response Body (JSON - 201 Created):** ```json { "short_url": "string", "long_url": "string", "custom_short_code": "string" (if provided), "expires_at": "ISO 8601 datetime string" (if provided) } ``` * **Error Responses:** * `400 Bad Request`: Invalid `long_url` format or missing. * `409 Conflict`: `custom_short_code` already exists. * `500 Internal Server Error`: General server error. 2. **Redirect Short URL Endpoint:** * **Method:** `GET` * **Path:** `/{shortCode}` * **Response:** `302 Found` HTTP redirect to the `long_url`. * **Error Responses:** * `404 Not Found`: `shortCode` does not exist or has expired. * `500 Internal Server Error`: General server error. B) Data Model and Storage: **Storage Choice:** A sharded relational database (e.g., PostgreSQL) with read replicas. **Justification:** * **Strong Consistency for Writes:** Essential for ensuring the uniqueness of short codes. Relational databases provide ACID properties, which are crucial for reliable data integrity during URL creation. * **Well-understood Sharding:** PostgreSQL supports various sharding strategies (e.g., range-based, hash-based) to distribute write load and scale horizontally. * **Efficient Indexing:** B-tree indexes are highly efficient for point lookups on `short_code`, which is the primary operation for redirects. * **Read Replicas:** Easily supports scaling read operations (redirects) by adding multiple read-only replicas. * **Maturity and Ecosystem:** Robust tools for monitoring, backup, and recovery. **Schema:** `urls` Table: * `id`: BIGINT, Primary Key, Auto-incrementing (or generated by a distributed ID service). Used as the basis for the short code. * `short_code`: VARCHAR(7), Unique Index, NOT NULL. The actual short string used in the URL. * `long_url`: TEXT, NOT NULL. The original long URL. * `created_at`: TIMESTAMP WITH TIME ZONE, NOT NULL, Default: `NOW()`. * `expires_at`: TIMESTAMP WITH TIME ZONE (nullable). When the short URL should expire. * `user_id`: BIGINT (nullable, foreign key to a `users` table if user accounts are supported). **Storage Estimation (over 10 years):** * **Volume:** 100 million new URLs/month * 12 months/year * 10 years = 12 billion URLs. * **Record Size Estimation:** * `id`: 8 bytes (BIGINT) * `short_code`: 7 bytes (VARCHAR(7)) * `long_url`: Average 100 bytes (TEXT, variable length) * `created_at`: 8 bytes (TIMESTAMP) * `expires_at`: 8 bytes (TIMESTAMP) * Total per record: ~131 bytes. * **Raw Data Size:** 12 billion records * 131 bytes/record = 1.572 TB. * **With Indexes and Overhead:** Accounting for indexes (especially on `short_code` and `id`), replication, and database overhead, the total storage could be approximately 3-5 TB over 10 years. This is manageable with a sharded database architecture. C) Short URL Generation: **Algorithm:** 1. When a new URL shortening request arrives, a unique, monotonically increasing ID is obtained. This ID can be generated by: * **Database Auto-increment:** If using a sharded database, each shard can be configured with a unique ID range (e.g., shard 1 uses IDs 1, 11, 21..., shard 2 uses 2, 12, 22...). * **Distributed ID Generator:** A dedicated service like Snowflake (or a similar custom implementation) can generate globally unique, time-ordered 64-bit integers. 2. This unique ID is then converted to a base62 string. Base62 uses 62 characters (0-9, a-z, A-Z), which allows for a compact representation. **Collision Avoidance:** * By deriving the short code from a globally unique ID (either via sharded auto-increment or a distributed ID generator), collisions are inherently avoided. Each generated ID is unique, and its base62 representation will also be unique. * For `custom_short_code` requests, the system attempts to insert the user-provided code. If a conflict occurs (due to an existing entry), a `409 Conflict` error is returned to the user. **Character Set and Length:** * **Character Set:** Base62 (0-9, a-z, A-Z) - 62 unique characters. * **Length:** 6 characters initially. **Mathematical Justification for Keyspace Sufficiency:** * **Required Volume:** 12 billion unique URLs over 10 years. * **Keyspace with 6 characters:** 62^6 = 56,800,235,584 (approximately 56.8 billion unique codes). * This keyspace (56.8 billion) is significantly larger than the required 12 billion URLs, providing ample room for growth and ensuring sufficiency for at least 10 years. If the service were to exceed this, the short code length could be extended to 7 characters, providing 62^7 (approximately 3.5 trillion) unique codes. D) Scaling and Performance: **Scaling Reads (Redirects):** * **Distributed Cache (e.g., Redis Cluster):** The primary scaling mechanism for reads. `short_code -> long_url` mappings are stored in a highly available, distributed cache. Given the 100:1 read/write ratio, most redirect requests will be served directly from the cache. * **Database Read Replicas:** The sharded PostgreSQL instances will have multiple read replicas. In case of a cache miss, the request falls back to a read replica. Load balancers distribute queries across these replicas. * **Content Delivery Network (CDN):** While not directly caching the 302 redirect, a CDN can serve static assets and potentially optimize routing for initial requests, reducing latency for geographically dispersed users. **Scaling Writes (Shortenings):** * **Database Sharding:** The core strategy. Data is partitioned across multiple PostgreSQL instances based on a sharding key (e.g., the `id` from which the `short_code` is derived). This distributes the write load and storage requirements. * **Connection Pooling:** Efficiently manages database connections to reduce overhead. * **Asynchronous Processing:** For non-critical tasks (e.g., analytics, logging, updating statistics), message queues (e.g., Kafka, RabbitMQ) can offload work from the primary write path, improving responsiveness. **Caching Strategy:** * **Cache Type:** Distributed in-memory cache (e.g., Redis Cluster). * **Data Cached:** `short_code` to `long_url` mappings. * **Cache Population:** On a successful URL shortening, the new mapping is written to both the database and the cache. On a cache miss during a redirect, the mapping is fetched from the database and then written to the cache (write-through/write-aside). * **Eviction Policy:** LRU (Least Recently Used) is suitable. Popular URLs will remain in the cache, while less frequently accessed ones will be evicted to make space. Time-to-Live (TTL) can also be applied, especially for URLs with an `expires_at` field. * **Expected Hit Rate:** Given the 100:1 read/write ratio and the power-law distribution of URL access (a small percentage of URLs account for a large percentage of traffic), a cache hit rate of 90-95%+ is highly achievable, significantly reducing database load. **Meeting 50ms p95 Latency Requirement:** * **High Cache Hit Rate:** The vast majority of redirect requests will be served from the distributed cache, which can respond in single-digit milliseconds. * **Optimized Database Access:** For cache misses, efficient indexing on `short_code` in the sharded database ensures fast lookups. * **Proximity and Network:** Deploying services in multiple regions close to users and utilizing high-speed, low-latency network infrastructure. * **Load Balancing:** Efficiently distributing requests across healthy service instances and database replicas. * **Stateless Application Servers:** Allows for easy horizontal scaling of the API layer, ensuring sufficient capacity to handle peak loads without becoming a bottleneck. D) Reliability and Fault Tolerance: **Data Center Failures:** * **Multi-Region Deployment:** The entire service (API servers, cache clusters, database shards) is deployed across at least two geographically distinct data centers/regions. * **Global Load Balancer (e.g., DNS-based traffic management):** Directs user traffic to the nearest healthy region. If one region fails, traffic is automatically rerouted to the operational region. * **Automated Failover:** Database clusters are configured for automatic failover within a region (primary to replica) and across regions (active-passive or active-active setup). **Data Replication Strategy:** * **Database (PostgreSQL):** * **Within a Region:** Synchronous streaming replication is used between the primary database instance and its local replica(s). This ensures zero data loss in case of a primary failure within the same data center. * **Across Regions:** Asynchronous streaming replication is used from the primary in the active region to a replica in the passive/standby region. This provides disaster recovery capabilities with minimal performance impact on the primary write path. In an active-active setup, each region's primary would asynchronously replicate to the other. * **Distributed Cache (Redis Cluster):** Data is sharded and replicated across multiple nodes within each Redis cluster. Each shard has a primary and at least one replica. In case of a node failure, a replica is promoted to primary. **Trade-offs (CAP Theorem):** * **Choice:** Prioritize **Availability (A)** and **Partition Tolerance (P)** over strong **Consistency (C)** for read operations (redirects), while maintaining strong consistency for write operations (shortening) within a database shard. * **Justification:** For a URL shortening service, it is more critical that the service remains available and responsive (low latency) even during network partitions or data center failures. Users expect redirects to work quickly. A brief period where a newly created short URL might not be immediately resolvable globally (due to replication lag) is generally acceptable. * **How it's achieved:** * **Availability:** Multi-region deployment, global load balancing, database read replicas, and a highly available distributed cache ensure that requests can always be served. * **Partition Tolerance:** The distributed nature of the system (sharding, replication) inherently handles network partitions. * **Consistency:** For writes, strong consistency is maintained within a database shard. Cross-region replication is asynchronous, meaning there might be a small window of inconsistency between regions for newly created URLs. The cache also serves as an eventually consistent layer, as it's updated on writes and on cache misses. F) Trade-off Discussion: 1. **Consistency vs. Availability for Redirects (CAP Theorem):** * **Choice:** Prioritize **Availability** and **Partition Tolerance** over immediate **Strong Consistency** for the redirect path. * **Why:** The primary goal of a URL shortener is to provide fast and reliable redirects. If a newly created URL takes a few seconds to propagate to all read replicas and caches globally, it's a minor inconvenience. However, if the system waits for global consistency before serving a redirect, it would introduce significant latency and reduce availability during network partitions or regional failures. Users would rather experience a rare 404 for a brand new URL than frequent timeouts or slow redirects. * **Sacrifice:** A small window of eventual consistency. A user might create a URL in Region A, and if they immediately try to access it from Region B (before asynchronous replication completes), they might temporarily receive a 404. In extreme multi-region failure scenarios with asynchronous replication, there's a small risk of data loss for very recent writes if the primary region fails catastrophically before replication to the secondary region completes. * **Gain:** High availability (99.9% uptime) and extremely low latency (sub-50ms p95) for the vast majority of redirect requests, which are the most frequent operations. The system remains operational and responsive even if a data center goes offline. 2. **Short Code Generation Method (Sequential ID to Base62 vs. Hashing Long URL):** * **Choice:** Generate short codes by converting a unique, sequentially increasing ID (from a distributed ID generator or sharded auto-increment) to Base62. * **Why:** This method guarantees uniqueness by design, simplifying the write path and improving performance. It avoids the complexities and performance overhead associated with collision detection and resolution inherent in hash-based approaches. * **Sacrifice:** The short codes might appear somewhat sequential (e.g., `abcde1`, `abcde2`) rather than completely random. This might be a minor aesthetic concern for some users, but it doesn't impact functionality. Also, it requires a robust distributed ID generation mechanism, which adds a component to the architecture. * **Gain:** * **Guaranteed Uniqueness:** No collisions, eliminating the need for database lookups and retries during short code generation, which is critical for high write throughput (100M/month). * **Simpler Write Path:** The process of creating a new short URL is a straightforward insert operation after ID generation. * **Predictable Keyspace:** Easier to manage and ensure the keyspace is sufficient for future growth. * **Flexibility:** Allows the same `long_url` to be shortened multiple times, yielding different `short_code`s if desired (e.g., for tracking different campaigns), which is not possible with a simple hash of the `long_url`.