How to Generate Billions of Conflict‑Free Short URLs

Step 1 – Quantify the Scale

The system must generate 5 × 10⁸ short URLs per month, kept for two years, resulting in 1.2 × 10¹⁰ total entries. Each entry occupies roughly 1 KB, so storage needs are about 12 TB. Average read frequency is 100× per URL, giving an average QPS of 20 k; peak traffic is estimated at 40 k QPS.

Six‑character Base64 strings provide 64⁶ ≈ 6.8 × 10¹¹ combinations, far exceeding the 1.2 × 10¹⁰ required, confirming that a 6‑character code is sufficient.

Step 2 – Compare Generation Algorithms

Option 1: One‑way hash – Compute MD5 or SHA‑256 of the long URL, Base64‑encode, and truncate to six characters. This can cause collisions; resolving them requires additional lookups, harming performance.

Option 2: Auto‑increment ID – Encode sequential integers in Base64. Collisions never occur, but the resulting codes are predictable, which is a security risk because an attacker can infer adjacent URLs.

Option 3: Pre‑generation – Generate the entire pool of random six‑character strings offline, de‑duplicate them, and store them in a file. At runtime the service simply draws a code from the pool. This moves the hardest part—conflict detection—to an offline batch process.

The article selects Option 3 because it eliminates online conflict checks and avoids the performance bottleneck.

Step 3 – Use a Bloom Filter for Offline De‑duplication

To verify that 1.44 × 10⁹ randomly generated codes (20 % extra over the required 1.2 × 10⁹) are unique, a Bloom filter is employed. The filter uses a large bit array and multiple hash functions; a bit still at 0 guarantees the code is new, while all bits at 1 indicate a possible duplicate.

After filtering, the unique codes occupy 86.4 GB in HDFS.

Step 4 – Three‑Layer Architecture to Handle 40 k QPS

Layer 1 – Load Balancer : Distributes incoming requests across a cluster of short‑URL servers, ensuring high availability.

Layer 2 – Redis Cache : Serves the hot 80 % of requests (those generated within the last six days, about 100 million URLs) from memory. With ~100 GB of RAM, Redis responds in ~1 ms, handling the majority of traffic without hitting the database.

Layer 3 – HBase Persistent Store : Handles the remaining 20 % of cache misses. HBase delivers an average response time of ~10 ms, satisfying the overall latency target.

Performance accounting: 80 % of requests < 5 ms (Redis), 20 % < 20 ms (HBase), yielding an overall average latency < 10 ms.

Design Template

The four‑step process—capacity calculation, algorithm selection, offline de‑duplication with a Bloom filter, and layered caching/storage—forms a reusable template for any massive‑data, high‑concurrency system such as file‑fingerprint services, order‑number generators, or message‑ID allocators.

The core principle is to trade space for time and move work offline whenever possible.