Sliding Window Log

Sliding Window Counter는 움직이는 시간 구간을 유지하지만, Sliding Window Log는 시간 단위를 세밀하게 제어한다. 추정하는 것이 아니라, 실제 모든 기록을 일일이 확인하여 가장 정확하게 판단한다.

• 로그 (Log): 각 요청이 들어온 정확한 시간(타임스탬프)을 순서대로 모두 저장한다.

• 슬라이딩 윈도우 (Sliding Window): 항상 '현재 시간'을 기준으로, 과거의 특정 시간 범위(예: 지난 1분)를 동적으로 설정한다.

• 정확한 카운트 (Precise Count): 이 동적 시간 범위 안에 포함된 로그(타임스탬프)의 개수를 정확히 센다.

핵심 아이디어

이 알고리즘의 핵심 아이디어는, "현재 시간을 기준으로 지난 윈도우 시간 동안 발생한 모든 요청의 타임스탬프를 실제로 기록하고, 그 기록의 개수를 세어 한도를 제어하는 것" 이다.

동작 방식

1. 타임스탬프 기록: 요청이 들어오면, 현재 시간을 타임스탬프로 변환하여 로그(보통 Redis의 Sorted Set 같은 자료구조)에 저장한다.

2. 오래된 로그 제거: 현재 윈도우의 시작 시간보다 오래된 타임스탬프 로그는 모두 삭제하여 항상 최신 로그만 유지한다.

3. 로그 개수 카운트: 현재 윈도우 범위 내에 남아있는 로그의 총개수를 센다.

4. 한도 확인: 이 개수가 설정된 한도(Limit)보다 작은지 확인한다.

   • 허용 (Allow): 한도 이내라면 요청을 처리한다. (1번 단계에서 이미 로그는 기록되었음)

   • 거부 (Deny): 한도를 초과했다면, 방금 기록한 타임스탬프를 다시 삭제하고 요청을 거부한다.

👍 장점

• 완벽한 정확성: 모든 요청을 기록하고 세기 때문에, 추정 방식에서 발생하는 오차가 전혀 없다. 이론적으로 가장 완벽한 Rate Limiting을 제공한다.

• 유연성: 윈도우 경계 문제가 아예 존재하지 않으며, 어떤 트래픽 패턴에도 정확하게 대응한다.

👎 단점

• 높은 메모리 비용:

  • 윈도우 내의 모든 요청 타임스탬프를 저장해야 한다.

  • 만약 분당 10,000개의 요청을 허용한다면, 사용자 한 명당 최대 10,000개의 타임스탬프 데이터를 메모리에 유지해야 하므로 비용이 매우 비싸다.

• 계산 부하:

  • 요청마다 로그를 추가하고, 범위를 계산하여 개수를 세는 과정에서 약간의 계산 부하가 발생할 수 있다.

예시

• 규칙: 1분당 10개의 요청 허용 (Window 크기 = 60초, Limit = 10)

• 상황: 현재 시간 12:01:15. 지난 1분 동안 다음과 같은 요청 기록(타임스탬프)이 로그에 저장되어 있음

  • [12:00:20, 12:00:35, 12:00:58, 12:00:59, 12:01:01, 12:01:05, 12:01:10]

• 새로운 요청 도착: 12:01:15에 새로운 요청이 1개 들어온다.

• 알고리즘의 판단:

  1. 현재 윈도우 범위 설정: 12:00:15 ~ 12:01:15

  2. 범위 내 로그 필터링: 기존 로그 중 이 범위에 해당하는 기록만 확인한다.

     • [12:00:20, 12:00:35, 12:00:58, 12:00:59, 12:01:01, 12:01:05, 12:01:10] -> 총 7개

  3. 카운트 확인: 현재 로그 개수는 7개로, 한도 10개보다 작다.

  4. 처리: 요청을 허용하고, 새로운 타임스탬프 12:01:15를 로그에 추가한다.

     • [..., 12:01:05, 12:01:10, 12:01:15]