레이트 리미터 패턴

using System;

var clock = new FakeClock();
// 용량 3, 1000 ms마다 토큰 1개를 다시 채운다.
var bucket = new TokenBucketLimiter(capacity: 3, refillPeriodMs: 1000, clock);
long[] requestTimesMs = [0, 100, 200, 300, 500, 1300, 1400, 3500];

foreach (var t in requestTimesMs)
{
    clock.NowMs = t;
    var d = bucket.TryAcquire();
    Console.WriteLine(d.Allowed
        ? $"t={t,4} ms allowed  tokens left {d.TokensLeft}"
        : $"t={t,4} ms rejected Retry-After: {RetryAfterSeconds(d.RetryAfterMs)} (next token in {d.RetryAfterMs} ms)");
}

// Retry-After는 정수 초만 담으므로 올림한다. 내림하면 클라이언트가 너무 일찍 다시 온다.
static long RetryAfterSeconds(long ms) => (ms + 999) / 1000;

interface IClock { long NowMs { get; } }

// 예제가 시각을 직접 정하는 가짜 시계다. 실제로 기다리지 않는다.
sealed class FakeClock : IClock { public long NowMs { get; set; } }

readonly record struct Decision(bool Allowed, int TokensLeft, long RetryAfterMs)
{
    public static Decision Allow(int tokensLeft) => new(true, tokensLeft, 0);
    public static Decision Reject(long retryAfterMs) => new(false, 0, retryAfterMs);
}

sealed class TokenBucketLimiter(int capacity, long refillPeriodMs, IClock clock)
{
    private readonly int capacity = capacity;
    private readonly IClock clock = clock;
    private int tokens = capacity; // 가득 찬 버킷으로 시작한다.
    private long lastRefillMs = clock.NowMs;

    public Decision TryAcquire()
    {
        var now = clock.NowMs;
        Refill(now);
        if (tokens == 0)
        {
            // 다음 토큰이 들어오는 시각까지 남은 시간을 함께 돌려준다.
            return Decision.Reject(lastRefillMs + refillPeriodMs - now);
        }
        tokens--;
        return Decision.Allow(tokens);
    }

    // 타이머 없이, 요청이 올 때 지난 보충 시각부터 흐른 시간만큼 토큰을 더한다.
    private void Refill(long now)
    {
        var periods = (now - lastRefillMs) / refillPeriodMs;
        tokens = (int)Math.Min(capacity, tokens + periods);
        // 가득 차면 쌓이던 자투리 시간을 버린다. 가득 찬 버킷에는 토큰이 더 들어가지 않는다.
        lastRefillMs = tokens == capacity ? now : lastRefillMs + periods * refillPeriodMs;
    }
}

t=   0 ms allowed  tokens left 2
t= 100 ms allowed  tokens left 1
t= 200 ms allowed  tokens left 0
t= 300 ms rejected Retry-After: 1 (next token in 700 ms)
t= 500 ms rejected Retry-After: 1 (next token in 500 ms)
t=1300 ms allowed  tokens left 0
t=1400 ms rejected Retry-After: 1 (next token in 600 ms)
t=3500 ms allowed  tokens left 1

using System;
using System.Collections.Generic;

var clock = new FakeClock();
var gate = new RateLimitGate(clock, capacity: 3, refillPeriodMs: 1000);
(long At, string? ApiKey)[] trace =
[
    (0, "alice"), (100, "alice"), (200, "alice"), (250, "bob"),
    (300, "alice"), (350, null), (400, "bob"), (1300, "alice"),
];

Console.WriteLine("== per-client token buckets (capacity 3, 1 token per 1000 ms)");
foreach (var (at, key) in trace)
{
    clock.NowMs = at;
    Console.WriteLine($"t={at,4} {key ?? "(none)",-6} -> {gate.Handle(new Request(key))}");
}

// 같은 요청 흐름을 "초당 2개" 한도의 두 알고리즘에 동시에 보낸다.
var clock2 = new FakeClock();
var fixedWindow = new FixedWindowLimiter(limit: 2, windowMs: 1000, clock2);
var bucket = new TokenBucketLimiter(capacity: 2, refillPeriodMs: 500, clock2);
long[] burst = [900, 950, 1000, 1050, 1400];
int fixedInSpan = 0, bucketInSpan = 0;

Console.WriteLine();
Console.WriteLine("== limit 2 per second: fixed window vs token bucket");
foreach (var at in burst)
{
    clock2.NowMs = at;
    var f = fixedWindow.TryAcquire();
    var b = bucket.TryAcquire();
    if (at <= 1050 && f.Allowed) fixedInSpan++;
    if (at <= 1050 && b.Allowed) bucketInSpan++;
    Console.WriteLine($"t={at,4}  fixed window: {Show(f),-16} token bucket: {Show(b)}");
}
Console.WriteLine($"admitted from 900 to 1050 ms: fixed window {fixedInSpan}, token bucket {bucketInSpan}");

static string Show(Decision d) => d.Allowed ? "allowed" : $"rejected {d.RetryAfterMs} ms";

interface IClock { long NowMs { get; } }

sealed class FakeClock : IClock { public long NowMs { get; set; } }

readonly record struct Decision(bool Allowed, int TokensLeft, long RetryAfterMs)
{
    public static Decision Allow(int tokensLeft) => new(true, tokensLeft, 0);
    public static Decision Reject(long retryAfterMs) => new(false, 0, retryAfterMs);
}

sealed record Request(string? ApiKey);

sealed record Response(int Status, string Text, long? RetryAfterSeconds)
{
    public override string ToString() =>
        RetryAfterSeconds is { } s ? $"{Status} {Text}, Retry-After: {s}" : $"{Status} {Text}";
}

sealed class RateLimitGate(IClock clock, int capacity, long refillPeriodMs)
{
    // 키마다 버킷을 따로 두어, 한 클라이언트가 몰아 보내도 다른 클라이언트의 토큰은 줄지 않는다.
    private readonly Dictionary<string, TokenBucketLimiter> buckets = new();

    public Response Handle(Request request)
    {
        // 키 검증(인증)은 생략했다. 검증하지 않은 값마다 버킷을 만들면 메모리가 끝없이 늘 수 있다.
        if (request.ApiKey is null) return new Response(401, "Unauthorized", null);
        if (!buckets.TryGetValue(request.ApiKey, out var bucket))
        {
            bucket = new TokenBucketLimiter(capacity, refillPeriodMs, clock);
            buckets[request.ApiKey] = bucket;
        }
        var d = bucket.TryAcquire();
        if (!d.Allowed)
        {
            // 조용히 버리지 않고 429와 다시 시도할 시각(정수 초, 올림)을 알린다.
            return new Response(429, "Too Many Requests", (d.RetryAfterMs + 999) / 1000);
        }
        return new Response(200, $"OK (tokens left {d.TokensLeft})", null);
    }
}

sealed class TokenBucketLimiter(int capacity, long refillPeriodMs, IClock clock)
{
    private readonly int capacity = capacity;
    private readonly IClock clock = clock;
    private int tokens = capacity;
    private long lastRefillMs = clock.NowMs;

    public Decision TryAcquire()
    {
        var now = clock.NowMs;
        Refill(now);
        if (tokens == 0) return Decision.Reject(lastRefillMs + refillPeriodMs - now);
        tokens--;
        return Decision.Allow(tokens);
    }

    private void Refill(long now)
    {
        var periods = (now - lastRefillMs) / refillPeriodMs;
        tokens = (int)Math.Min(capacity, tokens + periods);
        // 가득 차면 쌓이던 자투리 시간을 버린다. 가득 찬 버킷에는 토큰이 더 들어가지 않는다.
        lastRefillMs = tokens == capacity ? now : lastRefillMs + periods * refillPeriodMs;
    }
}

sealed class FixedWindowLimiter(int limit, long windowMs, IClock clock)
{
    private long windowStartMs;
    private int count;

    public Decision TryAcquire()
    {
        var now = clock.NowMs;
        // 창은 0, 1000, 2000 ms처럼 고정된 경계에서 시작하고, 경계를 넘으면 개수를 0으로 되돌린다.
        var start = now - now % windowMs;
        if (start != windowStartMs) { windowStartMs = start; count = 0; }
        if (count == limit) return Decision.Reject(windowStartMs + windowMs - now);
        count++;
        return Decision.Allow(limit - count);
    }
}

== per-client token buckets (capacity 3, 1 token per 1000 ms)
t=   0 alice  -> 200 OK (tokens left 2)
t= 100 alice  -> 200 OK (tokens left 1)
t= 200 alice  -> 200 OK (tokens left 0)
t= 250 bob    -> 200 OK (tokens left 2)
t= 300 alice  -> 429 Too Many Requests, Retry-After: 1
t= 350 (none) -> 401 Unauthorized
t= 400 bob    -> 200 OK (tokens left 1)
t=1300 alice  -> 200 OK (tokens left 0)

== limit 2 per second: fixed window vs token bucket
t= 900  fixed window: allowed          token bucket: allowed
t= 950  fixed window: allowed          token bucket: allowed
t=1000  fixed window: allowed          token bucket: rejected 400 ms
t=1050  fixed window: allowed          token bucket: rejected 350 ms
t=1400  fixed window: rejected 600 ms  token bucket: allowed
admitted from 900 to 1050 ms: fixed window 4, token bucket 2

interface IClock { readonly nowMs: number; }

// 예제가 시각을 직접 정하는 가짜 시계다. 실제로 기다리지 않는다.
class FakeClock implements IClock { nowMs = 0; }

type Decision =
  | { allowed: true; tokensLeft: number }
  | { allowed: false; retryAfterMs: number };

class TokenBucketLimiter {
  #tokens: number;
  #lastRefillMs: number;
  constructor(
    private readonly capacity: number,
    private readonly refillPeriodMs: number,
    private readonly clock: IClock,
  ) {
    this.#tokens = capacity; // 가득 찬 버킷으로 시작한다.
    this.#lastRefillMs = clock.nowMs;
  }

  tryAcquire(): Decision {
    const now = this.clock.nowMs;
    this.#refill(now);
    if (this.#tokens === 0) {
      // 다음 토큰이 들어오는 시각까지 남은 시간을 함께 돌려준다.
      return { allowed: false, retryAfterMs: this.#lastRefillMs + this.refillPeriodMs - now };
    }
    this.#tokens--;
    return { allowed: true, tokensLeft: this.#tokens };
  }

  // 타이머 없이, 요청이 올 때 지난 보충 시각부터 흐른 시간만큼 토큰을 더한다.
  #refill(now: number): void {
    const periods = Math.floor((now - this.#lastRefillMs) / this.refillPeriodMs);
    this.#tokens = Math.min(this.capacity, this.#tokens + periods);
    // 가득 차면 쌓이던 자투리 시간을 버린다. 가득 찬 버킷에는 토큰이 더 들어가지 않는다.
    this.#lastRefillMs = this.#tokens === this.capacity ? now : this.#lastRefillMs + periods * this.refillPeriodMs;
  }
}

type RateLimitResponse = { status: number; text: string; retryAfterSeconds?: number };

class RateLimitGate {
  // 키마다 버킷을 따로 두어, 한 클라이언트가 몰아 보내도 다른 클라이언트의 토큰은 줄지 않는다.
  readonly #buckets = new Map<string, TokenBucketLimiter>();
  constructor(
    private readonly clock: IClock,
    private readonly capacity: number,
    private readonly refillPeriodMs: number,
  ) {}

  handle(apiKey: string | null): RateLimitResponse {
    // 키 검증(인증)은 생략했다. 검증하지 않은 값마다 버킷을 만들면 메모리가 끝없이 늘 수 있다.
    if (apiKey === null) return { status: 401, text: "Unauthorized" };
    let bucket = this.#buckets.get(apiKey);
    if (bucket === undefined) {
      bucket = new TokenBucketLimiter(this.capacity, this.refillPeriodMs, this.clock);
      this.#buckets.set(apiKey, bucket);
    }
    const d = bucket.tryAcquire();
    if (!d.allowed) {
      // 조용히 버리지 않고 429와 다시 시도할 시각(정수 초, 올림)을 알린다.
      return { status: 429, text: "Too Many Requests", retryAfterSeconds: Math.ceil(d.retryAfterMs / 1000) };
    }
    return { status: 200, text: `OK (tokens left ${d.tokensLeft})` };
  }
}

function show(r: RateLimitResponse): string {
  return r.retryAfterSeconds === undefined
    ? `${r.status} ${r.text}`
    : `${r.status} ${r.text}, Retry-After: ${r.retryAfterSeconds}`;
}

const clock = new FakeClock();
const gate = new RateLimitGate(clock, 3, 1000);
const trace: Array<[number, string | null]> = [
  [0, "alice"], [100, "alice"], [200, "alice"], [250, "bob"],
  [300, "alice"], [350, null], [400, "bob"], [1300, "alice"],
];
for (const [at, key] of trace) {
  clock.nowMs = at;
  console.log(`t=${String(at).padStart(4)} ${(key ?? "(none)").padEnd(6)} -> ${show(gate.handle(key))}`);
}

t=   0 alice  -> 200 OK (tokens left 2)
t= 100 alice  -> 200 OK (tokens left 1)
t= 200 alice  -> 200 OK (tokens left 0)
t= 250 bob    -> 200 OK (tokens left 2)
t= 300 alice  -> 429 Too Many Requests, Retry-After: 1
t= 350 (none) -> 401 Unauthorized
t= 400 bob    -> 200 OK (tokens left 1)
t=1300 alice  -> 200 OK (tokens left 0)