Rate Limiter의 경계 값 문제를 해결한 Sliding Window Log 구현

슬라이딩 윈도우 로그 처리율 제한에 대해서 정리하려고 합니다.

Sliding Window Log Rate Limiter는 뭘까?

Fixed Window(고정 윈도우)와 달리 고정된 시간 구간이 아닌 현재 시점을 기준으로 과거 N분간의 요청 기록을 실시간으로 추적하는 방식 입니다.

 

5분 슬라이딩 윈도우 예시는 다음과 같습니다.

 

현재 시각이 09:03:30 이라면

• 09:03:30 기준으로 08:58:30 ~ 구간의 요청들을 확인해서
• 09:04:00이 되면 08:59:00 ~ 09:04:00 구간으로 윈도우를 슬라이딩합니다.

 

동작원리

마찬가지로 사이드 프로젝트에서 슬랙 알림 중복 발송 방지를 위해 사용하였습니다.

Fixed Window의 문제점들을 해결하기 위해 개선된 방식을 적용했습니다.

 

ConcurrentHashMap + ArrayList 자료 구조를 선정하였습니다.

ConcurrentHashMap<String, List<Long>> alerts = new ConcurrentHashMap<>();

• 동시성을 보장하는 자료구조는 동일하지만, value 로 타임스탬프 리스트를 사용합니다.
• 각 요청 시간을 모두 기록하여 정확한 윈도우 슬라이딩이 가능합니다.

key 는 [예외 코드 + ":" + 예외 레벨]로 설정하였습니다.

 

Fixed Window와 달리 시작 윈도우 시간을 포함하지 않았습니다.

String key = createKey(errorCode, level);
List<Long> timestamps = alerts.computeIfAbsent(key, k -> new ArrayList<>());

 

핵심로직은 다음과 같습니다.

long now = clock.millis();
timestamps.removeIf(ts -> ts <= now - RATE_LIMIT_WINDOW_MILLIS);
timestamps.add(now);
int maxAlerts = getMaxAlertsPerPeriod(level);
return timestamps.size() <= maxAlerts;

 

동작 단계:

1. 만료된 타임스탬프를 제거합니다. (N분 이전의 기록들을 삭제)
2. 현재 요청 기록을 추가 합니다. 
3. 제한을 확인합니다.

Fixed Window처럼 별도의 스케줄러 기반 정리 작업이 불필요합니다. 매 요청마다 자동으로 만료된 기록이 정리됩니다.

 

해결되는 Fixed Window 문제점

1. 경계에서 2배 트래픽 문제 해결

1분 단위로 10개 요청 제한 시나리오:

• 09:00:59 -> 10개 요청 (과거 1분간 기록 확인)
• 09:01:00 -> 1초 전 요청들이 여전히 윈도우 내에 있어 새 요청 거부

실시간으로 슬라이딩이 이루어지면서 경계 값 트래픽 급증을 방지할 수 있습니다.

 

2. 선착순 독점 문제 완화

• 09:00:00 -> 10개 요청을 처리합니다.
• 09:00:30 -> 30초 전 요청들이 여전히 유효하므로 추가 요청을 제한합니다.
• 09:01:00 -> 1분 전 요청들이 순차적으로 만료되며 새 요청을 허용합니다.

시간이 지나가면서 새 요청이 가능합니다.

 

발견되는 새로운 문제점

메모리 사용량이 증가합니다.

Fixed Window는 카운터(AtomicInteger) 하나만 저장하지만 Sliding Window는 모든 요청의 타임스탬프를 저장해야 합니다.

// Fixed: 키당 4바이트(int)  
AtomicInteger count = new AtomicInteger(0);

// Sliding: 키당 요청 개수 × 8바이트(long)
List<Long> timestamps = new ArrayList<>();

 

처리 성능 오버헤드

매 요청마다 리스트를 전체 조회하고 필터링 작업을 수행합니다.

timestamps.removeIf(ts -> ts <= now - RATE_LIMIT_WINDOW_MILLIS);

요청이 많을수록 O(n) 시간 복잡도로 성능에 영향을 줄 수 있습니다.

 

그래서 어떤 상황에 선택할지?

Sliding Window Log가 적합한 경우는 트래픽이 불규칙하고 경계 값에 몰릴 가능성이 높은 경우

 

그리고 메모리 사용량보다 정확성이 우선인 경우라고 생각합니다.

 

모든 요청의 타임스탬프를 기록하기 때문에 고정 윈도우 방식보다 메모리 효율성은 떨어지게 됩니다.