2. Rate limiting алгоритмы

Введение: Зачем ограничивать поток?

Rate limiting (ограничение скорости потока запросов) — это не просто примитивный барьер «защиты от спама». В зрелой архитектуре распределенного бэкенда это фундаментальный механизм управления пропускной способностью (flow control), гарантирующий устойчивость микросервисов, защищающий реляционные базы данных от лавинообразных каскадных сбоев (cascade failure), предотвращающий разорение бюджета на внешние облачные API и реализующий гибкую тарификацию клиентских аккаунтов.

В отличие от наивной блокировки горутин через time.Sleep или каналы, алгоритмически корректный rate limiter обязан мгновенно отвечать на три вопроса: «Сколько запросов разрешено прямо сейчас?», «Когда будет доступна следующая квота?» и «Как корректно срезать или пропустить импульсный всплеск (burst-трафик)?». При этом алгоритм обязан работать со строгой сложностью O(1), не порождать паразитной борьбы за мьютексы (lock contention), минимизировать аллокации в куче и предсказуемо масштабироваться на сотни тысяч запросов в секунду.

В этой статье мы подробно разберем алгоритмическую DSA-основу ограничения скорости, реализуем идиоматичные и быстрые решения на Go с учетом особенностей планировщика, vDSO-таймеров и атомарных инструкций процессора, а также исследуем паттерны координации лимитов в распределенных кластерах.

Классификация алгоритмов и их DSA-основа

Каждый алгоритм опирается на собственные структуры данных и обеспечивает специфический баланс между точностью, потреблением памяти и сглаживанием пиков:

В инженерной практике бэкенда Token Bucket стал де-факто промышленным стандартом для API-шлюзов и сервисов тарификации. Sliding Window Counter отлично подходит для биллинга и аналитики, а Leaky Bucket незаменим при защите чувствительных downstream-сервисов с жестким лимитом одновременных транзакций.

Production-реализация: Token Bucket в Go

Пакет стандартного расширения golang.org/x/time/rate прекрасно справляется с типовыми задачами, однако на системных собеседованиях и в кастомных высоконагруженных API-гейтвеях требуется понимание его внутренней механики. Ниже представлена потокобезопасная, оптимизированная реализация структуры TokenBucket.

package ratelimit

import (
    "sync"
    "time"
)

// TokenBucket реализует алгоритм корзины токенов.
// Потокобезопасен, O(1) на запрос, lazy refill.
type TokenBucket struct {
    mu           sync.Mutex
    capacity     float64
    rate         float64 // токенов в секунду
    tokens       float64
    lastRefillAt time.Time
}

// NewTokenBucket создаёт лимитер с заданной пропускной способностью и burst.
func NewTokenBucket(rate float64, burst float64) *TokenBucket {
    return &TokenBucket{
        capacity:     burst,
        rate:         rate,
        tokens:       burst,
        lastRefillAt: time.Now(),
    }
}

// Allow проверяет и резервирует 1 токен. Возвращает true, если запрос разрешён.
func (tb *TokenBucket) Allow() bool {
    return tb.AllowN(1)
}

// AllowN проверяет и резервирует n токенов.
func (tb *TokenBucket) AllowN(n float64) bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    tb.refill(now)

    if tb.tokens >= n {
        tb.tokens -= n
        return true
    }
    return false
}

// WaitTime возвращает время ожидания до возможности выполнить запрос.
func (tb *TokenBucket) WaitTime() time.Duration {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    tb.refill(now)

    if tb.tokens >= 1 {
        return 0
    }
    // Сколько секунд нужно, чтобы набрать 1 - tb.tokens
    need := 1.0 - tb.tokens
    waitSec := need / tb.rate
    return time.Duration(waitSec * float64(time.Second))
}

// refill лениво пополняет токены на основе прошедшего времени.
// Вызывается ТОЛЬКО под tb.mu.
func (tb *TokenBucket) refill(now time.Time) {
    elapsed := now.Sub(tb.lastRefillAt).Seconds()
    if elapsed > 0 {
        tb.tokens += elapsed * tb.rate
        if tb.tokens > tb.capacity {
            tb.tokens = tb.capacity
        }
        tb.lastRefillAt = now
    }
}

Ключевые инженерные решения:

• Lazy Refill: Токены не генерируются фоновым таймером. Их количество рассчитывается «на лету» в момент обращения Allow(). Это экономит миллионы тактов CPU, исключает аллокации time.Ticker и разгружает планировщик горутин.
• Использование float64: Позволяет начислять дробные доли токенов при низких скоростях rate, предотвращая потери пропускной способности из-за целочисленного усечения.
• Блокировка через sync.Mutex: Согласованное обновление нескольких связанных полей (tokens и lastRefillAt) под легким мьютексом быстрее и надежнее сложных спин-циклов CAS на плавающей точке.

Механическая симпатия: таймеры, атомики и GC

Поведение rate limiter под нагрузкой тесно связано с устройством ядра ОС и процессора.

Стоимость time.Now() и vDSO

Вызов time.Now() в современном Linux опирается на механизм vDSO (Virtual Dynamically Shared Object) для системного вызова clock_gettime(CLOCK_MONOTONIC). Ядро операционной системы проецирует страницу текущего системного времени напрямую в адресное пространство пользователя, позволяя считывать метки без дорогостоящего переключения контекста ядро/пользователь. Это занимает всего ~5–10 нс.

Однако при сверхвысоком темпе обращений (>1M RPS) страница времени может вымываться из процессорного кэша L1, увеличивая накладные расходы до 50–100 нс. В экстремальных сценариях системные архитекторы кэшируют время в sync.Pool или обновляют переменную метки раз в 10 мс через выделенную горутину, хотя в 99% сервисов стандартного time.Now() более чем достаточно.

Конкурентность и False Sharing

Если приложение динамически создает структуры TokenBucket для сотен тысяч клиентов и хранит их по указателям в единой мапе map[string]*TokenBucket, поля мьютексов mu sync.Mutex могут попадать в смежные адреса одной и той же 64-байтной кэш-линии. При высокой конкуренции разных ядер процессора возникает эффект False Sharing, приводящий к лавинообразной инвалидации L1-кэшей.
Решение: Применять шардирование пула лимитеров по хешу идентификатора клиента (Client ID / IP).

type ShardedLimiter struct {
    shards []*TokenBucket
    mask   uint32
}

Escape Analysis и аллокации

Структура TokenBucket не содержит указателей на внешние структуры. Если экземпляр создается для локального расчета внутри стекового фрейма, Escape Analysis оставляет его на стеке. При совместном доступе из параллельных горутин объект выносится в кучу, однако нагрузка на сборщик мусора минимальна, так как структура монолитна и не требует рекурсивного сканирования полей.

Распределённый Rate Limiting

Локальный ограничитель защищает отдельный экземпляр приложения, но в облачном кластере Kubernetes общий трафик распределяется между десятками подов. Для согласованного лимитирования применяется связка Redis + Lua-скрипт.

Благодаря однопоточному event-loop ядра Redis и изоляции Lua-скрипта операции чтения текущего состояния, расчета прошедшего времени и записи обновленных токенов выполняются абсолютно атомарно:

-- Redis Lua script for distributed Token Bucket
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1])
local last_refill = tonumber(bucket[2])

if tokens == nil then
    tokens = capacity
    last_refill = now
end

local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * rate)

if tokens >= requested then
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / rate) + 1)
    return 1 -- Allowed
end

return 0 -- Denied

Инженерные аспекты:

• Сетевой RTT и сериализация параметров накладывают оверхед 0.5–2 мс на каждый проверяемый запрос.
• Для критичных к задержкам сервисов применяют двухуровневые схемы: локальный лимитер на ноде с периодической асинхронной синхронизацией квот либо вероятностное ограничение (Probabilistic Rate Limiting).
• Горизонтальное масштабирование самого Redis достигается кластеризацией через шардинг ключей по слотам (HASH_SLOT).

Ловушки production-разработки и вопросы с собеседований

Итог

• Rate Limiting — инструмент управления потоком, а не блокирующий механизм. Выбор алгоритмической основы диктуется сценарием: Token Bucket для всплесков и тарификации, Leaky Bucket для строгого выравнивания потока, Sliding Window для высокоточной аналитики.
• В языке Go наиболее эффективна ленивая схема (lazy refill) на sync.Mutex и монотонном времени time.Now(). Она полностью исключает оверхед фоновых таймеров и выполняется за O(1) времени без динамических аллокаций.
• Механическая симпатия: системные тайминги быстры благодаря механизму vDSO ядра Linux, а шардирование контейнеров устраняет взаимную инвалидацию кэш-линий CPU (False Sharing).
• Распределенная среда: требует атомарного выполнения через связку Redis + Lua. Рассинхронизация часов (clock skew) парируется использованием времени координатора или демон-службами точной синхронизации chrony.
• Production-паттерны: всегда возвращайте статус HTTP 429 с информативным заголовком Retry-After, категорически избегайте time.Sleep в обработчиках и комбинируйте лимитирование с 1. Проектирование кэшей.
• Интервью-фокус: компромиссы между burst-пропускной способностью и постоянной скоростью, точность аппроксимаций при экономии памяти, пределы применимости атомиков против спин-мьютексов.

Разобравшись с управлением потоком запросов на одном инстансе, мы переходим к архитектурной задаче маршрутизации в кластере: как направлять запросы к нужной ноде, минимизировать переезд данных при масштабировании и обеспечивать равномерную загрузку без централизованного координатора? В следующей статье мы детально изучим алгоритм, который стал стандартом для распределённых хеш-таблиц, CDN и балансировки нагрузки.

3. Consistent hashing