Design a URL Shortening Service

A. Short URL Generation Strategy 1. Requirements-driven choice - New writes: 100M/month ≈ 3.3M/day ≈ 38.6 writes/sec average. - Reads at 100:1 ≈ 3.3B/month ≈ 1,270 reads/sec average, with peak likely 10–50x higher. - We need compact, globally unique IDs with very fast lookup. 2. Code generation approach I would use a deterministic ID-generation service plus Base62 encoding. Flow: - A globally unique numeric ID is generated. - That integer is encoded into Base62 using characters [0-9a-zA-Z]. - Example: 125 -> "21" in Base62. Why this approach: - No collision risk if IDs are unique. - Very fast to generate. - Easy to operate compared with random-code collision checking. - Predictable code length growth. 3. ID generator design Preferred option: - Use a Snowflake-style 64-bit ID generator or a centralized range allocator. - ID fields can include timestamp + machine ID + sequence, or we can allocate monotonically increasing ranges to app servers. Two good implementations: - Snowflake-like IDs: decentralized, high throughput, low coordination. - Range allocation from metadata store: each write node leases a block of IDs, e.g. 1M IDs at a time. I prefer range allocation for simplicity because write throughput is modest. Each write server can generate IDs locally from its leased range, avoiding a hot central dependency. 4. Encoding scheme and expected length Base62 capacity: - 62^6 ≈ 56.8B - 62^7 ≈ 3.52T Total links over 5 years: - 100M/month * 60 months = 6B links So 6 Base62 chars are not enough for long-term headroom if IDs are densely used globally, but 7 chars are more than enough. Expected length: - Start at 6 chars for early lifecycle if desired. - In practice, standardize on 7 chars to keep implementation simple and avoid length changes in user expectations. 5. Collision handling With deterministic unique IDs: - No collisions at the code level. - Database uniqueness constraint on short_code provides a final safety net. - If a very rare duplicate is observed due to software bug or ID misconfiguration, regenerate from a fresh ID and alert. 6. Exhaustion strategy - 7-char Base62 gives 3.52 trillion combinations, far beyond 6B needed in 5 years. - If future scale grows substantially, support 8-char codes seamlessly. - The redirect service should treat code length as variable, so no migration issue. 7. Optional custom aliases If the product supports user-defined aliases: - Store in the same mapping table with uniqueness enforced. - Reserve blocked words and abusive terms. - Apply stricter rate limits because custom aliases are a contention hotspot. B. Data Storage 1. Primary database choice Use a distributed, highly available key-value store for the URL mapping, such as: - DynamoDB / Bigtable / Cassandra Why: - Primary access pattern is simple key lookup by short_code. - Need horizontal scaling, high availability, and multi-replica reads. - Writes are modest, reads are dominant. - Key-value access is ideal for sub-50ms redirect latency. I would choose DynamoDB-like or Cassandra-like storage conceptually: - Partition by short_code hash. - Replicate across availability zones. - Tune for low-latency point reads. 2. Secondary stores - Relational DB for control plane metadata, billing, users, domains, policies. - Object storage + data lake for analytics/click logs. - Optional search/index store if admins need querying by creator, date, tags, etc. 3. Schema design Primary mapping table: - short_code (PK) - destination_url - created_at - expires_at nullable - owner_id nullable - status (active, disabled, deleted) - redirect_type (301/302) - checksum or normalized_url hash optional - metadata pointer optional Optional dedup table if product wants same long URL to return same short URL per tenant: - dedup_key = hash(tenant_id + canonicalized_url) - short_code This is optional; many URL shorteners do not globally deduplicate because semantics differ by user, campaign, or analytics needs. 4. Storage estimate over 5 years Total links: - 6B records Per record rough estimate: - short_code: ~8 bytes raw equivalent - destination_url: assume average 200 bytes - timestamps/status/flags: ~24 bytes - replication/versioning/index overhead: substantial in real systems - storage engine overhead: assume total effective ~350–500 bytes per record in primary DB Using 400 bytes/record: - 6B * 400 bytes = 2.4 TB raw logical data With replication factor 3: - 7.2 TB Add indexes, compaction overhead, tombstones, metadata, operational headroom: - Plan for 10–15 TB in primary storage over 5 years Analytics/click logs are much larger than mappings. At 100 reads per write: - 600B redirects over 5 years If each click log event averaged even 100 bytes compressed, that is ~60 TB compressed, likely much more with richer fields. Therefore logs should go to cheap object storage, not the serving database. 5. Partitioning/sharding strategy Primary table sharding: - Partition key: short_code or hash(short_code) - Uniformly distributed because IDs are encoded from well-distributed numeric IDs or range IDs mixed appropriately Important note: - Pure sequential IDs can create hot partitions in some databases if key locality matters. - To avoid this, either: 1. Hash the short_code for partition placement, or 2. Use IDs with enough entropy in lower bits, or 3. Prefix with shard bits before Base62 encoding I would explicitly hash-partition on short_code to ensure even distribution. C. Read Path Architecture 1. Read path overview Request flow: - User hits https://sho.rt/abc1234 - DNS routes to nearest edge/CDN - CDN forwards to regional redirect service if not cache-hit - Redirect service checks in-memory/Redis cache - On cache miss, read from distributed KV store - Return HTTP 301/302 with Location header - Asynchronously emit click event to analytics pipeline 2. Meeting <50ms p95 latency The redirect path must be extremely lightweight. Latency budget example: - Edge/CDN routing: small, geographically local - App processing: 1–3ms - Redis/in-memory cache hit: 1–5ms - DB miss path within region: 5–15ms typical - Total p95 under 50ms is achievable with regional serving and aggressive caching 3. Caching layers Layer 1: CDN/edge caching - Cache redirect responses for hot links at the edge. - Very effective because many popular short links are repeatedly accessed. - Use cache-control headers with TTL, e.g. minutes to hours depending on mutability. - If links can be disabled quickly, choose shorter TTL or purge support. Layer 2: Application local cache - Each redirect node keeps an LRU cache of hot mappings. - Ultra-low latency, avoids network hop to Redis. - Good for the most frequently requested codes. Layer 3: Distributed cache (Redis/Memcached) - Shared cache for regional fleet. - Stores short_code -> destination_url, status, redirect type. - TTL can be long for immutable links; shorter for mutable/admin-controlled links. 4. Replication strategy for reads - Multi-AZ replicas inside each region. - Serve reads from local region storage replicas. - Active-active across multiple regions for global traffic. - Use geo-DNS or Anycast to route to nearest healthy region. 5. Cache population strategy - Read-through on miss: app fetches from DB, populates Redis and local cache. - Negative caching for nonexistent/disabled codes for short TTL to absorb abuse and typo storms. - Prewarm cache for trending links if known from analytics. 6. Redirect semantics - 302 by default if destination may change or if analytics/tracking policies require flexibility. - 301 for permanent links where clients and CDNs may cache aggressively. - Product decision can expose both options. 7. Abuse handling on read path - Rate limit by IP / ASN / token for suspicious high-rate requests. - WAF and bot filters at CDN. - Protect origin from brute-force short-code scanning. D. Write Path Architecture 1. Write path overview Request flow: - Client sends long URL and optional metadata/custom alias. - API gateway authenticates and rate limits. - URL validation and normalization happen in stateless app tier. - App obtains/generates short code. - Persist mapping to primary KV store. - Populate caches asynchronously or synchronously for immediate availability. - Emit creation event to queue for analytics, abuse scanning, and downstream indexing. 2. Capacity 100M/month is not high for modern systems: - Average ~39 writes/sec - Even 100x burst is only a few thousand writes/sec So the main goals are reliability, idempotency, and operational simplicity rather than extreme write throughput. 3. Validation steps - Validate URL syntax. - Enforce allowed protocols, usually http/https only. - Optional safe-browsing or malware scan asynchronously; if risk found, disable link. - Canonicalize URL for optional dedup logic. 4. Queuing and asynchronous work Use a durable queue or log such as Kafka/SQS/PubSub for side effects: - Analytics event for new link creation - Abuse/scam/phishing detection - Cache warmup - Search indexing - Notification/audit pipeline Critical path should only include what is necessary to create the mapping and return the shortened URL. 5. Consistency model For create response, use write-after-create consistency for the new short code: - Once API returns success, redirect should work immediately. How: - Persist mapping to quorum/leader in primary DB before acknowledging. - Optionally write-through to Redis after DB commit. - Redirect path falls back to DB on cache miss, so cache propagation lag does not break correctness. 6. Idempotency Support idempotency keys for API clients to prevent duplicate links during retries. - Store request_id -> short_code for a bounded TTL in a fast store. - Especially useful for mobile/network-retry scenarios. 7. Rate limiting - Per-user/API-key quotas to control abuse. - Stronger limits on custom alias requests. - Global safeguards to prevent attack-induced write amplification. E. Reliability and Fault Tolerance 1. Availability target: 99.9% 99.9% uptime allows about 43.8 minutes downtime/month. This is achievable with multi-AZ deployment and regional failover. 2. Failure handling Node failure: - Stateless app nodes behind load balancers; auto-replace unhealthy instances. - Local caches are disposable. - Redis deployed as highly available cluster/sentinel mode. AZ failure: - App tier deployed across at least 3 AZs. - Primary DB replicated across AZs. - Load balancer removes unhealthy AZ. Regional/DC outage: - Active-active read serving across multiple regions. - Data replicated cross-region asynchronously or near-synchronously depending on DB capabilities. - DNS/traffic manager fails over users to healthy region. 3. Data durability - Primary DB replication factor 3 across AZs. - Periodic snapshots/backups to object storage. - WAL/commit-log archival if supported. - Cross-region backup copies for disaster recovery. 4. Backup and recovery strategy - Daily full snapshots plus incremental backups. - Point-in-time recovery for accidental deletion/corruption. - Regular restore drills into staging to verify RTO/RPO. - Backup retention aligned with 5-year accessibility requirement and compliance needs. Reasonable objectives: - RPO: minutes to 1 hour depending on cross-region replication model - RTO: under 1 hour for regional failover, longer for full storage rebuild but that should be rare 5. Cache invalidation strategy If links are mostly immutable, caching is simple. For mutable links (disable/change destination/expiration): - Update DB first. - Publish invalidation event. - Evict Redis key and local cache entries. - Purge CDN cache if edge caching is used for that code. - Use bounded TTL so stale cache self-heals even if invalidation misses. 6. Protection against data corruption and abuse - DB uniqueness constraints on short_code. - Checksums/version fields for records. - Audit logs for admin actions. - Soft delete or disabled state instead of hard delete where possible. - Malware/phishing scanning and takedown tooling. F. Key Trade-offs 1. Deterministic ID generation vs random short codes Options: - Deterministic sequential/range-based IDs: simple, no collisions, compact, fast. - Random codes: less predictable/enumerable but require collision checks and more complexity. Choice: - I choose deterministic IDs encoded in Base62. Why: - Simpler, faster, and operationally safer for this scale. - Collision-free without retry loops. - Better fit because throughput is modest and the main challenge is read latency. Cost: - Codes may be more enumerable/predictable. Mitigation: - Rate limiting, bot detection, optional longer/non-sequential aliases for sensitive links. 2. Stronger consistency on create vs eventual consistency everywhere Options: - Eventual consistency could reduce write latency and simplify multi-region writes. - Strong acknowledgment after durable write ensures a returned short URL works immediately. Choice: - Strong consistency for the single-link create path within a home region; eventual consistency for secondary caches and cross-region propagation. Why: - Better user experience: once the API returns, redirect should succeed. - Write volume is low enough that we do not need to relax consistency on the critical write. 3. Aggressive edge caching vs fast invalidation Options: - Long CDN TTLs maximize read performance and reduce origin cost. - Short TTLs make disable/update operations propagate faster. Choice: - Moderate TTL with explicit purge for mutable/admin-managed links; longer TTL for immutable links. Why: - Most shortened URLs are effectively immutable, so caching gives major latency and cost benefits. - But abuse takedowns require reasonably fast invalidation. 4. Simplicity vs analytics richness on redirect path Options: - Synchronous click logging gives immediate analytics guarantees but adds latency and failure coupling. - Asynchronous event emission keeps redirects fast but analytics may lag or lose small amounts during failures. Choice: - Asynchronous analytics. Why: - The product’s hard SLA is redirect latency and availability, not zero-loss real-time analytics. - Redirect path should never block on downstream logging systems. Summary architecture - Short code generation: range-leased or Snowflake-style unique 64-bit IDs encoded in Base62, standard 7-char codes. - Primary store: distributed KV database, hash-partitioned by short_code, RF=3, multi-AZ. - Read path: CDN + local cache + Redis + KV store fallback; multi-region active-active reads. - Write path: stateless API + durable DB write + async queue for side effects; idempotency and rate limits. - Reliability: multi-AZ, cross-region replication, backups, cache invalidation events, DNS failover. - This design comfortably supports 100M new URLs/month, 100:1 read ratio, 5-year retention, 99.9% uptime, and <50ms p95 redirects.

## Design of a URL Shortening Service This document outlines the design for a URL shortening service capable of handling 100 million new URLs per month, a 100:1 read-to-write ratio, 5-year data retention, 99.9% uptime, and redirect latency under 50ms at the 95th percentile. ### A. Short URL Generation Strategy **Encoding Scheme**: We will use Base62 encoding (0-9, a-z, A-Z). This scheme is URL-safe and provides a compact representation for unique identifiers. **Expected URL Length**: Over 5 years, the service needs to support 100 million URLs/month * 12 months/year * 5 years = 6 billion unique URLs. A 6-character Base62 string provides 62^6 = 56,800,235,584 possible unique keys, which is more than sufficient for 6 billion URLs. We will start with 6 characters and have the flexibility to extend to 7 characters (62^7 ≈ 352 billion keys) if the key space ever approaches exhaustion. **Generation Method**: We will employ a **Key Generation Service (KGS)**. This service will be responsible for generating unique, monotonically increasing numeric IDs. These IDs will then be Base62 encoded to produce the short URL codes. The KGS can use a distributed ID generation algorithm (e.g., a modified Snowflake ID generator or a dedicated service that increments a counter and pre-allocates blocks of IDs to multiple KGS instances to avoid contention). This approach guarantees uniqueness and avoids collisions by design, eliminating the need for database lookups during key generation. **Collision Handling**: With the KGS generating unique numeric IDs, collisions are inherently avoided. Each generated ID is unique, and its Base62 encoding will also be unique. If a random generation strategy were chosen, collision handling would involve checking the database for existence and regenerating upon collision, which adds latency and complexity. **Exhaustion of Key Space**: As discussed, a 6-character Base62 key provides ample space for 6 billion URLs. Should the service grow beyond this, extending the key length to 7 characters would provide significantly more capacity. The KGS would be designed to handle this transition seamlessly by generating longer IDs when necessary. ### B. Data Storage **Database Selection**: For the core `short_code` to `long_url` mapping, we will use a **distributed NoSQL key-value store** like **Apache Cassandra**. Cassandra is highly scalable, fault-tolerant, and optimized for high-volume, low-latency reads and writes, making it ideal for our read-heavy workload. Its distributed nature and built-in replication capabilities ensure high availability and data durability. **Storage Estimation**: * Total URLs over 5 years: 6 billion. * Each entry will store: * `short_code`: 6-7 characters (approx. 7 bytes) * `long_url`: Average 100 characters (approx. 100 bytes) * `created_at`: Timestamp (8 bytes) * `expires_at`: Timestamp (8 bytes, for 5-year retention) * `click_count`: Counter (8 bytes) * `user_id` (optional): e.g., 36 bytes for UUID * Total per entry (conservative estimate, including overhead): ~150 bytes. * Total raw storage: 6 billion URLs * 150 bytes/URL = 900 billion bytes = 0.9 TB. * With a replication factor of 3 (common for Cassandra for high availability): 0.9 TB * 3 = **2.7 TB**. **Schema Design (Cassandra)**: ```sql CREATE TABLE short_urls ( short_code text PRIMARY KEY, -- Partition key for even distribution long_url text, created_at timestamp, expires_at timestamp, click_count counter, user_id text ); ``` **Partitioning/Sharding Strategy**: Cassandra inherently handles data partitioning and sharding based on the primary key (`short_code`). The Base62 `short_code` provides a good distribution of data across the cluster nodes, preventing hot spots and ensuring efficient data retrieval. We will configure Cassandra with a replication factor of 3 across multiple data centers or availability zones for fault tolerance and high availability. ### C. Read Path Architecture **Throughput**: With 100M writes/month and a 100:1 read-to-write ratio, we expect 10 billion reads/month, averaging approximately 3,858 reads/second. Peak loads could be 5-10x higher, reaching 20,000-40,000 reads/second. **Architecture Components**: 1. **Load Balancer (e.g., AWS ELB, Nginx)**: Distributes incoming HTTP requests for short URLs across multiple Redirect Service instances. 2. **Distributed Cache (e.g., Redis Cluster)**: This is critical for meeting the latency and throughput requirements. The cache will store `short_code` to `long_url` mappings. Given the 100:1 read-to-write ratio, a very high cache hit rate (e.g., 95%+) is expected, significantly reducing the load on the database. * **Cache Invalidation**: Short URL mappings are generally immutable. Cache entries can have a very long TTL or be permanent. If a `long_url` ever needs to be updated (rare), an explicit cache invalidation would be triggered. 3. **Redirect Service (Application Servers)**: A fleet of stateless application servers (e.g., running Go, Java, or Node.js) behind the load balancer. * Upon receiving a short URL request, the service first checks the Redis cache. * If a cache hit, it immediately issues an HTTP 301 (Permanent) or 302 (Temporary) redirect to the `long_url`. * If a cache miss, it queries the Cassandra database for the `long_code`. * Once retrieved from Cassandra, the mapping is stored in Redis for future requests, and then the redirect is issued. * Click counts are updated asynchronously (e.g., by sending messages to a Kafka queue for processing by a separate analytics service or by incrementing a counter in Cassandra directly, which supports atomic increments). 4. **Database (Cassandra Cluster)**: Serves as the persistent storage for all URL mappings and handles cache misses. Its distributed nature and replication ensure high availability and low-latency data retrieval for the scale required. **Replication Strategies**: * **Application Servers**: Multiple instances deployed across different availability zones, managed by auto-scaling groups. * **Cache**: Redis Cluster with master-replica configurations for each shard, ensuring high availability and data redundancy. * **Database**: Cassandra's native multi-datacenter replication (e.g., 3x replication factor across at least two data centers) provides strong fault tolerance and disaster recovery capabilities. ### D. Write Path Architecture **Throughput**: 100 million new URLs per month translates to an average of ~38 writes/second. Peak loads might reach 300-400 writes/second. **Architecture Components**: 1. **Load Balancer**: Distributes incoming requests for new URL shortenings to the Write Service instances. 2. **Write Service (API Gateway/Application Servers)**: * Receives the `long_url` from the user. * Calls the **Key Generation Service (KGS)** to obtain a unique `short_code`. * Constructs the `short_code` to `long_url` mapping. * Publishes this mapping to a **Message Queue (e.g., Apache Kafka)**. This decouples the write service from the database, provides buffering, and enhances reliability. * Returns the generated `short_code` to the user. 3. **Key Generation Service (KGS)**: As described in Section A, this service generates unique numeric IDs and encodes them to Base62 `short_code`s. It can pre-generate blocks of keys to minimize latency during peak write times. 4. **Worker Processes (Consumers)**: A pool of worker processes consumes messages from the Kafka queue. * For each message, the worker writes the `short_code` and `long_url` to the **Cassandra database**. * It then immediately writes the mapping to the **Redis Cache** to ensure the newly created short URL is instantly available for reads. 5. **Database (Cassandra Cluster)**: Persistently stores the new URL mappings. **Consistency Considerations**: * For the `short_code` to `long_url` mapping, strong consistency is desired. By writing to Cassandra with appropriate consistency levels (e.g., `QUORUM`) and then immediately populating the cache, we ensure that once a short URL is returned to the user, it will correctly resolve. * The use of a message queue provides eventual consistency for the persistence layer, but the immediate cache update ensures the read path is consistent for new URLs. If the cache update fails, the read path will eventually hit the database, which will be consistent. ### E. Reliability and Fault Tolerance **Node Failures**: * **Application Servers (Redirect & Write Services)**: Stateless and deployed in auto-scaling groups across multiple availability zones. Load balancers automatically route traffic away from failed instances, and new instances are launched to replace them. * **Distributed Cache (Redis Cluster)**: Configured with master-replica replication. If a master node fails, a replica is automatically promoted to master, minimizing downtime and data loss for cached items. * **Database (Cassandra Cluster)**: Designed for high availability with a replication factor of 3 across multiple nodes and data centers. If a node fails, its data is available on other replicas, and Cassandra automatically handles data repair and replacement of the failed node. * **Key Generation Service (KGS)**: Deployed with multiple instances behind a load balancer. The underlying distributed ID generation mechanism (e.g., using Zookeeper for coordination or a highly available counter) ensures that unique IDs can still be generated even if some KGS instances fail. * **Message Queue (Kafka)**: Deployed as a cluster with replication. If a broker fails, other brokers continue to operate, and data is replicated to ensure no message loss. **Data Center Outages**: The entire system will be deployed across at least two geographically distinct data centers or multiple availability zones within a region. Load balancers will be configured for cross-zone/cross-region failover. Cassandra's multi-datacenter replication ensures data durability and availability even if an entire data center becomes unavailable. **Cache Invalidation**: As `short_code` to `long_url` mappings are largely immutable, explicit cache invalidation is rarely needed. Cache entries can have a very long TTL. If a `long_url` ever needs to be updated (e.g., for legal reasons), the write service would update the database and then explicitly invalidate/update the corresponding entry in the Redis cache. **Backup and Recovery Strategy**: * **Database**: Regular, automated snapshots of the Cassandra cluster data will be taken and stored in a highly durable object storage service (e.g., AWS S3, Google Cloud Storage). These backups enable point-in-time recovery in case of data corruption or accidental deletion. Cassandra's incremental backups and commit logs can also be used for more granular recovery. * **Configuration**: All infrastructure (Infrastructure as Code) and application configurations will be version-controlled (e.g., Git) and deployed using automated pipelines, allowing for quick restoration of service configurations. * **Monitoring and Alerting**: Comprehensive monitoring (e.g., Prometheus, Grafana) will be in place to track system health, performance metrics, and error rates. Automated alerts will notify operations teams of any anomalies or failures, enabling rapid response and recovery. ### F. Key Trade-offs 1. **Consistency vs. Availability (for `short_code` to `long_url` mapping)** * **Trade-off Chosen**: We prioritize strong consistency for the core `short_code` to `long_url` mapping, while allowing for eventual consistency for auxiliary data like click counts. * **Explanation**: The fundamental purpose of a URL shortener is to reliably redirect a short URL to its correct long URL. An inconsistent mapping (e.g., redirecting to the wrong URL or failing to redirect) would severely degrade user experience and break the service's core contract. Therefore, we ensure that once a `short_code` is created and returned to the user, it immediately resolves to the correct `long_url`. This is achieved by writing to Cassandra with strong consistency levels (e.g., `QUORUM`) and immediately populating the Redis cache. Availability is maintained through extensive replication and distributed architecture, ensuring the service remains operational even with strong consistency requirements for the critical path. Click counts, however, can tolerate slight delays in updates, making eventual consistency acceptable for this non-critical data. 2. **Simplicity vs. Scalability/Performance (Key Generation Strategy)** * **Trade-off Chosen**: We opted for a dedicated Key Generation Service (KGS) using a distributed counter and Base62 encoding, which is more complex, over a simpler approach of generating random Base62 strings and checking for collisions. * **Explanation**: While generating random strings and checking for collisions in the database is simpler to implement initially, it introduces several scalability and performance challenges. As the key space fills up, the probability of collisions increases, leading to more retries and higher latency on the write path. This read-before-write pattern can become a bottleneck under high write loads. The chosen KGS approach, while more complex to design and maintain (requiring a distributed ID generator), guarantees unique keys without collisions. It allows for pre-generation of key blocks, significantly reducing the latency of key acquisition for the write service. This upfront complexity is justified by the need for predictable, high-performance, and highly scalable key generation over the service's 5-year lifespan, ensuring the write path remains efficient and reliable as the system grows.