Как реализовать Rate Limiter и какие алгоритмы используются?

Rate Limiter — это механизм, предназначенный для контроля частоты запросов к системе, предотвращая её перегрузку и защищая от злоупотреблений (например, DDoS-атак).

Пример реализации на Python с использованием алгоритма Token Bucket:

import time

class RateLimiter:
    def __init__(self, capacity: int, refill_rate: float):
        """
        Инициализация Rate Limiter.
        :param capacity: Максимальное количество токенов (запросов).
        :param refill_rate: Скорость пополнения токенов в секунду.
        """
        self.capacity = capacity
        self.tokens = capacity
        self.last_refill = time.time()
        self.refill_rate = refill_rate  # tokens per second

    def allow_request(self) -> bool:
        """
        Проверяет, разрешен ли запрос.
        :return: True, если запрос разрешен, False иначе.
        """
        now = time.time()
        elapsed = now - self.last_refill
        # Пополняем токены, но не превышаем capacity
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

# Пример использования:
# limiter = RateLimiter(capacity=5, refill_rate=1) # 5 запросов, 1 токен/сек
# for _ in range(10):
#     if limiter.allow_request():
#         print("Request allowed")
#     else:
#         print("Request denied")
#     time.sleep(0.5)

Сферы применения:

• API-сервисы (REST/gRPC): Защита от перегрузок, злоупотреблений и обеспечение справедливого использования ресурсов.
• Ограничение вызовов внешних API: Контроль над количеством запросов к сторонним сервисам (например, Telegram Bot API, платежные шлюзы) для соблюдения их лимитов.

Другие алгоритмы и готовые решения:

• Фиксированное окно (Fixed Window): Разрешает N запросов в течение фиксированного временного интервала. Прост в реализации, но может быть уязвим к всплескам запросов в начале или конце окна.
• Скользящее окно (Sliding Window): Более сложный, но точный алгоритм, который учитывает запросы из предыдущего окна, обеспечивая более плавное ограничение.
• Готовые решения: Для распределённых систем часто используются Redis с модулями типа redis-cell или специализированные библиотеки, такие как FastAPI-Limiter для Python-фреймворков.

Важно: В распределённых системах необходимо учитывать race conditions, поскольку одновременные запросы могут привести к некорректному состоянию лимитера. В таких случаях рекомендуется использовать распределённые хранилища (например, Redis) с атомарными операциями для обеспечения консистентности.