So sánh các thuật toán giới hạn tốc độ

Một policy như “100 request mỗi phút” nghe có vẻ đầy đủ cho đến khi hai client gửi request sát mốc đổi phút, một operation đắt gấp 50 lần operation khác, hoặc đồng hồ hệ thống quay ngược. Câu hỏi hữu ích không phải thuật toán nào tốt nhất trong mọi tình huống, mà là mô hình thời gian và capacity nào khớp với contract của traffic.

Bài này giữ state ở local và trình bày nó tường minh. Quyền sở hữu state phân tán, Redis script hay coordination đa vùng là bài toán kiến trúc khác. Trọng tâm ở đây là bản thân thuật toán: nó nhận request nào, cho phép burst đến đâu, giữ bao nhiêu state và chứng minh các thuộc tính đó bằng virtual clock như thế nào.

Định nghĩa contract trước khi chọn thuật toán #

Gọi L là số unit được phép trong khoảng W, c là cost của một request, và A(t) là tổng cost đã nhận trong một khoảng thời gian. Policy rolling window nghiêm ngặt yêu cầu:

Khoảng này mở bên trái: event đúng tại t - W đã hết hạn. Ghi rõ quy tắc boundary giúp production và test không lệch nhau một mili giây. Nó cũng cho thấy fixed window khác hẳn: fixed window giới hạn các bucket căn theo mốc cố định chứ không giới hạn mọi khoảng trượt.

Limiter nên trả về nhiều hơn một boolean:

export type Decision = {
  allowed: boolean;
  remaining: number;
  retryAfterMs: number;
};

function requireCost(cost: number): void {
  if (!Number.isFinite(cost) || cost <= 0) {
    throw new RangeError('cost must be finite and positive');
  }
}

remaining được đo theo unit của policy, không nhất thiết là số request. Cache hit rẻ có thể tốn 1, một lần export tốn 20, còn operation LLM tính theo lượng token ước tính. Cost có thể là số thập phân, nhưng khi đưa ra HTTP header cần dùng một quy tắc làm tròn nhất quán.

Cần phân biệt ba dạng burst:

• Boundary burst: traffic tăng thêm vì bộ đếm reset tại một boundary cố định.
• Burst capacity: credit được chủ ý tích lũy, như trong token bucket.
• Queue burst: công việc được nhận ngay nhưng bị một shaper trì hoãn.

Fairness cũng luôn có phạm vi. Queue FIFO của leaky bucket giữ thứ tự đến, nhưng một request nặng có thể chặn nhiều request nhẹ. Bucket riêng theo client tạo isolation giữa các client, nhưng không tự làm chúng công bằng khi cùng dùng một dependency. Thuật toán không thể sửa keying policy đã gom sai actor.

Nhóm window: đơn giản, chính xác hoặc xấp xỉ #

Fixed window giữ một bucket id và số unit đã dùng. Memory là hằng số và semantics dễ giải thích, nhưng client có thể dùng L ngay trước boundary rồi dùng tiếp L ngay sau đó. Như vậy có thể có 2L request trong một khoảng cực ngắn.

export class FixedWindow {
  #windowId = Number.NaN;
  #used = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    const windowId = Math.floor(nowMs / this.windowMs);
    if (windowId !== this.#windowId) {
      this.#windowId = windowId;
      this.#used = 0;
    }

    if (cost > this.limit) {
      return { allowed: false, remaining: this.limit - this.#used, retryAfterMs: Infinity };
    }
    const allowed = this.#used + cost <= this.limit;
    if (allowed) this.#used += cost;
    return {
      allowed,
      remaining: Math.max(0, this.limit - this.#used),
      retryAfterMs: allowed
        ? 0
        : (windowId + 1) * this.windowMs - nowMs,
    };
  }
}

Sliding log ghi từng event được chấp nhận. Xóa event thỏa at <= nowMs - windowMs sẽ triển khai chính xác khoảng mở bên trái. Với weighted event, thời gian retry là lúc tổng cost cũ hết hạn đủ nhiều, không nhất thiết là lúc event đầu tiên hết hạn.

type Event = { at: number; cost: number };

export class SlidingLog {
  readonly #events: Event[] = [];
  #used = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    while (this.#events[0]?.at <= nowMs - this.windowMs) {
      this.#used -= this.#events.shift()!.cost;
    }

    if (cost > this.limit) {
      return { allowed: false, remaining: this.limit - this.#used, retryAfterMs: Infinity };
    }
    if (this.#used + cost <= this.limit) {
      this.#events.push({ at: nowMs, cost });
      this.#used += cost;
      return { allowed: true, remaining: this.limit - this.#used, retryAfterMs: 0 };
    }

    const mustExpire = this.#used + cost - this.limit;
    let expired = 0;
    for (const event of this.#events) {
      expired += event.cost;
      if (expired >= mustExpire) {
        return {
          allowed: false,
          remaining: Math.max(0, this.limit - this.#used),
          retryAfterMs: Math.max(0, event.at + this.windowMs - nowMs),
        };
      }
    }
    throw new Error('unreachable');
  }
}

Mảng dùng shift() phù hợp để minh họa. Bản production nên dùng deque hoặc mảng kèm head index để tránh compact lặp lại. Memory là O(n) theo số event đã nhận trên mỗi key: chính xác nhưng nguy hiểm nếu L rất lớn.

Sliding counter chỉ giữ bucket hiện tại và bucket liền trước, sau đó nhân bucket trước với tỷ lệ overlap. Với e mili giây đã trôi qua trong window hiện tại:

export class SlidingCounter {
  #start = Number.NaN;
  #current = 0;
  #previous = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    this.#advance(nowMs);
    const estimated = this.#estimate(nowMs);
    if (cost > this.limit) {
      return { allowed: false, remaining: Math.max(0, this.limit - estimated), retryAfterMs: Infinity };
    }
    if (estimated + cost <= this.limit) {
      this.#current += cost;
      return { allowed: true, remaining: Math.max(0, this.limit - estimated - cost), retryAfterMs: 0 };
    }
    return {
      allowed: false,
      remaining: Math.max(0, this.limit - estimated),
      retryAfterMs: Math.ceil(this.#timeUntil(cost, nowMs)),
    };
  }

  #advance(nowMs: number): void {
    const start = Math.floor(nowMs / this.windowMs) * this.windowMs;
    if (Number.isNaN(this.#start)) this.#start = start;
    if (start === this.#start) return;
    this.#previous = start === this.#start + this.windowMs ? this.#current : 0;
    this.#current = 0;
    this.#start = start;
  }

  #estimate(nowMs: number): number {
    const elapsed = nowMs - this.#start;
    return this.#current + this.#previous * (1 - elapsed / this.windowMs);
  }

  #timeUntil(cost: number, nowMs: number): number {
    const target = this.limit - cost;
    if (this.#previous > 0 && target >= this.#current) {
      const at = this.#start + this.windowMs *
        (1 - (target - this.#current) / this.#previous);
      return Math.max(0, at - nowMs);
    }
    const nextStart = this.#start + this.windowMs;
    if (this.#current === 0) return Math.max(0, nextStart - nowMs);
    const at = nextStart + this.windowMs * (1 - target / this.#current);
    return Math.max(0, at - nowMs);
  }
}

Estimate thay đổi mượt và tốn constant memory, nhưng giả định event trong bucket trước phân bố đều. Burst dồn ở một đầu bucket có thể bị đếm thừa hoặc thiếu. Hãy dùng khi chấp nhận sai số có giới hạn và exact log quá đắt.

Token bucket, leaky bucket và GCRA #

Token bucket refill liên tục với tốc độ r unit mỗi mili giây đến capacity B. Mỗi request tiêu c token:

export class TokenBucket {
  #tokens: number;
  #lastMs: number;

  constructor(
    readonly capacity: number,
    readonly refillPerMs: number,
    nowMs = 0,
  ) {
    this.#tokens = capacity;
    this.#lastMs = nowMs;
  }

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    const safeNow = Math.max(nowMs, this.#lastMs);
    this.#tokens = Math.min(
      this.capacity,
      this.#tokens + (safeNow - this.#lastMs) * this.refillPerMs,
    );
    this.#lastMs = safeNow;
    if (cost > this.capacity) {
      return { allowed: false, remaining: this.#tokens, retryAfterMs: Infinity };
    }
    const allowed = cost <= this.#tokens;
    if (allowed) this.#tokens -= cost;
    const deficit = Math.max(0, cost - this.#tokens);
    return {
      allowed,
      remaining: Math.max(0, this.#tokens),
      retryAfterMs: allowed ? 0 : deficit / this.refillPerMs,
    };
  }
}

Client không hoạt động có thể tích lũy một burst chủ ý bằng B, sau đó tiếp tục ở tốc độ trung bình r. Mô hình này thường hợp với interactive API vì burst ngắn được hoàn tất ngay.

Tên leaky bucket thường được dùng mơ hồ. Khi làm meter, nó gần như token bucket. Khi làm shaper như dưới đây, nó xếp hàng công việc đã nhận và phát ra với tốc độ đều. readyAtMs là thời điểm hoàn tất được lịch FIFO gán cho request.

export type ShapingDecision = Decision & { readyAtMs: number };

export class LeakyBucketShaper {
  #nextAvailableMs = 0;

  constructor(
    readonly capacity: number,
    readonly leakPerMs: number,
  ) {}

  schedule(cost: number, nowMs: number): ShapingDecision {
    requireCost(cost);
    const queued = Math.max(0, this.#nextAvailableMs - nowMs) * this.leakPerMs;
    if (cost > this.capacity || queued + cost > this.capacity) {
      const deficit = Math.max(0, queued + cost - this.capacity);
      return {
        allowed: false,
        remaining: Math.max(0, this.capacity - queued),
        retryAfterMs: cost > this.capacity ? Infinity : deficit / this.leakPerMs,
        readyAtMs: nowMs,
      };
    }

    const start = Math.max(nowMs, this.#nextAvailableMs);
    this.#nextAvailableMs = start + cost / this.leakPerMs;
    return {
      allowed: true,
      remaining: Math.max(0, this.capacity - queued - cost),
      retryAfterMs: 0,
      readyAtMs: this.#nextAvailableMs,
    };
  }
}

Shaping làm output xuống downstream mượt hơn nhưng đổi lại bằng latency và head-of-line blocking. Capacity phải tính cả cost vừa được nhận; request có cost lớn hơn capacity sẽ không bao giờ vừa.

GCRA (Generic Cell Rate Algorithm) chỉ giữ một theoretical arrival time (TAT). Gọi T = 1 / r là thời gian cho mỗi unit và B là burst unit. Weighted request hợp lệ khi TAT dự kiến không vượt burst horizon:

export class Gcra {
  #tatMs = 0;
  readonly #timePerUnitMs: number;

  constructor(
    readonly burstUnits: number,
    unitsPerMs: number,
  ) {
    this.#timePerUnitMs = 1 / unitsPerMs;
  }

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    const candidate = Math.max(nowMs, this.#tatMs) + cost * this.#timePerUnitMs;
    const horizon = nowMs + this.burstUnits * this.#timePerUnitMs;
    const allowed = cost <= this.burstUnits && candidate <= horizon;
    if (allowed) this.#tatMs = candidate;
    const debtUnits = Math.max(0, (this.#tatMs - nowMs) / this.#timePerUnitMs);
    return {
      allowed,
      remaining: Math.max(0, this.burstUnits - debtUnits),
      retryAfterMs: allowed ? 0 : Math.max(0, candidate - horizon),
    };
  }
}

GCRA cho hành vi gần token bucket bằng một timestamp, không cần cập nhật số token thập phân liên tục. Với request cost bằng 1, tolerance truyền thống là tau = (B - 1) * T. Dạng candidate có trọng số ở trên còn ngăn một request lớn hơn toàn bộ burst budget lọt qua khi limiter đang rỗng.

So sánh và chọn theo hình dạng traffic #

Một public endpoint có thể cần nhiều policy: token bucket cho burst ngắn của client và fixed quota dài hơn cho chi phí theo ngày. Chỉ compose limiter khi mỗi rule có ý nghĩa sản phẩm độc lập. Chồng nhiều limit gần giống nhau làm nguyên nhân reject và Retry-After rất khó giải thích.

Clock, weighted cost và hành vi HTTP #

Mọi implementation trên đều nhận nowMs thay vì tự đọc global clock. Trong Node.js, dùng performance.now() hoặc adapter từ process.hrtime.bigint() cho elapsed time trong process. Vẫn nên clamp delta âm như TokenBucket: snapshot được restore, mock sai và lỗi chuyển đổi số vẫn có thể xảy ra dù source đơn điệu. Process chạy nhiều tháng nên định kỳ rebase floating state để tránh mất precision.

Weighted request cần được tính trước phần xử lý đắt tiền, vì vậy hãy suy ra cost từ thuộc tính rẻ và đáng tin: plan đã authenticate, batch size khai báo kèm hard maximum, route class hoặc content length đã validate. Không tin cost tùy ý do client gửi. Cũng cần quyết định request bị reject có tiêu unit không; các implementation trên không tính. Attempt malformed hoặc abusive có thể dùng limiter riêng.

Với HTTP, chỉ trả 429 Too Many Requests khi client hoặc policy này bị rate limit; dùng 503 khi shared capacity hết bất kể budget của client. Retry-After nhận số giây nguyên hoặc HTTP date, nên làm tròn mili giây lên:

const retryAfterSeconds = Math.max(1, Math.ceil(decision.retryAfterMs / 1000));
response.setHeader('Retry-After', String(retryAfterSeconds));

RateLimit-Limit, RateLimit-Remaining và RateLimit-Reset trong RFC 9333 có thể mô tả quota đang hoạt động. Với weighted policy, tài liệu phải nói rõ remaining là unit. Với token bucket và GCRA, phân biệt “thời gian đến khi cost của request này vừa” với “thời gian đến khi bucket đầy hoàn toàn.” Nếu có nhiều policy, báo policy ràng buộc response mạnh nhất hoặc dùng cú pháp nhiều policy của RFC. Header chỉ là snapshot tư vấn; request concurrent có thể dùng hết remainder trước khi client kịp dùng nó.

Không sleep bên trong API rate limiter thông thường. Hãy reject sớm và để client lên lịch retry. Sleep chỉ thuộc về shaper tường minh có queue length hữu hạn, cancellation, deadline và metric. Nếu không, request chờ sẽ giữ socket và memory trong khi trông có vẻ vô hại.

Mô phỏng và kiểm thử tập trung vào boundary #

Virtual time biến test rate limit thành phép tính table-driven thay vì các lệnh sleep dễ flaky. Harness nhỏ sau replay một chuỗi arrival có trọng số:

type Limiter = { allow(cost: number, nowMs: number): Decision };
type Arrival = { at: number; cost: number; allowed: boolean };

export function verify(limiter: Limiter, arrivals: Arrival[]): void {
  for (const arrival of arrivals) {
    const actual = limiter.allow(arrival.cost, arrival.at);
    if (actual.allowed !== arrival.allowed) {
      throw new Error(
        `at=${arrival.at} cost=${arrival.cost}: expected ${arrival.allowed}, got ${actual.allowed}`,
      );
    }
  }
}

verify(new TokenBucket(4, 1 / 1000), [
  { at: 0, cost: 4, allowed: true },
  { at: 1500, cost: 2, allowed: false },
  { at: 2000, cost: 2, allowed: true },
]);

Vector nên tấn công contract thay vì chỉ kiểm tra happy path cách đều:

Hãy thêm property test: tổng cost đã nhận trong mọi exact rolling window không vượt L; token balance luôn thuộc [0, B]; work đã nhận của leaky bucket không vượt queue capacity; và trì hoãn một request giống hệt không thể làm nó kém eligible hơn nếu không có request xen vào. So sánh GCRA với token bucket trên trace unit-cost ngẫu nhiên có cùng B và r; decision của chúng phải trùng trong floating-point tolerance.

Cuối cùng, mô phỏng trace giống thực tế: nhiều client đồng bộ tại mốc giây, một request nặng nằm giữa nhiều request nhẹ, traffic idle rồi burst, và traffic liên tục cao hơn r một chút. Ghi accept ratio, chuỗi reject dài nhất, queue delay và độ chính xác của retry. Throughput trung bình không thể làm lộ unfair burst hay tail latency bất thường.

Điều cần nhớ #

• Fixed window dùng ít state nhất nhưng chủ ý chấp nhận spike khi reset.
• Sliding log thực thi đúng rolling-window contract; sliding counter đổi độ chính xác lấy constant memory.
• Token bucket thưởng idle time bằng burst tức thời; leaky-bucket shaper đổi latency lấy output đều.
• GCRA biểu diễn continuous conformance bằng một timestamp và ánh xạ rõ sang burst cùng sustained rate.
• Boundary, weighted unit, clock behavior và rejection header phải là một phần của contract.
• Hãy chứng minh contract bằng virtual-time vector quanh expiry, rollback, fractional cost và overload trước khi tối ưu storage.