System Design. Part04. 처리율 제한 장치의 설계

Part04. 처리율 제한 장치의 설계

처리율 제한 장치란?

• API 서버, 웹 서비스 등에서 지나치게 많은 요청이 들어오는 것을 방지하기 위해 일정 시간 동안 허용하는 요청 수를 제한하는 기능이다.

처리율 제한 방식 3가지 비교

구분	🧍 클라이언트	서버	미들웨어(API Gateway 등)
요청 처리 시점	요청 전 차단	서버 내부에서 차단	서버 도달 전 차단
장점	- 서버 부하 감소 - 외부 API 요금 방지	- 사용자/요금제별 세밀 제어	- 과부하 효과적으로 차단 - 인스턴스 간 일관성 유지
단점	- 우회 가능 (신뢰 불가) - 보안 취약	- 서버 리소스 소비 후 거부 - 분산 환경에선 상태 공유 필요	- 구성 복잡성 및 운영 비용 증가
사용 예	- 버튼 연타 방지 - 외부 API 호출 제한	- 토큰당 요청 수 제한 - 로그인 시도 제한	- 전체 시스템 트래픽 제한 - IP별 요청 수 제한

---

처리율 제한 알고리즘

1. 토큰 버킷 알고리즘

원리

• 토큰은 정해진 속도로 버킷에 지속적으로 추가됨.
• 요청이 들어오면 버킷에서 토큰을 하나씩 소비함.
• 토큰이 없으면 요청을 거부하거나 큐에 넣어 대기함.

핵심 요소

• capacity (버킷 크기): 최대 보유 가능한 토큰 개수 (burst 허용량 결정)
• refill rate (보충 속도): 단위 시간 당 토큰 추가 속도 (지속 가능한 처리량)

📍 예시

• capacity: 10개, refill rate: 초당 1개
  • 순간적으로 최대 10개의 요청 처리 가능, 그 후 초당 1개씩 처리 가능

✅ 장점

• 순간적인 트래픽 증가 허용 (요청이 몰리면 그 버킷에 남아있는 토큰만큼 한꺼번에 소비할 수 있으므로)
• 버킷 크기(capacity)와 현재 토큰 수(tokens), 마지막 보충 시점(timestamp) 정도만 저장하면 되기 때문에 효율적인 메모리 사용

⚠️ 단점

• 두개의 인자 (버킷 크기, 토큰 공급률)을 튜닝하는게 까다로움

class TokenBucketRateLimiter(
    private val capacity: Int, // 버킷이 최대 보유할 수 있는 토큰 수
    private val refillRatePerSecond: Double // 초당 버킷에 보충할 토큰 수
) {
    private var tokens: Double = capacity.toDouble()  / 현재 남아있는 토큰 수
    private var lastRefillTimestamp: Long = System.currentTimeMillis() // 마지막 보충 시점
    private val lock = ReentrantLock()

    /**
     * 요청 허용 여부 판단
     */
    fun allowRequest(): Boolean {
        lock.withLock {
            refillTokens() //요청이 들어온 시점에 토큰을 최신 상태로 갱신
            return if (tokens >= 1) {
                tokens -= 1
                true
            } else {
                false
            }
        }
    }

    /**
     * 경과 시간만큼 토큰 보충
     */
    private fun refillTokens() {
        val now = System.currentTimeMillis()
        val elapsedMillis = now - lastRefillTimestamp // 경과 시간 계산
        val tokensToAdd = elapsedMillis / 1000.0 * refillRatePerSecond // 경과 시간 * 시간 당 보충할 토큰 수
        tokens = min(capacity.toDouble(), tokens + tokensToAdd) // 기존 tokens 에 tokensToAdd 를 더하되 capacity를 넘지 않도록 min으로 제한
        lastRefillTimestamp = now
    }
}

2. 누출 버킷

원리

• 요청이 오면 버킷(queue)에 들어가고, 처리 시스템은 고정된 속도로 처리함.
• 요청 처리율이 고정되어 있어 버킷이 가득 차면 추가 요청은 즉시 거부됨.

핵심 요소

• queue size (버킷 크기): 최대 보관 가능한 요청 수
• leak rate (누출 속도): 요청 처리 속도 (고정됨)

📍 예시

• queue size: 10, leak rate: 초당 1개
  • 초당 1개씩 요청 처리, 요청이 초당 2개씩 오면 점차 차서 결국 차단됨

✅ 장점

• 큐의 크기가 제한되어 있어 효율적인 메모리 사용
• 고정된 처리율을 갖고 있어 안정적인 처리율로 서버 보호에 탁월

⚠️ 단점

• 순간적인 트래픽 허용 어려움
• queue에 적체될 경우 latency(지연 시간) 증가 가능

/**
 * 요청을 큐에 저장하고 고정 속도로 처리 (누출)
 * 큐가 가득 차면 추가 요청은 거절
 */
class LeakyBucketRateLimiter(
    private val queueSize: Int, // 큐(버킷)가 보관할 최대 요청 수
    leakRatePerSecond: Int, // 초당 처리(누출)할 요청 수
) {
    private val queue: Queue<Long> = LinkedList()
    private val leakIntervalMillis = 1000L / leakRatePerSecond

    init {
        fixedRateTimer(period = leakIntervalMillis, daemon = true) {
            processOne()
        }
    }

    /**
     * 요청 추가 시도
     * @param requestId 요청 식별자
     */
    @Synchronized
    fun allowRequest(requestId: Long): Boolean {
        return if (queue.size < queueSize) {
            queue.add(requestId)
            true
        } else {
            false
        }
    }

    /** 하나의 요청을 큐에서 꺼내 처리 */
    @Synchronized
    private fun processOne() {
        queue.poll()?.let { id ->
            println("Processing request: $id")
        }
    }
}

3. 고정 윈도 카운터

원리

• 일정한 시간 간격의 윈도(예: 매 1분)를 정해두고, 그 안에서 요청 수를 세서 제한함.
• 윈도가 끝나면 카운트 리셋

핵심 요소

• window size: 윈도의 시간 간격
• threshold: 윈도 내 최대 허용 요청 수

📍 예시

• window size: 1분, request limit: 100
  • → 매 분당 100개의 요청만 허용. 윈도가 끝나면 카운트 0으로 초기화

✅ 장점

• 구현 가장 간단하고 메모리 소모 최소
• 빠르고 간단한 제어

⚠️ 단점

• 카운터 초기화 시점이 고정된 구간 경계에만 일어나기때문에 윈도 경계 문제 발생 (e.g. 59초~60초 사이 많은 요청이 몰리면, 최대 2배 요청 허용 가능)

/**
 * 고정된 시간 윈도우마다 카운트를 초기화하고 제한
 */
class FixedWindowRateLimiter(
    private val windowSizeMillis: Long, // 윈도우 크기 (ms)
    private val maxRequests: Int, // 윈도우 내 허용 최대 요청 수
) {
    // 현재 윈도우 시작 시각 (초기에는 인스턴스 생성 시점)
    private var windowStart: Long = System.currentTimeMillis()
    private var count: Int = 0

    /**
     * 요청 허용 여부 판단
     */
    @Synchronized
    fun allowRequest(): Boolean {
        val now = System.currentTimeMillis()

        // 1 현재 시각이 윈도우 시작 시각(windowStart)에서 windowSizeMillis만큼 지났는지 확인
        if (now - windowStart >= windowSizeMillis) {
            // 윈도우가 만료됐으므로 새로운 윈도우 시작 시각을 현재 시각으로 갱신
            // count를 0으로 초기화
            windowStart = now
            count = 0
        }
        return if (count < maxRequests) {
            count++
            true
        } else {
            false
        }
    }
}

4. 이동 윈도 로그(Sliding Window Log)

원리

• 요청 발생 시 타임스탬프를 모두 로그에 기록함.
• 요청 제한 체크 시, 현재 시간에서 윈도 크기만큼 과거의 요청 로그만 확인하여 판단.

핵심 요소

• window size: 판단에 쓰일 시간 윈도 크기 (e.g. 최근 1분)
• log storage: 모든 요청의 타임스탬프 저장

📍 예시

• window size: 1분, request limit: 100
  • → 요청이 들어올 때마다 최근 1분 로그를 체크해서, 100건 초과면 차단

✅ 장점

• 정밀도 가장 높음

⚠️ 단점

• 요청 수 많을 시 메모리 및 처리 비용 증가 (로그 관리 부담)

/**
 * 모든 요청 타임스탬프를 기록하고, 윈도우 내 로그 수로 제한
 */
class SlidingWindowLogRateLimiter(
    private val windowSizeMillis: Long, // 윈도우 크기
    private val maxRequests: Int, // 윈도우 내 허용할 최대 요청 수
) {
    private val timestamps: Queue<Long> = LinkedList()  // 요청이 들어온 시각들을 저장하는 큐
    private val lock = ReentrantLock()

    fun allowRequest(): Boolean {
        lock.withLock {
            val now = System.currentTimeMillis()

            // 윈도우 바깥(= now - windowSizeMillis 이전) 요청들 제거
            while (timestamps.isNotEmpty() && now - timestamps.peek() > windowSizeMillis) {
                timestamps.poll()
            }
            
            // 처리 방식에는 2가지 방식이 있는 것 같다.

            // 1번. 항상 기록 (카운트 포함 → 처리율 감소 (보수적))
            timestamps.add(now)
            return timestamps.size <= maxRequests

            // 2번. 거부된 시도 미포함 → 처리율 유지
            if (timestamps.size < maxRequests) {
                timestamps.add(now)
                return true
            } else {
                return false
            }
        }
    }
}

5. 이동 윈도 카운터(Sliding Window Counter)

원리

• 전체 윈도를 고정 구간으로 나누지 않고, 현재 윈도와 직전 윈도의 카운트를 가중합산해 지금 기준 지난 시간 만큼의 요청량을 추정

핵심 요소

• window size (전체 윈도)
• max request (윈도 내 허용할 최대 요청 수)

📍 예시

• 이전 윈도(1분 전~0분 전)에 5건, 현재 윈도(지금까지) 3건
• 새 요청이 현재 윈도의 30% 경과 시점에 도착 → overlapRatio = 1 – 0.3 = 0.7
• 추정 요청량 = 3 + 5 × 0.7 = 6.5 → 내림하면 6 < 7 → 허용

✅ 장점

• 고정 윈도보다 정확하고, 로그 방식보다 효율적

⚠️ 단점

• 약간의 계산 복잡성 존재

class WeightedSlidingWindowRateLimiter(
    private val windowSizeMillis: Long, // 윈도우 크기
    private val maxRequests: Int, // 윈도우 내 허용 최대 요청 수
) {
    // 윈도우 시작 시각(밀리초) → 카운터 맵 (고정 윈도우 방식 사용)
    private val counters = ConcurrentHashMap<Long, AtomicInteger>()
    private val lock = ReentrantLock()

    /**
     * 요청 허용 여부 판단 (이동 윈도 가중치 계산 방식)
     *
     * 1) 현재 윈도우와 바로 이전 윈도우의 카운트 가져오기
     * 2) 이전 윈도우가 남아 있는 비율만큼 가중치 적용
     * 3) 두 값을 합산한 후 한도 비교
     */
    fun allowRequest(): Boolean {
        val now = System.currentTimeMillis()

        // 1) 윈도우 경계 계산
        val currentWindowStart = (now / windowSizeMillis) * windowSizeMillis
        val previousWindowStart = currentWindowStart - windowSizeMillis

        lock.withLock {
           // 현재와 이전 윈도우를 제외한 모든 키를 제거
            counters.keys.removeIf { it < previousWindowStart }
            
            // 2) 현재 및 이전 윈도우 요청 수 조회
            val currentCount = counters[currentWindowStart]?.get() ?: 0
            val previousCount = counters[previousWindowStart]?.get() ?: 0

            // 3) 윈도우 내 경과/잔여 시간 계산
            val elapsedInCurrent = now - currentWindowStart
            val remainingInCurrent = windowSizeMillis - elapsedInCurrent

            // 4) 이전 윈도우의 가중치 비율 (잔여 시간 비율)
            val overlapRatio = remainingInCurrent.toDouble() / windowSizeMillis

            // 5) 가중 합산
            val estimatedRequests = currentCount + (previousCount * overlapRatio)

            // 6) 허용 여부 판단
            return if (estimatedRequests < maxRequests) {
                counters
                    .computeIfAbsent(currentWindowStart) { AtomicInteger(0) }
                    .incrementAndGet()
                true
            } else {
                false
            }
        }
    }
}