PrepBro
← Назад к вопросам

Rate Limiter (Token Bucket)

2.0 Middle🔥 251 комментариев
#Конкурентность и горутины#Основы Go#Производительность и оптимизация

Условие

Реализуйте алгоритм ограничения запросов по принципу корзины токенов (Token Bucket Rate Limiter).

Требования

  • Токены пополняются с фиксированной скоростью
  • Максимальный запас токенов ограничен фиксированным значением
  • За каждый вызов нужно вычитать N токенов
  • Если токенов недостаточно, возвращается false

Сигнатура

type RateLimiter struct {
    // ваши поля
}

func NewRateLimiter(rate float64, capacity int) *RateLimiter
func (r *RateLimiter) Allow() bool
func (r *RateLimiter) AllowN(n int) bool

Пример

limiter := NewRateLimiter(10.0, 100) // 10 токенов/сек, макс 100
limiter.Allow() // true если есть токен
limiter.AllowN(5) // true если есть 5 токенов

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Token Bucket Rate Limiter — это алгоритм для ограничения частоты запросов. Используется в системах ограничения API, защиты от DDoS, и контроля нагрузки. Ключевая идея: токены пополняются с фиксированной скоростью, каждый запрос расходует токены.

Принцип работы

  1. Инициализация: в корзине максимум capacity токенов
  2. Пополнение: каждую секунду добавляется rate токенов (но не более capacity)
  3. Проверка доступа: если токенов достаточно, вычитаем их и разрешаем запрос
  4. Отказ: если токенов недостаточно, отказываем в запросе

Реализация

import (
    "sync"
    "time"
)

type RateLimiter struct {
    mu       sync.Mutex
    rate     float64
    capacity float64
    tokens   float64
    lastTime time.Time
}

func NewRateLimiter(rate float64, capacity int) *RateLimiter {
    return &RateLimiter{
        rate:     rate,
        capacity: float64(capacity),
        tokens:   float64(capacity),
        lastTime: time.Now(),
    }
}

func (r *RateLimiter) refill() {
    now := time.Now()
    elapsed := now.Sub(r.lastTime).Seconds()
    r.lastTime = now
    
    r.tokens += elapsed * r.rate
    
    if r.tokens > r.capacity {
        r.tokens = r.capacity
    }
}

func (r *RateLimiter) Allow() bool {
    return r.AllowN(1)
}

func (r *RateLimiter) AllowN(n int) bool {
    r.mu.Lock()
    defer r.mu.Unlock()
    
    r.refill()
    
    if r.tokens >= float64(n) {
        r.tokens -= float64(n)
        return true
    }
    
    return false
}

Пример использования

func main() {
    limiter := NewRateLimiter(10.0, 100)
    
    for i := 0; i < 100; i++ {
        if limiter.Allow() {
            println("Request", i, "allowed")
        }
    }
    
    if !limiter.Allow() {
        println("Request rejected: no tokens")
    }
    
    time.Sleep(1 * time.Second)
    
    for i := 0; i < 10; i++ {
        if limiter.Allow() {
            println("After wait - request allowed")
        }
    }
}

Ключевые моменты

  • Mutex: потокобезопасность
  • Lazy refill: пополнение только при вызове Allow()
  • Floating-point: точные расчёты времени
  • Времени последнего обновления: для корректного расчёта прошедшего времени

Сложность

  • Временная: O(1)
  • Пространственная: O(1)
Rate Limiter (Token Bucket) | PrepBro