Rate Limiting

ทดสอบบน Redis 8.10.2 (redis:8.10.2-alpine), ioredis 6.0.0, Node 24 บน Mac (Apple silicon) transcript แบบ # cli/... คือ session เดียวเรียงตามเอกสารที่ harness ของคอร์สรันซ้ำ ผลลัพธ์ของสคริปต์มาจากการรันของผม มันใช้เวลาจริงรอบขอบ window ดังนั้นจำนวน allowed ในแถว burst คือประเด็น ไม่ใช่มิลลิวินาที

Rate limiter คืออะไร?

rate limiter จำกัดจำนวนคำขอที่ client ทำได้ในช่วงเวลาหนึ่ง Redis เหมาะเพราะ counter ราคาถูก key หมดอายุเองได้ และสคริปต์ตัดสินใจหลายขั้นแบบ atomic ได้ บทนี้สร้าง limiter สามแบบและแสดงจุดที่แบบยอดนิยมพัง

Fixed window: INCR บวก TTL

นับคำขอใน key ที่เข้ารหัส window ไว้ คำขอแรกใน window ให้ TTL กับ key เพื่อให้มันหายเมื่อ window จบ วิธีเขียน “ให้ TTL ตอนเข้าครั้งแรก” แบบไร้เดียงสาคือกับดัก:

cli/patterns-rate-limiting-1.redis

127.0.0.1:6379> INCR rate:user:42:window1
(integer) 1
127.0.0.1:6379> TTL rate:user:42:window1
(integer) -1
127.0.0.1:6379> EXPIRE rate:user:42:window1 60 NX
(integer) 1
127.0.0.1:6379> INCR rate:user:42:window1
(integer) 2
127.0.0.1:6379> EXPIRE rate:user:42:window1 60 NX
(integer) 0
127.0.0.1:6379> TTL rate:user:42:window1
(integer) 60
127.0.0.1:6379> SET rate:stuck 3
OK
127.0.0.1:6379> TTL rate:stuck
(integer) -1
127.0.0.1:6379> EXPIRE rate:stuck 60 NX
(integer) 1
127.0.0.1:6379> MULTI
OK
127.0.0.1:6379> INCR rate:user:7:window1
QUEUED
127.0.0.1:6379> EXPIRE rate:user:7:window1 60 NX
QUEUED
127.0.0.1:6379> EXEC
1) (integer) 1
2) (integer) 1

INCR และ EXPIRE คือ สองคำสั่ง ไม่ใช่หนึ่ง ระหว่างสองคำสั่ง client อาจ crash การเชื่อมต่ออาจหลุด หรือ EXPIRE อาจ timeout key จึงไม่มี TTL (TTL = -1 ทันทีหลัง INCR แรก) และเพราะโค้ดปกติเรียก EXPIRE เฉพาะเมื่อ counter เท่ากับ 1 พอดี จึงไม่มีใครให้ TTL อีกเลย: counter เพิ่มเกิน limit และผู้ใช้คนนั้นถูกบล็อกตลอดไป (บทเวอร์ชันแรกเรียกคู่นี้ว่า “atomic”; INCR เดี่ยวๆ atomic แต่ตัวคู่ไม่ใช่)

วิธีแก้สองแบบ ทั้งคู่อยู่ใน transcript:

• EXPIRE key seconds NX (Redis 7.0) ตั้ง TTL เฉพาะเมื่อ key ไม่มี: คืน 1 ครั้งแรก, 0 ครั้งที่สอง (TTL ไม่ถูกแตะ) และ 1 อีกครั้งกับ rate:stuck ซึ่งเป็น counter ที่ทำ TTL หาย การส่งมันใน ทุก คำขอทำให้ limiter รักษาตัวเองได้
• MULTI … EXEC ทำให้ INCR กับ EXPIRE NX เป็นหน่วยเดียว จึงถูก client crash แยกออกจากกันไม่ได้

INCR rate:user:42:window1
EXPIRE rate:user:42:window1 60 NX
INCR rate:user:42:window1
TTL rate:user:42:window1

Copy commands ⧉

flowchart TD
  A["Incoming request"] --> B["MULTI: INCR rate:user:window, EXPIRE ... NX, PTTL"]
  B --> C{"count > limit?"}
  C -->|"No"| G["Allow request"]
  C -->|"Yes"| F["Reject: HTTP 429 with Retry-After from PTTL"]

Fixed-window rate limiter: INCR กับ EXPIRE NX ใน MULTI เดียว และตอบ 429 เมื่อเกิน limit

limiter ใน ioredis

src/patterns-rate-limiting.ts

// @run
import { Redis } from 'ioredis';

const redis = new Redis(process.env.REDIS_URL!);
const sleep = (ms: number) => new Promise((r) => setTimeout(r, ms));

declare module 'ioredis' {
  interface RedisCommander<Context> {
    slidingLog(key: string, windowMs: number, limit: number, member: string): Promise<number>;
    tokenBucket(key: string, capacity: number, refillPerSec: number): Promise<number>;
  }
}

// sliding log: keep one ZSET member per allowed request, drop the ones older than the window
redis.defineCommand('slidingLog', {
  numberOfKeys: 1,
  lua: `
    local t = redis.call('TIME')
    local now = t[1] * 1000 + math.floor(t[2] / 1000)
    redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - ARGV[1])
    if redis.call('ZCARD', KEYS[1]) < tonumber(ARGV[2]) then
      redis.call('ZADD', KEYS[1], now, ARGV[3])
      redis.call('PEXPIRE', KEYS[1], ARGV[1])
      return 1
    end
    return 0`,
});

// token bucket: tokens refill continuously, a request costs 1; state lives in one hash
redis.defineCommand('tokenBucket', {
  numberOfKeys: 1,
  lua: `
    local t = redis.call('TIME')
    local now = t[1] * 1000 + math.floor(t[2] / 1000)
    local capacity, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
    local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
    local tokens, ts = tonumber(b[1]), tonumber(b[2])
    if not tokens then tokens = capacity; ts = now end
    tokens = math.min(capacity, tokens + (now - ts) * rate / 1000)
    local ok = 0
    if tokens >= 1 then tokens = tokens - 1; ok = 1 end
    redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
    redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)
    return ok`,
});

const LIMIT = 5;
const WINDOW_MS = 1000;

// the version an assistant tends to write: INCR, then EXPIRE only on the first hit
async function naive(user: string, crashAfterIncr = false) {
  const key = `b3:rl:naive:${user}`;
  const n = await redis.incr(key);
  if (crashAfterIncr) return { n, allowed: true }; // the process dies here: EXPIRE never runs
  if (n === 1) await redis.expire(key, 60);
  return { n, allowed: n <= LIMIT };
}

// fixed window, safe: INCR + EXPIRE NX in one MULTI. NX = only set a TTL if there is none,
// so even a key that lost its TTL gets one on the next request.
async function fixedWindow(user: string, windowMs = WINDOW_MS) {
  const key = `b3:rl:fw:${user}:${Math.floor(Date.now() / windowMs)}`;
  const res = await redis.multi().incr(key).pexpire(key, windowMs, 'NX').pttl(key).exec();
  const n = res![0]![1] as number;
  const ttlMs = res![2]![1] as number;
  return { allowed: n <= LIMIT, remaining: Math.max(0, LIMIT - n), retryAfterSec: Math.ceil(ttlMs / 1000) };
}

// 1) the naive limiter after a crash between INCR and EXPIRE
await naive('u1', true);
const stuck = [];
for (let i = 0; i < 8; i++) stuck.push((await naive('u1')).allowed);
console.log('naive after crash: ttl =', await redis.ttl('b3:rl:naive:u1'), '| allowed:', stuck.join(' '));

// 2) EXPIRE NX heals a key that has no TTL
await redis.set('b3:rl:heal', '3');
console.log('EXPIRE NX on a key without TTL ->', await redis.expire('b3:rl:heal', 60, 'NX'), ', again ->', await redis.expire('b3:rl:heal', 60, 'NX'));

// 3) HTTP 429 with Retry-After from the safe fixed window
let last;
for (let i = 0; i < 7; i++) last = await fixedWindow('u2', 60000);
console.log(last!.allowed ? '200 OK' : `429 Too Many Requests\nRetry-After: ${last!.retryAfterSec}`, '| remaining', last!.remaining);

// 4) the window-boundary burst: 5 requests just before the edge, 5 just after
const untilEdge = () => WINDOW_MS - (Date.now() % WINDOW_MS);
async function burst(fn: () => Promise<boolean>) {
  await sleep(untilEdge() - 100); // 100 ms before the next window starts
  const first = await Promise.all(Array.from({ length: 5 }, fn));
  await sleep(200); // now 100 ms after the edge
  const second = await Promise.all(Array.from({ length: 5 }, fn));
  return first.filter(Boolean).length + second.filter(Boolean).length;
}
console.log('fixed window: allowed in 200 ms around the edge:', await burst(async () => (await fixedWindow('u3')).allowed), 'of 10 (limit is 5 per second)');
console.log('sliding log : allowed in 200 ms around the edge:', await burst(async () => (await redis.slidingLog('b3:rl:sl', WINDOW_MS, LIMIT, Math.random().toString(36))) === 1), 'of 10');

// 5) token bucket: capacity 3, refill 1 token/s
const tb = [];
for (let i = 0; i < 5; i++) tb.push(await redis.tokenBucket('b3:rl:tb', 3, 1));
await sleep(1100);
tb.push(await redis.tokenBucket('b3:rl:tb', 3, 1));
console.log('token bucket: 5 quick calls then one after 1.1 s ->', tb.join(' '));

for await (const ks of redis.scanStream({ match: 'b3:rl:*' })) if (ks.length) await redis.del(ks);
await redis.quit();

ผลลัพธ์จริง (Mac เครื่องนี้):

naive after crash: ttl = -1 | allowed: true true true true false false false false
EXPIRE NX on a key without TTL -> 1 , again -> 0
429 Too Many Requests
Retry-After: 60 | remaining 0
fixed window: allowed in 200 ms around the edge: 10 of 10 (limit is 5 per second)
sliding log : allowed in 200 ms around the edge: 5 of 10
token bucket: 5 quick calls then one after 1.1 s -> 1 1 1 0 0 1

แต่ละแถวแสดงอะไร:

• bug ตอน crash มี INCR หนึ่งครั้งโดยไม่มี EXPIRE (crash จำลอง) key จึงมี ttl = -1; 8 การเรียกถัดมานับเป็น 2..9 ผ่านสี่ตัวที่เหลือถูกปฏิเสธ และเพราะ n === 1 จะไม่เกิดอีก key จึงไม่มีวันได้ TTL ผู้ใช้คนนั้นถูกบล็อกจนกว่าจะมีคนลบ key ด้วยมือ
• EXPIRE NX รักษาให้หาย: 1 แล้ว 0
• 429 และ Retry-After fixedWindow คืน retryAfterSec จาก PTTL ใน MULTI เดียวกัน คำขอที่ถูกปฏิเสธตอบ 429 Too Many Requests พร้อม Retry-After: 60 (header นิยามใน RFC 9110 section 10.2.3, 429 ใน RFC 6585) ถ้าไม่มี client จะลองใหม่แบบสุ่ม
• Fixed window เพิ่ม limit เป็นสองเท่าได้ 5 คำขอก่อนขอบ window 100 ms และอีก 5 คำขอหลังขอบ 100 ms: ผ่านทั้ง 10 จาก 10 ใน 200 ms ทั้งที่ limit คือ 5 ต่อวินาที แต่ละคำขอถูกกฎภายใน bucket ของตัวเอง
• sliding log แก้เรื่องนั้น ใช้ ZSET หนึ่ง member ต่อคำขอที่ผ่าน และ ZREMRANGEBYSCORE ทิ้ง member ที่เก่ากว่า window: burst เดียวกันผ่านเพียง 5 จาก 10 การตรวจแล้วค่อยเพิ่มรันใน Lua เพื่อไม่ให้สองคำขอที่แข่งกันเห็นที่ว่างเหลือหนึ่งที่พร้อมกัน และใช้ TIME ของเซิร์ฟเวอร์ ความคลาดของนาฬิกา app server จึงไม่มีผล ราคาที่จ่ายคือหน่วยความจำเป็นสัดส่วนกับ limit ต่อผู้ใช้ (หนึ่ง member ต่อคำขอ) แทนที่จะเป็น counter เดียว
• Token bucket ความจุ 3 เติม 1 token ต่อวินาที: 5 การเรียกเร็วได้ 1 1 1 0 0 (burst ได้ถึงความจุ แล้วถูกปฏิเสธ) และการเรียกหลัง 1.1 วินาทีได้ token ที่เติมแล้ว (1) มันอนุญาต burst ที่ควบคุมได้และบังคับอัตราเฉลี่ย โดยเก็บสถานะใน hash เล็กๆ อันเดียว

🟥 ให้ counter ได้ TTL แบบ atomic และในทุกคำขอ

ใช้ MULTI + INCR + EXPIRE ... NX (หรือสคริปต์ Lua) เพื่อไม่ให้ counter มีอยู่โดยไม่มี TTL ได้ Fixed window ถูกและเร็ว แต่ให้ได้ถึง 2 เท่าของ limit ที่ขอบ ใช้ sliding log หรือ token bucket เมื่อเรื่องนี้สำคัญ

Reading AI-generated code

AI เขียน limiter แบบคลาสสิกและบอกว่า “INCR เป็น atomic ดังนั้นไม่มี race”:

🐛 หา bug ในโค้ดนี้

async function isAllowed(userId: string) {
const key = `rate:${userId}`;
const count = await redis.incr(key);
if (count === 1) await redis.expire(key, 60);   // "only set the TTL once"
return count <= 100;
}

เฉลย

INCR เป็น atomic; แต่ คู่ ไม่ใช่ ถ้า process ตาย (หรือการเชื่อมต่อหลุด) หลัง INCR และก่อน EXPIRE key จะไม่มี TTL และ count === 1 จะไม่เป็นจริงอีก การรันข้างบนแสดง ttl = -1 และผู้ใช้ที่ถูกปฏิเสธทุกคำขอหลังจากนั้น โดยไม่มีทางกู้ นอกจากลบ key ใส่ทั้งสองคำสั่งใน MULTI เดียว และให้ EXPIRE ... NX ตั้ง TTL เมื่อใดก็ตามที่ key ไม่มี:

const [[, count]] = (await redis.multi().incr(key).expire(key, 60, 'NX').exec())!;
return (count as number) <= 100;

Mental Model

fixed-window limiter คือ ประตูหมุนที่มี counter รีเซ็ตทุกต้นชั่วโมง: ถูก แต่ใครสักคนผ่านได้ 100 คนตอน 11:59:59 และอีก 100 คนตอน 12:00:00 sliding log คือยามที่มีสมุดจดและนับเฉพาะ 60 วินาทีล่าสุด token bucket คือโถที่เติมด้วยอัตราคงที่: ใช้ได้เท่าที่มีในโถ ทั้งสามต้องอัปเดตสถานะในขั้นเดียว ไม่เช่นนั้นสองคำขอเห็นที่ว่างเหลือหนึ่งที่พร้อมกัน

Trade-offs

ตัวเลือก	ข้อดี	ข้อเสีย
Fixed window (INCR + EXPIRE NX ใน MULTI)	เรียบง่าย เร็ว key เล็กอันเดียว	ได้ถึง 2 เท่าของ limit ข้ามขอบ window (10 จาก 10 ข้างบน)
Sliding log (ZSET + Lua)	แม่นยำ: ไม่มี burst ที่ขอบ (5 จาก 10)	หน่วยความจำโตตาม limit; งานต่อคำขอมากขึ้น
Token bucket (hash + Lua)	อนุญาต burst ได้ถึงความจุ บังคับอัตราเฉลี่ย	ต้องคำนวณการเติมและสคริปต์ฝั่งเซิร์ฟเวอร์
Lua สำหรับการตัดสินใจทั้งหมด	ตรวจและอัปเดตแบบ atomic ไม่มีสถานะครึ่งๆ	ต้องดูแลสคริปต์; ระหว่างรันคำสั่งอื่นต้องรอ
ใช้นาฬิกาฝั่ง client สำหรับ window	ไม่ต้องเรียก TIME	ความคลาดระหว่าง app server ทำให้ window เลื่อน; ใช้ TIME ใน Lua หรือขอบ window ร่วมกัน

Common Misconceptions

• “INCR เป็น atomic ดังนั้น INCR + EXPIRE ก็ atomic” แต่ละคำสั่ง atomic ส่วนคู่คือสองขั้นที่ crash แยกได้
• “fixed window บังคับอัตราได้” บังคับต่อ bucket ข้ามขอบ อัตราจริงอาจเป็นสองเท่า
• “ปฏิเสธคำขอแล้ว limiter ก็จบหน้าที่” ตอบ 429 พร้อม Retry-After ไม่เช่นนั้น client จะรัวเรียก endpoint แบบมืดบอด
• “rate limiting ต้องใช้ module พิเศษ” counter, ZSET, hash และสคริปต์ Lua สั้นๆ ก็พอ

Common mistakes

• INCR แล้ว EXPIRE แยกกัน — crash ทิ้ง counter ที่ไม่เคยรีเซ็ต (พิสูจน์ข้างบน)
• เข้าใจว่า fixed window กัน burst ได้ — ที่ขอบได้ 2 เท่า
• ไม่มี Retry-After — client ลองใหม่แบบมืดบอด
• sliding log ที่ไม่ atomic (ZCARD แล้ว ZADD จาก client) — สองคำขอที่แข่งกันผ่านทั้งคู่ ใช้ Lua
• เชื่อนาฬิกาของ app server แต่ละตัว — ใช้ TIME ในสคริปต์หรือนาฬิกาเดียวร่วมกัน

Real-world example

REST API ของ GitHub ระบุ rate limit ต่อ token และรายงานโควตาที่เหลือใน response header (Rate limits for the REST API); header (x-ratelimit-remaining, x-ratelimit-reset) คือแนวคิดเดียวกับ Retry-After ข้างบน: บอกสถานะให้ client แทนที่จะปล่อยให้เดา

INCR key ตามด้วย if (count === 1) EXPIRE key 60 เป็นสองการเรียกแยกกัน มีอะไรผิด?

ไม่มี INCR เป็น atomic crash ระหว่างสองคำสั่งทิ้ง counter ที่ไม่มี TTL และไม่เคยถูกแก้ EXPIRE ใช้หลัง INCR ไม่ได้ มันนับสองครั้ง

EXPIRE key 60 NX ทำอะไร?

ตั้ง TTL เฉพาะเมื่อ key ไม่มี TTL ตั้ง TTL เฉพาะเมื่อ key ไม่มีอยู่ ลบ TTL ตั้ง TTL เป็นมิลลิวินาที

5 คำขอมาก่อนขอบ fixed-window 100 ms และอีก 5 คำขอหลังขอบ 100 ms limit 5 ต่อวินาที ผ่านกี่ตัว?

5 6 10 0

โครงสร้างใดให้ sliding-window limiter ที่แม่นยำ?

String กับ INCR List กับ LPUSH Sorted set ที่ใช้ timestamp เป็น score Hash กับ HINCRBY

response ที่ถูก rate limit ควรมีอะไรนอกจากสถานะ 429?

Set-Cookie Retry-After (จำนวนวินาทีที่ client ควรรอก่อนลองใหม่) Content-Length: 0 Location

token bucket ความจุ 3 เติม 1 token ต่อวินาที ได้รับ 5 การเรียกทันที เกิดอะไรขึ้น?

ผ่านทั้ง 5 ผ่าน 3 ปฏิเสธ 2 ผ่านแค่ 1 ปฏิเสธทั้ง 5

Submit

Mark as complete