←

Rate Limiter (OO)

LLD

Understand it step by step (한국어로 이해 → 영어로 말하기)

API 요청을 제한하는 Rate Limiter를 설계합니다. 클라이언트(예: 사용자 ID)별로 일정 시간 안에 허용되는 요청 수를 제한하고, 한도를 넘으면 요청을 거절합니다. 핵심 요구사항은 (1) 여러 알고리즘(토큰 버킷, 고정 윈도우)을 교체 가능하게 지원, (2) 클라이언트별로 따로 카운트, (3) 멀티스레드 환경에서 안전하게 동작입니다.
  1. 1

    먼저 요구사항과 핵심 동작을 정합니다. Rate Limiter는 '이 요청을 허용할까?'라는 질문에 true/false로 답하는 것이 핵심입니다. 그래서 가장 기본이 되는 인터페이스 RateLimiter를 만들고, allow(clientId) 메서드 하나로 시작합니다.

    ⚖️ Trade-off: 메서드를 boolean을 돌려주는 allow로 할지, 거절 시 예외를 던지게 할지 고민할 수 있습니다.

    ✅ Fix: 예외는 흐름 제어용으로 비싸고 호출자가 try/catch를 강제당하므로, boolean을 돌려주는 allow로 단순하게 둡니다.

    🔧 도구:인터페이스 분리SOLID/SRP

    interface RateLimiter {
    boolean allow(String clientId);
}
    🗣 영어로 말해

    “I start with a simple RateLimiter interface that returns true or false for each request.”

    checking microphone…

  2. 2

    이제 알고리즘이 여러 개라는 점을 반영합니다. 토큰 버킷, 고정 윈도우 같은 서로 다른 알고리즘을 같은 인터페이스 뒤에 숨겨서 교체할 수 있게 합니다. 이것이 Strategy 패턴입니다. 호출하는 쪽은 RateLimiter 타입만 알면 됩니다.

    ⚖️ Trade-off: 알고리즘마다 if/else로 분기하는 한 클래스로 만들 수도 있습니다.

    ✅ Fix: if/else는 새 알고리즘이 생길 때마다 그 클래스를 고쳐야 해서 OCP를 깨뜨립니다. 각 알고리즘을 별도 클래스(Strategy)로 분리해 추가에 열려 있고 수정에 닫히게 합니다.

    🔧 도구:Strategy 패턴OCP (개방-폐쇄 원칙)

    // 두 구현이 같은 인터페이스를 따른다
class TokenBucketLimiter implements RateLimiter { /* ... */
    public boolean allow(String clientId) { return true; }
}
class FixedWindowLimiter implements RateLimiter { /* ... */
    public boolean allow(String clientId) { return true; }
}
    🗣 영어로 말해

    “Each algorithm is a separate strategy behind the same interface, so I can swap them.”

    checking microphone…

  3. 3

    클라이언트별로 따로 카운트해야 하므로, 클라이언트마다 자기 상태를 가진 작은 객체가 필요합니다. 토큰 버킷에서는 Bucket이라는 내부 클래스를 만들어 남은 토큰 수(tokens)와 마지막 리필 시각(lastRefillMs)을 담습니다.

    ✅ Fix: Bucket을 private static 중첩 클래스로 두어 TokenBucketLimiter 안에서만 쓰는 상태 전용 객체임을 분명히 합니다.

    🔧 도구:composition-over-inheritance캡슐화

    private static final class Bucket {
    double tokens;
    long lastRefillMs = System.currentTimeMillis();
    Bucket(long capacity) { this.tokens = capacity; }
}
    🗣 영어로 말해

    “Each client gets its own small Bucket object holding tokens and the last refill time.”

    checking microphone…

  4. 4

    클라이언트와 그의 상태를 연결합니다. clientId를 키로, Bucket을 값으로 갖는 맵을 둡니다. 새 클라이언트가 처음 오면 그때 버킷을 만들어줍니다(lazy 생성). computeIfAbsent로 '없으면 만들기'를 한 줄로 처리합니다.

    ⚖️ Trade-off: 일반 HashMap을 쓸지 ConcurrentHashMap을 쓸지 정해야 합니다.

    ✅ Fix: 여러 스레드가 동시에 요청하므로 맵 자체가 스레드 안전해야 합니다. ConcurrentHashMap을 써서 맵에 대한 동시 접근을 안전하게 만듭니다.

    🔧 도구:ConcurrentHashMaplazy initialization

    private final Map<String, Bucket> buckets = new ConcurrentHashMap<>();

Bucket b = buckets.computeIfAbsent(clientId, k -> new Bucket(capacity));
    🗣 영어로 말해

    “A concurrent map links each client id to its bucket, created lazily on first request.”

    checking microphone…

  5. 5

    이제 핵심 동작인 토큰 버킷 알고리즘을 채웁니다. 요청이 올 때마다 지난 시간만큼 토큰을 채우고(refill), 토큰이 1개 이상 있으면 하나 쓰고 허용, 없으면 거절합니다. 이렇게 하면 capacity까지는 한꺼번에 몰려도(burst) 허용됩니다.

    ⚖️ Trade-off: 토큰을 백그라운드 타이머로 주기적으로 채울지, 요청이 올 때 계산할지 선택해야 합니다.

    ✅ Fix: 타이머 스레드는 복잡하고 자원을 씁니다. 요청 시점에 경과 시간 × 리필 속도로 토큰을 계산하는 lazy refill이 더 단순하고 정확합니다.

    🔧 도구:Token Bucket 알고리즘lazy refill

    long now = System.currentTimeMillis();
double add = (now - b.lastRefillMs) * refillPerMs;
if (add > 0) { b.tokens = Math.min(capacity, b.tokens + add); b.lastRefillMs = now; }
if (b.tokens >= 1.0) { b.tokens -= 1.0; return true; }
return false;
    🗣 영어로 말해

    “On each request I refill tokens by elapsed time, then spend one if available.”

    checking microphone…

  6. 6

    동시성 문제를 해결합니다. 한 클라이언트의 버킷을 두 스레드가 동시에 읽고 쓰면 토큰을 중복으로 차감할 수 있습니다(race condition). 그래서 그 버킷 객체 단위로만 synchronized 락을 겁니다. 클라이언트마다 락이 달라서 서로 다른 클라이언트는 막히지 않습니다.

    ⚖️ Trade-off: 메서드 전체에 synchronized를 걸면 모든 클라이언트가 하나의 락을 두고 줄을 섭니다.

    ✅ Fix: 전역 락은 처리량을 떨어뜨립니다. 버킷 객체별로 잠그는 fine-grained locking으로 클라이언트 간 병렬성을 살립니다.

    🔧 도구:fine-grained locking동시성 (race condition 방지)

    synchronized (b) {
    // refill + 토큰 차감을 한 번에 (원자적)
    long now = System.currentTimeMillis();
    b.refill(now, capacity, refillPerMs);
    if (b.tokens >= 1.0) { b.tokens -= 1.0; return true; }
    return false;
}
    🗣 영어로 말해

    “I lock per bucket, not globally, so different clients never block each other.”

    checking microphone…

  7. 7

    확장 지점을 보여줍니다. 두 번째 알고리즘인 FixedWindowLimiter를 같은 RateLimiter 인터페이스로 추가합니다. 현재 시각을 windowMs로 나눠 어느 윈도우인지 구하고, 윈도우가 바뀌면 카운트를 0으로 리셋합니다. 기존 코드를 전혀 안 고치고 새 전략만 추가하면 됩니다.

    ⚖️ Trade-off: 고정 윈도우는 윈도우 경계에서 한도의 거의 2배 요청이 몰릴 수 있는 약점이 있습니다.

    ✅ Fix: 더 정밀하게 하려면 sliding window나 token bucket을 고르면 됩니다. 인터페이스가 같으니 호출부 변경 없이 전략만 바꿔 끼웁니다.

    🔧 도구:Fixed Window 알고리즘Strategy 확장 (OCP)

    public boolean allow(String clientId) {
    Window w = windows.computeIfAbsent(clientId, k -> new Window());
    synchronized (w) {
        long bucket = System.currentTimeMillis() / windowMs;
        if (bucket != w.bucket) { w.bucket = bucket; w.count = 0; }
        if (w.count < limit) { w.count++; return true; }
        return false;
    }
}
    🗣 영어로 말해

    “Adding a fixed-window limiter needs no change to existing code, just a new strategy.”

    checking microphone…

7단계 영어를 다 말하면 → 이 메커니즘 전체를 영어로 설명할 수 있게 된다.

Full Java (javac-verified)

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

// Strategy: each algorithm implements this contract.
interface RateLimiter {
    boolean allow(String clientId);
}

// Token bucket: refills tokens over time, allows burst up to capacity.
class TokenBucketLimiter implements RateLimiter {
    private final long capacity;
    private final double refillPerMs;
    private final Map<String, Bucket> buckets = new ConcurrentHashMap<>();

    TokenBucketLimiter(long capacity, double refillPerSecond) {
        this.capacity = capacity;
        this.refillPerMs = refillPerSecond / 1000.0;
    }

    @Override
    public boolean allow(String clientId) {
        Bucket b = buckets.computeIfAbsent(clientId, k -> new Bucket(capacity));
        synchronized (b) {
            long now = System.currentTimeMillis();
            b.refill(now, capacity, refillPerMs);
            if (b.tokens >= 1.0) {
                b.tokens -= 1.0;
                return true;
            }
            return false;
        }
    }

    private static final class Bucket {
        double tokens;
        long lastRefillMs = System.currentTimeMillis();
        Bucket(long capacity) { this.tokens = capacity; }
        void refill(long now, long capacity, double refillPerMs) {
            double add = (now - lastRefillMs) * refillPerMs;
            if (add > 0) {
                tokens = Math.min(capacity, tokens + add);
                lastRefillMs = now;
            }
        }
    }
}

// Fixed window: counts requests per discrete time window.
class FixedWindowLimiter implements RateLimiter {
    private final long limit;
    private final long windowMs;
    private final Map<String, Window> windows = new ConcurrentHashMap<>();

    FixedWindowLimiter(long limit, long windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
    }

    @Override
    public boolean allow(String clientId) {
        Window w = windows.computeIfAbsent(clientId, k -> new Window());
        synchronized (w) {
            long bucket = System.currentTimeMillis() / windowMs;
            if (bucket != w.bucket) {
                w.bucket = bucket;
                w.count = 0;
            }
            if (w.count < limit) {
                w.count++;
                return true;
            }
            return false;
        }
    }

    private static final class Window {
        long bucket = -1;
        long count = 0;
    }
}

public class Solution {
    public static void main(String[] args) {
        RateLimiter limiter = new TokenBucketLimiter(3, 1.0);
        for (int i = 0; i < 5; i++) {
            System.out.println("req " + i + " -> " + limiter.allow("userA"));
        }
        RateLimiter fixed = new FixedWindowLimiter(2, 1000);
        for (int i = 0; i < 4; i++) {
            System.out.println("fixed " + i + " -> " + fixed.allow("userB"));
        }
    }
}
🎙 이 카드 AI랑 음성 대화 · 기록 저장