Sliding Window Log

Sliding Window Log — это алгоритм ограничения частоты запросов (rate limiting), используемый в компьютерных системах для контроля интенсивности поступления событий (например, HTTP-запросов, вызовов API, попыток входа) за скользящий временной интервал. Относится к классу алгоритмов скользящего окна, обеспечивающих более точное и гибкое ограничение по сравнению с фиксированными оконными методами (например, Fixed Window Counter). Основная задача Sliding Window Log — предотвратить превышение заданного лимита запросов в любой момент времени, что критично для защиты серверов от перегрузок, DDoS-атак (распределённых атак типа «отказ в обслуживании») и злоупотребления ресурсами.

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

В основе алгоритма лежит ведение лога (журнала) временных меток каждого события, поступившего в систему. Для каждого клиента или сессии (идентифицируемых по IP-адресу, API-ключу или другому параметру) поддерживается отдельный список, в котором хранятся моменты времени (timestamp) всех запросов, совершённых в пределах текущего скользящего окна.

Этапы обработки запроса

1. Получение запроса: система фиксирует текущее время (например, в миллисекундах или секундах с эпохи Unix).
2. Определение окна: задаётся длина окна (например, 1 минута, 10 секунд) и максимально допустимое количество запросов (лимит) за это окно.
3. Очистка лога: из лога удаляются все записи, время которых меньше, чем текущее_время — длина_окна. Таким образом, в логе остаются только метки, попадающие в актуальное окно.
4. Подсчёт запросов: вычисляется количество записей, оставшихся в логе после очистки.
5. Принятие решения:

• Если количество запросов меньше лимита, запрос разрешается, а его временная метка добавляется в лог.
• Если количество запросов равно лимиту или превышает его, запрос отклоняется (обычно с HTTP-статусом 429 Too Many Requests).

Пример

Предположим, лимит составляет 5 запросов в минуту, а окно равно 60 секундам. Клиент отправляет запросы в моменты: 0, 10, 20, 30, 40 и 50 секунд. При поступлении шестого запроса (на 50-й секунде) лог содержит метки 0, 10, 20, 30, 40 — все они попадают в окно (50 — 60 = -10, то есть все метки от 0 до 50). Количество запросов равно 5, что равно лимиту, поэтому запрос на 50-й секунде будет отклонён. Если бы запрос поступил на 61-й секунде, то из лога удалилась бы метка 0 (так как 61 — 60 = 1, а 0 < 1), и количество запросов стало бы равно 4, что меньше лимита — запрос был бы разрешён.

Отличия от других алгоритмов

Sliding Window Log часто сравнивают с другими методами ограничения частоты, такими как Fixed Window Counter, Sliding Window Counter (на основе счётчиков) и Token Bucket.

Fixed Window Counter (фиксированное окно)

• Принцип: время делится на равные интервалы (например, 60 секунд), и для каждого интервала ведётся отдельный счётчик. В начале нового интервала счётчик сбрасывается.
• Недостаток: возможен «всплеск» запросов на границе окон. Например, при лимите 5 запросов в минуту клиент может отправить 5 запросов в последнюю секунду одного окна и ещё 5 — в первую секунду следующего, что в сумме даст 10 запросов за 2 секунды, хотя формально лимит не нарушен.
• Преимущество Sliding Window Log: скользящее окно устраняет этот эффект, так как граница окна определяется не фиксированными моментами, а текущим временем.

Sliding Window Counter (скользящее окно на счётчиках)

• Принцип: комбинирует фиксированные окна и интерполяцию. Хранит счётчики для двух соседних окон, а текущее количество запросов вычисляется как взвешенная сумма.
• Недостаток: менее точен, чем Sliding Window Log, так как использует аппроксимацию.
• Преимущество Sliding Window Log: обеспечивает точное соблюдение лимита в любой момент времени, так как учитывает каждую временную метку.

Token Bucket (ведро токенов)

• Принцип: система накапливает токены с постоянной скоростью, и каждый запрос потребляет один токен. Если токенов нет, запрос отклоняется.
• Недостаток: допускает кратковременные всплески трафика, если в ведре накопилось много токенов.
• Преимущество Sliding Window Log: более строгое ограничение, не допускающее всплесков, так как лимит фиксирован для любого момента времени.

Преимущества и недостатки

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

• Точность: Sliding Window Log гарантирует, что за любой скользящий интервал заданной длины количество запросов не превысит лимит. Это особенно важно для систем, где критична равномерность нагрузки (например, в финансовых API или системах управления доступом).
• Гибкость: легко адаптируется к разным единицам времени (секунды, минуты, часы) и лимитам. Можно задавать разные окна для разных типов запросов.
• Простота реализации: базовая версия требует лишь хранения списка временных меток и их периодической очистки.

Недостатки

• Потребление памяти: для каждого клиента или сессии необходимо хранить все временные метки запросов в пределах окна. При высоком лимите (например, 10 000 запросов в минуту) и большом количестве клиентов объём хранимых данных может стать значительным. Это ограничивает масштабируемость алгоритма в распределённых системах.
• Сложность очистки: удаление устаревших записей требует дополнительных вычислительных затрат, особенно при большом размере лога. В некоторых реализациях используется фоновый процесс или ленивое удаление (при каждом запросе).
• Невозможность использования в реальном времени без оптимизации: в высоконагруженных системах (миллионы запросов в секунду) хранение и обработка всех меток может быть неэффективной. В таких случаях применяются приближённые алгоритмы (например, Sliding Window Counter или вероятностные структуры данных, такие как HyperLogLog).

Применение

Sliding Window Log широко используется в веб-серверах, API-шлюзах, прокси-серверах и облачных платформах для защиты от злоупотреблений и перегрузок. Примеры:

• API-шлюзы: Nginx, Kong, AWS API Gateway, Yandex API Gateway (входит в состав Yandex Cloud) — могут использовать Sliding Window Log для ограничения частоты запросов к API. В России, например, платформа «СберБизнес API» применяет подобные алгоритмы для защиты своих сервисов.
• Веб-серверы: модули для Apache и Nginx (например, ngx_http_limit_req_module) реализуют алгоритмы, близкие к Sliding Window Log, для ограничения числа запросов от одного IP-адреса.
• Системы аутентификации: для предотвращения перебора паролей (brute force) — например, ограничение числа попыток входа за 15 минут.
• Платформы электронной коммерции: Ozon, Wildberries, «Яндекс Маркет» — для ограничения частоты запросов к каталогам товаров и ценам, чтобы избежать скрейпинга (автоматического сбора данных).
• Социальные сети и мессенджеры: «ВКонтакте», Telegram, «Одноклассники» — для ограничения частоты отправки сообщений, запросов к API или действий пользователей.

Реализация

Пример на псевдокоде

``` class SlidingWindowLog: def __init__(self, limit, window_size_ms): self.limit = limit self.window_size_ms = window_size_ms self.log = [] # список временных меток

def allow_request(self, current_time_ms):

Очистка устаревших записей

self.log = [t for t in self.log if t > current_time_ms - self.window_size_ms]

Проверка лимита

if len(self.log) < self.limit: self.log.append(current_time_ms) return True else: return False ```

Оптимизации

Для снижения потребления памяти и ускорения работы применяются следующие техники:

• Использование очередей с фиксированной длиной: вместо хранения всех меток можно хранить только последние limit меток, так как более старые записи не влияют на решение.
• Ленивое удаление: очистка лога производится только при превышении лимита, а не при каждом запросе.
• Хранение в оперативной памяти: для быстрого доступа лог часто хранится в Redis или Memcached, что позволяет реализовать распределённое ограничение частоты.
• Приближённые методы: в высоконагруженных системах вместо точного Sliding Window Log могут использоваться алгоритмы на основе счётчиков с экспоненциальным сглаживанием или вероятностные структуры данных.

Критика и альтернативы

Основной критикой Sliding Window Log является его ресурсоёмкость при больших объёмах трафика. В распределённых системах, где запросы обрабатываются несколькими серверами, синхронизация логов между узлами может стать проблемой. В таких случаях предпочтение отдаётся алгоритмам, не требующим хранения всех меток, например:

• Sliding Window Counter — компромисс между точностью и производительностью.
• Token Bucket — допускает всплески, но проще в реализации и масштабировании.
• Leaky Bucket (дырявое ведро) — сглаживает трафик, но может задерживать запросы.

Несмотря на недостатки, Sliding Window Log остаётся популярным выбором для систем, где требуется строгое соблюдение лимитов в любой момент времени, особенно в контексте защиты от атак и злоупотреблений.

Источники

• «Rate Limiting Algorithms» — документация AWS API Gateway.
• «High Performance Browser Networking» by Ilya Grigorik (O'Reilly Media, 2013).
• «Designing Data-Intensive Applications» by Martin Kleppmann (O'Reilly Media, 2017).
• «Sliding Window Log Algorithm» — статья на Medium (автор: Rahul Shetty).
• «Nginx ngx_http_limit_req_module» — официальная документация Nginx.
• «Rate Limiting in Distributed Systems» — технический блог компании Cloudflare.
• «Алгоритмы ограничения частоты запросов» — статья на Habr (автор: @alexey_smirnov).