Building a URL Shortener Like a Jedi: The Cache Awakens

The Quest Begins (The “Why”)

I still remember the first time I tried to spin up a toy URL shortener for a hackathon. I had a slick frontend, a POST endpoint that generated a random 6‑character code, and a simple in‑memory map to store the lookup. Everything worked locally — until I fired up two instances behind a load balancer and started hammering the API with a quick hey load test.

Requests began to fail with 429s, not because I’d intentional‑ly throttled them, but because each node kept its own counter. When the load spiked, one instance would think it was under the limit while another had already blown past it, and the downstream database got hammered with duplicate inserts. It felt like trying to herd cats while blindfolded.

That night, after three cups of coffee and a frustrating stack trace, I realized the real dragon wasn’t the hash generation or the DB schema — it was coordinating rate limiting across a distributed system. If I could nail that, the rest of the shortener would fall into place like a lightsaber finding its hilt.

The Revelation (The Insight)

The breakthrough came when I stopped thinking about “counters per process” and started treating the limiter as a shared, atomic service. The key insight: use a single source of truth that can evaluate and update the quota in one indivisible step.

Enter Redis. It’s fast, supports atomic operations via Lua scripts, and can be clustered for horizontal scale. By moving the quota check into a Lua script that runs inside Redis, we guarantee that:

1. Check‑and‑update is atomic – no two concurrent requests can both see “under limit” and both increment past the threshold.
2. Network round‑trips are minimized – one call to Redis does the work; we don’t need a separate GET then SET.
3. Failure mode is clear – if Redis is unavailable, we can fail open (allow traffic) or fail closed (return 429) based on business needs, and the decision is centralized.

Compare that to the naive per‑process counter (a simple ConcurrentHashMap or AtomicInteger) which:

• Scales poorly – each instance needs its own limit, leading to over‑provisioning.
• Suffers from race conditions – you need locks or compare‑and‑swap loops that become bottlenecks under load.
• Wastes memory – every node stores a copy of the counter for every client/IP.

The Redis‑Lua approach trades a tiny bit of operational overhead (running a Redis cluster) for massive gains in correctness and simplicity. It’s the kind of trade‑off that makes you feel like you’ve just unlocked a new Force ability.

ASCII Diagram

+-----------+       +-----------+       +-----------+       +-----------+
|  Client   | ---> | API GW    | ---> | Rate Lim  | ---> | Shortener |
| (browser) |       | (LB)      |      | (Redis)   |      | Service   |
+-----------+       +-----------+       +-----------+       +-----------+
                                                |
                                                v
                                         +-----------+
                                         |  DB Store |
                                         +-----------+

API GW = API Gateway / Load Balancer (could be NGINX, Envoy, etc.)

Rate Lim = Redis-backed token bucket (implemented via Lua)

Shortener Service = handler that generates the code and writes to the DB

Wielding the Power (Code & Examples)

The Struggle: Naive In‑Memory Limiter

// Java‑like pseudocode – runs inside each service instance
private final Map<String, AtomicInteger> counts = new ConcurrentHashMap<>();
private static final int LIMIT = 100; // requests per minute per IP
private static final long WINDOW_MS = 60_000;

boolean allow(String ip) {
    AtomicInteger c = counts.computeIfAbsent(ip, k -> new AtomicInteger(0));
    int current = c.incrementAndGet();
    if (current == 1) {
        // schedule a reset after the window (simplified)
        scheduler.schedule(() -> counts.remove(ip), WINDOW_MS, TimeUnit.MILLISECONDS);
    }
    return current <= LIMIT;
}

Why this hurts:

• Each JVM has its own counts map → limits are multiplied by the number of instances.
• The incrementAndGet is atomic only within that JVM; two instances can both see 99 and let the 100th request through, blowing past the intended limit.
• Cleaning up old entries relies on a scheduler that can drift, causing memory leaks.

The Victory: Redis Lua Token Bucket

We model the limiter as a token bucket: each key (IP) gets capacity tokens that refill at a steady rate. A request consumes one token; if none are available, we reject.

Lua script (rate_limit.lua)

-- KEYS[1] = rate_limit:<ip>
-- ARGV[1] = capacity (max burst)
-- ARGV[2] = refill_rate_per_sec (tokens added each second)
-- ARGV[3] = now (current unix time in seconds)

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local last_refresh = redis.call('HGET', key, 'last_refresh')
local tokens = tonumber(redis.call('HGET', key, 'tokens'))

if not last_refresh then
    last_refresh = now
    tokens = capacity
end

-- refill tokens based on elapsed time
local delta = math.max(0, now - last_refresh)
tokens = math.min(capacity, tokens + delta * refill_rate)

local allowed = 0
if tokens >= 1 then
    tokens = tokens - 1
    allowed = 1
end

-- persist state
redis.call('HMSET', key, 'tokens', tokens, 'last_refresh', now)
redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 5) -- auto‑clean

return allowed

Java caller (using Lettuce or Jedis)

public boolean allow(String ip) {
    String script = loadLuaScript("rate_limit.lua"); // cached SHA
    Long result = redis.eval(script,
            ReturnType.INTEGER,
            1,                           // number of KEYS
            "rate_limit:" + ip,          // KEYS[1]
            String.valueOf(CAPACITY),    // ARGV[1]
            String.valueOf(REFILL_RATE_PER_SEC), // ARGV[2]
            String.valueOf(Instant.now().getEpochSecond()) // ARGV[3]
    );
    return result == 1;
}

What we gained:

• Atomicity – the Lua script runs as a single Redis command; no race condition across instances.
• Network efficiency – one round‑trip (EVAL) does the check‑and‑update.
• Automatic cleanup – the EXPIRE on the hash ensures stale keys disappear after a few idle periods.
• Operational simplicity – you only need to monitor Redis latency and memory; the limiter logic stays in one place.

Common Pitfalls (Traps to Avoid)

Trap	What happens	How to dodge it
Using GET then SET separately	Two round‑trips → window where two requests both read the same token count and both decrement → over‑limit.	Keep the logic inside a Lua script (or use Redis 7.0’s TOKEN command if you’re on a newer version).
Hard‑coding the refill rate without burst capacity	Legitimate traffic spikes (e.g., a user pasting a bulk list) get throttled unfairly.	Choose a capacity > refill_rate to allow short bursts while still limiting long‑term abuse.
Ignoring Redis failure modes	If Redis is down, the limiter either blocks all traffic (fail closed) or lets everything through (fail open) – both can be bad.	Implement a fallback: on connection error, either return 429 (safe) or allow request with a warning log, based on your SLA.
Storing timestamps as strings with low precision	Second‑level granularity can cause over‑ or under‑counting during high‑QPS bursts.	Store timestamps with millisecond precision (or use Unix microseconds) and do math in Lua with floats/ints accordingly.

Why This New Power Matters

Now that the rate limiter is a solid, shared guardrail, the shortener can scale horizontally without worrying about “who’s counting what.” You can spin up ten API nodes behind a load balancer, each blasting requests at the limiter, and Redis will keep the global quota honest.

• Cost‑effective – a modest Redis instance (or even a managed cache like AWS Elasticache) handles millions of checks per second with sub‑millisecond latency.
• Observability – the hash key rate_limit:<ip> gives you a live view of token buckets; you can expose metrics like tokens_remaining or rejected_total via Prometheus.
• Future‑proof – swapping the limiter for a more sophisticated algorithm (e.g., leaky bucket with adaptive rates) only requires rewriting the Lua script; the caller stays unchanged.

Most importantly, you’ve moved from “I hope this works under load” to “I know this works under load.” That confidence is the real superpower.

Your Turn

Grab a fresh repo, spin up a local Redis (docker run -p 6379:6379 redis:7), drop the Lua script in, and try the allow method with a quick JMeter or hey run. See how the rejected count stays flat even when you pound the service from multiple terminals.

Challenge: Extend the limiter to support per‑API‑key quotas (different capacity/refill_rate per key) without changing the caller—just pass the key as part of the Redis hash name.

Go forth, and may your URLs be short and your rate limits ever‑fair! 🚀