Design a URL Shortener for 10K Requests per Second

System design: scalable URL shortener

Assumptions

1. Redirect traffic peaks at 10,000 requests per second. A nominal 100:1 read-to-write ratio implies approximately 100 creates per second at that peak.

2. Thirty billion links in five years requires approximately 190 creates per second on average, so the storage and write path will be provisioned for at least 1,000 creates per second to reconcile this figure and absorb bursts.

3. Links are immutable by default. If deletion or destination editing is later supported, it uses explicit versioning and cache invalidation.

4. Basic analytics may be eventually consistent and can lose a very small number of events during catastrophic failures. Redirect correctness does not depend on analytics.

5. Redirect responses use HTTP 302 or 307 rather than permanent 301 redirects, preserving operational control and improving analytics visibility.

6. The service runs active-active in at least three geographic regions and uses a globally replicated link datastore.

7. High-level architecture

Components are global DNS or Anycast routing, regional load balancers, stateless redirect services, stateless creation services, local in-process caches, regional distributed caches, a partitioned link datastore, a durable event stream, and analytics processors and storage.

Create path

1. A client sends the long URL and optional custom alias to the nearest healthy region.
2. The API authenticates or rate-limits the caller, validates URL syntax, limits URL length, permits only supported schemes such as HTTP and HTTPS, and checks reserved aliases.
3. For an automatically generated link, the service creates a cryptographically random code. For a custom alias, it normalizes the alias according to a documented, case-sensitive or case-insensitive policy.
4. The creation service performs a conditional insert into the authoritative datastore: insert only if the code or alias does not already exist.
5. On a random collision, it generates another code and retries. On a custom alias collision, it returns HTTP 409 without silently changing the requested alias.
6. After the database acknowledges the write, the service inserts the new mapping into the local regional cache and broadcasts a cache-fill or invalidation message to other regions.
7. It returns the short URL. A request idempotency key can map repeated client requests to the same result.

The write is acknowledged only after a quorum or consensus commit. This adds cross-zone and, depending on the datastore configuration, cross-region write latency, but creates an authoritative global uniqueness guarantee. Creation is much less latency-sensitive than redirect traffic.

Redirect path

1. Global routing sends the request to the nearest healthy region.
2. The redirect service validates and extracts the code.
3. It checks a small in-process cache. If absent, it checks the regional distributed cache.
4. On a cache miss, it performs a point lookup in a local datastore replica using the code as the primary key.
5. If found and active, it populates both cache levels, asynchronously emits a click event, and immediately returns a 302 or 307 response containing the destination.
6. If absent, it returns 404. Negative results are cached only briefly.

The redirect path has no synchronous analytics operation and no cross-region network hop under normal conditions. Stateless services horizontally scale behind regional load balancers.

2. Short-code generation and uniqueness

A seven-character base62 space contains 62^7, approximately 3.52 trillion, values and can technically hold 30 billion links. However, at 30 billion stored links, about 0.85 percent of that namespace is occupied. A random bulk scanner would therefore discover roughly one valid link per 117 guesses, which does not satisfy the requirement that codes be difficult to guess in bulk.

The default code will therefore use 11 URL-safe base62 characters generated from a cryptographically secure random source. This provides approximately 65.5 bits and 5.2 × 10^19 possibilities. With 30 billion active links, a random guess succeeds with probability around 5.8 × 10^-10. Rate limiting and abuse detection further constrain enumeration. The trade-off is a four-character longer link. Seven-character aliases may still be allowed when explicitly chosen by users, but they do not receive the same non-enumerability guarantee.

Random generation avoids exposing creation order and distributes keys evenly. A primary-key conditional insert is the final uniqueness authority. Birthday collisions across the complete history are expected in a random system, but only simultaneous candidate collisions matter operationally: every attempted insert is checked and retried. At the planned occupancy of the 11-character space, retries are effectively nonexistent.

An alternative would be encrypting or applying a keyed permutation to a sequence number. That guarantees unique generated inputs but requires key lifecycle management and sequence allocation. Random generation plus conditional insertion is simpler, removes centralized ID allocation, and is sufficiently efficient at this namespace size.

Custom aliases share the same primary-key namespace as generated codes. Alias normalization occurs before insertion, and one globally consistent conditional insert decides the winner of concurrent requests. Reserved paths such as health, API, admin, and static are rejected. If aliases are case-insensitive, the normalized lowercase form is the key while the requested display form may be stored separately.

3. Data model and datastore

Authoritative link record fields are:

code: primary key
long_url: destination URL
created_at: timestamp
owner_id: optional account identifier
status: active, disabled, or deleted
ttl_or_expiry: optional
version: monotonically increasing value for cache invalidation
custom_alias: boolean

Click counts are not updated in this record on each redirect because that would turn popular links into write hotspots.

The link store is a distributed, partitioned key-value database optimized for primary-key access, such as DynamoDB, Bigtable, Cassandra with carefully managed consistency, or an equivalent internally operated system. For globally unique conditional writes, the selected implementation must provide linearizable conditional creation for a key, either natively or through per-shard consensus leaders. Relational joins and range scans are not needed on the redirect path.

The primary partition key is a hash of the full code. Hash distribution prevents chronological hotspots and evenly spreads both generated codes and custom aliases. The logical keyspace is divided into thousands of virtual shards, which are reassigned as nodes are added. Each shard has at least three replicas across availability zones, with additional cross-region replicas.

Capacity estimate

Assume an average URL of 400 bytes and approximately 200 bytes for keys, metadata, encoding, indexes, and storage-engine overhead. At roughly 600 bytes per record, 30 billion records require about 18 TB of logical data. Allowing for longer URLs, compaction overhead, tombstones, and operational headroom, budget 30 TB logical. Three durable replicas require approximately 90 TB, and backups plus cross-region copies can raise the fleet allocation to roughly 150–250 TB. This is well within the intended range of horizontally partitioned key-value stores but is unsuitable for a single conventional database instance.

At 10,000 redirects per second, even a complete cache outage generates only 10,000 random point reads per second. The datastore is provisioned for at least 20,000–30,000 reads per second per serving region during failover and at least 1,000 conditional creates per second. Capacity is governed more by dataset size, replication, and failover reserve than by normal request throughput.

Analytics uses separate storage. A stream processor writes per-code, time-bucketed counts to an analytics key-value or columnar store with a model such as code plus day or hour as the key and count as the value. A compact total can be maintained asynchronously. Keeping analytics separate prevents hot-link counters from contending with redirect lookups.

4. Caching strategy

Each redirect process has a bounded LRU or TinyLFU in-memory cache for the hottest mappings. A regional Redis or Memcached-compatible cluster forms the second level. Cached values include destination, status, expiry, and record version.

A representative target is a 95–99 percent regional cache hit rate. Zipf-like URL popularity generally makes this feasible even though the total corpus is very large. The cache stores hot objects, not all 30 billion links. For example, 100 million entries at approximately 600 bytes each consume about 60 GB before cache overhead and perhaps 100–150 GB in practice, distributed across a regional cache cluster.

Mappings are immutable by default, so positive entries can have a long TTL, such as 6–24 hours with jitter. If editing, disabling, or deleting is supported, the authoritative write commits first and then publishes an invalidation containing the code and new version to all regions. Shorter TTLs bound stale-serving time if an invalidation is lost. Safety-sensitive disable operations can also place a small global deny-list in every redirect process.

Negative results are cached for approximately 5–30 seconds to resist repeated scans. The creation path invalidates negative cache entries after successfully claiming a code. The short negative TTL limits a race in which another region briefly cached a miss before replication or invalidation arrived.

On a cache miss, the redirect service reads the regional datastore replica and fills both cache levels. Request coalescing ensures that concurrent misses for a newly popular code issue one database request rather than thousands. TTL jitter avoids synchronized expiration. The datastore is sized to carry the entire 10,000-request-per-second load if the distributed cache fails, accepting somewhat higher latency while remaining functional.

The trade-off of long cache TTLs is potential staleness after edits. Immutability, versioned invalidations, and bounded TTLs make that trade-off explicit. Redirect correctness for newly created links can be improved by synchronously filling the creating region and routing an immediate read to that region when necessary.

5. Scaling and latency

Redirect services are stateless and scale horizontally based on requests per second, CPU, and p99 latency. If one instance safely processes 1,000 requests per second, each region might run at least 15–20 instances for a 10,000-request-per-second regional failover load, plus deployment and zone-failure headroom. Actual sizing is established through load testing.

A normal cache-hit latency budget is approximately 2–5 ms for load balancing and application work, 1–3 ms for an in-process lookup or 2–8 ms for a regional distributed-cache lookup, and a few milliseconds to construct the response. A cache-miss budget allocates approximately 10–25 ms to a local replicated datastore point lookup. These budgets leave room to keep origin server-side p99 below 50 ms.

Strict per-hop timeouts prevent a damaged cache or replica from consuming the entire latency budget. Cache access may be limited to roughly 8 ms and datastore access to roughly 25–30 ms, with retries only when enough budget remains. Hedged reads to a second local replica may be used for the slowest percentile, but they are delayed and rate-limited to avoid doubling normal load.

Keys are hash-partitioned across virtual shards. Random generated codes naturally balance traffic, while an exceptionally hot individual link is absorbed by in-process and regional caches. If a hot key reaches the datastore, request coalescing and replicated reads prevent one storage node from becoming the bottleneck.

Autoscaling maintains enough capacity for a complete availability-zone loss and at least one region receiving redirected traffic from a failed peer. Regions run below roughly 50–60 percent peak capacity. The trade-off is higher idle cost in exchange for the 99.99 percent availability objective.

6. Reliability and failure handling

Availability target

A 99.99 percent monthly target permits about 4.4 minutes of unavailability in a 30-day month. No single cache node, application instance, availability zone, or region may be required for redirects.

Application instance or zone failure

Health checks remove failed instances and load balancers distribute requests across at least three zones. Services use rolling or canary deployments, connection draining, and automated rollback. Regional capacity survives losing one zone.

Cache-node or cache-cluster failure

Cache nodes are sharded and replicated within a region. If an individual node fails, its replica takes over. If the whole cache is unavailable, redirect services use circuit breakers, skip cache calls, and query the datastore directly. Database capacity and application connection pools are explicitly provisioned for this mode. Admission control protects the datastore from unbounded scanner traffic.

Datastore-node failure

Each shard is replicated across zones using quorum or consensus. A failed leader is replaced automatically; reads use another healthy local replica. Conditional creates remain unavailable for a shard during the brief election rather than risking duplicate ownership. Redirects can continue from replicas and caches. This favors correctness for creation while preserving read availability.

Region failure

Global health-based routing removes the failed region and sends traffic to the nearest healthy region. Every serving region has a replicated copy of link data and independent redirect, cache, and event-ingestion infrastructure. Cache hit rate will initially be lower after failover, so standby regions retain warm caches for globally hot links and enough datastore/read capacity for the cold-cache surge.

For generated codes, global replication may be asynchronous after a consensus-backed authoritative insert if the datastore architecture routes each key to a home shard. For custom aliases, the authoritative conditional insert must remain globally serialized. If a newly created link has not reached a surviving region before catastrophic loss, the service may briefly return a retriable error rather than an incorrect mapping. Stronger synchronous multi-region replication reduces this recovery-point window but increases create latency. The preferred configuration commits link creation across replicas in at least two regions because writes are relatively low volume.

Backups and corruption

The datastore uses checksums, point-in-time recovery, immutable snapshots, and regularly tested restore procedures. Deletes use tombstones and a retention period rather than immediate physical removal. Backups protect against logical corruption but are not part of normal redirect failover.

Overload behavior

Rate limits apply by source, account, and suspicious code-scanning pattern. Creation and analytics traffic have lower priority than redirects. Load shedding rejects abusive or excess creation requests before redirect capacity is affected. Circuit breakers, bounded queues, and deadlines prevent cascading failures.

7. Click analytics

After selecting the redirect destination, the service creates a compact event containing an event id, code, timestamp, region, and optionally coarse referrer or user-agent fields. It places the event into a bounded local asynchronous buffer and returns the redirect without waiting for analytics acknowledgement.

A regional collector batches events into a durable replicated stream such as Kafka, Pulsar, or Kinesis. Stream processors aggregate events by code and time bucket, then write batched increments to the analytics store. Periodic compaction produces total click counts. Dashboards and APIs read the analytics store, never the authoritative redirect table.

Event ids allow downstream deduplication when collectors retry. Partitioning the stream directly by code would concentrate a viral link on one partition, so the ingestion key can be code plus a random stripe. Processors first aggregate striped counters and then merge them. This permits hot-link analytics to scale horizontally.

A purely in-memory asynchronous buffer can lose events if a redirect process crashes. If stronger durability is required, each host or sidecar can append batches to a local write-ahead log before forwarding them, but redirect responses should still not wait for the central stream. The accepted trade-off for basic analytics is eventual consistency and a small, measured undercount during severe failure in exchange for preserving redirect latency and availability.

Result

The normal redirect path is a local cache lookup followed, only on misses, by a local partitioned key-value lookup. Random 11-character codes prevent sequential exposure and make successful bulk guessing impractical. Conditional inserts provide uniqueness, hash partitioning supports the 30-billion-record corpus, active-active regional serving removes regional single points of failure, and asynchronous striped analytics keeps counter writes entirely off the latency-critical path.

System Design: URL Shortener (10K RPS)

Assumptions:

• We are designing for a single region initially, with multi-region being a future enhancement.
• The primary focus is on the redirect path due to the 100:1 read:write ratio.
• Custom aliases are a secondary feature and can tolerate slightly higher latency or occasional unavailability compared to standard redirects.
• Click analytics are not strictly real-time and can have a slight delay.

1. High-Level Architecture and Request Flow

Write Path (Create Short Link):

1. API Gateway: Receives the POST request with the long URL and optional custom alias.
2. Load Balancer: Distributes write requests to the URL Shortening Service (US) API instances.
3. US API (Write Service):
   • Validates the input URL.
   • Generates a short code (see Section 2).
   • If a custom alias is provided, it attempts to reserve it first (see Section 2).
   • Persists the mapping (short_code -> original_url, custom_alias -> short_code) in the datastore.
   • Returns the generated short URL to the client.

Read Path (Redirect):

1. API Gateway: Receives the GET request for a short URL.
2. Load Balancer: Distributes read requests to the US API instances.
3. US API (Read Service):
   • Extracts the short code from the URL path.
   • Cache Lookup: Checks a distributed cache (e.g., Redis Cluster) for the short code.
     • Cache Hit: If found, retrieves the original URL and returns an HTTP 301/302 redirect response.
     • Cache Miss: If not found, queries the primary datastore.
   • Datastore Lookup: Queries the primary datastore for the original URL associated with the short code.
   • Cache Update: If found in the datastore, the original URL is added to the cache for future requests.
   • Redirect: Returns an HTTP 301/302 redirect response with the original URL.
   • Error Handling: If not found, returns a 404 Not Found.
4. Click Analytics (Asynchronous): A separate service or mechanism (see Section 7) asynchronously records click events.

Trade-offs:

• Separation of Concerns: Separating read and write services allows independent scaling and optimization. The read path is optimized for low latency and high throughput.
• API Gateway/Load Balancer: Introduces a single point of failure if not configured for high availability, but essential for scaling and managing traffic.
• Cache Miss Penalty: A cache miss incurs higher latency due to datastore lookup, but this is mitigated by a large cache and a high hit ratio.

2. Short Code Generation Strategy

Strategy: Base62 Encoding with a Counter/ID Generator.

1. ID Generation: We'll use a distributed ID generation service (e.g., Snowflake-like or a dedicated service using ZooKeeper/etcd) to generate unique, monotonically increasing 64-bit integers. This ensures uniqueness and avoids collisions at the source.
   • Trade-off: Requires a highly available and performant ID generation service. If it fails, new short links cannot be created.
2. Base62 Encoding: Each generated 64-bit integer ID is converted into a Base62 string (0-9, a-z, A-Z). A 64-bit ID can represent up to 2^64 unique values. The first 6 characters can represent ~68 billion unique values (62^6), and 7 characters can represent ~4.1 trillion (62^7). For 30 billion links over 5 years, 7 characters are sufficient and provide ample room for growth.
   • Trade-off: Base62 encoding is slightly more complex than simple hashing but provides shorter URLs and avoids guessability compared to sequential IDs.
3. Custom Aliases:
   • When a user requests a custom alias (e.g., /my-link), the write service first checks if the alias is already taken in a dedicated table/index in the datastore (e.g., custom_aliases table mapping alias -> short_code).
   • If the alias is available, it's reserved and associated with the newly generated short code.
   • If the alias is taken, the API returns an error to the user.
   • Collision Handling: The ID generation and Base62 encoding ensure uniqueness for generated short codes. Custom aliases are handled via a separate, atomic check-and-set operation in the datastore to prevent collisions.
   • Trade-off: Custom alias lookups add a small overhead to the write path. Availability of custom aliases is not guaranteed.

Uniqueness Guarantee: Achieved by the distributed ID generator. Each ID is unique, and its Base62 representation will also be unique.

Non-guessable: Base62 encoded IDs are not sequential and do not reveal the order of creation or the total number of links. They are effectively random-looking strings.

3. Data Model and Datastore(s)

Datastore Choice: A distributed NoSQL key-value store (e.g., Cassandra, DynamoDB, or a sharded relational DB like Vitess) for the primary link mapping, and a separate system for analytics.

Primary Datastore (Link Mapping):

• Schema:

  • links table/collection:
    • short_code (Primary Key, String, e.g., "aBcDeFg")
    • original_url (String)
    • created_at (Timestamp)
    • user_id (Optional, for ownership/management)
  • custom_aliases table/collection:
    • alias (Primary Key, String, e.g., "my-link")
    • short_code (String, Foreign Key to links.short_code)

• Datastore Type Justification: A distributed NoSQL key-value store is chosen for its high availability, horizontal scalability, and excellent read performance for key lookups, which is critical for the redirect path. It can handle the massive scale of 30 billion entries.

• Capacity/Storage Estimate:

  • Links Table: 30 billion entries.
    • short_code: ~7 bytes (Base62, 7 chars)
    • original_url: Average 100 bytes (can vary significantly, assume average)
    • created_at, user_id: ~10 bytes
    • Total per entry: ~117 bytes. Let's round up to 150 bytes for overhead and replication.
    • Total storage: 30 billion * 150 bytes = 4.5 * 10^12 bytes = 4.5 TB.
  • Custom Aliases Table: Assume 10% of links have custom aliases (3 billion).
    • alias: Average 15 bytes (shorter than long URLs).
    • short_code: ~7 bytes.
    • Total per entry: ~22 bytes. Round up to 50 bytes for overhead.
    • Total storage: 3 billion * 50 bytes = 150 * 10^9 bytes = 0.15 TB.
  • Total Primary Storage: ~4.65 TB. This is manageable for distributed NoSQL systems.

• Partitioning/Sharding: The datastore will be sharded by short_code (for the links table) and alias (for the custom_aliases table). This allows for even distribution of data and load across nodes.

Trade-offs:

• NoSQL vs. SQL: A NoSQL store is preferred for schema flexibility and horizontal scaling. A relational DB could work but would require more complex sharding management (e.g., Vitess).
• Data Redundancy: NoSQL stores typically replicate data for availability, increasing storage requirements but improving fault tolerance.
• Custom Alias Table: A separate table is used to efficiently check for alias availability without scanning the main links table, which would be inefficient.

4. Caching Strategy

Strategy: Distributed In-Memory Cache (e.g., Redis Cluster, Memcached).

• What to Cache: Frequently accessed short_code to original_url mappings.
• Cache Key: short_code (e.g., "aBcDeFg")
• Cache Value: original_url (e.g., "https://www.verylongurl.com/...")
• Cache Size: Sized to hold a significant portion of hot links. Given 10K RPS and 100:1 ratio, we expect millions of active links per second. A cache holding 1-5 million entries should provide a high hit ratio for hot links.
• Cache Invalidation:
  • No explicit invalidation needed for standard links: Once created, links are immutable. The mapping doesn't change.
  • For custom aliases: If a custom alias is changed (not typically allowed, but if it were), the old short_code -> original_url mapping would remain in the cache. However, standard practice is that custom aliases are unique and permanent once set. If a link is deleted (not a common feature for URL shorteners), then the entry would be removed from the cache.
• Cache Miss Handling:
  1. On a cache miss, the US API (Read Service) queries the primary datastore for the original_url using the short_code.
  2. If found in the datastore, the original_url is written back to the cache with a Time-To-Live (TTL) (e.g., 24-48 hours) before being returned to the client.
  3. If not found in the datastore, a 404 is returned, and no entry is added to the cache.

Trade-offs:

• Cache Staleness: TTL-based caching means there's a small window where a link might be updated (if updates were allowed) and the cache would be stale. However, for immutable links, this is not an issue.
• Cache Availability: The cache is a critical component. If it fails, latency increases significantly due to datastore lookups, but the service remains available (though slower).
• Cost: Large in-memory caches can be expensive.

5. Scaling Strategy

Read Path Scaling (Redirects):

• Stateless API Servers: The US API instances handling redirects are stateless. This allows us to horizontally scale them infinitely behind a load balancer.
• Distributed Cache: A sharded and replicated distributed cache (like Redis Cluster) can handle millions of QPS and provides low latency. It's designed for horizontal scaling.
• Datastore Scaling: The chosen distributed NoSQL datastore (Cassandra, DynamoDB) is designed for horizontal scaling. We can add more nodes to increase throughput and capacity.
• Load Balancers: Load balancers at multiple layers (API Gateway, internal service-to-service) distribute traffic evenly.

Data Partitioning/Sharding:

• Datastore Sharding: As mentioned in Section 3, the primary datastore is sharded by short_code (or a hash of it) for the links table and alias for the custom_aliases table. This distributes data and read/write load across multiple nodes.
• Cache Sharding: The distributed cache is inherently sharded, distributing keys across its nodes.
• ID Generation Service: This service must also be scalable, potentially using multiple instances coordinated by ZooKeeper/etcd or a distributed consensus protocol.

Trade-offs:

• Complexity: Sharding and distributed systems add significant operational complexity.
• Hotspots: While sharding helps, extremely popular links could still create hotspots on specific cache shards or datastore partitions. Strategies like consistent hashing or more advanced load balancing can mitigate this.

6. Reliability and Failure Handling

Availability Target (99.99%): Requires redundancy at every layer.

• Datastore Node Failure:
  • Strategy: Data is replicated across multiple nodes (e.g., 3-5 replicas) and potentially across availability zones within a region.
  • Handling: The datastore cluster automatically handles node failures by promoting a replica and continuing to serve requests. Reads and writes might experience a brief spike in latency during failover, but the service remains available.
  • Trade-off: Increased storage costs due to replication.
• Cache Node Failure:
  • Strategy: Distributed caches like Redis Cluster are designed with replication and sharding. If a node fails, its replicas can take over, or data can be rebalanced.
  • Handling: Cache misses will increase temporarily as the cache rebuilds or fails over. The system will fall back to the datastore, leading to higher latency but continued availability.
  • Trade-off: Temporary performance degradation on cache failure.
• API Server Failure:
  • Strategy: Run multiple instances of the stateless US API servers behind load balancers.
  • Handling: Load balancers detect unhealthy instances and stop sending traffic to them. Traffic is automatically routed to healthy instances.
  • Trade-off: Requires robust load balancing and health checking.
• Region Failure:
  • Strategy: Deploy the service across multiple Availability Zones (AZs) within a region. For higher availability, a multi-region active-active or active-passive setup can be implemented.
  • Handling: If one AZ fails, traffic is routed to healthy AZs. If an entire region fails, traffic is routed to a secondary region (requires global load balancing and data replication).
  • Trade-off: Significant increase in complexity and cost for multi-region deployments.

Meeting Availability Target: Redundancy, automated failover, and graceful degradation (falling back to datastore on cache miss) are key. Monitoring and alerting are crucial for detecting and responding to failures quickly.

7. Click Analytics Collection

Strategy: Asynchronous processing to avoid impacting the critical redirect path.

1. Event Generation: When a redirect occurs (after the original URL is retrieved and before the redirect response is sent), the US API (Read Service) publishes a lightweight