가상 면접 사례로 배우는 대규모 시스템 설계 기초 책을 보고 만든 처리율 제한기

1. Fixed Window Counter (고정 윈도우 카운터)

개념
• 일정한 시간 간격 (예: 1초, 10초, 1분 등)마다 요청 카운트를 초기화하는 방식.
• 매우 단순하며 메모리 사용량이 적고 속도가 빠름.
• 하지만 시간 경계 문제(Time Boundary Issue)가 발생할 수 있음.

구현 방식
1. ConcurrentHashMap<String, Integer>를 사용하여 클라이언트의 요청 횟수를 저장.
2. AtomicInteger를 사용하여 카운터를 업데이트.
3. 일정 시간이 지나면 카운터를 초기화.

import java.time.Clock;
import java.time.Instant;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowRateLimiter {
    private final int maxRequests;
    private final long windowMillis;
    private final Map<String, AtomicInteger> requestCounts = new ConcurrentHashMap<>();
    private volatile long windowStart;
    private final Clock clock;

    public FixedWindowRateLimiter(int maxRequests, long windowMillis, Clock clock) {
        this.maxRequests = maxRequests;
        this.windowMillis = windowMillis;
        this.clock = clock;
        this.windowStart = clock.millis();
    }

    public synchronized boolean allowRequest(String clientId) {
        long now = clock.millis();

        // 윈도우 초기화
        if (now - windowStart >= windowMillis) {
            requestCounts.clear();
            windowStart = now;
        }

        // 요청 카운트 증가
        requestCounts.putIfAbsent(clientId, new AtomicInteger(0));
        return requestCounts.get(clientId).incrementAndGet() <= maxRequests;
    }
}

장점 & 단점

장점
• 구현이 단순하고 메모리 사용량이 적음.
• 매우 빠른 속도 (AtomicInteger 사용).
• 트래픽이 균등할 경우 매우 효과적.

단점
• 시간 경계 문제: 시간이 갱신되면 카운트가 리셋되므로, 한 윈도우의 끝과 다음 윈도우의 시작 부분에서 몰아치는 트래픽을 허용할 수 있음.
→ 예: 10초 동안 10개 제한인데, 9.9초에 10개 + 10.1초에 10개 = 20개 요청 허용될 수 있음.

---

2. Sliding Window Counter (슬라이딩 윈도우 카운터)

개념
• Fixed Window 방식의 단점을 개선한 방식.
• 일정 시간 간격을 작은 슬롯(slot)으로 나누고, 요청이 들어올 때마다 최신 슬롯을 업데이트.
• 트래픽이 몰리는 문제를 완화하면서도 Sliding Window Log보다 메모리 효율적.

구현 방식
1. ConcurrentHashMap<String, Deque\>를 사용하여 요청 수를 슬롯 단위로 저장.
2. 오래된 슬롯을 제거하고 새로운 슬롯을 추가.
3. 요청이 들어오면, 최근 N초 동안의 총 요청 수를 계산.

import java.time.Clock;
import java.time.Instant;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class SlidingWindowCounterRateLimiter {
    private final int maxRequests;
    private final long windowMillis;
    private final int slotCount;
    private final Map<String, Deque<Integer>> requestCounts = new ConcurrentHashMap<>();
    private final Clock clock;

    public SlidingWindowCounterRateLimiter(int maxRequests, long windowMillis, int slotCount, Clock clock) {
        this.maxRequests = maxRequests;
        this.windowMillis = windowMillis;
        this.slotCount = slotCount;
        this.clock = clock;
    }

    public synchronized boolean allowRequest(String clientId) {
        long now = clock.millis();
        requestCounts.putIfAbsent(clientId, new LinkedList<>());

        Deque<Integer> slots = requestCounts.get(clientId);

        // 오래된 슬롯 제거
        while (slots.size() >= slotCount) {
            slots.pollFirst();
        }

        // 현재 슬롯 증가
        if (slots.isEmpty() || now - slots.peekLast() > windowMillis / slotCount) {
            slots.addLast(1);
        } else {
            slots.addLast(slots.pollLast() + 1);
        }

        return slots.stream().mapToInt(Integer::intValue).sum() <= maxRequests;
    }
}

장점 & 단점

장점
• Fixed Window보다 트래픽이 몰리는 문제를 완화.
• Sliding Window Log보다 메모리 사용량이 적음.

단점
• 요청 개수를 합산해야 하므로 연산 비용이 증가.

---

3. Token Bucket (토큰 버킷)

개념
• N개의 토큰을 가진 버킷을 생성하고, 요청이 올 때마다 토큰을 하나씩 사용.
• 버킷이 비어있으면 요청 차단, 일정 시간마다 토큰을 일정 개수만큼 추가.

구현 방식
1. AtomicInteger를 사용하여 현재 토큰 개수를 저장.
2. 주기적으로 일정 개수의 토큰을 추가 (ScheduledExecutorService 사용).
3. 요청이 들어오면 토큰이 남아있는지 확인 후 요청을 허용.

import java.time.Clock;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class TokenBucketRateLimiter {
    private final int maxTokens;
    private final int refillRate;
    private final AtomicInteger availableTokens;
    private final Clock clock;

    public TokenBucketRateLimiter(int maxTokens, int refillRate, Clock clock) {
        this.maxTokens = maxTokens;
        this.refillRate = refillRate;
        this.availableTokens = new AtomicInteger(maxTokens);
        this.clock = clock;

        ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);
        scheduler.scheduleAtFixedRate(this::refillTokens, 1, 1, TimeUnit.SECONDS);
    }

    private void refillTokens() {
        availableTokens.updateAndGet(current -> Math.min(maxTokens, current + refillRate));
    }

    public boolean allowRequest() {
        return availableTokens.getAndDecrement() > 0;
    }
}

장점 & 단점

장점
• 트래픽이 갑자기 몰리는 문제를 완화하면서도, 일정 속도로 요청을 허용할 수 있음.
• 네트워크 대역폭 제한, API Rate Limiting에 가장 적합.

단점
• 구현이 조금 복잡하고, ScheduledExecutorService를 사용해야 함.

---

어떤 기법을 선택해야 할까?

기법	성능	정확도	메모리 사용	추천 사용 사례
Fixed Window	빠름	낮음 (경계 문제 발생)	낮음	단순한 요청 제한
Sliding Window Counter	중간	높음	중간	실시간 API Rate
Sliding Window Log	느림	높음	높음	매우 정확한 요청 제한 필요할 때
Token Bucket	빠름	높음	낮음	네트워크 트래픽 제한

결론
• 성능이 가장 중요하면 Fixed Window 또는 Token Bucket 추천.
• 트래픽이 몰리는 문제가 중요하면 Sliding Window Counter 추천.
• 정확성이 중요한 경우 Sliding Window Log.

네트워크 요청을 안정적으로 처리하려면 Token Bucket이 가장 추천