Что такое Token Bucket

• Capacity: max tokens в bucket (burst size)
• Refill rate: r tokens/sec (long-term average)
• Per-key: один bucket per user/IP/API key
• Storage: Redis atomic ops (INCR/DECR + EXPIRE)
• Typical: 60 req/min = 1 token/sec refill + capacity 10 (burst)

# Redis Lua pseudocode
local tokens = redis.call("GET", key) or capacity
tokens = min(capacity, tokens + (now - last_refill) * rate)
if tokens >= 1 then
  redis.call("SET", key, tokens - 1)
  return allow
else
  return deny
end

• Rate Limiting
• Idempotency

Алгоритм Token Bucket — это метод ограничения скорости (rate limiting), который позволяет контролировать количество запросов, отправляемых на сервер, с помощью токенов, хранящихся в «ведре». Каждый токен соответствует одному запросу, и когда ведро заполняется, новые токены могут быть добавлены с заданной скоростью. Это позволяет гибко управлять трафиком и защищать сервер от перегрузки. Например, типичная настройка может включать ведро на 10 токенов, где токены добавляются со скоростью 1 токен в секунду.

Алгоритм Token Bucket работает по следующему принципу: у вас есть ведро фиксированного объема, в которое могут помещаться токены. Каждый раз, когда происходит запрос, сервер проверяет, есть ли доступные токены. Если токены доступны, один из них «извлекается» из ведра, и запрос обрабатывается. Если ведро пустое, запрос отклоняется или ставится в очередь, в зависимости от конфигурации.

Токены добавляются в ведро с определенной скоростью, что позволяет контролировать максимальное количество запросов в секунду. Например, если ведро имеет максимальный объем 10 токенов и скорость добавления 1 токен в секунду, то в течение 10 секунд может быть обработано до 10 запросов, после чего сервер будет ограничивать доступ до тех пор, пока не добавится новый токен.

Настройка Token Bucket

Рассмотрим, как можно настроить алгоритм Token Bucket в приложении на Node.js с использованием библиотеки rate-limiter-flexible. Вот пример кода:

const { RateLimiterBuilder } = require('rate-limiter-flexible');

const rateLimiter = new RateLimiterBuilder()
  .setTokensPerInterval(10, 'second')
  .setBlockDuration(60) // Блокировка на 60 секунд
  .build();

app.use(async (req, res, next) => {
  try {
    await rateLimiter.consume(req.ip);
    next();
  } catch (rejRes) {
    res.status(429).send('Слишком много запросов, попробуйте позже');
  }
});

В этом примере мы создаем лимитер, который позволяет 10 запросов в секунду с блокировкой на 60 секунд для IP-адресов, превышающих лимит. Такой подход помогает защитить сервер от DDoS-атак и обеспечивает стабильную работу приложения.

Алгоритм Token Bucket имеет несколько преимуществ, которые делают его популярным выбором для реализации ограничения скорости. Во-первых, он позволяет гибко управлять трафиком, позволяя пользователям делать временные всплески запросов, что особенно полезно для приложений с переменной нагрузкой. Во-вторых, алгоритм легко реализуется и адаптируется под различные сценарии использования.

Преимущества:

• Гибкость: пользователи могут отправлять несколько запросов за короткий период, если ведро не пустое.
• Простота реализации: легко интегрируется в существующие системы.
• Эффективность: позволяет избежать блокировки легитимных пользователей в пиковые моменты.

Недостатки:

• Потеря токенов: если токены не используются, они теряются, что может привести к неэффективному использованию ресурсов.
• Сложность настройки: необходимо корректно настроить параметры, чтобы избежать перегрузки или недогрузки сервера.

Для оптимизации работы алгоритма Token Bucket важно внимательно подойти к выбору значений для объема ведра и скорости добавления токенов. Например, для веб-приложений с высокой нагрузкой может потребоваться увеличить объем ведра, чтобы обрабатывать больший поток запросов в короткие временные промежутки.