Rate Limiting Algorithms: Token Bucket, Leaky Bucket, Fixed và Sliding Window | Shanverse

Rate Limiting Algorithms: Token Bucket, Leaky Bucket, Fixed và Sliding Window | Shanverse

Codelua

1local current = redis.call('INCR', KEYS[1])23if current == 1 then4  redis.call('PEXPIRE', KEYS[1], ARGV[1])5end67local allowed = 08if current <= tonumber(ARGV[2]) then9  allowed = 110end1112local ttl = redis.call('PTTL', KEYS[1])13return { allowed, current, ttl }

Codelua

1local key = KEYS[1]2local now = tonumber(ARGV[1])3local window = tonumber(ARGV[2])4local limit = tonumber(ARGV[3])5local member = ARGV[4]6local oldest = now - window78redis.call('ZREMRANGEBYSCORE', key, 0, oldest)910local current = redis.call('ZCARD', key)11local allowed = 01213if current < limit then14  redis.call('ZADD', key, now, member)15  current = current + 116  allowed = 117end1819redis.call('PEXPIRE', key, window)20return { allowed, current }

Codelua

1local key = KEYS[1]2local capacity = tonumber(ARGV[1])3local refill_per_ms = tonumber(ARGV[2])4local cost = tonumber(ARGV[3])5local ttl_ms = tonumber(ARGV[4])67local time = redis.call('TIME')8local now = tonumber(time[1]) * 1000 + math.floor(tonumber(time[2]) / 1000)910local state = redis.call('HMGET', key, 'tokens', 'updated_at')11local tokens = tonumber(state[1])12local updated_at = tonumber(state[2])1314if tokens == nil then15  tokens = capacity16  updated_at = now17end1819local elapsed = math.max(0, now - updated_at)20tokens = math.min(capacity, tokens + elapsed * refill_per_ms)2122local allowed = 023if tokens >= cost then24  tokens = tokens - cost25  allowed = 126end2728redis.call('HSET', key, 'tokens', tokens, 'updated_at', now)29redis.call('PEXPIRE', key, ttl_ms)3031return { allowed, tostring(tokens), now }

Codejavascript

1class FixedWindowLimiter {2  constructor({ limit, windowMs }) {3    this.limit = limit;4    this.windowMs = windowMs;5    this.counters = new Map();6  }78  consume(key, now = Date.now()) {9    const windowStart = Math.floor(now / this.windowMs) * this.windowMs;10    const stateKey = key + ":" + windowStart;11    const current = this.counters.get(stateKey) ?? 0;12    const next = current + 1;1314    this.counters.set(stateKey, next);1516    return {17      allowed: next <= this.limit,18      remaining: Math.max(0, this.limit - next),19      resetAt: windowStart + this.windowMs,20    };21  }22}

Codejavascript

1class TokenBucket {2  constructor({ capacity, refillPerSecond }) {3    this.capacity = capacity;4    this.tokens = capacity;5    this.refillPerSecond = refillPerSecond;6    this.updatedAt = performance.now();7  }89  consume(cost = 1) {10    const now = performance.now();11    const elapsedSeconds = (now - this.updatedAt) / 1000;1213    this.tokens = Math.min(14      this.capacity,15      this.tokens + elapsedSeconds * this.refillPerSecond,16    );17    this.updatedAt = now;1819    if (this.tokens < cost) {20      return {21        allowed: false,22        remaining: Math.floor(this.tokens),23        retryAfterMs:24          ((cost - this.tokens) / this.refillPerSecond) * 1000,25      };26    }2728    this.tokens -= cost;29    return {30      allowed: true,31      remaining: Math.floor(this.tokens),32      retryAfterMs: 0,33    };34  }35}

Codejavascript

1class LeakyBucketQueue {2  constructor({ capacity, leakPerSecond, handle }) {3    this.capacity = capacity;4    this.intervalMs = 1000 / leakPerSecond;5    this.handle = handle;6    this.queue = [];78    this.timer = setInterval(() => this.drainOne(), this.intervalMs);9    this.timer.unref?.();10  }1112  enqueue(job) {13    if (this.queue.length >= this.capacity) {14      return { accepted: false, reason: "QUEUE_FULL" };15    }1617    this.queue.push(job);18    return { accepted: true, position: this.queue.length };19  }2021  async drainOne() {22    const job = this.queue.shift();23    if (!job) return;2425    try {26      await this.handle(job);27    } catch (error) {28      job.onError?.(error);29    }30  }31}

Codejavascript

1async function rateLimitMiddleware(request, response, next) {2  const subject = request.user?.id || getTrustedClientIp(request);3  const route = normalizedRoute(request);4  const cost = costForRoute(route);56  const result = await distributedLimiter.consume({7    key: "ratelimit:" + subject + ":" + route,8    cost,9  });1011  response.setHeader("RateLimit-Limit", String(result.limit));12  response.setHeader("RateLimit-Remaining", String(result.remaining));13  response.setHeader("RateLimit-Reset", String(result.resetSeconds));1415  if (!result.allowed) {16    response.setHeader("Retry-After", String(result.retryAfterSeconds));17    response.statusCode = 429;18    response.end(JSON.stringify({19      error: "RATE_LIMITED",20      retryAfterSeconds: result.retryAfterSeconds,21    }));22    return;23  }2425  next();26}