Go에서 토큰 버킷 알고리즘 구현하기

속도 제한 소개

컴퓨터 과학 및 네트워크 엔지니어링 영역에서 속도 제한은 시스템 안정성을 유지하고, 남용을 방지하고, 공정한 리소스 할당을 보장하기 위한 중요한 메커니즘입니다. 핵심적으로 속도 제한은 특정 시간 창 내에서 처리할 수 있는 요청 또는 작업의 수를 제어합니다. 이는 API 게이트웨이, 분산 시스템 및 리소스 소비를 규제해야 하는 모든 애플리케이션과 같은 시나리오에서 필수적입니다.

속도 제한을 구현하기 위해 설계된 다양한 알고리즘 중에서 토큰 버킷 알고리즘은 가장 인기 있고 다재다능한 선택 중 하나로 부상했습니다. 그 매력은 정상 상태 트래픽과 간헐적인 트래픽 버스트를 모두 처리할 수 있는 능력에 있으며, 이는 광범위한 실제 애플리케이션에 적합합니다. 이 포괄적인 가이드에서는 토큰 버킷 알고리즘의 내부 작동 방식을 자세히 살펴보고 Go 프로그래밍 언어에서 구현하고 실제 애플리케이션과 고려 사항을 검토합니다.

토큰 버킷 알고리즘 이해

핵심 개념

토큰 버킷 알고리즘은 토큰을 담는 버킷이라는 간단하면서도 우아한 메타포로 작동합니다. 각 토큰은 작업 수행 또는 요청 처리 권한을 나타냅니다. 이 알고리즘은 다음의 주요 메커니즘을 통해 작동합니다.

• 토큰 생성: 고정된 간격으로 새 토큰이 버킷에 추가됩니다. 토큰이 생성되는 속도는 시스템이 처리할 수 있는 장기 평균 요청 속도를 결정합니다.
• 토큰 소비: 요청을 처리하려면 버킷에서 토큰을 제거해야 합니다. 토큰을 사용할 수 있으면 요청이 허용됩니다. 그렇지 않으면 요청이 지연되거나 거부됩니다.
• 버킷 용량: 버킷에는 최대 용량이 있어 한 번에 보유할 수 있는 토큰 수를 제한합니다. 이 용량은 트래픽 버스트를 처리하는 시스템의 능력을 결정합니다.

시각적 표현

+------------------------+
|													|
|  [토큰]  [토큰]						|
|  [토큰]  [토큰]						|  <- 용량 = 5인 버킷
|  [토큰]									 |     현재 5개의 토큰 보유
|													|
+------------------------+
			^       |
			|			v
+------------------------+
|													|
|  토큰 생성기						 |  <- 초당 2개의 토큰 추가
|													|
+------------------------+
			^     
			|
+------------------------+
|													|
|  수신 요청							 |
|													|
+------------------------+

이 다이어그램에서 버킷은 최대 5개의 토큰을 담을 수 있습니다. 토큰 생성기는 매초 버킷에 2개의 토큰을 추가하지만 버킷은 용량 5개의 토큰을 초과하지 않습니다. 수신 요청이 도착하면 각 요청은 버킷에서 하나의 토큰을 가져옵니다. 사용 가능한 토큰이 없으면 요청은 나중에 처리를 위해 대기열에 넣거나 즉시 거부됩니다.

동적 동작

토큰 버킷 알고리즘의 진정한 힘은 동적 동작에 있습니다.

• 요청 볼륨이 낮은 기간 동안 토큰은 최대 용량까지 버킷에 누적됩니다. 이는 갑작스러운 트래픽 급증을 처리하는 데 사용할 수 있는 "예비"를 구축합니다.
• 트래픽 버스트 중에는 버킷에 토큰이 있는 한 시스템은 평균 토큰 생성 속도보다 높은 속도로 요청을 처리할 수 있습니다.
• 버킷이 비어 있으면 시스템은 토큰 생성 속도로만 요청을 처리할 수 있으므로 트래픽을 장기 평균으로 효과적으로 조절합니다.

이러한 동작은 웹 서버, API 엔드포인트 및 네트워크 라우터와 같이 가변적인 트래픽 패턴을 경험하는 애플리케이션에 토큰 버킷 알고리즘을 특히 적합하게 만듭니다.

Go에서 토큰 버킷 구현

Go의 동시성 기본 요소, 특히 고루틴과 채널은 토큰 버킷 알고리즘을 구현하는 데 탁월한 언어입니다. 단계별 구현을 살펴보겠습니다.

기본 토큰 버킷 구조

먼저 토큰 버킷의 구조를 정의해 보겠습니다.

package tokenbucket

import (
    "sync"
    "time"
)

// TokenBucket은 토큰 버킷 속도 제한기를 나타냅니다.
type TokenBucket struct {
    capacity  int			// 버킷이 담을 수 있는 최대 토큰 수
    rate      int       	// 초당 추가할 토큰 수
    tokens    int       	// 버킷의 현재 토큰 수
    lastRefill time.Time	// 마지막 토큰 리필의 타임스탬프
    mutex     sync.Mutex	// 동시 액세스를 보호하기 위한 뮤텍스
}

이 구조체는 다음을 포함합니다.

• capacity: 버킷이 담을 수 있는 최대 토큰 수
• rate: 초당 추가할 토큰 수
• tokens: 버킷의 현재 토큰 수
• lastRefill: 토큰이 마지막으로 버킷이 추가된 타임스탬프
• mutex: 스레드 안전성을 보장하기 위한 동기화 프리미티브

새 토큰 버킷 만들기

다음으로 새 토큰 버킷을 만드는 함수를 구현해 보겠습니다.

// NewTokenBucket은 지정된 용량과 속도로 새 토큰 버킷을 만듭니다.
func NewTokenBucket(capacity, rate int) *TokenBucket {
    return &TokenBucket{
        capacity:  capacity,
        rate:      rate,
        tokens:    capacity, // 전체 버킷으로 시작
        lastRefill: time.Now(),
    }
}

이 함수는 지정된 용량과 토큰 생성 속도로 새 토큰 버킷을 초기화합니다. 전체 버킷으로 시작하여 버킷의 용량까지 즉각적인 트래픽 버스트를 허용합니다.

토큰 리필

토큰 버킷 알고리즘의 핵심은 토큰 리필 메커니즘입니다. 마지막 리필 이후 경과된 시간에 따라 버킷에 추가해야 하는 토큰 수를 계산해야 합니다.

// refill은 마지막 리필 이후 경과된 시간을 기준으로 버킷에 토큰을 추가합니다.
func (tb *TokenBucket) refill() {
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill)
    
    // 추가해야 하는 토큰 수 계산
    tokensToAdd := int(elapsed.Seconds() * float64(tb.rate))
    
    if tokensToAdd > 0 {
        tb.lastRefill = now
        // 토큰을 추가하되 버킷의 용량을 초과하지 마십시오.
        tb.tokens = min(tb.tokens+tokensToAdd, tb.capacity)
    }
}

// min은 두 정수의 최소값을 찾는 도우미 함수입니다.
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

토큰 획득

이제 클라이언트가 버킷에서 토큰을 획득할 수 있도록 하는 메서드를 구현해 보겠습니다.

// Take는 버킷에서 지정된 수의 토큰을 가져오려고 시도합니다.
// 성공하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
func (tb *TokenBucket) Take(tokens int) bool {
    tb.mutex.Lock()
    defer tb.mutex.Unlock()
    
    // 먼저 경과된 시간을 기준으로 버킷을 토큰으로 리필합니다.
    tb.refill()
    
    // 토큰이 충분한지 확인하십시오.
    if tb.tokens >= tokens {
        tb.tokens -= tokens
        return true
    }
    
    // 사용 가능한 토큰이 충분히 않습니다.
    return false
}

Take 메서드는 다음 단계를 따릅니다.

1. 여러 고루틴이 버킷에 동시에 액세스하려고 시도할 수 있으므로 스레드 안전성을 보장하기 위해 잠금을 획득합니다.
2. 마지막 작업 이후 생성된 토큰으로 버킷을 리필합니다.
3. 요청을 충족하기에 충분한 토큰이 있는지 확인합니다.
4. 충분한 토큰이 있으면 버킷에서 토큰을 제거하고 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

차단 획득

경우에 따라 즉시 false를 반환하는 대신 토큰을 사용할 수 있을 때까지 차단하려고 할 수 있습니다. 토큰을 사용할 수 있을 때까지 지정된 시간 동안 대기하는 TakeWithTimeout 메서드를 구현해 보겠습니다.

// TakeWithTimeout은 버킷에서 토큰을 가져오려고 시도하고 지정된 시간 초과까지 대기합니다.
// 성공하면 true를 반환하고, 시간 초과에 도달하면 false를 반환합니다.
func (tb *TokenBucket) TakeWithTimeout(tokens int, timeout time.Duration) bool {
    // 기다릴 수 있는 가장 빠른 시간 계산
    deadline := time.Now().Add(timeout)
    
    for {
        tb.mutex.Lock()
        
        // 버킷 리필
        tb.refill()
        
        // 지금 토큰이 충분한지 확인하십시오.
        if tb.tokens >= tokens {
            tb.tokens -= tokens
            tb.mutex.Unlock()
            return true
        }
        
        // 더 많은 토큰을 기다려야 하는 시간 계산
        tokensNeeded := tokens - tb.tokens
        timeNeeded := time.Duration(tokensNeeded) * time.Second / time.Duration(tb.rate)
        
        // 마감일 전에 토큰을 얻을 수 있으면 대기했다가 다시 시도하십시오.
        if time.Now().Add(timeNeeded).Before(deadline) {
            // 다른 작업을 허용하기 위해 대기하기 전에 잠금 해제
            tb.mutex.Unlock()
            
            // 필요한 시간 동안 대기하되 남은 시간 초과보다 길게는 대기하지 마십시오.
            waitTime := minDuration(timeNeeded, deadline.Sub(time.Now()))
            time.Sleep(waitTime)
        } else {
            // 필요한 토큰을 얻을 시간이 충분히 않습니다.
            tb.mutex.Unlock()
            return false
        }
    }
}

// minDuration은 두 기간의 최소값을 찾는 도우미 함수입니다.
func minDuration(a, b time.Duration) time.Duration {
    if a < b {
        return a
    }
    return b
}

이 메서드는 필요한 토큰을 얻거나 시간 초과에 도달할 때까지 사용 가능한 토큰을 반복적으로 확인하는 루프를 사용합니다. 필요한 토큰을 생성하는 데 필요한 최소 시간을 계산하고 해당 기간(또는 시간 초과, 먼저 오는 것)까지 대기한 다음 다시 확인합니다.

고급 기능 및 최적화

버스트 제어

기본 구현에서는 토큰 누적을 허용하여 버스트를 처리하지만 더 정교한 버스트 제어를 추가할 수 있습니다. 예를 들어 단일 요청에서 가져올 수 있는 최대 토큰 수를 제한할 수 있습니다.

// TakeWithBurstLimit는 Take와 유사하지만 한 번의 요청에서 가져온 최대 토큰 수를 제한합니다.
func (tb *TokenBucket) TakeWithBurstLimit(tokens, maxBurst int) bool {
    // 최대 버스트 크기보다 많이 가져오지 않도록 하십시오.
    if tokens > maxBurst {
        tokens = maxBurst
    }
    return tb.Take(tokens)
}

이 수정은 단일 요청이 사용 가능한 모든 토큰을 소비하는 것을 방지하여 다른 요청에 대해 일부 토큰이 유지되도록 합니다.

모니터링 및 메트릭

프로덕션 시스템의 경우 토큰 버킷의 상태를 모니터링하는 것이 유용한 경우가 많습니다.

// Metrics는 토큰 버킷의 현재 상태를 반환합니다.
func (tb *TokenBucket) Metrics() (capacity, rate, currentTokens int) {
    tb.mutex.Lock()
    defer tb.mutex.Unlock()
    
    // 정확한 현재 토큰 수를 얻으려면 리필하십시오.
    tb.refill()
    
    return tb.capacity, tb.rate, tb.tokens
}

이 메서드는 버킷의 용량, 토큰 생성 속도 및 현재 토큰 수에 대한 통찰력을 제공하여 성능 모니터링 및 튜닝에 매우 유용할 수 있습니다.

동적 속도 조정

일부 시나리오에서는 시스템 조건에 따라 토큰 생성 속도를 동적으로 조정할 수 있습니다.

// SetRate는 토큰 생성 속도를 업데이트합니다.
func (tb *TokenBucket) SetRate(newRate int) {
    tb.mutex.Lock()
    defer tb.mutex.Unlock()
    
    // 먼저 이전 속도로 시간을 고려하여 리필하십시오.
    tb.refill()
    
    tb.rate = newRate
}

이를 통해 시스템은 트래픽이 적은 시간 동안 속도를 높이거나 로드가 높은 기간 동안 속도를 줄이는 것과 같이 변화하는 조건에 적응할 수 있습니다.

실제 응용 프로그램

API 속도 제한

토큰 버킷 알고리즘의 가장 일반적인 응용 프로그램 중 하나는 API 속도 제한입니다.

// 예: 토큰 버킷을 사용하여 API 엔드포인트의 속도를 제한합니다.
func handleAPIRequest(w http.ResponseWriter, r *http.Request, bucket *TokenBucket) {
    // 이 요청에 대한 토큰을 가져오십시오.
    if !bucket.Take(1) {
        http.Error(w, "요청이 너무 많습니다.", http.StatusTooManyRequests)
        return
    }
    
    // 요청 처리...
    w.WriteHeader(http.StatusOK)
    w.Write([]byte("요청이 성공적으로 처리되었습니다."))
}

이 예제에서 각 API 요청은 버킷에서 하나의 토큰을 소비합니다. 사용 가능한 토큰이 없으면 서버는 429 Too Many Requests 응답을 반환합니다.

트래픽 쉐이핑

토큰 버킷 알고리즘을 네트워크 애플리케이션의 트래픽 쉐이핑에도 사용할 수 있습니다.

// 예: 트래픽 쉐이핑에 토큰 버킷 사용
func sendPackets(packets [][]byte, bucket *TokenBucket) {
    for _, packet := range packets {
        // 각 패킷은 크기에 따라 토큰을 소비합니다.
        packetSize := len(packet)
        
        // 이 패킷에 대한 토큰이 충분할 때까지 기다리십시오.
        if !bucket.TakeWithTimeout(packetSize, 5*time.Second) {
            fmt.Println("토큰 대기가 시간 초과되었습니다.")
            return
        }
        
        // 패킷 보내기...
        fmt.Printf("크기 %d의 패킷 보내기\n", packetSize)
    }
}

여기서 필요한 토큰 수는 전송되는 패킷의 크기에 비례하여 네트워크 대역폭에 대한 보다 세분화된 제어가 가능합니다.

리소스 할당

토큰 버킷을 사용하여 시스템 내에서 리소스 할당을 관리할 수도 있습니다.

// 예: 토큰 버킷을 사용하여 다양한 유형의 작업에 우선 순위를 지정합니다.
type ResourceManager struct {
    criticalOperationsBucket *TokenBucket
    normalOperationsBucket   *TokenBucket
    lowPriorityBucket        *TokenBucket
}

func NewResourceManager() *ResourceManager {
    return &ResourceManager{
        // 중요 작업은 더 많은 토큰과 더 큰 버스트 용량을 얻습니다.
        criticalOperationsBucket: NewTokenBucket(100, 50),
        // 일반 작업은 적당한 토큰 할당을 받습니다.
        normalOperationsBucket: NewTokenBucket(50, 20),
        // 낮은 우선 순위 작업은 더 적은 토큰을 얻습니다.
        lowPriorityBucket: NewTokenBucket(20, 5),
    }
}

func (rm *ResourceManager) performCriticalOperation() bool {
    return rm.criticalOperationsBucket.Take(1)
}

func (rm *ResourceManager) performNormalOperation() bool {
    return rm.normalOperationsBucket.Take(1)
}

func (rm *ResourceManager) performLowPriorityOperation() bool {
    return rm.lowPriorityBucket.Take(1)
}

이 예제에서 다양한 유형의 작업은 다양한 용량과 속도를 가진 다양한 토큰 버킷을 가지므로 중요 작업이 시스템 리소스에 대한 우선 순위 액세스를 받도록 보장합니다.

성능 고려 사항

동시성

Go에서 토큰 버킷 알고리즘을 구현할 때 동시 액세스의 성능 영향을 고려하는 것이 중요합니다. 뮤텍스의 사용은 스레드 안전성을 보장하지만 매우 동시적인 시스템에서 병목 현상이 될 수 있습니다.

이를 완화하는 한 가지 방법은 더 세분화된 잠금 전략을 사용하거나 토큰 버킷을 여러 인스턴스에 걸쳐 분할하는 것입니다.

// 예: 더 나은 동시성을 위해 토큰 버킷 분할
type ShardedTokenBucket struct {
    buckets   []*TokenBucket
    numShards int
}

func NewShardedTokenBucket(capacity, rate, numShards int) *ShardedTokenBucket {
    buckets := make([]*TokenBucket, numShards)
    for i := 0; i < numShards; i++ {
        // 각 샤드는 총 용량과 속도의 동일한 몫을 얻습니다.
        buckets[i] = NewTokenBucket(capacity/numShards, rate/numShards)
    }
    
    return &ShardedTokenBucket{
        buckets:   buckets,
        numShards: numShards,
    }
}

func (stb *ShardedTokenBucket) Take(tokens int) bool {
    // 해시(예: 요청 ID)를 기반으로 샤드를 선택하십시오.
    shard := 0 // 실제로 적절한 해시 함수를 사용하십시오.
    
    return stb.buckets[shard].Take(tokens)
}

토큰 버킷을 여러 샤드로 나누어 뮤텍스에 대한 경합을 줄여 동시 환경에서 더 나은 성능을 얻을 수 있습니다.

정밀도 대 효율성

이 기사에 제시된 구현은 각 작업에서 토큰 수를 다시 계산하여 높은 정밀도를 제공하지만 처리량이 매우 높은 시스템에서는 성능에 영향을 미칠 수 있습니다.

대안적인 접근 방식은 백그라운드 고루틴을 사용하여 주기적으로 토큰을 버킷에 추가하는 것입니다.

// 예: 백그라운드 고루틴을 사용하여 토큰 추가
func startRefillGoroutine(bucket *TokenBucket, interval time.Duration) {
    go func() {
        ticker := time.NewTicker(interval)
        defer ticker.Stop()
        
        for range ticker.C {
            bucket.mutex.Lock()
            // 간격과 속도를 기준으로 토큰을 추가하십시오.
            tokensToAdd := int(interval.Seconds() * float64(bucket.rate))
            bucket.tokens = min(bucket.tokens+tokensToAdd, bucket.capacity)
            bucket.mutex.Unlock()
        }
    }()
}

이 접근 방식은 토큰이 지속적으로 추가되는 것이 아니라 일괄적으로 추가되므로 더 효율적이지만 일부 부정확성을 도입합니다.

결론

토큰 버킷 알고리즘은 광범위한 애플리케이션에서 속도 제한 및 트래픽 쉐이핑을 구현하는 유연하고 효율적인 방법을 제공합니다. 정상적인 트래픽과 갑작스러운 버스트를 모두 처리할 수 있는 기능이 있어 트래픽 패턴을 예측할 수 없는 실제 시스템에서 특히 유용합니다.

이 기사에서는 토큰 버킷 알고리즘의 핵심 개념을 살펴보고 Go에서 구현하고 다양한 확장 및 최적화를 검토했습니다. 또한 API 속도 제한에서 네트워크 트래픽 쉐이핑에 이르기까지 실제 응용 프로그램을 살펴보았습니다.

자신의 애플리케이션에서 토큰 버킷을 구현할 때는 다음 사항을 고려하십시오.

• 사용 사례에 적합한 용량 및 토큰 생성 속도
• 토큰을 사용할 수 없는 경우 요청을 처리하는 방법(거부, 대기열 또는 지연)
• 동시 환경에서 스레드 안전성 및 성능
• 시스템 조건에 따른 모니터링 및 동적 조정

Leapcell: 최고의 서버리스 웹 호스팅

마지막으로 Go 서비스를 배포하기 위한 훌륭한 플랫폼인 **Leapcell**을 추천합니다.

🚀 좋아하는 언어로 빌드

JavaScript, Python, Go 또는 Rust로 손쉽게 개발하십시오.

무료로 무제한 프로젝트 배포

사용한 만큼만 지불하십시오. 요청도 없고 요금도 없습니다.

⚡ 사용량에 따라 지불하고 숨겨진 비용 없음

유휴 요금 없이 원활한 확장성만 있습니다.

📖 설명서 탐색

🔹 Twitter에서 팔로우하세요: @LeapcellHQ