Building a URL Shortener with 7 ms Redirects: LRU, Redis and PostgreSQL Caching

TL;DR. Shortify is a URL shortener I built with Node.js (Express), Redis and PostgreSQL. A redirect checks an in-process LRU cache, then Redis, then a Bloom filter that rejects codes that cannot exist, and only then PostgreSQL, behind a Redis lock that stops a cache stampede. Short codes are Snowflake IDs in Base62, a token bucket in Redis rate-limits each IP, and every link gets a QR code generated on the fly. It runs on AWS EC2 with Docker Compose, deployed by GitHub Actions, with a static frontend on S3. In a k6 test with 50 virtual users, redirects averaged 7.12 ms (median 4.08 ms) with a 100% success rate. This post walks through each layer, what the benchmark really measures, and what I would fix next.

Code: GitHub · Live frontend: Shortify on S3

The shape of the problem

A URL shortener has two operations with very different traffic:

• Shorten (POST /api/shorten): rare. Generate a unique code, store the mapping, return the short URL and a QR code.
• Redirect (GET /:shortCode): constant. Every click on every link in every chat and email lands here, and the user is waiting.

Reads outnumber writes by orders of magnitude, so almost every design decision below is about making the redirect path fast and keeping it away from the database.

                    GET /aB3x9Qk2Lm
                           │
        ┌──────────────────▼──────────────────┐
        │ token bucket (Redis, per IP)        │── empty ──▶ 429
        ├─────────────────────────────────────┤
        │ L1: in-process LRU (5,000 entries)  │── hit ──▶ 302
        ├─────────────────────────────────────┤
        │ L2: Redis (1 h TTL)                 │── hit ──▶ fill L1, 302
        ├─────────────────────────────────────┤
        │ Bloom filter (Redis bitmap)         │── "definitely not" ──▶ 404
        ├─────────────────────────────────────┤
        │ stampede lock (SET NX EX 5)         │── held by another ──▶ wait 50 ms, retry
        ├─────────────────────────────────────┤
        │ PostgreSQL (source of truth)        │──▶ fill L2 and L1, release lock, 302
        └─────────────────────────────────────┘

Generating short codes: Snowflake IDs in Base62

The code has to be unique, short, and cheap to generate. The common options all have a catch:

• A database sequence is unique and compact, but every shorten request needs a round trip to one central counter.
• Random strings (nanoid, UUIDs) need no coordination, but a collision is possible, so you check the database before every insert.
• A hash of the long URL collides too, and gives the same code to everyone who shortens the same URL, which breaks per-link expiry and custom aliases.

I used Snowflake IDs, the scheme Twitter designed for exactly this. A 64-bit ID packs 41 bits of milliseconds since a custom epoch, a 10-bit machine ID and a 12-bit per-millisecond sequence, so a single process can generate 4,096 unique IDs per millisecond with no coordination at all:

generate() {
    let timestamp = this._timeGen();
    if (timestamp < this.lastTimestamp) {
        throw new Error('Clock moved backwards. Refusing to generate id');
    }
    if (timestamp === this.lastTimestamp) {
        this.sequence = (this.sequence + 1n) & this.maxSequence;
        if (this.sequence === 0n) {
            timestamp = this._tilNextMillis(this.lastTimestamp); // 4,096 IDs used up: wait 1 ms
        }
    } else {
        this.sequence = 0n;
    }
    this.lastTimestamp = timestamp;
    return (((timestamp - this.epoch) << this.timestampShift) |
            (this.machineId << this.machineIdShift) |
            this.sequence).toString();
}

JavaScript numbers lose precision above 2^53, so the generator uses BigInt throughout. The ID is then encoded in Base62 (0-9a-zA-Z), which is URL-safe, unlike Base64's + and /. The epoch starts in 2024 rather than 1970 so that 41 bits of milliseconds last about 69 years from launch instead of running out decades sooner.

Two consequences I only worked out later:

• Codes are 10 characters today and grow over time. The timestamp sits in the high bits, so IDs increase steadily. Around 2030 they pass 62^10 and become 11 characters long, which would overflow the VARCHAR(10) short-code column in the schema. Shorter codes would need either fewer timestamp bits or a counter-based scheme.
• Machine IDs must be unique per process. Every instance currently uses machine ID 1. That is fine for one server, but a second instance would generate colliding IDs. Each instance should get its ID from configuration (or from a coordinator such as ZooKeeper or etcd).

The redirect path, layer by layer

Here is the core of the handler, slightly trimmed:

export const redirectUrl = async (req, res) => {
    const { shortCode } = req.params;

    const l1Result = l1Cache.get(shortCode);                     // 1. in-process LRU
    if (l1Result) return res.redirect(l1Result);

    const l2Result = await redisClient.get(`url:${shortCode}`);  // 2. Redis
    if (l2Result) {
        l1Cache.set(shortCode, l2Result);
        return res.redirect(l2Result);
    }

    if (!(await bloomFilter.mightContain(shortCode))) {          // 3. Bloom filter
        return res.status(404).json({ error: 'URL not found' });
    }

    const acquiredLock = await redisClient.set(`lock:${shortCode}`, '1', { NX: true, EX: 5 });
    if (!acquiredLock) {                                         // 4. someone else is loading it
        await sleep(50);
        return redirectUrl(req, res);
    }

    const result = await pool.query(                             // 5. PostgreSQL
        'SELECT original_url, expires_at FROM urls WHERE short_code = $1', [shortCode]);
    // ... 404 if missing, 410 Gone if expired
    await redisClient.set(`url:${shortCode}`, originalUrl, { EX: 3600 });
    l1Cache.set(shortCode, originalUrl);
    await redisClient.del(`lock:${shortCode}`);
    res.redirect(originalUrl);
};

L1: an in-process LRU cache

The first layer is an LRU cache inside the Node.js process (the lru-cache package, up to 5,000 URLs with a 5-minute TTL). A hit costs no network round trip at all, which is as fast as a lookup can get. The trade-offs: each instance has its own copy, and a change to a link becomes visible only once the 5-minute TTL expires. Short links almost never change, so that staleness bound is acceptable here.

L2: Redis

The second layer is shared across instances: a Redis key url:<code> with a one-hour TTL. On an L2 hit the URL is copied into L1, so the next click on that instance skips the network entirely. Popular links therefore stay in memory at two levels without anyone deciding in advance what is "popular".

A Bloom filter against cache penetration

A request for a code that does not exist misses both caches by definition. If someone requests millions of random codes, every one of them would reach PostgreSQL. This is called cache penetration, and it is a cheap way to overload a database.

A Bloom filter answers "definitely not present" or "maybe present" from a fixed amount of memory. Shortify keeps it in a Redis bitmap so every instance shares it, sized with the standard formulas for 1 million URLs at a 1% false-positive rate:

• bits: m = −n·ln(p) / (ln 2)² ≈ 9,585,058 bits, about 1.14 MB
• hash functions: k = (m/n)·ln 2 ≈ 7

function getHashIndices(str) {
    const indices = [];
    for (let i = 0; i < K_HASHES; i++) {
        indices.push(fnv1a(str + i) % M_BITS);  // 7 different FNV-1a hashes via a suffix
    }
    return indices;
}

async mightContain(shortCode) {
    const pipeline = redisClient.multi();       // 7 GETBITs, one round trip
    for (const index of getHashIndices(shortCode)) pipeline.getBit(BLOOM_KEY, index);
    const results = await pipeline.exec();
    return !results.some((bit) => bit === 0);
}

Every new code is added when it is created. The check sits after both caches on purpose: hot codes never pay for it, and only the unusual requests (true misses) do. If Redis errors, the filter fails open and lets the request through to the database, which is the safer side to fail on.

Stopping a cache stampede with SET NX

When a popular link drops out of Redis (its TTL expires), hundreds of concurrent requests can all miss at the same moment and all query PostgreSQL for the same row. This is the thundering-herd, or cache-stampede, problem.

Shortify lets exactly one request rebuild the cache: it takes a lock with SET lock:<code> 1 NX EX 5, which succeeds only if the key does not exist yet. Everyone else waits 50 ms and starts again from the top, by which time they usually hit L2. The 5-second expiry ensures that a crashed lock holder cannot block a link forever.

One subtlety is worth knowing for interviews. The lock is released with a plain DEL. If the query took longer than 5 seconds, the lock could already have expired and been taken by another request, and the DEL would release their lock. The standard fix is to store a unique token as the lock's value and release it with a small Lua script that deletes only if the token still matches (see Redis's notes on distributed locks).

PostgreSQL: the source of truth

PostgreSQL stores every mapping, with expiry and optional custom aliases:

CREATE TABLE urls (
    id VARCHAR(15) PRIMARY KEY,           -- the Snowflake ID
    original_url TEXT NOT NULL,
    short_code VARCHAR(10) UNIQUE NOT NULL,
    custom_alias VARCHAR(50) UNIQUE,
    expires_at TIMESTAMP WITH TIME ZONE,
    created_at TIMESTAMP WITH TIME ZONE DEFAULT CURRENT_TIMESTAMP
);

Thanks to the two cache layers, the database sees a request only on the first click of a link, or once per hour per link after the Redis entry expires. Expired links return 410 Gone rather than 404, which tells the client the link existed but is no longer valid.

Rate limiting with a token bucket in Redis

Shortening and redirects are both rate-limited per IP address with a token bucket: each IP gets a bucket of 5 tokens that refills at 1 token per second. A request spends a token; an empty bucket gets 429 Too Many Requests. Unlike a fixed window, a token bucket allows short bursts and enforces the average rate without a reset boundary that clients can game.

The bucket is a Redis hash, so the limit holds across all app instances:

const data = await redisClient.hGetAll(key);
const now = Math.floor(Date.now() / 1000);
let tokens = capacity;
if (Object.keys(data).length > 0) {
    const timePassed = now - parseInt(data.lastRefill);
    tokens = Math.min(capacity, parseFloat(data.tokens) + timePassed * refillRate);
}
if (tokens < 1) {
    return res.status(429).json({ error: 'Too Many Requests. Please wait.' });
}
await redisClient.hSet(key, ['tokens', (tokens - 1).toString(), 'lastRefill', now.toString()]);
await redisClient.expire(key, windowSec);   // idle buckets disappear after 60 s

There is a race in this version. It reads the bucket and writes it back in two separate steps, so two requests from the same IP that arrive together can both read "1 token left" and both get through. The fix is to make read-refill-spend a single atomic operation with a Lua script, which Redis runs without interleaving other commands:

-- KEYS[1] = bucket key, ARGV = capacity, refill rate, now
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or tonumber(ARGV[1])
local ts = tonumber(b[2]) or tonumber(ARGV[3])
tokens = math.min(tonumber(ARGV[1]), tokens + (tonumber(ARGV[3]) - ts) * tonumber(ARGV[2]))
if tokens < 1 then return 0 end
redis.call('HSET', KEYS[1], 'tokens', tokens - 1, 'ts', ARGV[3])
redis.call('EXPIRE', KEYS[1], 60)
return 1

The limiter also fails open: if Redis is unreachable, requests are allowed rather than rejected, which keeps the service up at the cost of temporarily losing protection.

QR codes without storing images

Each shortened link comes back with a QR code. Instead of rendering PNG files and storing them in S3, the API generates the image on the fly with the qrcode package and returns it as a data:image/png;base64,… URL inside the JSON response. Nothing is stored, and the frontend can drop the string straight into an <img> tag.

Deployment: Docker Compose on EC2, CI/CD with GitHub Actions

The stack is three containers defined in Docker Compose: the Node.js app (node:20-alpine), PostgreSQL 15 and Redis 7. It runs on an AWS EC2 instance. On every push to main, a GitHub Actions workflow connects to the instance over SSH, pulls the code, writes the .env file from repository secrets, and runs docker compose up -d --build. The frontend is a static page hosted on S3, calling the API with CORS enabled.

The load test, and what it actually measures

I load-tested the redirect endpoint with k6: ramp up to 50 virtual users over 5 seconds, hold for 10, ramp down over 5, each user requesting a short link (without following the redirect) and pausing 100 ms between requests.

Two caveats. The token-bucket limiter was switched off for this run, because all 50 virtual users share one IP and a 5-request burst would have throttled them, so these numbers measure the redirect path, not the limiter. And the test requested a single short code, so after the first request every redirect was an L1 hit. The 7.12 ms is therefore the hot path: Express, the in-process cache and the local network stack. It is a useful number, but it says nothing about Redis or PostgreSQL. A more honest test would draw codes from a large set with a skewed (Zipf-like) popularity, so all three layers get exercised in realistic proportions.

What I would change next

• Make the limiter atomic with the Lua script above.
• Bound the stampede retries (today a waiting request retries until the lock frees up) and release locks with a token check.
• Respect expiry in the caches. Cache hits do not check expires_at, so an expired link can keep redirecting for up to an hour from Redis. Setting each cache TTL to the time remaining until expiry fixes that.
• Degrade gracefully when Redis fails. The Bloom filter and the limiter already fail open, but an error from the L2 lookup still fails the whole redirect. Wrapping it would let a Redis outage fall back to PostgreSQL.
• Let the database enforce uniqueness of custom aliases. The code checks with a SELECT before inserting, so two simultaneous requests for the same alias can both pass the check, and one then fails with a 500. Catching the UNIQUE violation and returning 409 Conflict is both simpler and race-free.
• Drop the duplicate index. The schema also creates an index on short_code, but the UNIQUE constraint already creates one, so every insert maintains two identical B-trees.
• Widen short_code before the Snowflake codes grow past 10 characters, and give each instance its own machine ID.

If you are preparing a URL-shortener system design question, building one end to end is worth it: most of these issues only show up once real code runs under load.