Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Allows the user to add optional custom aliases. This adds namespace management capabilities.
• Optional TTL on links so they can expire automatically after a set duration.

Non-Functional Requirements:

• High availability
  • redirect API should be available at all times.
    • a user has no way to resolve the short URL without an available redirect API
  • create API can tolerate outages
• Low latency
  • redirects should be instantaneous
  • creation can tolerate higher latency
• Horizontal scalability
  • Should be able to scale to billions of stored URLs and tens of thousands of redirects per second.
• Durability
  • A URL mapping must never be lost.

Capacity Estimation

Traffic

• A mid size URL shortener should be able to create about 200 URLs per second, which approximates to about 17 million new URLs per day.
• Assuming a 100:1 read-to-write ratio, the redirect path should handle approximately 20,000 requests per second.
• Access pattern is highly skewed - a small fraction of the URLs generate the vast majority of the redirect traffic.
  • A relatively small cache will be able to absorb most of the read traffic.

Storage

• Each URL mapping contains:
  • Short code (7 bytes)
  • Long URL (100 bytes average)
  • User ID (20 bytes)
  • Created timetamp (8 bytes)
  • Expiration timestamp (8 bytes)
• A total of approximately 143 bytes.
  • Accounting for metadata, indexing overhead and padding would round up the total to 256 bytes.
• Daily storage growth: 200 requests/sec x 86,400 seconds x 256 bytes = approximately 4.4 GB per day.
• Over 5 years: 4.4 GB x 365 days x 5 years = approximately 8 TB
  • With growth buffer, plan for 10-15 TB.

Bandwidth

• Write bandwidth: 200 requests/sec x 256 bytes = approx. 50 KB/sec - negligible
• Read bandwith: 20,000 requests/sec x 256 bytes = approx 5 MB/sec - modest by modern standards

Cache Sizing

• With 17 million URLs per day and an average entry size of 256 bytes, caching 20% of the total dataset (approx. 6.2 billion entries) would require roughly 1.5TB of Redis memory.
• In practice, caching just the last 30 days of active URLs (approx. 500 million entries) in a Redis cluster with 200-300 GB memory should provide an 80-90% cache hit rate.
  • This is well know within the capacity of a modern Redis cluster

API Design

Create Short URL

POST /api/vi/urls

Request body:

• longUrl (required): destination URL to shorten
• customAlias (optional): user generated short code instead of a system generated one
• expiresAt (optional): ISO 8601 timestamp to define when the short URL should stop working

Response body:

• shortCode: system generated or user generated
• shortUrl: full short URL
• longUrl: echo of the destination URL for confirmation
• createdAt: timestamp of creation
• expiresAt: timestamp of expiry if set

Authentication: API key in the authorization header. Every write request must be associated with a registered account for rate limiting and abuse tracking.

Rate limit: 100 URLs per hour per API key for free tier. Higher limits for paid accounts. Returns 429 (Too Many Requests) when exceeded with a Retry-After header indicating when the client can try again.

Redirect

GET /shortCode

• Returns a 302 (Found) response with the Location header set to the original long URL. The browser follows the redirect automatically.
• No authentication required. Anyone with the shortUrl can follow it. This is intentional. Short URLs are shared publicly and must work for everyone who clicks them.
• Error handling:
  • If the short code doesn't exist or has expired, should return 404 (Not Found) with a JSON body explaining the error.
  • For expired links, include a message indicating the link has expired rather than saying "not found". This helps users understand what happened and reduces confusion.
• For SEO and social media capability, following standard headers should be added:
  • Cache-Control to control CDN behavior.
  • X-Robots-Tag (optional) to tell search engines whether to index the short URL or the long URL.

301 vs 302

301 (Moved Permanently):

• Browser caches the long URL. Next time, the same short URL is clicked, the browser will directly redirect to the destination without engaging the shortener service.
• Reduces server load.
• Trade off:
  • Analytics can not be tracked.
  • Cannot the update the destination URL.
  • Expiries can not be enforced, since the browser never checks back.

302 (Found):

• Redirect is temporary. Every click goes through the shortener service.
• Enables click analytics, destination updates and expiration enforcement.
• Trade off:
  • higer server load because every click hits your infrastructure.

For most URL shortening services, 302 is the right default.

• Analytics and policy controls outweigh the server load increase.
• Server load can be handled by CDN caching.
  • CDN caches the 302 response at edge locations, giving the load reduction of 301 with the flexibility of 302.

Rate Limiting

• Without rate limiting, a single malicious or misconfigured client could create millions of URLs, exhausting the short code space and consuming storage.
• Rate limiting protects shared resources and ensures fair usage.
• Implementation: per-API-key counters with sliding window limits, enforced at the API Gateway layer before requests reach the shortening service.

High-Level Design

Read (Redirect) path:

• Client click --> CDN --> API Gateway --> Mapping Service --> Redis Cache --> DynamoDB.
• Optimized for sub-10ms latency with multiple caching layers.
• CDN handles the hottest URLs at edge locations.
• Redis handles the warm set in the data center.
• DynamoDB is the durable fallback for cache misses.

Write (Shorten) path:

• Client request --> API Gateway --> Shortening Service --> Message Queue --> Queue Worker --> DynamoDB.
• Optimized for reliability and database protection.
• The shortening service creates the short URL and enqueues the write.
• The message queue decouples the client response from the durable write, smoothing traffic spikes.

Components

API Gateway:

• All external traffic enters through the gateway, providing a single enforcement point for authentication and throttling.
• Provides TLS termination, DDoS protection, request routing and rate limiting for write requests.

Shortening Service:

• Each instance ows an exclusive range of IDs, so codes are guaranteed unique at generation time.
• Generates short codes from the pre-allocated ID range, validates inputs, and enqueues write requests.
• Stateless and horizontally scalable behind a load balancer.

Mapping Service:

• Handles redirect requests.
  • Checks redis first, fall through to DynamoDB on cache miss.
• Also stateless.
• Most latency sensitive component.

Message Queue (SQS or Kafka):

• Buffers write requests between the shortening service and the database.
  • If a large number of requests arrive in one second, the queue absorbs the spike and the queue worker drains them at a steady rate that the database can comfortably handle.

Queue Worker:

• Consume messages from the queue and writes URL mappings to DynamoDB.
  • Since short codes are created from exclusive ID ranges, collision cannot occur and every write succeeds on first attempt.
• Rate limited to match database write capacity.

Redis Cache:

• Stores the warm set of URL mappings (recently and frequently accessed)
• LRU eviction policy ensures the cache holds the most useful entries.
• Cluster mode for horizontal scaling across multiple shards.

CDN (Cloudfront):

• Caches redirect responses at edge locations worldwide.
• For viral URLs, serves most of the redirect traffice without letting the requests reach the backend.
• Most impactful component for read performance.

DynamoDB:

• Durable source of truth for URL mappings.
• Handles cache misses from Redis.
• Supports conditional writes for custom alias conflict detection.
• Provides automatic TTL based expiration.

• Each component scales independently and clear responsiblities.
• CDN scales by adding edge locations (no code changes needed).
• Redis scales by adding shards to the cluster.
• Mapping service scales by adding instances behind the load balancer.
• Message queue scales by adding partitions.
• DynamoDB scales automatically by splitting partitions.
• CDN absorbs 80-90% of the traffic, Redis handles most of the rest and DynamoDB acts as the source of truth.

Database Design

Why a Key-Value Store

• Core operation of a URL shortener is a simple lookup: given a short code, return the long URL.
  • There are no joins, no multi-table transactions, no aggregation queries, and no complex filtering.
• DynamoDB is a good fit.
  • Managed operations with no infrastructure overhead.
  • Automatic horizontal scaling via partition-based distribution.
  • Single digit-millisecond reads at any table size.
  • Built-in replication across 3 AZs.
  • Conditional writes for atomic conflict detection on custom aliases.
  • Can either provision read and write capacity or avail on-demand mode.

Schema

• shortCode (partition key): 7-character Base62 code. Primary lookup key for every redirect.
• longUrl: original destination URL. approx. 100 bytes.
• userId: account that created the mapping. Associates records to specific users for management and billing.
• createdAt: Creation timestamp. Used for analytics and audit.
• expiresAt: Optional expiration time. DynamoDB TTL uses this field to automatically delete expired items at no read/write cost.

Secondary Indices

GSI on longUrl:

• Enables duplicate detection
• When a user submits a longUrl that has already been shortened, the system can check the GSI in O(1) time and return the existing short code instead of creating a new one.

GSI on userId:

• Useful for user management dashboard.
• User can query all URLs to view click statistics, update destinations, or delete records.
• Without the GSI, a full table scan would be required to list a user's URLs.

Why Not PostgreSQL

• Is a viable option for loads under 5,000 reads/sec.
• As the dataset grows to billions of rows and reads exceed 20,000 per second, PostgreSQL will require significant modifications like - connection pooling, read replicas, manual sharding, and careful index tuning.
  • DynamoDB handles this automatically through partition based scaling.

Why Not Redis Alone

• Excellent as cache, but risky as the sole data store.
• Stores data in volatile memory.
  • Involves issues like server restart, out-of-memory condition, or failover gap can lose data.
• Redis persistence modes like, RDB snapshots and AOF logs, reduce the risk but introduce write latency and still have small data loss windows during crashes.
• Since loss of any mapping would mean a permanently broken short url with no recovery path, a durable databse backing the cache is essential.

Consistency Model

• URL shortening can tolerate eventual consistency for a brief window.
  • When a new short URL is created, the mapping may not be immediately readable from DynamoDB or Redis.
  • This window is typically under 1 second for DynamoDB eventually consistent reads and 0 for for strongly consistent reads.
• For the redirect endpoint, eventually consistent reads are acceptable - worst case is a single 404 that resolves on retry.
• For the write path, since short codes are selected from an exclusive range of pre-allocated IDs, queue worker's write to DynamoDB doesn't need strong consitency for collision detection.
• Conditional writes will be available as a safety net for custom aliases, where two users could ask for the same alias simultaneously.

Detailed Component Design

Short Code Generation

• A short code uses Base62 encoding.
• a-z, A-Z, 0-9 - total of 62 characters per position
• 7-character code provides 3.5 trillion possible values.
• At a rate of 200 new URLs per second for 10 years, will only exhaust 2% of the code space.

Approach 1: Hash then truncate

• Hash the long URL using MD5 or SHA256 and then take the first 7 characters of the Base62-encoded hash.
• Deterministic - same long URL always creates the same short code.
• Provides natural deduplication.
• Truncating a hash increases collision probability due to the birthday paradox.
  • With 7 characters (3.5 trillion values), the probability of at least 1 collision reaches 50% at around 2 million entries.

Approach 2: Random generation

• Generate random 7-character Base62 encoded hash for each URL.
• Provides excellent distribution across the code space and avoids the truncation problem.
• Trade off - two submissions of the same long URL generate different short codes.
  • A separate deduplication mechanism is needed
  • Deduplication can be implemented by creating a longUrl GSI in DynamoDB.
• Collision probability smaller than truncated hashes because the full 7-character space is utilized uniformly.

Approach 3: Range-based counter (chosen approach)

• A coordination service (Zookeeper or DynamoDB) pre-allocates large ranges of sequential IDs to each application server.
  • Server A gets x to x + n, server B gets x + n + 1 to x + 2n + 1.
  • Each server generates sequential IDs within its range and Base62 encodes them.
• Zero collision probability within a range.
• When a range is exhausted, the server requests a new one.
• Guarantees code uniqueness at generation time, making the async queue-based write pattern safe.
• Trade off -
  • Requires a coordination service.
  • Sequential IDs are somewhat predictable - can be mitigated by shuffling or salting the Base62 encoding.

Collision Handling with Conditional Writes

• With range based allocation, conditional writes can be used as a safety net (especially for custom aliases).
• DynamoDB provides conditional writes.
• A conditional write is an atomic operation; it either succeeds or returns a ConditionalCheckFailedException in a single round trip.
  • No race condition window between checking and inserting, because the check and the insert are the same operation.
• With range based allocation, collisions cannot occur because each server owns an exclusive ID range.
• Custom aliases are the primary use-case for conditional writes; two users might request the same alias simultaneously.
  • Shortening service performs a synchronous conditional write (bypassing the async queue) to confirm the alias is available before returning it to the client.
• Alternative - a separate read-then-write pattern - has a fatal race condition.
  • Two concurrent requests can both conclude to non-existence of the custom alias and then proceed to write the same, one overriding the other.

Caching Strategy

• CDN (hot tier)
  • Caches 302 redirect responses at edge locations.
  • TTL based expiration ensure updates eventually propagate.
  • Best for viral and popular URLs that receive thousands of clicks per second.
• Redis (Warm tier)
  • In-datacenter cache using cluster mode with multiple shards.
  • Stores millions of URL mappings with LRU eviction.
  • Cache-aside pattern is used over write-through.
    • Write-through caching would fill Redis with millions of cold entries that nobody clicks, wasting memory.
    • Cache-aside only populates the cache with URL mappings that generate actual traffic, maximizing the cache hit rate for a given memory budget.
• Cache invalidation
  • When a URL mapping is updated or deleted, the corresponding cache entries must be invalidated in both Redis and CDN.
  • For Redis - delete the key directly.
  • For CDN - use cache invalidation APIs or rely on short CDN TTL for eventual consistency.
    • CDN TTL approach is simpler and brief staleness window is acceptable for most use cases.
• Partitioning
  • Both Redis and DynamoDB partition by the short code hash.
    • Short code is the ideal partition key:
      • It is the primary lookup key - every redirect uses it.
      • Drawn from a large uniform space - even distribution after hashing.
      • It is fixed-length - consistent hashing behavior.
  • Alternative - long URL
    • Long URLs vary wildly in length and structure.
    • Some domains would concentrate on a few partitions while others have a few entries.
  • Alternative - user ID
    • Creates hotspots when a single user generates millions of URLs.