API Rate Limiting 완전 가이드 2025: Token Bucket, Sliding Window, 분산 환경, Stripe/GitHub 사례

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 비교표

추천: 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,
        1,
        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 클라이언트의 대응

import requests
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 식별 방법

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)

import time
import random

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

퀴즈

참고 자료

• Stripe Rate Limiting — 우수한 글
• GitHub API Rate Limits
• System Design Interview - Rate Limiter
• IETF RateLimit Headers Draft
• Cloudflare Rate Limiting
• Redis Rate Limiting Patterns
• Token Bucket Algorithm
• Leaky Bucket Algorithm
• AWS API Gateway Throttling
• Designing Data-Intensive Applications — Martin Kleppmann
• Aperture — Open source rate limiting