Rate Limiter

1. Rate Limiter란

정해진 시간 안에 허용되는 요청 수를 제한하는 장치입니다.

목적으로는 다음과 같습니다.

• 남용/DDoS 방어, 서버 자원 보호(특히 2GB 같은 저사양)
• 공정한 사용(한 유저가 자원 독점 방지)
• 비용 제어(외부 API 호출량 등)

 

그러면 위 목적으로 사용하되 분명히 알아야할 것이 있습니다.

1. rate limiter가 요청이 왔을 때 어떤 걸로 카운터를 셀 것인가.
2. 이 요청에 대해 통과를 시킬까 막을까에 대한 수학적 방법 == 알고리즘
3. 알고리즘 코드가 어느 서버/ 어느 층에서 도느냐. 즉, 요청이 지나가는 경로 중 어디에 rate limiter를 심을 것이냐

→ 그래서 Rate Limiter를 도입할 때는 다음과 같은 문장이 완성되어야합니다

[3번. NGINX 에서] [1번. IP 기준으로] [2번. Token Bucket 방식으로] 분당 10개 제한한다

 

1,2,3번에 대한 각각 부분을 좀 더 세밀하게 공부해도록 하겠습니다.

무엇을 기준으로 셀까? (Key)

분당 10개 제한이라고 하였을 때 누구/무엇의 10개냐를 정하는 것입니다. 카운터를 무슨 단위로 묶을지.

기준(key)	의미	쓰는 곳
IP 주소	이 IP에서 온 요청을 셈	NGINX 기본, 익명 트래픽
유저 ID	로그인한 이 사람 요청을 셈	로그인 후 API
API 키	이 키(외부 개발자)로 온 요청	공개 API
IP + 엔드포인트	이 IP가 /login에 온 것만 셈	로그인 brute-force 방어

이 기준이 중요한 이유는 기준을 잘못 잡으면 엉뚱하게 막히게 됩니다. 예를 들어서

• IP로만 세면 → 회사/카페 같은 IP 쓰는 100명이 한 덩어리로 묶여 억울하게 차단.
• 유저 ID로 세면 → 정확하지만 로그인 안 한 요청(회원가입, 로그인 자체)은 유저ID가 없어서 못 셈.

그래서 상황마다 key를 다르게 구분하는 것도 생각을 해봐야합니다. 로그인 전엔 IP, 로그인 후엔 유저 ID형태

 

어떤 알고리즘으로 셀까

어떻게 세느냐" 의 방식입니다. 이 알고리즘들은 크게 5가지 정도가 있습니다. 이 알고리즘들은 같은 분당 10개라도 세는 방식에 따라 동작이 달라집니다.

각 알고리즘들을 공부해보았습니다. 전부 분당 5개 허용 기준으로 공부해보았습니다.

 

Fixed Window Counter (고정 윈도우)

• 시간을 고정 구간으로 쪼개고, 구간마다 카운터를 세는 방법입니다.

[10:00:00~10:00:59] 카운터=0 → 요청마다 +1, 5 넘으면 거부
[10:01:00~10:01:59] 카운터=0으로 리셋

장점은 구현 초간단 (Redis INCR + EXPIRE 한 줄)하고, 메모리 소비량이 작습니다.

단점으로는 정말 치명적인 문제가 있습니다. 구간 경계에서 최대 2배까티 통과할 수 있는 경계 문제(burst at boundary)가 있습니다.

10:00:59 에 5개  +  10:01:00 에 5개
→ 실제로 1초 사이에 10개가 몰림 (한도 5인데!)

이 알고리즘은 시간을 딱 잘린 구간으로 나누고 구간이 바뀌면 카운터를 0으로 리셋합니다. 경계문제는 실제 흐르는 시간이 아니라 시계의 정각 기준으로 돌리게 됩니다.

구간 A: [10:00:00 ~ 10:00:59]   카운터 A
구간 B: [10:01:00 ~ 10:01:59]   카운터 B  ← 10:01:00 되는 순간 0으로 리셋

카운터 A와 B는 서로를 전혀 모릅니다. A가 5개를 다 썼든, 말든, B는 10:01:00에 0에서 시작합니다.

 

그러면 타임라인으로

시각        요청   구간   카운터        판정
─────────────────────────────────────────────
10:00:57    1개    A     A=1           통과
10:00:58    1개    A     A=2           통과
10:00:59    3개    A     A=3,4,5       통과 (A 꽉 참)
─────────── 10:01:00 정각, 카운터 리셋! ───────────
10:01:00    3개    B     B=1,2,3       통과 (B 새 구간!)
10:01:01    2개    B     B=4,5         통과 (B 꽉 참)

각 구간만 보면 A도 5개, B도 5개로 규칙을 지켰습니다. 하지만

 

문제의 핵심은 “구간 경계를 걸친 실제 시간 창”입니다.

10:00:57 ~ 10:01:01 이라는 실제 연속된 5초를 보면

A에서 5개 (10:00:57~59) + B에서 5개 (10:01:00~01) = 10개

어떤 연속된 1분(예: 10:00:30~10:01:29)을 잘라봐도 최대 10개가 들어올 수 있습니다. 한도는 5인데 실제론 2배(10개)가 통과해버린 것입니다.

 

즉, 규칙은 분당 5개인데 구간 경계 근처에 몰아치면 짧은 시간에 2배를 뚫을 수 있습니다.

 

쉽게 말하면 시간을 자르는 방식이 2가지 종류이기 때문입니다.

• A: 알고리즘이 자르는 창 - 시계 정각 기준으로 고정
• B: 실제로 우리가 지키고 싶은 창 - 아무 60초

Fixed Window는 A로만 검사하는데 B는 어느 구간을 봤을 때 한도를 넘을 수 있다느 것입니다.

 

그러면 이 문제가 왜 심각하냐면 이 알고리즘은 정각~정각 사이 5개만 보장합니다. 근데 공격자가 B방식으로 (정각을 걸쳐서) 자르면 10개가 잡히게 됩니다. 즉 알고리즘은 A로 5개 지켰다고 하는데 실제 세상에서는 10개가 들어온 것입니다.

 

그래서 Fixed Window는 자기가 정한 위치(정각)에서만 5개를 보장하고 다른 위치(경계 걸침)에선 최대 10개가 되는 걸 못 습니다.

 

Sliding Window Log (슬라이딩 로그)

모든 요청의 타임스탬프를 리스트로 저장하는 방식입니다. 매 요청마다 지금부터 1분 이내 개수를 셉니다.

요청 올 때: 1분 지난 타임스탬프 제거 → 남은 개수 < 5 면 허용하고 현재시각 기록

장점은 가장 정확하고 Fixed Window에서 나온 경계 문제가 없습니다.

하지만 단점으로는 요청마다 타임스탬프를 다 저장해야하기에 메모리를 많이 먹습니다. 초당 수천 요청이면 폭팔할 수도 있습니다. 구현은 Redis Sorted Set으로 구현할 수 있지만 비용이 비싸게 됩니다.

 

또한, 추가적인 단점으로는 clock skew(시계 오차)가 있습니다.

 

분산처리에서는 각 서버의 시계가 완벽히 똑같지 않습니다. NTP로 맞추어도 수십~수백ms씩 차이가 날 수 있습니다.

Spring #1 시계: 10:00:00.000
Spring #2 시계: 10:00:00.300   ← 300ms 빠름

Sliding Window Log는 지금부터 1분 이내 타임스탬프를 세는데 이 지금(현재시각)과 저장되는 타임스탬프를 누가 찍느냐가 문제가 됩니다.

 

만약 각 인스턴스가 자기 로컬 시계로 타임스탬프를 찍어서 Redis에 넣으면

#1이 찍은 10:00:59.900  과  #2가 찍은 10:01:00.100
→ 실제론 #2 시계가 빨라서 진짜 순서가 뒤바뀔 수도
→ "1분 이내" 판정이 인스턴스마다 미묘하게 달라짐

이것이 창 경계 계산이 어긋나서 한도를 살짝 초과 통과시키거나, 반대로 억울하게 일찍 거부할 수도 있습니다.

 

해결책으로는 시계를 하나로 통일할 수 있습니다. 즉, 단일 시계 하나를 기준으로 삼는 방법입니다.

1. Redis 자신의 시간을 쓴다. 이 방법은 제일 흔한 방법입니다.
2. NTP로 서버 시계 동기화 → 오차를 줄이지만 0으로 만들진 못한다. == 보조 방법
3. 작은 오차는 그냥 감수

 

Sliding Window Counter (슬라이딩 카운터)

Fixed Window의 가벼움과 Sliding Log의 정확함을 합친 버전입니다. 즉, 현재 윈도우 + 이전 윈도우 카운터를 가중 평균한 것입니다.

현재 윈도우 진행률이 30%라면:
추정치 = 이전윈도우_카운트 × (1 - 0.3) + 현재윈도우_카운트
       = 이전 5개 × 0.7 + 현재 2개 = 5.5 → 5 초과 → 거부

 

예시를 들어 한 번 자세하게 보겠습니다.

• 카운터를 2개 유지하게 됩니다. → 이전 구간, 현재 구간

이전 윈도우 [10:00:00~10:00:59]  카운트 = 5
현재 윈도우 [10:01:00~10:01:59]  카운트 = 2
지금 시각 = 10:01:18   → 현재 윈도우 18초 지남 = 진행률 30%

이 알고리즘의 목표는 지금 기준 뒤로 60초를 보는 것입니다.

지금이 10:01:18이니

진짜 보고 싶은 창 = [10:00:18 ~ 10:01:18]  (딱 60초)

이 60초 창을 그림으로 보면 두 구간에 거려있습니다

이전 윈도우                     현재 윈도우
[10:00:00 ────────── 10:00:59][10:01:00 ──── 10:01:18 ──── 10:01:59]
          |◄── 겹침 (70%) ──►||◄─ 겹침(30%) ─►|
       10:00:18                            10:01:18

• 이전 윈도우의 뒤쪽 70% (10:00:18~10:00:59)가 겹침
• 현재 윈도우의 앞쪽 30% (10:01:00~10:01:18)가 겹침

 

문제는 이전 윈도우 요청이 언제 왔는지 모릅니다.

→ 이전 윈도우에 5개가 왔다는 거는 알 수 있지만 그게 앞에 몰렸는지 뒤에 몰렸는지에 대한 기록이 없습니다.. 그래서 고르게 퍼져 있다고 가정합니다.

 

고르게 퍼졌다면 겹치는 70% 구간엔 5개 중 70%인 3.5개가 있다고 추정합니다.

이전 윈도우 기여분 = 5 × 0.7 = 3.5

현재 윈도우 2개는 지금 창 안에 확실히 있으니 그대로

현재 윈도우 기여분 = 2

추정치 = 3.5 + 2 = 5.5 → 한도 5 초과 → 거부

 

공식을 정리하면 다음과 같습니다.

추정치 = 이전카운트 × (1 - 진행률) + 현재카운트

(1-진행률)이 왜 이전 윈도우 가중치냐면 현재 윈도우가 진행될 수록 60초 차으이 꼬리가 이전 윈도우 밖으로 빠져나가서 겹치는 부분이 점점 줄어들게 됩니다.

진행률 0%  (10:01:00): 창 = [10:00:00~10:01:00] → 이전 윈도우 전체 겹침 → 가중치 1.0
진행률 30% (10:01:18): 이전 윈도우 70% 겹침       → 가중치 0.7
진행률 50% (10:01:30): 이전 윈도우 50% 겹침       → 가중치 0.5
진행률 100%(10:01:59): 이전 윈도우 0% 겹침         → 가중치 0.0

즉 시간이 갈수록 이전 윈도우의 영향력이 선형적으로 사라집니다. 그게 1 - 진행률 입니다.

장점으로는 메모리가 적고 경계 문제는 대두분 해결 됩니다. 보통 NGINX, 대형 서비스가 실제로 많이 쓰는 방법입니다.

단점으로는 근사치라 100% 정확하지는 않다는 것입니다.

 

Token Bucket (토큰 버킷)

이 알고리즘은 버킷에 토큰이 일정 속도로 채워지고, 요청은 토큰 1개를 소모하게 됩니다. 토큰이 없으면 거부하게 됩니다.

버킷 용량 = 5 (최대 저장)
채우는 속도 = 분당 5개 (12초에 1개)

- 요청 오면 토큰 1개 소모
- 안 쓰면 토큰이 쌓임(최대 5까지) → 잠깐 몰리는 burst 허용
- 비어 있으면 거부

 

조금 더 자세하게 본다면 비유부터 하자면 동전 저금통이라고 볼 수 있습니다. (위 예제를 좀 더 분석)

• 12초 마다 동전(토큰) 1개가 저금통에 자동으로 떨어집니다.
• 저금통은 최대 5개까지만 담깁니다. (넘치면 버려짐)
• 요청 1개 = 동전 1개 꺼내 쓰기 동전 옶으면 거부

안 쓰고 놔두면 동전이 5개까지 쌓이며 그러면 그 수간 5개를 한 번에 꺼내 쓸 수 있습니다. 이것이 brust입니다.

 

타임라인으로 보다면 다음과 같습니다.

시각      이벤트              토큰 잔량    판정
──────────────────────────────────────────────
10:00:00  시작 (가득)          5
          ...1분간 아무 요청 없음...  (충전돼도 5가 max라 그대로)
10:01:00  토큰 = 5 (꽉 참)     5

10:01:00  요청 1              5→4        통과
10:01:00  요청 2              4→3        통과
10:01:00  요청 3              3→2        통과   ← 같은 순간에
10:01:00  요청 4              2→1        통과      5개가
10:01:00  요청 5              1→0        통과   ← 한꺼번에 통과! (burst)
10:01:00  요청 6              0          거부 (토큰 없음)

10:01:12  (12초 경과, +1 충전) 0→1
10:01:12  요청 7              1→0        통과

10:01:00에 동시에 5개가 몰렸지만 다 통과했습니다. 평소에 안 써서 토큰 5개를 쌓여뒀기 때문이죠. 하지만 6번째는 즉시 거부 그리고 그 뒤론 12초에 1개씩만 통과하게 됩니다.

 

2개의 파라미터가 각각 뭘 정하는지 본다면

Token Bucket은 이 두 개로 움직입니다.

파라미터	의미	위 예시
충전 속도 (refill rate)	장기 평균 허용 속도	12초당 1개 = 분당 5개
버킷 용량 (capacity)	한 번에 몰아칠 수 있는 최대량 (burst 크기)	5개

• 충전 속도는 길게 보면 결국 이 속도로 수렴한다를 정하게 됩니다. 버스트로 5개 써버려도 그 후엔 12초당 1개 페이스로 강제됩니다.
• 용량은 얼마나 몰아칠 수 있나를 정하게 됩니다. 용량이 크면 큰 버스트 허용 작으면 빡빡하게 진행 됩니다.

 

장점은 현실 트래픽은 뚝뚝 끊겨서 요청이 몰려옵니다 예를 들어

• 사용자가 앱을 켜는 순간 API 5~6개 동시에 호출(프로필 + 알림 + 목록..)
• 평소엔 조용하다가 이 순간만 확 몰리게 됩니다.

초당 1개로 딱 자르는 (leaky bucket 식 - 밑에서 하게 됩니다) 방식이면 이 정상적인 앱 켜기도 막혀서 사용자 경험이 나빠집니다. Token Bucket은 평소 안 쓴 토큰을 쌓아뒀다가 이 순간 버트스를 허용하니 정상 사용자는 매끄럽게 쓰고, 지속적인 남용만 막습니다.

또 다른 장점으로는 상태가 토큰수/시각 2개뿐이라 가볍습니다.

 

사용되는 곳들은 bucket4j(자바), AWS API Gateway, Stripe 등. NGINX limit_req의 burst 옵션이 이 개념입니다.

 

Leaky Bucket (리키 버킷)

이 알고리즘은 요청을 큐에 넣고 일정 속도로만 처리하는 방법입니다. 큐가 다 차면 거부하게 됩니다

큐 처리 속도 = 12초에 1개 (분당 5개)
요청 → 큐에 쌓임 → 일정 속도로 빠져나감 → 큐 꽉 차면 거부

 

비유로 하면 바닥에 구멍 뚫린 양동이 입니다.

• 위에서 물(요청)이 아무 속도로나 쏟아져 들어오게 되빈다.
• 바닥 구멍으로는 항상 일정한 속도로만 물이 빠져나가게 됩니다(12초 1개)
• 양동이가 넘치면(큐가 꽉 차면) 그 물은 버려집니다.(거부)

들어오는 건 들쭉날쭉해도, 나가는 건 무조건 일정합니다.

 

타임라인으로 보면 (처리속도 12초당 1개, 큐 용량 5)

시각      들어옴   큐 상태          나감(처리)     비고
─────────────────────────────────────────────────────────
10:00:00  5개 몰림  [■■■■■] (5/5)    -            5개가 확 들어와 큐에 쌓임
10:00:00  +1개      큐 꽉참!          -            → 거부 (넘침)

10:00:12  -        [■■■■_] (4/5)    1개 처리   12초마다
10:00:24  -        [■■■__] (3/5)    1개 처리   1개씩
10:00:36  -        [■■___] (2/5)    1개 처리   일정하게
10:00:48  -        [■____] (1/5)    1개 처리   빠져나감
10:01:00  -        [_____] (0/5)    1개 처리 

10:00:00에 5개가 동시에 몰렸지만, 실제 처리는 12초 간격으로 하나씩 나가게 됩니다. 요청들은 큐에서 기다렸다가 순서대로 처리됩니다. 6번째는 큐가 꽉 차서 거부.

즉 출력이 완벽하게 평탄합니다. 아무리 몰려와도 뒷단 예를 들어 Spring/DB엔 항상 12초에 1개씩 전달됩니다.

 

Token Bucket과의 결정적 차이는

	Token Bucket	Leaky Bucket
양동이에 든 것	토큰(허가증)	요청(대기열)
요청 처리	토큰 있으면 즉시 통과, 없으면 거부	큐에 넣고 기다렸다가 일정속도로 처리
지연(대기)	없음 (통과 아니면 거부)	있음 (큐에서 대기)
출력 모양	버스트 가능 (쌓인 토큰만큼 순간 폭발)	항상 평탄 (일정 속도)
성격	버스트 허용	버스트 평탄화(흡수)

 

그림으로

입력:          ●●●●● (5개 동시에)

Token Bucket:  ●●●●● ────────    ← 쌓인 토큰으로 5개 즉시 통과, 그 후 거부/대기
Leaky Bucket:  ● ─ ● ─ ● ─ ● ─ ● ← 5개를 일정 간격으로 하나씩 흘려보냄

• Token: 지금 몰아쳐도 돼(토큰 있으면). 대신 순간 부하는 뒷단이 감당해야 함.
• Leaky: 몰아쳐도 뒷단엔 일정하게만 갈게. 대신 요청들은 기다려야 함(지연).

즉 Token은 응답이 빠른 대신 뒷단에 순간 부하, Leaky는 뒷단이 편한 대신 요청에 지연이 생기게 됩니다. 트레이드오프가 반대입니다.

 

NGINX limit_req에 매핑이 되게 됩니다. NGINX가 딱 이 Leaky Bucket 방식입니다.

limit_req_zone $binary_remote_addr zone=api:10m rate=5r/m;

location /api/ {
    limit_req zone=api burst=5;          # ← 큐 용량 = 5
}

• rate=5r/m = 구멍에서 빠지는 속도 (12초당 1개).
• burst=5 = 큐(양동이) 크기. 초과분을 5개까지 대기시킴.
• 큐 넘으면 → 503/429 거부.

 

nodelay 옵션의 의미:

limit_req zone=api burst=5 nodelay;

• nodelay 없으면: burst 요청을 큐에 넣고 천천히(12초 간격) 처리 → 요청이 지연됨(순수 leaky).
• nodelay 있으면: burst 한도 내 요청을 기다리게 하지 않고 즉시 통과시킴 → 이 순간만은 Token Bucket처럼 동작. (대신 토큰 자리는 여전히 rate 속도로 회복)

실무에서는 burst=N nodelay을 많이 쓴다고 합니다. 정상적인 순간 몰림은 즉시 통과시키되 지속적 남용은 막는 절충

 

Leaky를 쓰는 상황은

• 뒷단(DB, 외부 API)이 일정 속도 이상 못 버틸 때 - 무조건 평탄하게 흘려보내야 안전
• 트래픽 shaping(대역폭 제어, 결제/외부 연동 호출량 조절 등).
• 반대로 사용자 대면 API에서 응답 지연이 싫으면 Token Bucket(또는 nodelay)이 나음.

 

요약 비교표

알고리즘	정확도	메모리	버스트	구현 난이도
Fixed Window	낮음(경계문제)	적음	경계서 2배 샘	매우 쉬움
Sliding Log	최고	많음	없음	중간
Sliding Counter	높음	적음	거의 없음	중간
Token Bucket	높음	적음	허용	쉬움
Leaky Bucket	높음	적음	평탄화	중간

 

어디서 셀까

카운팅 로직을 어느 위치에 둘거냐를 말해볼 수 있습니다. 다음은 예시 입니다.

클라이언트 → [CDN/WAF] → [NGINX/게이트웨이] → [애플리케이션] → [DB]
              (엣지)        (네트워크, IP)       (유저/비즈니스)

• 엣지(CDN/WAF): 대규모 DDoS 흡수. Cloudflare 등.
• 게이트웨이/NGINX: IP 단위 거친 제한. 요청이 앱에 닿기 전 차단 → 제일 쌈.
• 애플리케이션: 유저, API키, 등급별 정밀 제한. 비즈니스 규칙 반영.

"앞단에서 거를수록 싸다"라고 말할 수 있습니다. 뒤로 갈수록 이미 자원을 쓴 뒤라 비싸게 됩니다. 즉, 위치에 따라 비용과 정밀도가 트레이드오프가 됩니다.

 

분산 환경의 어려움 (Redis)

인스턴스가 여러 개면 카운터를 공유해야 함 여기서 2가지 함정이 있습니다.

1. 원자성(atomicity) / race condition

동시에 두 요청이:
  read 카운터=4  →  둘 다 "4<5니까 OK"  →  둘 다 +1  →  실제 6 (한도 초과!)

read-modify-write가 쪼개지면 초과 통과하게 됩니다. Redis Lua 스크립트나 INCR(원자적 연산)로 "읽고-검사-증가"를 한 번에 처리해야 함. bucket4j-redis 같은 라이브러리가 이걸 해주게 됩니다.

 

 

2. 네트워크 비용

매 요청마다 Redis 왕복 → 지연 추가. 그래서 로컬 캐시 + 주기적 동기화 같은 최적화도 있습니다.

 

실무 (HTTP 규약)

• 초과 시 429 Too Many Requests 반환.
• 헤더로 상태 알려주기

RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 30          (초 후 리셋)
Retry-After: 30              (재시도까지 대기 초)

• key 전략: IP / 유저ID / API키 / (IP+엔드포인트) 조합. 로그인 API는 IP+계정 조합으로 brute-force 방어.
• Fail-open vs fail-closed: rate limiter(Redis)가 죽으면? 요청을 통과시킬지(open, 가용성 우선) 막을지(closed, 보안 우선) 미리 정해두기.