시스템 설계 인터뷰에서 Rate Limiter를 설계하는 방법?

Source: Dev.to

번역을 진행하려면 번역하고자 하는 본문 텍스트를 제공해 주세요. 텍스트를 주시면 요청하신 대로 한국어로 번역해 드리겠습니다.

레이트 리미터란?

레이트 리미터는 사용자가(또는 클라이언트가) 일정 시간 내에 수행할 수 있는 동작 수를 제한하는 시스템 구성 요소입니다.

예시

• API 게이트웨이 – 사용자당 분당 100개의 요청만 허용합니다.
• 로그인 시스템 – 10분 안에 실패한 로그인 시도를 5번만 허용합니다.
• 메시징 앱 – 사용자가 초당 20개 이상의 메시지를 보내는 것을 방지합니다.

사용자가 이러한 제한을 초과하면 시스템은 요청을 차단해야 하며(보통 HTTP 상태 코드 429 Too Many Requests를 반환합니다).

인터뷰에서의 핵심 Rate‑Limiter 시스템 요구사항

• 정확성 – 제한을 초과하는 요청은 거부됩니다.
• 효율성 – 초당 수백만 건의 요청을 낮은 지연 시간으로 처리합니다.
• 확장성 – 여러 서버에 걸친 분산 시스템에서 동작합니다.
• 공정성 – 버스트 트래픽이 허용되는 구멍을 방지합니다.
• 구성 가능성 – 사용자별, API별 등 제한을 쉽게 변경할 수 있습니다.

또한 명확히 할 질문을 할 수 있습니다. 예: “URL별 및 HTTP 메서드별로 제한이 필요합니까?”

속도 제한을 위한 일반적인 알고리즘

고정 윈도우 카운터

• 시간을 고정된 윈도우(예: 매분)로 나눕니다.
• 요청을 카운트합니다.
• 간단하지만 윈도우 경계에서 급증을 허용할 수 있습니다.

슬라이딩 윈도우 로그

• 요청의 타임스탬프를 로그(배열/큐)에 저장합니다.
• 오래된 타임스탬프를 제거합니다.
• 더 정확하지만 요청량에 비례하는 메모리가 필요합니다.

슬라이딩 윈도우 카운터

• 현재와 이전 윈도우에 대한 카운터를 사용하며, 시간에 따라 가중치를 부여합니다.
• 메모리 효율적이며 고정 윈도우보다 부드럽습니다.

토큰 버킷 / 리키 버킷

• 토큰은 고정된 비율로 추가되고, 요청은 토큰을 소비합니다.
• 트래픽을 부드럽게 하고, 실제 시스템에서 널리 사용됩니다.

인터뷰에서 레이트 리미터를 설계하는 방법?

1. 슬라이딩 윈도우 로그 (타임스탬프 배열)

이 방법은 각 요청에 대한 타임스탬프 큐를 유지합니다. 새로운 요청을 처리하기 전에:

1. 설정된 시간 창보다 오래된 타임스탬프를 제거합니다.
2. 큐 크기가 제한보다 작으면 요청을 허용하고 새로운 타임스탬프를 삽입합니다.
3. 그렇지 않으면 요청을 거부합니다.

Java 구현

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Simple sliding‑window log rate limiter.
 */
public class SlidingWindowLogRateLimiter {
    private final int maxRequests;
    private final long windowSizeInMillis;
    private final Deque<Long> timestamps = new ArrayDeque<>();

    public SlidingWindowLogRateLimiter(int maxRequests, int windowSizeInSeconds) {
        this.maxRequests = maxRequests;
        this.windowSizeInMillis = windowSizeInSeconds * 1000L;
    }

    /**
     * Returns true if the request is allowed, false otherwise.
     */
    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();

        // Discard timestamps that are outside the current window
        while (!timestamps.isEmpty() && now - timestamps.peekFirst() > windowSizeInMillis) {
            timestamps.pollFirst();
        }

        if (timestamps.size() < maxRequests) {
            timestamps.addLast(now);
            return true;   // request allowed
        }
        return false;      // request rejected
    }

    // Demo
    public static void main(String[] args) throws InterruptedException {
        SlidingWindowLogRateLimiter limiter = new SlidingWindowLogRateLimiter(5, 10); // 5 requests per 10 s
        for (int i = 1; i <= 7; i++) {
            System.out.println("Request " + i + ": " + (limiter.allowRequest() ? "allowed" : "rejected"));
            Thread.sleep(1500);
        }
    }
}

이 솔루션은 인터뷰에 최적이며, 간단하고 직관적이며 슬라이딩 윈도우 레이트 리미팅에 대한 이해를 보여줍니다.

2. 토큰 버킷

Token Bucket 알고리즘은 프로덕션에서 널리 사용됩니다 (예: API 게이트웨이, 마이크로서비스).

• 토큰은 고정된 비율로 추가됩니다.
• 각 요청은 하나의 토큰을 소모합니다.
• 토큰이 없으면 요청이 거부됩니다.

Java 구현

public class TokenBucket {
    private final int capacity;
    private final double refillRate; // tokens per second
    private double tokens;
    private long lastRefillTimestamp; // nanoseconds

    public TokenBucket(int capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    public synchronized boolean allowRequest() {
        long now = System.nanoTime();
        double tokensToAdd = ((now - lastRefillTimestamp) / 1e9) * refillRate;
        tokens = Math.min(capacity, tokens + tokensToAdd);
        lastRefillTimestamp = now;

        if (tokens >= 1) {
            tokens -= 1;
            return true;    // request allowed
        }
        return false;       // request rejected
    }

    // Demo
    public static void main(String[] args) throws InterruptedException {
        TokenBucket bucket = new TokenBucket(10, 5); // burst up to 10, 5 tokens/sec refill
        for (int i = 1; i <= 15; i++) {
            System.out.println("Request " + i + ": " + (bucket.allowRe

quest() ? "allowed" : "rejected"));
            Thread.sleep(200);
        }
    }
}

이 구현은 thread‑safe하며 동시 부하에서도 잘 작동합니다.

인터뷰 전략 (Java 개발자를 위한)

When asked “How would you design a rate limiter?” you can progress through these points:

1. Fixed‑Window Counter – 설명하기 쉽지만, 경계 상황 문제가 있습니다.
2. Sliding‑Window Log – 타임스탬프를 저장하기 위해 Deque<Long>를 사용합니다.
3. Token Bucket – 버스트 처리에 적합한 프로덕션 급 솔루션입니다.
4. Distributed Rate Limiting – Redis 기반 카운터 또는 API‑gateway 기능(예: Nginx, Envoy)을 언급합니다.

알고리즘에 대한 폭넓은 지식(폭)과 실제 Java 코드 구현 능력(깊이)을 모두 다루면 강력한 시스템 설계 역량을 보여줄 수 있습니다.

Source:

시스템 디자인 인터뷰 준비 자료

ByteByteGo

• 웹사이트: https://bytebytego.com/?fpr=javarevisited
• 시스템 디자인 책과 포괄적인 준비를 위한 플랫폼을 제공합니다.

Codemia.io

• 웹사이트: https://codemia.io/?via=javarevisited
• 120개 이상의 시스템 디자인 문제(많은 부분이 무료)와 편집 솔루션 및 연습 도구를 제공합니다.

Exponent

• 웹사이트: https://bit.ly/3cNF0vw
• 주요 기술 기업을 위한 전문 코스, 모의 인터뷰, 시스템 디자인 자료를 제공합니다.

일반적인 준비 조합

1. ByteByteGo – 이론 및 기본 개념.
2. Codemia – 실전 연습.
3. Exponent – 모의 인터뷰 및 인터뷰 맞춤 코칭.

최종 생각

Rate limiting은 알고리즘 지식과 시스템 설계 직관을 모두 테스트하는 인터뷰 질문 중 하나입니다.

• 깔끔하고 인터뷰에 바로 사용할 수 있는 답변을 위해서는 Sliding Window Log 접근법(예: Java의 Deque)을 사용하세요.
• 프로덕션 수준의 전문성을 보여주려면 Token Bucket 알고리즘도 논의하세요.

이렇게 하면 실용적인 코딩 측면과 더 넓은 시스템 설계 관점을 하나의 답변에 모두 포함할 수 있습니다.