Какие бывают типы rate limiting (token bucket, leaky bucket) и где они применяются

1️⃣ Как кратко ответить

Rate limiting — это техника управления потоком данных, чтобы предотвратить перегрузку системы. Основные типы: token bucket и leaky bucket. Token bucket позволяет гибко накапливать и использовать токены для обработки запросов, обеспечивая гибкость в пиковых нагрузках. Leaky bucket выравнивает поток запросов, обеспечивая постоянную скорость обработки, что полезно для стабилизации нагрузки.

2️⃣ Подробное объяснение темы

Rate limiting — это метод контроля количества запросов, которые могут быть обработаны системой за определенный период времени. Это важно для предотвращения перегрузки серверов, обеспечения справедливого распределения ресурсов и защиты от злоупотреблений, таких как DDoS-атаки. Существует несколько алгоритмов для реализации rate limiting, среди которых наиболее популярны token bucket и leaky bucket.

Token Bucket

Token bucket — это алгоритм, который позволяет накапливать "токены" в "ведре" с определенной скоростью. Каждый токен представляет собой разрешение на выполнение одного запроса. Когда приходит запрос, система проверяет, есть ли в ведре токены. Если есть, один токен удаляется, и запрос обрабатывается. Если токенов нет, запрос отклоняется или задерживается.

Пример работы:

1. Инициализация: Ведро имеет максимальную емкость C токенов и наполняется токенами со скоростью R токенов в секунду.
2. Прием запроса: Когда приходит запрос, проверяется наличие токенов.
3. Обработка: Если токены есть, один токен удаляется, и запрос обрабатывается.
4. Отклонение: Если токенов нет, запрос отклоняется или ставится в очередь.

type TokenBucket struct {
    capacity     int       // Максимальная емкость ведра
    tokens       int       // Текущее количество токенов
    refillRate   int       // Скорость пополнения токенов в секунду
    lastRefill   time.Time // Время последнего пополнения
}
​
func (tb *TokenBucket) Allow() bool {
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens += int(elapsed) * tb.refillRate // Пополнение токенов
    if tb.tokens > tb.capacity {
        tb.tokens = tb.capacity // Ограничение по емкости
    }
    tb.lastRefill = now
​
    if tb.tokens > 0 {
        tb.tokens-- // Удаление токена для обработки запроса
        return true
    }
    return false // Отклонение запроса
}

Leaky Bucket

Leaky bucket — это алгоритм, который выравнивает поток запросов, обеспечивая постоянную скорость обработки. Он работает как ведро с дыркой: запросы поступают в ведро, и они "утекают" с постоянной скоростью. Если ведро переполняется, новые запросы отклоняются.

Пример работы:

1. Инициализация: Ведро имеет фиксированную емкость C.
2. Прием запроса: Запросы поступают в ведро.
3. Обработка: Запросы "утекают" из ведра с постоянной скоростью R.
4. Отклонение: Если ведро переполнено, новые запросы отклоняются.

type LeakyBucket struct {
    capacity     int       // Максимальная емкость ведра
    currentLoad  int       // Текущая загрузка ведра
    leakRate     int       // Скорость утечки запросов в секунду
    lastLeakTime time.Time // Время последней утечки
}
​
func (lb *LeakyBucket) Allow() bool {
    now := time.Now()
    elapsed := now.Sub(lb.lastLeakTime).Seconds()
    lb.currentLoad -= int(elapsed) * lb.leakRate // Утечка запросов
    if lb.currentLoad < 0 {
        lb.currentLoad = 0 // Ограничение по минимальной загрузке
    }
    lb.lastLeakTime = now
​
    if lb.currentLoad < lb.capacity {
        lb.currentLoad++ // Добавление запроса в ведро
        return true
    }
    return false // Отклонение запроса
}

Применение

• Token Bucket: Используется в системах, где важна гибкость в обработке пиковых нагрузок, например, в API-сервисах, где могут быть резкие всплески запросов.
• Leaky Bucket: Применяется в системах, где важна стабильность и постоянная скорость обработки, например, в сетевых маршрутизаторах для управления трафиком.

Оба алгоритма помогают эффективно управлять ресурсами и обеспечивать стабильную работу систем под нагрузкой.