[Golang] 고정 메모리 기반 Rate Limit

 

시스템을 설계하는 백엔드 개발자의 고민 중 하나는 트래픽 제어일 것입니다.
특히 대규모 분산 환경에서는 성능과 메모리 사이의 균형을 맞추는 것이 중요할텐데요.

주로 트래픽 제어 기능을 구현할 때 많이 사용하는 슬라이딩 윈도우 방식이 가지는 단점과

해결 방법에 대해서 알아보는 시간을 가져보겠습니다.

 

1. 레코드 방식의 문제점

가장 정확한 슬라이딩 윈도우 방식은 요청이 들어올 때마다 타임 스탬프를 기록하는 레코드 방식입니다.

type SlidingWindowLog struct {
    timestamps []time.Time // 요청마다 데이터가 append
    limit      int
    window     time.Duration
}

 

정확도는 높지만 대신 요청이 100만건이 들어오면 슬라이스 길이도 100만개가 추가되어 길이가 100만이 될 겁니다.
이는 메모리 점유율이 트래픽의 양에 따라서 급격히 상승 할 수 있으며, DDos 같은 공격이 들어올 경우 Rate Limit을 처리하기도 전에 OOM(out of memory)가 발생해 서버가 멈출수도 있습니다.

 

2. 해결 방법

Cloudflare 에서는 이러한 문제를 해결하기 위해 요청 기록은 남기는 대신에, 이전 주기의 통계치를 이용한 방법을 사용했습니다.
예를들면 1분이라는 주기가 있다고 가정을 해봅시다.
이전 주기에서 1분 동안 80번의 요청이 들어왔다고 했을 때, 현재 주기가 진행된지 15초가 되었을 때 요청의 수가 10개라면,
이전 주기 동안 들어온 요청의 개수 80개 * 0.75 + 현재까지 진행된 요청 수 10 = 60 + 10 로 계산하는 방식으로 구현 했습니다.

다시 설명하자면

• prev : 1분당 80번 요청
• curr : 주기가 진행된지 15초가 된 시점(주기의 25%지점)에 까지 들어온 요청 수 10번 
• 계산 :  [ 지난 주기 요청 수 * 남은 비중(75%) + 현재 요청 수 = 80 * 0.75 + 10 = 70 ]

 

3. Go로 구현하기

package main

import (
	"fmt"
	"math"
	"time"
)

type SlidingWindow struct {
	prevCount int // 이전 주기의 총 요청 수
	currCount int // 현재 주기의 총 요청 수
	limit     int
	lastReset time.Time     // 주기가 교체된 마지막 시점
	window    time.Duration // 주기
}

func NewSlidingWindow(limit int, window time.Duration) *SlidingWindow {
	return &SlidingWindow{
		limit:     limit,
		window:    window,
		lastReset: time.Now(),
	}
}

func (s *SlidingWindow) Allow() bool {
	now := time.Now()

	if now.Sub(s.lastReset) >= s.window {
		s.prevCount = s.currCount
		s.currCount = 0
		s.lastReset = now
	}

	// 2. 시간 흐름에 따른 가중치 계산
	passedFraction := float64(now.Sub(s.lastReset)) / float64(s.window)

	// 3. 현재 트래픽 추정치 계산
	estimate := float64(s.prevCount)*(1.0-passedFraction) + float64(s.currCount)

	// 4. 허용 여부 결정
	if int(math.Round(estimate)) < s.limit {
		s.currCount++
		return true
	}
	return false
}

func main() {
	limiter := NewSlidingWindow(10, time.Second)

	for i := 1; i <= 12; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: ALLOWED (Current Count: %d)\n", i, limiter.currCount)
		} else {
			fmt.Printf("Request %d: REJECTED (Rate Limit Exceeded)\n", i)
		}
	}

	time.Sleep(1 * time.Second)        // wait sec
	limiter.Allow()                    // swap
	time.Sleep(250 * time.Millisecond) // wait 25%

	for i := 1; i <= 7; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: ALLOWED (Current Count: %d)\n", i, limiter.currCount)
		} else {
			fmt.Printf("Request %d: REJECTED (Estimate reached limit)\n", i)
		}
	}
}

 

- 동작 결과

Request 1: ALLOWED (Current Count: 1)
Request 2: ALLOWED (Current Count: 2)
Request 3: ALLOWED (Current Count: 3)
Request 4: ALLOWED (Current Count: 4)
Request 5: ALLOWED (Current Count: 5)
Request 6: ALLOWED (Current Count: 6)
Request 7: ALLOWED (Current Count: 7)
Request 8: ALLOWED (Current Count: 8)
Request 9: ALLOWED (Current Count: 9)
Request 10: ALLOWED (Current Count: 10)
Request 11: REJECTED (Rate Limit Exceeded)
Request 12: REJECTED (Rate Limit Exceeded)
Request 1: ALLOWED (Current Count: 1)
Request 2: ALLOWED (Current Count: 2)
Request 3: ALLOWED (Current Count: 3)
Request 4: REJECTED (Estimate reached limit)
Request 5: REJECTED (Estimate reached limit)
Request 6: REJECTED (Estimate reached limit)
Request 7: REJECTED (Estimate reached limit)

 

 

동작 결과를 살펴보면 허용하는 10개까지는 잘 되었고, 초과하는 순간 잘 차단하는 것을 확인할 수 있습니다.
그리고 1초의 시간을 기다리면서 주기를 넘기고, Allow()를 호출함으로써 다음 주기로 넘어갑니다.
이후 250ms가 지난 후 두 번째 주기 요청 정보들을 허용 합니다.
이때 요청이 들어온 것은 3개가 있습니다.

계산 : 10(prev) * 0.75 + 3(curr) = 10.5

 

10.5는 앞서 설정한 리미트 10보다 큰 값임으로, 3번째 이후로 들어온 요청 정보들은 모두 취소하게 됩니다.
쉽게 "나 25프로 지점에 도달했어, 너는 아직 75프로 지점에 있을 테니까 우리 둘이 개수 합쳐보자 -> 추정치가 더 크네? 요청 막아!)
즉 추정치 10.5는 설정한 10보다 큼으로 지금 현재 주기를 변경하긴 했지만, 이 전 주기의 요청수를 보았을 때 지금은 새로운 요청 정보를 받을 수 없다고 이해하면 좋을거 같습니다.

 

3. 참고자료

https://blog.cloudflare.com/counting-things-a-lot-of-different-things/

How we built rate limiting capable of scaling to millions of domains