Rate Limiting 알고리즘 — Token Bucket에서 Sliding Window까지

API를 호출하는데 "429 Too Many Requests"가 돌아왔습니다. 서버는 어떤 기준으로 요청을 제한하는 걸까요?

개념 정의

Rate Limiting(속도 제한) 은 특정 시간 내에 허용되는 요청 수를 제한하는 기법입니다. 서버를 과부하로부터 보호하고, 공정한 자원 사용을 보장합니다.

왜 필요한가

**DoS 방어 **: 악의적인 대량 요청 차단
** 비용 관리 **: API 호출당 과금되는 서비스에서 비용 제어
** 공정성 **: 한 사용자가 자원을 독점하지 못하게 방지
** 안정성 **: 서버 과부하 방지

Fixed Window Counter

가장 단순한 방식입니다. 시간을 고정된 윈도우(예: 1분)로 나누고, 각 윈도우의 요청 횟수를 카운트합니다.

JAVA

public class FixedWindowRateLimiter {
    private final int maxRequests;
    private final long windowSizeMs;
    private long windowStart;
    private int count;

    public FixedWindowRateLimiter(int maxRequests, long windowSizeMs) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.windowStart = System.currentTimeMillis();
        this.count = 0;
    }

    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();

        // 새 윈도우 시작
        if (now - windowStart >= windowSizeMs) {
            windowStart = now;
            count = 0;
        }

        if (count < maxRequests) {
            count++;
            return true;
        }
        return false;
    }
}

경계 문제

PLAINTEXT

윈도우: 1분에 100개 허용

0:00~0:59 → 0:59에 100개 요청 → 허용
1:00~1:59 → 1:00에 100개 요청 → 허용

결과: 0:59~1:00 사이 1초 동안 200개 요청이 처리됨!

Sliding Window Log

각 요청의 타임스탬프를 저장하고, 현재 시점에서 윈도우 크기만큼 뒤를 봅니다.

JAVA

public class SlidingWindowLog {
    private final int maxRequests;
    private final long windowSizeMs;
    private final Deque<Long> timestamps = new ArrayDeque<>();

    public SlidingWindowLog(int maxRequests, long windowSizeMs) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
    }

    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        long windowStart = now - windowSizeMs;

        // 윈도우 밖의 오래된 타임스탬프 제거
        while (!timestamps.isEmpty() && timestamps.peekFirst() <= windowStart) {
            timestamps.pollFirst();
        }

        if (timestamps.size() < maxRequests) {
            timestamps.addLast(now);
            return true;
        }
        return false;
    }
}

정확하지만, 요청마다 타임스탬프를 저장해야 해서 메모리 사용량이 많습니다.

Sliding Window Counter

Fixed Window와 Sliding Window Log의 절충안입니다. 이전 윈도우의 카운트를 비율로 반영합니다.

JAVA

public class SlidingWindowCounter {
    private final int maxRequests;
    private final long windowSizeMs;
    private int prevCount, currCount;
    private long currWindowStart;

    public SlidingWindowCounter(int maxRequests, long windowSizeMs) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.currWindowStart = System.currentTimeMillis();
    }

    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();

        if (now - currWindowStart >= windowSizeMs) {
            prevCount = currCount;
            currCount = 0;
            currWindowStart += windowSizeMs;
        }

        // 이전 윈도우의 남은 비율만큼 반영
        double elapsed = (now - currWindowStart) / (double) windowSizeMs;
        double estimatedCount = prevCount * (1 - elapsed) + currCount;

        if (estimatedCount < maxRequests) {
            currCount++;
            return true;
        }
        return false;
    }
}

Token Bucket

**일정 속도로 토큰이 채워지고 **, 요청 시 토큰을 소비합니다. 토큰이 있으면 허용, 없으면 거부합니다.

JAVA

public class TokenBucket {
    private final int maxTokens;      // 버킷 최대 용량
    private final double refillRate;  // 초당 토큰 충전 속도
    private double tokens;
    private long lastRefillTime;

    public TokenBucket(int maxTokens, double refillRate) {
        this.maxTokens = maxTokens;
        this.refillRate = refillRate;
        this.tokens = maxTokens;
        this.lastRefillTime = System.nanoTime();
    }

    public synchronized boolean allowRequest() {
        refill();
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsed = (now - lastRefillTime) / 1_000_000_000.0;
        tokens = Math.min(maxTokens, tokens + elapsed * refillRate);
        lastRefillTime = now;
    }
}

특징

**버스트 허용 **: 토큰이 쌓여 있으면 한 번에 많은 요청을 처리할 수 있습니다
AWS API Gateway, Stripe, GitHub API 등이 사용하는 방식입니다

Leaky Bucket

요청을 ** 큐(버킷)에 넣고, ** 일정 속도로 처리합니다. 버킷이 가득 차면 새 요청은 버립니다.

JAVA

public class LeakyBucket {
    private final int capacity;       // 큐 최대 크기
    private final double leakRate;    // 초당 처리 속도
    private double water;             // 현재 큐에 있는 요청 수
    private long lastLeakTime;

    public LeakyBucket(int capacity, double leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
        this.water = 0;
        this.lastLeakTime = System.nanoTime();
    }

    public synchronized boolean allowRequest() {
        leak();
        if (water < capacity) {
            water += 1;
            return true;
        }
        return false;
    }

    private void leak() {
        long now = System.nanoTime();
        double elapsed = (now - lastLeakTime) / 1_000_000_000.0;
        water = Math.max(0, water - elapsed * leakRate);
        lastLeakTime = now;
    }
}

Token Bucket vs Leaky Bucket

항목	Token Bucket	Leaky Bucket
버스트	허용 (토큰 축적)	불허 (일정 속도)
출력 속도	가변적	일정
적합 상황	API Gateway	네트워크 대역폭 관리

Redis를 이용한 분산 Rate Limiting

단일 서버가 아닌 분산 환경에서는 Redis를 활용합니다.

JAVA

// Redis + Sliding Window Counter (Lua 스크립트)
public class RedisRateLimiter {
    private final StringRedisTemplate redis;
    private final int maxRequests;
    private final long windowSeconds;

    private static final String LUA_SCRIPT = """
        local key = KEYS[1]
        local limit = tonumber(ARGV[1])
        local window = tonumber(ARGV[2])
        local now = tonumber(ARGV[3])

        -- 윈도우 밖의 요청 제거
        redis.call('ZREMRANGEBYSCORE', key, 0, now - window * 1000)

        -- 현재 요청 수 확인
        local count = redis.call('ZCARD', key)

        if count < limit then
            redis.call('ZADD', key, now, now .. ':' .. math.random())
            redis.call('PEXPIRE', key, window * 1000)
            return 1
        end
        return 0
        """;

    public boolean allowRequest(String clientId) {
        long now = System.currentTimeMillis();
        Long result = redis.execute(
            RedisScript.of(LUA_SCRIPT, Long.class),
            List.of("rate:" + clientId),
            String.valueOf(maxRequests),
            String.valueOf(windowSeconds),
            String.valueOf(now)
        );
        return result != null && result == 1;
    }
}

Sorted Set에 타임스탬프를 저장하고, 윈도우 밖의 항목을 제거하는 방식입니다. Lua 스크립트로 원자적으로 처리합니다.

Spring Cloud Gateway Rate Limiting

YAML

# application.yml
spring:
  cloud:
    gateway:
      routes:
        - id: api-route
          uri: http://api-service
          predicates:
            - Path=/api/**
          filters:
            - name: RequestRateLimiter
              args:
                redis-rate-limiter.replenishRate: 10    # 초당 10개 토큰 충전
                redis-rate-limiter.burstCapacity: 20    # 최대 20개 토큰
                key-resolver: "#{@userKeyResolver}"

Spring Cloud Gateway는 내장 Token Bucket 기반의 Rate Limiter를 제공합니다.

알고리즘 비교

알고리즘	정확도	메모리	버스트	구현 난이도
Fixed Window	낮음	O(1)	경계에서 2배	쉬움
Sliding Window Log	높음	O(N)	없음	중간
Sliding Window Counter	중간	O(1)	약간	중간
Token Bucket	높음	O(1)	허용	쉬움
Leaky Bucket	높음	O(1)	없음	쉬움

주의할 점

Fixed Window Counter의 경계 문제를 모르는 실수

1분 윈도우에서 0:59에 100개, 1:00에 100개를 보내면 1초 사이에 200개가 허용됩니다. 윈도우 경계에서 제한이 2배로 완화되는 이 문제를 해결하려면 Sliding Window를 사용해야 합니다.

분산 환경에서 로컬 Rate Limiting만 적용하는 실수

서버가 여러 대인데 각 서버에서 독립적으로 Rate Limiting을 하면, 전체적으로는 서버 수 배의 요청이 허용됩니다. Redis 같은 중앙 저장소 기반의 분산 Rate Limiting이 필요합니다.

정리

Fixed Window: 단순하지만 경계 문제가 있습니다
Sliding Window: 정확하지만 메모리 또는 근사치 트레이드오프가 있습니다
Token Bucket: 버스트를 허용하며, API Gateway에서 가장 많이 사용됩니다
Leaky Bucket: 일정 속도 출력, 네트워크 트래픽 제어에 적합합니다
분산 환경에서는 Redis + Lua 스크립트 로 원자적 Rate Limiting을 구현합니다
Spring Cloud Gateway는 Redis 기반 Token Bucket을 기본 제공합니다