Что такое rate limiting и как его реализовать?

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

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

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

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

Зачем это нужно

1. Защита от перегрузки: Ограничивает количество запросов, чтобы сервер мог обрабатывать их без снижения производительности.
2. Безопасность: Предотвращает злоупотребления, такие как DDoS-атаки, где злоумышленники пытаются перегрузить сервер.
3. Справедливость: Обеспечивает равномерное распределение ресурсов между всеми пользователями, предотвращая монополизацию ресурсов одним клиентом.

Как это работает

Rate limiting может быть реализован с использованием различных алгоритмов и подходов. Рассмотрим несколько популярных методов:

1. Fixed Window

Этот метод делит время на фиксированные интервалы (например, минуты или часы) и ограничивает количество запросов в каждом интервале.

import time
​
class FixedWindowRateLimiter:
    def __init__(self, max_requests, window_size):
        self.max_requests = max_requests
        self.window_size = window_size
        self.requests = 0
        self.window_start = time.time()
​
    def allow_request(self):
        current_time = time.time()
        if current_time - self.window_start >= self.window_size:
            # Обновляем окно и сбрасываем счетчик запросов
            self.window_start = current_time
            self.requests = 0
        if self.requests < self.max_requests:
            # Разрешаем запрос и увеличиваем счетчик
            self.requests += 1
            return True
        return False

• max_requests: Максимальное количество запросов, разрешенных в одном окне.
• window_size: Длительность окна в секундах.
• requests: Текущий счетчик запросов в текущем окне.
• window_start: Время начала текущего окна.

2. Sliding Window

Этот метод улучшает Fixed Window, позволяя более плавное распределение запросов, обновляя окно с каждым новым запросом.

from collections import deque
import time
​
class SlidingWindowRateLimiter:
    def __init__(self, max_requests, window_size):
        self.max_requests = max_requests
        self.window_size = window_size
        self.requests = deque()
​
    def allow_request(self):
        current_time = time.time()
        # Удаляем устаревшие запросы
        while self.requests and self.requests[0] <= current_time - self.window_size:
            self.requests.popleft()
        if len(self.requests) < self.max_requests:
            # Разрешаем запрос и добавляем его время
            self.requests.append(current_time)
            return True
        return False

• requests: Дек, хранящий временные метки запросов.
• Устаревшие запросы удаляются, чтобы поддерживать актуальное состояние окна.

3. Token Bucket

Этот метод использует "ведро" с токенами, где каждый токен позволяет сделать один запрос. Токены добавляются в ведро с фиксированной скоростью.

import time
​
class TokenBucketRateLimiter:
    def __init__(self, max_tokens, refill_rate):
        self.max_tokens = max_tokens
        self.refill_rate = refill_rate
        self.tokens = max_tokens
        self.last_refill = time.time()
​
    def allow_request(self):
        current_time = time.time()
        # Пополняем токены в ведре
        refill_tokens = (current_time - self.last_refill) * self.refill_rate
        self.tokens = min(self.max_tokens, self.tokens + refill_tokens)
        self.last_refill = current_time
        if self.tokens >= 1:
            # Разрешаем запрос и уменьшаем количество токенов
            self.tokens -= 1
            return True
        return False

• max_tokens: Максимальное количество токенов в ведре.
• refill_rate: Скорость пополнения токенов в секунду.
• tokens: Текущее количество токенов в ведре.