Design a URL shortening service like TinyURL or Bit.ly

Question

Accepted Answer

A URL shortener like TinyURL or Bit.ly converts an arbitrarily long URL into a compact alias — typically 6–8 characters — and then redirects any browser that visits the alias back to the original URL. The service sounds trivial but hides several interesting design problems: globally unique key generation without coordination bottlenecks , a read-to-write ratio of roughly 100:1 requiring aggressive caching, and analytics pipelines that must not add latency to the critical redirect path. Requirements and Scale Functional requirements: shorten a URL, redirect to the original, optional custom aliases, optional TTL/expiration, and click analytics. Non-functional: sub-10ms redirect latency at p99, 99.99% availability, and five-year durability. At scale, assume 100 million new URLs per month (roughly 40 writes/second) and a 100:1 read ratio, yielding about 4,000 redirect reads per second . Each record is ~500 bytes, so the dataset grows by ~50 GB/month — roughly 3 TB over five years, well within a single distributed key-value store. The Core Problem: Unique Short Key Generation A 7-character Base62 key (alphabet [A-Za-z0-9] ) gives 62^7 ≈ 3.5 trillion unique keys — comfortably more than any foreseeable need. There are three standard strategies for generating them: Hash-based — compute MD5 or SHA-256 of the long URL and take the first 7 Base62 characters. Simple, but collisions (different URLs mapping to the same prefix) require retry logic and break the idempotent property (two users shortening the same URL should ideally get the same short code). Distributed counter — a coordination service (ZooKeeper, or a Snowflake-style 64-bit ID generator embedding timestamp + machine ID + sequence) hands each app server a numeric ID, which is Base62-encoded into the short code. IDs are globally unique, sortable by creation time, and require no collision handling. The downside is that IDs are predictable — sequential enumeration reveals all shortened URLs. Key Generation Service (KGS) — a dedicated service pre-generates millions of random Base62 keys, stores them in a keys table with a used flag, and hands them out atomically (using a SELECT FOR UPDATE or a Redis SPOP ). Guarantees uniqueness, avoids runtime collision retries, and is the most scalable for high-write scenarios. Each app server can pre-cache a batch of ~1,000 keys in memory to eliminate network round trips on every write. Storage Layer The data model is a simple key-value map: short_key → (long_url, created_at, expires_at, user_id) . A NoSQL key-value store like DynamoDB or Cassandra is the natural fit — lookups are single point reads by the short key, write throughput is easily sharded, and TTL-based expiration is a native feature. A relational database (PostgreSQL with the short key as primary key) also works at this scale. The critical addition is a Redis cache in front: the hot 20% of links drive 80% of traffic (Zipf distribution), so caching popular short keys with a TTL of 24 hours collapses most redirect reads to sub-millisecond latency. Read and Write Paths The write path is: client → API gateway → shorten service → fetch a key from the KGS → write {short_key, long_url, metadata} to the DB → cache the mapping in Redis → return the short URL. The read path (the performance-critical one) is: client → CDN or edge cache → redirect service → Redis cache hit → HTTP 302 redirect response. On a cache miss, the redirect service queries the database and populates the cache for subsequent requests. Key trade-off — 301 vs 302 redirect: A 301 Permanent redirect is cached by the browser; subsequent visits to the same short URL bypass your servers entirely, saving infrastructure cost. A 302 Temporary redirect forces every click back through your origin, enabling accurate click analytics but increasing load. For a paid product that sells analytics, 302 is the right default. For a free link shortener optimizing for cost, 301 makes sense. Analytics Without Slowing Down Redirects Click tracking must not add latency to the redirect. The pattern is to publish click events (timestamp, short key, IP, referrer, user-agent) to a Kafka topic asynchronously — the redirect service fires-and-forgets the event and issues the 302 immediately. Downstream consumers aggregate clicks into a ClickHouse or data warehouse table, powering dashboards that show clicks per day, geographic distribution, and referrer breakdown. Scaling and Reliability Database sharding by a hash of the short key distributes read/write load evenly across DB nodes. Read replicas in each region serve local redirect traffic with low latency; writes go to the primary. CDN edge nodes can cache popular short-key redirects globally, serving responses from the closest PoP. Expiration is handled by setting a expires_at column and running a background sweeper, or by using native TTL in DynamoDB/Redis. Abuse protection — phishing and malware are serious risks; integrate a URL reputation API (Google Safe Browsing) during the