백엔드 프레임워크에서의 속도 제한 - 토큰 버킷 vs. 슬라이딩 윈도우

소개

백엔드 개발의 복잡한 세계에서 다양한 부하 조건 하에서 시스템 안정성과 성능을 유지하는 것은 무엇보다 중요합니다. 이를 달성하는 가장 효과적인 전략 중 하나는 속도 제한(rate limiting)입니다. 이는 클라이언트가 특정 기간 내에 API 또는 서비스에 대해 만들 수 있는 요청 빈도를 제어하는 메커니즘입니다. 적절한 속도 제한 없이는 서비스 거부(DoS)와 같은 악의적인 공격이나 합법적인 트래픽의 의도치 않은 급증조차도 서비스 품질을 빠르게 저하시키고, 리소스를 고갈시키며, 다운타임으로 이어질 수 있습니다. 이 글에서는 백엔드 프레임워크에서 속도 제한을 구현하기 위한 두 가지 기본 알고리즘인 토큰 버킷(Token Bucket)과 슬라이딩 윈도우(Sliding Window)를 살펴보겠습니다. 각 알고리즘의 핵심 원리, 실제 구현 및 적합한 사용 사례를 자세히 살펴보고, 각각이 어떻게 복원력 있고 확장 가능한 백엔드 시스템 구축에 기여하는지 명확하게 이해할 수 있도록 하겠습니다.

속도 제한의 핵심 개념

알고리즘에 대해 자세히 알아보기 전에, 속도 제한을 이해하는 데 중요한 몇 가지 주요 용어를 정의해 보겠습니다.

• 요청 속도(Request Rate): 단위 시간당 처리되는 요청 수(예: 초당 요청 수, 분당 요청 수).
• 스로틀(Throttle): 리소스 고갈 또는 시스템 과부하를 방지하기 위해 의도적으로 요청 속도를 제한합니다.
• 할당량(Quota): 특정 기간 동안 클라이언트 또는 서비스에 허용되는 최대 요청 수.
• 버스트(Burst): 평균을 초과하는 갑작스럽고 짧은 기간의 요청 속도 증가.
• 세분성(Granularity): 속도 제한이 적용되는 가장 세부적인 수준(예: 사용자별, IP 주소별, API 엔드포인트별).
• 분산 속도 제한(Distributed Rate Limiting): 서비스의 여러 인스턴스에 걸쳐 적용되는 속도 제한으로, 정확한 시행을 위해 공유 상태가 필요합니다.

토큰 버킷: 속도 제한을 위한 유연한 접근 방식

토큰 버킷 알고리즘은 속도 제한을 위한 직관적이고 널리 사용되는 방법으로, 트래픽 버스트를 우아하게 처리하는 능력으로 유명합니다.

원리

고정 용량의 버킷을 상상해 보세요. 토큰이 일정한 속도로 이 버킷에 지속적으로 추가됩니다. 클라이언트가 요청할 때마다 버킷에서 토큰을 가져오려고 시도합니다. 토큰이 사용 가능하면 요청이 처리되고 토큰이 제거됩니다. 버킷이 비어 있으면 요청이 거부되거나 대기열에 추가됩니다. 버킷의 용량은 허용되는 최대 버스트를 나타내고, 토큰이 추가되는 속도는 장기적인 평균 요청 속도를 결정합니다.

구현

토큰 버킷을 구현하려면 일반적으로 다음이 필요합니다.

1. 버킷 용량: 버킷이 담을 수 있는 최대 토큰 수.
2. 토큰 생성 속도: 초당 버킷에 새 토큰이 추가되는 빈도(예: 초당 1개 토큰).
3. 현재 토큰 수: 현재 버킷에 있는 토큰 수.
4. 마지막 채우기 시간: 토큰이 추가되거나 확인된 마지막 타임스탬프.

Python 유사 구문의 의사 코드 예시를 통해 설명해 보겠습니다.

import time

class TokenBucket:
    def __init__(self, capacity, fill_rate_tokens_per_second):
        self.capacity = float(capacity)
        self.fill_rate = float(fill_rate_tokens_per_second)
        self.tokens = float(capacity)  # 가득 찬 버킷으로 시작
        self.last_fill_time = time.time()

    def allow_request(self, tokens_needed=1):
        now = time.time()
        # 경과 시간 및 채우기 속도에 따라 토큰 추가
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last_fill_time) * self.fill_rate)
        self.last_fill_time = now

        if self.tokens >= tokens_needed:
            self.tokens -= tokens_needed
            return True
        else:
            return False

# 백엔드 프레임워크 (예: Flask 데코레이터) 에서의 예제 사용
# 이는 간단한 예제이며, 실제 구현에서는 클라이언트 식별 (IP, 사용자 ID)
# 및 공유 상태를 위한 분산 저장소 (Redis)가 필요할 수 있습니다.

# 다중 인스턴스 시나리오에서는 'bucket_for_client'가
# Redis와 같은 분산 캐시에서 검색되어 모든 인스턴스가 동일한 상태를 공유하도록 보장해야 합니다.
# 단순화를 위해 여기서는 로컬 딕셔너리를 사용합니다.
client_buckets = {}

def rate_limit_token_bucket(capacity, fill_rate):
    def decorator(f):
        def wrapper(*args, **kwargs):
            # 실제 API에서는 client_id가 request 헤더 또는 IP에서 가져옵니다.
            client_id = "default_client" # 시연 목적

            if client_id not in client_buckets:
                client_buckets[client_id] = TokenBucket(capacity, fill_rate)

            bucket = client_buckets[client_id]

            if bucket.allow_request():
                return f(*args, **kwargs)
            else:
                return "속도 제한 초과. 나중에 다시 시도하세요.", 429
        return wrapper
    return decorator

# @app.route('/api/data')
# @rate_limit_token_bucket(capacity=10, fill_rate=1) # 10개 요청 버스트, 초당 1개 요청 평균
# def get_data():
#     return "데이터를 성공적으로 검색했습니다!"

적용 시나리오

토큰 버킷은 다음과 같은 경우에 탁월합니다.

• 버스트 처리: 토큰을 저장하는 능력 덕분에 클라이언트가 평균 속도보다 빠르게 요청할 수 있으며, 이는 사용자 중심 상호 작용에서 일반적입니다.
• API 게이트웨이: 백엔드 서비스에 대한 외부 클라이언트의 요청 제한.
• 특정 사용자 또는 엔드포인트 스로틀링: 유연한 할당량 관리 제공.

슬라이딩 윈도우 로그: 정확성과 공정성

슬라이딩 윈도우 로그(Sliding Window Log) 알고리즘은 매우 정확하고 공정한 속도 제한 접근 방식을 제공하며, 버스트가 윈도우 경계를 넘어 "숨겨지는" 것을 방지합니다.

원리

토큰 버킷과 달리 슬라이딩 윈도우 로그는 각 성공적인 요청에 대한 타임스탬프 로그를 유지합니다. 새 요청이 도착하면 알고리즘은 현재 시간에서 윈도우 기간을 뺀 시간보다 오래된 모든 타임스탬프를 로그에서 삭제합니다. 로그에 남아 있는 타임스탬프 수가 허용 한도보다 적으면 요청이 허용되고 해당 타임스탬프가 로그에 추가됩니다. 그렇지 않으면 요청이 거부됩니다.

구현

슬라이딩 윈도우 로그의 핵심은 타임스탬프의 정렬된 목록입니다.

import time
from collections import deque

class SlidingWindowLog:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window_seconds = window_seconds
        # Deque는 양쪽 끝에서 추가/제거에 효율적입니다.
        self.requests = deque()

    def allow_request(self):
        now = time.time()
        # 윈도우보다 오래된 타임스탬프 제거
        while self.requests and self.requests[0] <= now - self.window_seconds:
            self.requests.popleft()

        if len(self.requests) < self.limit:
            self.requests.append(now)
            return True
        else:
            return False

# 백엔드 프레임워크 (예: Flask 데코레이터) 에서의 예제 사용
client_request_logs = {}

def rate_limit_sliding_window_log(limit, window_seconds):
    def decorator(f):
        def wrapper(*args, **kwargs):
            client_id = "default_client" # 실제 앱에서는 request 헤더/IP에서 가져옴

            if client_id not in client_request_logs:
                client_request_logs[client_id] = SlidingWindowLog(limit, window_seconds)

            window_log = client_request_logs[client_id]

            if window_log.allow_request():
                return f(*args, **kwargs)
            else:
                return "속도 제한 초과. 나중에 다시 시도하세요.", 429
        return wrapper
    return decorator

# @app.route('/api/report')
# @rate_limit_sliding_window_log(limit=5, window_seconds=60) # 분당 5회 요청
# def get_report():
#     return "보고서를 성공적으로 생성했습니다!"

정확하지만, deque는 트래픽이 많을 때 커질 수 있으며, 메모리를 더 많이 소비하고 리스트 작업으로 인해 성능에 영향을 미칠 수 있습니다. 분산 시스템의 경우, Redis에서 이러한 로그를 저장하는 것이 일반적인 접근 방식이며, ZREMRANGEBYSCORE를 사용하여 오래된 타임스탬프를 효율적으로 정리할 수 있습니다.

적용 시나리오

슬라이딩 윈도우 로그는 다음과 같은 경우에 적합합니다.

• 엄격한 속도 제한: 정의된 기간 동안 정확한 속도를 시행하는 것이 중요할 때, 윈도우 경계에 걸친 "부정 행위"를 방지합니다.
• 결제 및 사용량 추적: 결제를 위해 API 사용량을 정확하게 추적합니다.
• 보안 애플리케이션: 공격을 나타낼 수 있는 비정상적인 요청 패턴 감지.

토큰 버킷과 슬라이딩 윈도우 로그 비교

결론

토큰 버킷과 슬라이딩 윈도우 로그 모두 견고한 속도 제한 구현 알고리즘이며, 각각 장점과 단점이 있습니다. 토큰 버킷은 유연성과 뛰어난 버스트 처리를 제공하여, 간헐적인 트래픽 급증이 예상되고 심각한 영향 없이 수용되어야 하는 일반적인 API 사용 사례에 이상적입니다. 반면에 슬라이딩 윈도우 로그는 연속적인 윈도우 전반에 걸쳐 정의된 속도를 엄격하게 준수함으로써 우수한 정확성과 공정성을 제공하여, 정확한 사용량 추적과 엄격한 시행이 요구되는 시나리오에 더 적합합니다. 올바른 알고리즘을 선택하는 것은 백엔드 서비스의 특정 요구 사항에 따라 달라지며, 버스트 허용 또는 엄격한 속도 정확성 중 하나를 우선시해야 합니다. 잘 설계된 속도 제한 전략은 종종 이러한 기법과 다른 기법들을 조합하여 복원력 있고 성능이 뛰어난 시스템을 구축합니다.