Fixed/Sliding Window, Token Bucket, and Leaky-Bucket Rate Limiting with Atomic Operations

Learning outcomes

This lesson turns Fixed/Sliding Window, Token Bucket, and Leaky-Bucket Rate Limiting with Atomic Operations into an observable AtlasMart workflow with explicit correctness, failure, and production boundaries.

Lab prerequisite: start the isolated Chapter 23 node

Run the Chapter 23 setup from Lesson 1 once. Before continuing, verify redis_version:8.10.1, authenticated identity atlasmart-app, database 0, AOF state, and that the endpoint is 127.0.0.1:6431. Do not point these failure/concurrency exercises at production.

docker exec -e REDISCLI_AUTH=AtlasMart-Ch23-App-Lab-Only-2026 atlasmart-redis-ch23 redis-cli --user atlasmart-app PINGdocker exec -e REDISCLI_AUTH=AtlasMart-Ch23-Admin-Lab-Only-2026 atlasmart-redis-ch23 redis-cli --user academy-admin INFO serverdocker exec -e REDISCLI_AUTH=AtlasMart-Ch23-App-Lab-Only-2026 atlasmart-redis-ch23 redis-cli --user atlasmart-app ACL WHOAMI

1. Problem: “100 requests per minute” is underspecified

AtlasMart must protect checkout, login, and search APIs. “100 requests/minute” sounds simple but does not say whether a client may burst 100 requests at once, whether boundaries can double traffic, how much state each identity consumes, whose clock defines the window, or what happens under concurrent service instances. A rate limiter is a synchronous policy decision; its read-decide-update sequence must be atomic.

2. Four algorithms answer different traffic questions

Do not select a limiter from popularity. Select from burst semantics, accuracy, memory/cardinality, and failure policy.

3. Fixed window: make INCR + first EXPIRE one atomic unit

The classic race is INCR followed by a client crash before EXPIRE, leaving an immortal limiter key. A small Lua script keeps the increment and first expiration atomic. The boundary-burst behavior remains; atomicity does not change the policy semantics.

local key = KEYS[1]local limit = tonumber(ARGV[1])local ttl = tonumber(ARGV[2])local n = redis.call('INCR', key)if n == 1 then redis.call('EXPIRE', key, ttl) endlocal remaining = limit - nif remaining < 0 then remaining = 0 endreturn {n <= limit and 1 or 0, remaining, redis.call('PTTL', key)}

4. Sliding window: timestamps buy precision with memory

A sorted-set log removes timestamps older than the rolling window, counts what remains, and adds a unique request member when allowed. Use Redis TIME inside the script so every application instance shares the server clock for the decision. Member uniqueness matters when multiple requests land in the same millisecond.

local key = KEYS[1]local limit = tonumber(ARGV[1])local window_ms = tonumber(ARGV[2])local member = ARGV[3]local t = redis.call('TIME')local now_ms = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)local cutoff = now_ms - window_msredis.call('ZREMRANGEBYSCORE', key, '-inf', cutoff)local count = redis.call('ZCARD', key)if count < limit then  redis.call('ZADD', key, now_ms, member)  redis.call('PEXPIRE', key, window_ms * 2)  return {1, limit - count - 1, 0}endlocal oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')local retry = oldest[2] and math.max(0, tonumber(oldest[2]) + window_ms - now_ms) or window_msreturn {0, 0, math.floor(retry)}

5. Token bucket: capacity is burst allowance; refill is average rate

A token bucket accumulates tokens up to a capacity and deducts request cost. The script refills from elapsed Redis-server time before deciding. This supports bursts while enforcing a long-run average. Store and calculate with enough precision for the required rate; do not use floating-point state as financial/accounting truth.

local key = KEYS[1]local capacity = tonumber(ARGV[1])local refill_per_ms = tonumber(ARGV[2])local cost = tonumber(ARGV[3])local t = redis.call('TIME')local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)local state = redis.call('HMGET', key, 'tokens', 'ts')local tokens = tonumber(state[1]) or capacitylocal last = tonumber(state[2]) or nowtokens = math.min(capacity, tokens + math.max(0, now-last) * refill_per_ms)local allowed = 0if tokens >= cost then tokens = tokens - cost; allowed = 1 endredis.call('HSET', key, 'tokens', tokens, 'ts', now)redis.call('PEXPIRE', key, math.ceil((capacity / refill_per_ms) * 2))return {allowed, tostring(tokens), now}

6. Leaky bucket: distinguish policing from queue shaping

The policing form below models a bucket level that drains at a fixed rate and rejects arrivals that would overflow capacity. A shaping leaky bucket instead queues work and releases it at a fixed rate; that needs queue ownership, retries, and backpressure, not just an allow/deny script.

local key = KEYS[1]local capacity = tonumber(ARGV[1])local leak_per_ms = tonumber(ARGV[2])local cost = tonumber(ARGV[3])local t = redis.call('TIME')local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)local state = redis.call('HMGET', key, 'level', 'ts')local level = tonumber(state[1]) or 0local last = tonumber(state[2]) or nowlevel = math.max(0, level - math.max(0, now-last) * leak_per_ms)local allowed = 0if level + cost <= capacity then level = level + cost; allowed = 1 endredis.call('HSET', key, 'level', level, 'ts', now)redis.call('PEXPIRE', key, math.ceil((capacity / leak_per_ms) * 2))return {allowed, tostring(level), now}

7. Concurrency test: one Redis decision, many application threads

Use the dedicated Chapter 23 node. The test does not assume an exact latency; it checks that exactly the configured number of requests are allowed inside one fresh fixed window while all threads race concurrently.

import concurrent.futures, statistics, time, uuidimport redisr = redis.Redis(host="127.0.0.1", port=6431, username="atlasmart-app",                password="AtlasMart-Ch23-App-Lab-Only-2026", decode_responses=True)SCRIPT = r.register_script("""local key = KEYS[1]local limit = tonumber(ARGV[1])local ttl = tonumber(ARGV[2])local n = redis.call('INCR', key)if n == 1 then redis.call('EXPIRE', key, ttl) endreturn {n <= limit and 1 or 0, n, redis.call('PTTL', key)}""")r.delete("atlasmart:ch23:rl:burst")def one(_):    t0=time.perf_counter_ns()    allowed,n,pttl = SCRIPT(keys=["atlasmart:ch23:rl:burst"], args=[20, 2])    return bool(allowed), int(n), int(pttl), (time.perf_counter_ns()-t0)/1e6with concurrent.futures.ThreadPoolExecutor(max_workers=32) as ex:    rows=list(ex.map(one, range(64)))lat=[x[3] for x in rows]print("allowed", sum(x[0] for x in rows), "denied", sum(not x[0] for x in rows))print("counter_max", max(x[1] for x in rows), "pttl_range", min(x[2] for x in rows), max(x[2] for x in rows))print("latency_ms_p50", statistics.median(lat), "latency_ms_max", max(lat))

8. Deliberately wrong: GET counter → decide → INCR

A client-side GET, comparison, and later INCR is a time-of-check/time-of-use race. Two workers can both see room and both admit. Repair with an atomic Redis command when one exists, or a small script/function that computes time, reads state, decides, and updates inside one server execution. Pipelining reduces round trips but does not make a multi-command decision atomic.

9. Failure policy belongs in the API contract

If Redis times out, should AtlasMart fail open or fail closed? Login abuse controls may fail closed; a low-risk read endpoint may fail open with local emergency limiting. Document the choice, cap Redis client timeouts/retries, avoid retry storms, and monitor denied requests, Redis errors, decision latency, active limiter keys, and memory.

10. Cluster and key design

A limiter key should include the intended subject (user/API key/IP/tenant), endpoint or policy dimension, and—if a script touches multiple keys in Redis Cluster—a deliberate hash tag so every script key shares one slot. Do not put every tenant under one hash tag; that would manufacture a hot slot.

11. Production judgment and bridge

Rate limiting is shared mutable control state on the request path. Choose algorithm semantics before choosing commands, define behavior during Redis failure, bound identity cardinality, measure tail latency under concurrency, and test window boundaries. Lesson 3 applies the same atomic-ownership principle to distributed locks, where a lease can expire while the old owner is still running.

Summary and next step

Fixed/Sliding Window, Token Bucket, and Leaky-Bucket Rate Limiting with Atomic Operations is now connected to observable Redis behavior, bounded failure cases, and production tradeoffs. Keep the evidence and cleanup state from this lesson; next, continue with Distributed Locks: SET NX PX, Ownership Tokens, Safe Unlock, Leases, and Fencing Limitations.

Authoritative references

• Redis cache-aside
• Redis cache-aside with redis-py
• Redis rate limiter
• Rate limiter with redis-py
• INCR — rate limiter pattern
• SET
• DELEX
• Distributed locks with Redis
• EVAL
• TIME
• EXPIRE
• PTTL
• ZADD
• ZREMRANGEBYSCORE
• HSET
• HGETALL
• OBJECT FREQ
• redis-cli
• Redis eviction reference
• Redis replication
• Redis Cluster specification
• Redis 8.10 release notes
• Redis licenses
• redis-py 8.1.0