API Rate Limiter

문제 설명

API Rate Limiting을 위한 토큰 버킷(Token Bucket) 알고리즘을 구현하세요.

토큰 버킷 알고리즘

• 버킷에 일정 용량의 토큰 보관
• 일정 속도로 토큰 보충
• 요청 시 토큰 소비, 토큰 없으면 거부

요구사항

• 사용자별 독립적인 버킷
• 분산 환경 고려 (Redis 기반)
• 버킷 용량, 보충 속도 설정 가능
• 남은 토큰 수, 리셋 시간 반환

인터페이스

class RateLimiter:
    def __init__(capacity, refill_rate):
        # capacity: 최대 토큰 수
        # refill_rate: 초당 보충 토큰 수

    def allow(user_id) -> RateLimitResult:
        # allowed: bool
        # remaining: int (남은 토큰)
        # reset_at: timestamp (다음 토큰 보충 시간)

평가 기준

• 알고리즘 정확성
• 동시성 처리
• 시간 계산 정밀도