Sliding Window Counter

Sliding Window Counter는 Fixed Window Counter의 한계인 윈도우 경계 문제(버스트 문제)를 완화하기 위해 사용되는 알고리즘이다.

Fixed Window Counter가 “일정 시간”이었다면, Sliding Window Counter는 “지난 1분”이라는 움직이는 시간 구간을 유지한다. 그래서 두 개의 카운터를 사용하여 요청량을 추정한다.

핵심 아이디어

• 시간 구간을 고정시키는 대신, "슬라이딩"(rolling)되는 윈도우를 사용해 현재 시점을 기준으로 과거 일정 기간동안의 요청 수를 측정한다.

• 가장 최근 윈도우와 이전 윈도우의 가중치를 조합해 요청 허용 여부를 판단한다.

• 즉, "부분적인 이전 윈도우 + 현재 윈도우" 요청 수를 합산해 더 부드럽게 제한한다.

동작 방식

1. 요청이 들어올 때 현재 시간 기반으로 두 개의 윈도우를 계산한다.

   • 예를 들어 윈도우 크기 1분 기준으로 12:01:40은 12:01:00 윈도우와 12:02:00 윈도우 사이에 있음

2. 이전 윈도우 카운트와 현재 윈도우 카운트를 가져와 비율에 따라 가중 평균 계산

   • (이전 윈도우 카운트 × 가중치) + 현재 윈도우 카운트라는 공식을 사용

3. 합계가 허용 한도 내면 요청 허용, 그렇지 않으면 거부

4. 현재 윈도우 카운트 1 증가

👍 장점

• 경계 문제 해결: Fixed Window의 가장 큰 문제였던 윈도우 경계에서의 순간적인 트래픽 폭증(Burst)을 효과적으로 방어한다.

• 메모리 효율 유지: 모든 요청의 타임스탬프를 저장하는 'Sliding Window Log' 방식과 달리, 카운터 몇 개만 유지하므로 메모리 효율이 좋다. (정확성과 효율성 사이의 좋은 타협점)

👎 단점

• 완벽하지 않은 정확성: 이전 윈도우의 요청이 균등하게 분포했다고 가정하고 가중치를 계산하므로, 실제 요청량과 약간의 오차가 발생할 수 있다. 하지만 대부분의 경우 무시할 수 있는 수준이라고 한다.

• 구현 복잡성: Fixed Window에 비해 가중치를 계산하는 로직이 추가되어 구현이 좀 더 복잡하다.