💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

원문 렌더가 준비되기 전까지 텍스트 가이드로 표시합니다.

TL;DR

- **Rate Limiting은 필수**: DDoS 방어, 공정성, 비용 통제

- **5대 알고리즘**: Fixed Window, Sliding Window Log, Sliding Window Counter, Token Bucket, Leaky Bucket

- **Token Bucket이 가장 인기**: Burst 허용 + 단순함. Stripe, GitHub 사용

- **분산 환경 = Redis**: 원자적 INCR + EXPIRE

- **HTTP 표준**: 429 + Retry-After + RateLimit 헤더

- **사용자 식별**: API key > User ID > IP (마지막 수단)

1. Rate Limiting이 왜 필요한가?

1.1 보호하는 것들

**1. DDoS / Brute Force**

- 악의적 사용자가 초당 10만 요청

- 서버 다운, 다른 사용자 영향

**2. 공정성**

- 한 사용자가 자원 독점 X

- 모든 사용자에게 합리적 응답 시간

**3. 비용 통제**

- API 호출 = 비용 (DB, 외부 API)

- 폭주 비용 제한

**4. 신뢰할 수 없는 클라이언트**

- 버그 있는 클라이언트가 무한 루프

- 잘못된 retry 로직

1.2 Rate Limit 없이 일어나는 일

[악의적 사용자]

↓ 초당 10,000 요청

[당신의 API]

↓

[DB 다운]

↓

[모든 사용자 영향]

**하루치 비용**: 1억 API 호출 × $0.0001 = **$10,000** 손실.

2. 5대 알고리즘

2.1 Fixed Window Counter

가장 단순. 시간 윈도우(예: 1분)별로 카운트.

def is_allowed(user_id):

window = current_minute()

key = f"{user_id}:{window}"

count = redis.incr(key)

if count == 1:

redis.expire(key, 60)

return count <= LIMIT

**예**: 분당 100 요청 한도.

**장점**:

- 매우 단순

- 메모리 효율 (1 카운터/사용자/분)

- Redis로 쉽게 구현

**단점**:

- **Boundary 문제**: 윈도우 경계에서 2배 트래픽 가능

- 12:00:59에 100 요청

- 12:01:00에 100 요청

- 1초 사이에 200 요청 통과!

2.2 Sliding Window Log

각 요청의 타임스탬프를 기록. 윈도우 안의 요청 수 계산.

def is_allowed(user_id):

now = time.time()

key = f"requests:{user_id}"

윈도우 밖 요청 제거

redis.zremrangebyscore(key, 0, now - 60)

현재 카운트

count = redis.zcard(key)

if count < LIMIT:

redis.zadd(key, {str(now): now})

redis.expire(key, 60)

return True

return False

**장점**:

- **정확한 카운팅**

- Boundary 문제 없음

**단점**:

- **메모리 비쌈**: 모든 요청 타임스탬프 저장

- 100,000 요청 = 100,000 항목

2.3 Sliding Window Counter

Fixed Window의 진화. 이전 윈도우 비례 합산.

def is_allowed(user_id):

now = time.time()

current_window = int(now // 60)

previous_window = current_window - 1

current_count = redis.get(f"{user_id}:{current_window}") or 0

previous_count = redis.get(f"{user_id}:{previous_window}") or 0

이전 윈도우의 비율 계산

elapsed_in_current = now - (current_window * 60)

weight = (60 - elapsed_in_current) / 60

estimated = (previous_count * weight) + current_count

if estimated < LIMIT:

redis.incr(f"{user_id}:{current_window}")

return True

return False

**장점**:

- 메모리 효율 (Fixed Window와 같음)

- Boundary 문제 거의 해결

- **Cloudflare가 사용**

**단점**:

- 약간 부정확 (선형 분포 가정)

2.4 Token Bucket — 가장 인기

**개념**: 버킷에 토큰이 일정 속도로 충전. 요청 시 토큰 소비.

def is_allowed(user_id):

key = f"bucket:{user_id}"

bucket = redis.hgetall(key)

now = time.time()

last_refill = float(bucket.get('last_refill', now))

tokens = float(bucket.get('tokens', BUCKET_SIZE))

토큰 충전

elapsed = now - last_refill

tokens = min(BUCKET_SIZE, tokens + elapsed * REFILL_RATE)

if tokens >= 1:

tokens -= 1

redis.hset(key, mapping={

'tokens': tokens,

'last_refill': now

})

return True

return False

**예**: 버킷 크기 100, 초당 10 토큰 충전.

- 평소: 초당 10 요청

- Burst: 한 번에 100 요청 (버킷 가득)

**장점**:

- **Burst 허용** — 사용자 친화적

- 평균 속도 제어

- 단순

**단점**:

- 메모리 (버킷당 2 필드)

**사용**: Stripe, GitHub, AWS API Gateway

2.5 Leaky Bucket

큐 형태. 일정 속도로 처리.

[요청] → [큐] → [일정 속도로 처리]

큐 가득 차면 거부

**장점**:

- **출력 속도 일정** (smooth traffic)

- 트래픽 shaping에 적합

**단점**:

- Burst 못 함

- 큐 메모리 필요

**사용**: 네트워크 트래픽 제어, ISP

2.6 비교표

| 알고리즘 | Burst | 정확성 | 메모리 | 복잡도 |

|---|---|---|---|---|

| **Sliding Window Log** | ❌ | **완벽** | 많음 | 중간 |

| **Sliding Window Counter** | ❌ | 좋음 | 적음 | 중간 |

| **Token Bucket** | **✅** | 좋음 | 적음 | 단순 |

| **Leaky Bucket** | ❌ | 좋음 | 보통 | 중간 |

**추천**: **Token Bucket** — 대부분의 경우.

3. 분산 환경 구현

3.1 단일 서버 vs 분산

**단일 서버**: 메모리 카운터로 충분.

**분산 환경**:

[Server 1] [Server 2] [Server 3]

↓ ↓ ↓

각 서버가 자기 카운터?

→ 사용자가 3대에 분산되면 3배 통과!

**해결**: **중앙 카운터** (Redis).

3.2 Redis 기반 Token Bucket

LUA_SCRIPT = """

local key = KEYS[1]

local capacity = tonumber(ARGV[1])

local refill_rate = tonumber(ARGV[2])

local now = tonumber(ARGV[3])

local cost = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')

local tokens = tonumber(bucket[1]) or capacity

local last_refill = tonumber(bucket[2]) or now

-- 충전

local elapsed = now - last_refill

tokens = math.min(capacity, tokens + elapsed * refill_rate)

if tokens >= cost then

tokens = tokens - cost

redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)

redis.call('EXPIRE', key, 3600)

return 1

else

return 0

end

"""

def is_allowed(user_id):

return redis.eval(

LUA_SCRIPT,

f"bucket:{user_id}",

100, # capacity

10, # refill rate

time.time(),

1 # cost

)

**왜 Lua?**: **원자성 보장**. Redis의 multi-step 작업이 한 번에 실행.

3.3 분산 환경의 함정

**1. Race Condition**

- Lua 스크립트로 해결 (원자적)

**2. Redis 다운**

- 옵션 1: Fail open (모두 통과) — 가용성 우선

- 옵션 2: Fail closed (모두 거부) — 보안 우선

- 옵션 3: Local fallback — 로컬 카운터로 대체

**3. Latency**

- 매 요청마다 Redis 호출 = 1ms+ 추가

- 해결: 로컬 캐싱 + 주기적 동기화

3.4 Sliding Window 분산 구현

def is_allowed(user_id):

now = time.time()

window_start = now - 60

pipe = redis.pipeline()

pipe.zremrangebyscore(f"requests:{user_id}", 0, window_start)

pipe.zadd(f"requests:{user_id}", {str(now): now})

pipe.zcard(f"requests:{user_id}")

pipe.expire(f"requests:{user_id}", 60)

_, _, count, _ = pipe.execute()

return count <= LIMIT

4. HTTP 표준

4.1 429 Too Many Requests

HTTP/1.1 429 Too Many Requests

Content-Type: application/json

Retry-After: 60

RateLimit-Limit: 100

RateLimit-Remaining: 0

RateLimit-Reset: 1681545660

{

"error": "rate_limit_exceeded",

"message": "Too many requests. Try again in 60 seconds.",

"retry_after": 60

}

4.2 RateLimit 헤더 (RFC Draft)

**Standard headers** (IETF draft):

RateLimit-Limit: 100 # 윈도우 한도

RateLimit-Remaining: 42 # 남은 요청

RateLimit-Reset: 1681545660 # Reset 시간 (Unix)

**Retry-After**:

Retry-After: 60 # 초

Retry-After: Wed, 21 Oct 2025 07:28:00 GMT # 절대 시간

4.3 클라이언트의 대응

from time import sleep

def call_api(url):

while True:

response = requests.get(url)

if response.status_code == 429:

retry_after = int(response.headers.get('Retry-After', 60))

print(f"Rate limited. Waiting {retry_after}s...")

sleep(retry_after)

continue

return response

예방적 - 남은 요청 확인

def call_api_smart(url):

response = requests.get(url)

remaining = int(response.headers.get('RateLimit-Remaining', 100))

if remaining < 10:

print("Slowing down...")

sleep(1)

return response

5. 사용자 식별

5.1 식별 방법

| 방법 | 신뢰성 | 사용 |

|---|---|---|

| **API Key** | 높음 | 인증된 API |

| **User ID** | 높음 | 로그인된 사용자 |

| **OAuth Token** | 높음 | 외부 통합 |

| **IP Address** | 낮음 | 익명 사용자 |

5.2 IP 기반의 함정

**1. NAT 뒤 사용자**

- 학교, 회사 → 수천 사용자가 같은 IP

- 한 명이 한도 채우면 모두 차단

**2. IPv6**

- IP 공간 거대 → 공격자가 무한 IP

- /64 prefix로 묶기

**3. 프록시/VPN**

- 우회 가능

**4. CDN 뒤**

- `X-Forwarded-For` 헤더 신뢰?

- 위조 가능

def get_client_ip(request):

CDN 뒤에 있을 때

forwarded = request.headers.get('X-Forwarded-For')

if forwarded:

첫 IP가 실제 클라이언트

return forwarded.split(',')[0].strip()

return request.remote_addr

5.3 계층적 Rate Limit

**여러 차원에서 동시에**:

- **글로벌**: 전체 시스템 (DDoS 방어)

- **사용자**: 인증된 사용자 (1000 RPM)

- **IP**: 익명 사용자 (100 RPM)

- **endpoint**: 특정 API (`/api/expensive` 10 RPM)

def check_all_limits(user_id, ip, endpoint):

return (

check_global_limit() and

check_user_limit(user_id) and

check_ip_limit(ip) and

check_endpoint_limit(user_id, endpoint)

)

6. 다층 한도 (Tiered Limits)

6.1 사용자 등급별

Free tier: 100 RPM, 10K req/day

Pro tier: 1000 RPM, 100K req/day

Enterprise: 10000 RPM, unlimited

TIER_LIMITS = {

'free': {'rpm': 100, 'daily': 10000},

'pro': {'rpm': 1000, 'daily': 100000},

'enterprise': {'rpm': 10000, 'daily': float('inf')}

}

def get_limit(user):

return TIER_LIMITS[user.tier]

6.2 비용 기반

**모든 요청이 같지 않음**:

- `GET /user` = 1 token

- `POST /user/search` = 5 tokens

- `POST /image/analyze` = 50 tokens

**Token Bucket과 결합**: cost 매개변수 활용.

6.3 시간대별

피크 시간에 더 엄격:

def get_limit():

hour = datetime.now().hour

if 9 <= hour <= 18: # 비즈니스 시간

return STRICT_LIMIT

return RELAXED_LIMIT

7. 실전 — Stripe의 Rate Limiting

7.1 Stripe의 정책

- **읽기**: 100 requests/sec

- **쓰기**: 100 requests/sec

- **separate quotas** for read/write

- **Test mode**: 25/sec

- **Live mode**: 100/sec

7.2 Stripe의 응답

HTTP/1.1 429 Too Many Requests

Content-Type: application/json

{

"error": {

"type": "rate_limit_error",

"message": "Too many requests hit the API too quickly. ..."

}

7.3 Idempotency Key

POST /v1/charges

Idempotency-Key: my-unique-key-123

**효과**: 재시도 안전. 같은 key의 요청은 같은 결과 반환.

7.4 권장 retry 패턴 (Exponential Backoff)

def stripe_request(method, url, **kwargs):

max_retries = 3

base_delay = 1

for attempt in range(max_retries):

response = requests.request(method, url, **kwargs)

if response.status_code != 429:

return response

Exponential backoff with jitter

delay = base_delay * (2 ** attempt) + random.uniform(0, 1)

time.sleep(delay)

raise Exception("Max retries exceeded")

**Jitter 중요**: 모든 클라이언트가 동시에 재시도하면 thundering herd. Random jitter로 분산.

8. GitHub의 Rate Limiting

8.1 정책

- **인증된 사용자**: 5,000 requests/hour

- **인증 안 됨**: 60 requests/hour

- **GraphQL**: 5,000 points/hour (각 쿼리가 다른 비용)

- **검색 API**: 30 requests/min

8.2 GraphQL의 cost 시스템

query {

repository(owner: "facebook", name: "react") {

issues(first: 100) {

nodes {

title

comments(first: 100) {

nodes {

author { login }

}

이 쿼리의 cost = `1 + (100 issues) + (100 * 100 comments) = 10,001 points`

GitHub은 단순 횟수가 아니라 **실제 데이터 양**에 비례한 비용.

8.3 응답 헤더

X-RateLimit-Limit: 5000

X-RateLimit-Remaining: 4995

X-RateLimit-Reset: 1681545660

X-RateLimit-Used: 5

X-RateLimit-Resource: core

9. 우회 방지

9.1 흔한 우회 시도

**1. IP 바꾸기**

- VPN, Tor, Proxy

- 해결: User ID 기반 (인증 강제)

**2. 여러 계정 만들기**

- 무료 가입 폭주

- 해결: 이메일 검증, 캡차, fingerprinting

**3. Distributed attack**

- 보트넷에서 분산

- 해결: 글로벌 rate limit, 패턴 탐지

**4. Header 조작**

- `X-Forwarded-For` 위조

- 해결: 신뢰할 수 있는 헤더만, CDN 사용

9.2 다층 방어

[CloudFlare DDoS 보호]

↓

[L7 WAF (rate limiting)]

↓

[Application rate limit]

↓

[DB connection limit]

각 레이어에서 다른 종류의 공격 방어.

9.3 이상 탐지

**ML 기반**:

- 정상 패턴 학습

- 이상 패턴 실시간 차단

**규칙 기반**:

- 같은 IP에서 100 다른 user로 로그인 시도

- 같은 user agent + 다른 endpoint 폭주

- 비정상 요청 분포

10. 모니터링과 튜닝

10.1 핵심 메트릭

- Total requests

- Rate limited requests (429s)

- Per-user rate limit hits

- Per-endpoint rate limit hits

- Top rate limited users

- Rate limit hit rate (%)

**대시보드**: Grafana, Datadog.

10.2 한도 튜닝

**너무 엄격**:

- 정상 사용자도 차단

- 사용자 불만

- → 한도 완화

**너무 느슨**:

- 악의적 사용자가 시스템 압박

- 비용 폭증

- → 한도 강화

**원칙**: **사용자 95%가 정상 사용 가능** + **abuse 패턴 차단**.

10.3 통보

사용 80% → 알림

사용 100% → 차단

지속 abuse → 계정 일시 정지

**사용자에게 미리 알림**:

RateLimit-Remaining: 50

API 클라이언트가 자동으로 속도 조절.

10.4 화이트리스트

- 내부 서비스

- 신뢰할 수 있는 파트너

- VIP 고객

WHITELIST = {'192.168.1.0/24', 'partner-api-key-xyz'}

def is_whitelisted(user_id, ip):

return user_id in WHITELIST or ip in WHITELIST_IPS

퀴즈

**답**: (1) **Burst 허용** — 사용자가 가끔 많은 요청을 빠르게 보낼 수 있어 사용자 친화적, (2) **평균 속도 제어** — 장기적으로 충전 속도를 넘지 않음, (3) **단순한 구현** — 2개 변수(tokens, last_refill)만 필요, (4) **메모리 효율** — 사용자당 1 버킷, (5) **유연한 cost** — 비싼 요청은 더 많은 토큰. Stripe, GitHub, AWS API Gateway 모두 사용. **Leaky Bucket과 차이**: Token Bucket은 burst 허용, Leaky Bucket은 출력 속도 일정.

**답**: 윈도우 경계에서 **2배 트래픽이 통과**할 수 있습니다. 분당 100 요청 한도 시: 12:00:59에 100 요청 + 12:01:00에 100 요청 = **1초 사이에 200 요청 통과**. 정확히 boundary를 노린 공격에 취약. **해결책**: (1) **Sliding Window Log** — 정확하지만 메모리 비쌈, (2) **Sliding Window Counter** — 이전 윈도우 비례 합산, 메모리 효율 (Cloudflare 사용), (3) **Token Bucket** — 시간 기반 충전이라 boundary 문제 없음.

**답**: **Redis + Lua 스크립트**가 표준입니다. 각 서버가 자기 카운터를 가지면 사용자가 3대 서버에 분산될 때 3배 통과 가능. **중앙 카운터(Redis)**가 필요하지만 race condition을 피해야 함. **Lua 스크립트**로 multi-step 작업을 원자적으로 실행. Redis 다운 시 fail open(가용성 우선) vs fail closed(보안 우선) 결정 필요. Latency 절약을 위해 로컬 캐싱 + 주기적 동기화도 사용.

**답**: (1) **NAT 뒤 사용자** — 학교/회사의 수천 사용자가 같은 IP, 한 명이 한도 채우면 모두 차단, (2) **IPv6** — IP 공간 거대해 공격자가 무한 IP, /64 prefix로 묶어야 함, (3) **VPN/Proxy** — 우회 가능, (4) **CDN 뒤** — X-Forwarded-For 위조 가능. **해결**: 가능하면 **인증 강제**해서 user ID 기반으로 전환. 익명 API는 IP + 캡차 + 패턴 탐지 조합. 절대 IP만 신뢰하지 말 것.

**답**: **Thundering herd 방지**. Rate limited 후 모든 클라이언트가 정확히 같은 시간(예: 60초)에 재시도하면 → 동시에 폭주 → 다시 429 → 무한 루프. **Jitter**: 재시도 시간에 random 추가 (예: `delay + random(0, 1)`). 클라이언트들이 분산되어 폭주 방지. AWS, Google이 권장하는 패턴. 모든 retry 로직에 jitter 필수. 단순 exponential backoff는 충분하지 않습니다.

참고 자료

- [Stripe Rate Limiting](https://stripe.com/blog/rate-limiters) — 우수한 글

- [GitHub API Rate Limits](https://docs.github.com/en/rest/overview/resources-in-the-rest-api#rate-limiting)

- [System Design Interview - Rate Limiter](https://github.com/donnemartin/system-design-primer)

- [IETF RateLimit Headers Draft](https://datatracker.ietf.org/doc/draft-ietf-httpapi-ratelimit-headers/)

- [Cloudflare Rate Limiting](https://developers.cloudflare.com/waf/rate-limiting-rules/)

- [Redis Rate Limiting Patterns](https://redis.io/glossary/rate-limiting/)

- [Token Bucket Algorithm](https://en.wikipedia.org/wiki/Token_bucket)

- [Leaky Bucket Algorithm](https://en.wikipedia.org/wiki/Leaky_bucket)

- [AWS API Gateway Throttling](https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html)

- [Designing Data-Intensive Applications](https://dataintensive.net/) — Martin Kleppmann

- [Aperture](https://github.com/fluxninja/aperture) — Open source rate limiting