URL Shortener

Assume 100M new short URLs per month, a 100:1 redirect to create ratio, 30 days per month, a five-year retention window, an average URL mapping record of 500 bytes, and a peak traffic multiplier of 10x over average.

The 500-byte record includes the short code, long URL pointer or normalized long URL, timestamps, owner metadata, TTL, status flags, and small counters. Large analytics events are stored separately.

• Writes: 100M URLs per month divided by 30 days is 3.33M writes per day. 3.33M divided by 86,400 seconds is about 38.6 writes per second, rounded to 39.
• Reads: with a 100:1 read to write ratio, average redirect traffic is 3,860 reads per second, rounded to 3,900.
• Peak: using a 10x traffic multiplier gives about 390 write QPS and 39,000 redirect QPS.
• Records: 100M per month for 60 months is 6B URL mappings.
• Storage: 6B records times 500 bytes is 3,000,000,000,000 bytes, about 3 TB raw. With 3 replicas, indexes, tombstones, and compaction headroom, plan for 10 to 12 TB.
• Bandwidth: redirect responses are mostly headers. 3,900 redirects per second times about 500 bytes is about 1.95 MB per second average. Peak is about 19.5 MB per second before TLS and network overhead.
• Cache: the 80/20 rule says 20 percent of URLs may drive 80 percent of reads. If the active monthly set is 100M URLs, caching 20M hot mappings at 500 bytes is 10 GB raw. Redis object overhead and fragmentation often double or triple that, so reserve 20 to 30 GB per fully replicated hot cache tier.
• Keyspace: 6 base62 characters provide 62 to the power of 6, or about 56.8B codes. That covers 6B mappings but leaves less room for reserved, expired, and custom aliases. 7 base62 characters provide about 3.5T codes and are safer.

• urls.short_code is the primary key and must support single-row point lookup.
• urls.user_id, created_at supports user dashboards and link history.
• urls.expires_at supports background expiration sweeps or database TTL policies.
• users.email is unique for login.
• Avoid a secondary index on long_url for the redirect path. Deduplication by long URL is optional and often not worth the write amplification.

Each URL may belong to one user, but anonymous links have no user. Analytics aggregates reference short_code and can be rebuilt from raw events if necessary. The redirect service should not join across tables during a redirect.

A distributed key-value database such as DynamoDB, Cassandra, Bigtable, or FoundationDB fits the serving path well. Use short_code as the partition key, store the full redirect record as the value, and make reads single-partition lookups.

The design needs conditional writes for custom aliases and generated key claims. DynamoDB conditional put, Cassandra lightweight transaction for rare alias creation, or a separate key allocation service can enforce uniqueness. Analytics belongs in a write-optimized event pipeline and OLAP store, not in the primary redirect KV table.

There are three common approaches, and a strong answer compares them explicitly.

Counter plus base62: maintain a monotonically increasing integer and encode it using characters 0-9, a-z, and A-Z. It is compact, deterministic, and collision-free if the counter is serialized correctly. The downside is coordination. A single counter becomes a bottleneck, while distributed counters need range allocation, Snowflake-style IDs, or database sequences. Sequential codes are also enumerable, so attackers can scan links unless rate limiting and randomization are added.

Hash long URL: compute MD5, SHA-256, or another hash of the long URL and take the first N base62 characters. This avoids a central counter, but collisions are possible because the output is truncated. The system must check whether the candidate code already exists and retry with a salt, longer prefix, or random suffix. Hashing also makes duplicate long URLs produce the same short code unless user identity or salt is included, which may or may not be desirable.

Pre-generated Key Generation Service: generate random or sequential base62 codes offline and store them in two logical databases: unused_keys and used_keys. Create requests atomically move a code from unused to used and then write the URL mapping. This keeps code allocation fast, avoids collisions on the request path, and allows workers to prefetch batches. The tradeoff is operational complexity: the unused pool must be replenished, allocation must be idempotent, and lost prefetched batches need recovery.

For this question, the KGS or range-allocated counter approach is usually the cleanest interview answer because it gives uniqueness without repeated collision checks at high scale.

301 Moved Permanently tells clients and search engines that the redirect is permanent. Browsers and intermediate caches may cache it aggressively. This reduces load and latency, but it can bypass the service on later visits, which weakens click analytics, abuse takedowns, and destination changes.

302 Found or 307 Temporary Redirect keeps clients coming back to the shortener each time. That costs more serving capacity, but it preserves analytics accuracy, lets the service enforce expiration, and allows links to be disabled quickly. Most interview designs choose 302 by default.

A mature product can support both. For user-owned campaign links with analytics, use 302 and Cache-Control: no-store. For internal immutable links with no analytics requirements, 301 plus edge caching can reduce cost.

The cache should store the full redirect decision, not just the long URL. Include long URL, expiration, status, owner policy flags, and redirect type so the service does not need a database read on a hit.

Use read-through caching on misses and write-through or cache warming on creates. TTL should be the minimum of a default cache TTL and the link expiration time. Negative-cache unknown short codes for a short period such as 30 to 120 seconds to protect the database from random scans.

The 80/20 assumption is powerful here: if 20 percent of active links drive 80 percent of redirects, a modest Redis fleet can remove most database traffic. Track cache hit ratio, p99 cache latency, miss amplification, hot-key skew, and eviction rate. For celebrity or viral links, replicate hot keys across cache shards or use local in-process caching to avoid one shard becoming overloaded.

Custom aliases are user-visible and must be treated differently from generated keys. Validate length, allowed characters, reserved words, impersonation risk, trademarks for enterprise customers, and case sensitivity. A good default is case-sensitive generated codes but case-insensitive custom aliases only if the product explicitly wants that behavior.

The database operation must be atomic: insert the alias only if short_code does not already exist. Never check then insert in two separate steps because concurrent requests can both pass the check. If an alias is taken, return 409 Conflict and let the caller choose another.

Generated-code collisions should be invisible to users. With a KGS, collisions are prevented before allocation. With hash or random generation, the create service retries with a salt or longer code after a conditional insert fails. Put a small retry bound and surface a 500 only if the keyspace or generator is unhealthy.

A relational database is acceptable for a small single-region prototype, but the production serving path is a key-value workload: lookup by short code and return one record. That favors DynamoDB, Cassandra, Bigtable, or another horizontally scalable KV store.

Partition by short_code. Base62 codes generated sequentially can create hot partitions if the partitioner preserves prefix order, so use a database with hash partitioning or randomize prefixes. Replicate data across availability zones, use quorum or leader-based writes depending on the store, and keep redirect reads local to the serving region whenever possible.

Secondary indexes should not be needed for redirects. User dashboards and analytics can use separate tables optimized for user_id and time. This separation keeps the redirect store small, predictable, and highly available.

Counting clicks synchronously in the urls row is a common beginner mistake. A viral link could turn one row into a write hotspot, and the redirect would depend on the analytics store.

Instead, the redirect service emits an event after resolving the URL. The event pipeline can batch, sample if product allows it, and aggregate by short code and time window. For unique visitors, use approximate sketches such as HyperLogLog rather than storing every visitor in the serving database.

If analytics delivery fails, redirects should continue. The system can buffer locally for a short time, drop non-critical events under pressure, or write to a durable queue with backpressure, but it should not turn analytics degradation into redirect downtime.

Alternative one is a pure hash-based system: hash the long URL, truncate, and retry on collision. It is easy to build but collision handling and duplicate semantics become tricky.

Alternative two is a database sequence with base62 encoding. It is clean for a single region but needs range allocation or sharded sequences at scale.

Alternative three is edge-only redirect hosting for immutable links. It is extremely fast and cheap for static mappings, but weak for analytics, expiration, and abuse response.

Do not use a public URL shortener for sensitive access-control decisions. Anyone with the short link can usually access the destination. If the problem requires private sharing, signed URLs, authorization checks, or expiring secrets, design an access-controlled sharing system rather than a simple shortener.