Rate limiter на Go: алгоритмы, token bucket и middleware с 429

Зачем нужен лимитер и где его ставить

Лимит защищает дорогой ресурс — базу, платный внешний API, CPU, — делит мощность между клиентами и замедляет перебор паролей и скрейпинг. Для отказа есть стандартный код: RFC 6585 определяет 429 Too Many Requests — клиент отправил слишком много запросов за интервал, и ответ может содержать Retry-After. При этом RFC не определяет, как сервер идентифицирует клиента и как считает запросы: ключ, окно и алгоритм выбираете вы.

Мест обычно три. На краю — gateway или ingress — грубый лимит по IP отсекает мусор до приложения. В middleware сервиса — лимит по API-ключу или пользователю, где известны бизнес-контекст и тариф. Перед внешней зависимостью — исходящий лимит, чтобы не превысить квоту партнёра; здесь удобен Wait из golang.org/x/time/rate. С ключом по IP осторожнее: за NAT один адрес делят многие пользователи, а заголовку X-Forwarded-For можно доверять, только если его выставил ваш собственный прокси.

• RFC 6585, section 4: 429 Too Many Requests

Пять алгоритмов: что выбрать

Fixed window считает запросы в календарном окне: при лимите 100 в минуту клиент сделает 100 запросов в 12:00:59 и ещё 100 в 12:01:00. Sliding log хранит время каждого запроса и считает точно, но память растёт с лимитом. Sliding window counter взвешивает предыдущее окно: в примере Cloudflare при лимите 50 в минуту 42 запроса прошлой минуты и 18 текущей, начавшейся 15 секунд назад, дают 42 × 0,75 + 18 = 49,5. В их анализе 400 млн запросов от 270 тыс. источников ошибочно пропущены или ограничены 0,003% запросов — это результат на их трафике, а не универсальная точность.

Token bucket пополняется со скоростью r токенов в секунду до ёмкости b, каждый запрос тратит токен: средняя скорость ограничена r, а всплеск — b. Так устроен стандартный golang.org/x/time/rate. Leaky bucket в варианте с очередью пропускает запросы с постоянной скоростью: выход ровный, но клиент ждёт в очереди, и её размер тоже нужно ограничивать. Для API разумный выбор по умолчанию — token bucket; если нужна строгая точность окна — sliding log; если память важнее точности — sliding window counter.

• Cloudflare — How we built rate limiting capable of scaling to millions of domains (2017)
• pkg.go.dev: golang.org/x/time/rate

Token bucket на Go без зависимостей

Ведро хранит число токенов и время последнего пополнения. Allow не запускает таймеров: при каждом вызове считает, сколько токенов накопилось с прошлого раза, ограничивает их ёмкостью burst, тратит токен или возвращает время до следующего: (1 − tokens) / rate. Ленивое пополнение даёт O(1) памяти на ключ и не требует горутины на каждого клиента. Все фрагменты статьи — один файл main.go в package main с импортами fmt, math, net/http, net/http/httptest, strconv, sync и time; запуск — go run main.go.

Allow читает и меняет tokens и last, поэтому без мьютекса параллельные запросы дают гонку данных; sync.Mutex делает тип безопасным для конкурентного использования. Часы передаются функцией now: в production это time.Now, в тесте — поддельные часы. Проверка t.After(b.last) защищает от часов, идущих назад. Для time.Now это не критично: его значения содержат монотонные показания, и вычитание использует именно их, — но у поддельных часов и времени, прочитанного из хранилища, такой гарантии нет.

type Bucket struct { // token bucket: rate токенов/с, ёмкость burst
	mu                  sync.Mutex
	rate, burst, tokens float64
	last                time.Time
	now                 func() time.Time // внедрённые часы
}

func NewBucket(rate, burst float64, now func() time.Time) *Bucket {
	return &Bucket{rate: rate, burst: burst, tokens: burst, last: now(), now: now}
}

func (b *Bucket) Allow() (bool, time.Duration) {
	b.mu.Lock()
	defer b.mu.Unlock()
	if t := b.now(); t.After(b.last) {
		b.tokens = math.Min(b.burst, b.tokens+t.Sub(b.last).Seconds()*b.rate)
		b.last = t
	}
	if b.tokens >= 1 {
		b.tokens--
		return true, 0
	}
	return false, time.Duration((1 - b.tokens) / b.rate * float64(time.Second))
}

• pkg.go.dev: sync.Mutex
• pkg.go.dev: time, Monotonic Clocks

Внедрённые часы: детерминированный вывод

demoBucket создаёт ведро на 2 токена в секунду с ёмкостью 3 и двигает поддельные часы на заданные шаги. Вывод go run на Go 1.26.6: req1–req3 ok=true в t=0s, req4 ok=false wait=500ms. Через 250 мс req5 всё ещё отклонён с wait=250ms — накопилась половина токена. В t=500ms req6 проходит. После десяти секунд простоя, в t=10.5s, проходят req7, req8 и req9, а req10 снова получает wait=500ms: ведро не копит 20 токенов, его ограничивает ёмкость.

Тест на time.Sleep медленный и нестабильный: планировщик может разбудить горутину позже, и граница появления токена плавает. Поддельные часы делают границу точной: можно проверить момент за миллисекунду до токена и ровно в момент его появления. fakeClock здесь не потокобезопасен — для однопоточного теста этого достаточно; если тестируете конкурентный доступ, защитите и часы. Тот же приём работает для любого кода с таймаутами и TTL.

type fakeClock struct{ t time.Time }

func (c *fakeClock) Now() time.Time          { return c.t }
func (c *fakeClock) Advance(d time.Duration) { c.t = c.t.Add(d) }

func demoBucket() {
	clk := &fakeClock{t: time.Date(2026, 11, 7, 12, 0, 0, 0, time.UTC)}
	start := clk.t
	b := NewBucket(2, 3, clk.Now) // 2 токена в секунду, всплеск до 3
	ms := time.Millisecond
	for i, d := range []time.Duration{0, 0, 0, 0, 250 * ms, 250 * ms, 10000 * ms, 0, 0, 0} {
		clk.Advance(d)
		ok, wait := b.Allow()
		fmt.Printf("t=%-6v req%-2d ok=%-5v wait=%v\n", clk.t.Sub(start), i+1, ok, wait)
	}
}

HTTP middleware: 429 и Retry-After

KeyedLimiter держит карту «ключ → ведро» под собственным мьютексом и лениво создаёт ведро для нового клиента. Middleware берёт ключ из заголовка X-API-Key, при отказе выставляет Retry-After и отвечает 429 через http.Error. RFC 9110 разрешает в Retry-After дату HTTP или целое неотрицательное число секунд; ожидание 500 мс округляется вверх до 1, чтобы клиент не вернулся раньше, чем появится токен. Заголовок нужно выставить до записи статуса — http.Error пишет его сразу.

main из следующего раздела отправляет четыре запроса через httptest при rate = 1 и burst = 2. Вывод: alice 200, alice 200, alice 429 Retry-After="1", bob 200 — у bob своё ведро. Обратите внимание на запросы без заголовка: все они попадают в общее ведро с пустым ключом. В production для анонимных клиентов используйте IP или отклоняйте запрос, иначе один шумный клиент исчерпает лимит для всех анонимов.

type KeyedLimiter struct {
	mu          sync.Mutex
	rate, burst float64
	now         func() time.Time
	clients     map[string]*Bucket
}

func (k *KeyedLimiter) get(key string) *Bucket {
	k.mu.Lock()
	defer k.mu.Unlock()
	b, ok := k.clients[key]
	if !ok {
		b = NewBucket(k.rate, k.burst, k.now)
		k.clients[key] = b
	}
	return b
}

func (k *KeyedLimiter) Middleware(next http.Handler) http.Handler {
	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		ok, wait := k.get(r.Header.Get("X-API-Key")).Allow()
		if !ok {
			w.Header().Set("Retry-After", strconv.Itoa(int(math.Ceil(wait.Seconds()))))
			http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
			return
		}
		next.ServeHTTP(w, r)
	})
}

• RFC 9110, section 10.2.3: Retry-After

Память по ключам, x/time/rate и распределённый лимит

Карта растёт с каждым новым ключом, и атака со случайными ключами превращается в утечку памяти. Cleanup удаляет ведра, которые не трогали дольше idle. Безопасный порог — не меньше burst / rate: к этому моменту ведро всё равно наполнилось бы, и удаление не меняет поведения лимитера. В выводе после десяти минут простоя — «удалено: 2 осталось: 1»: ведра alice и bob ушли, а ведро пустого ключа только что использовалось. Cleanup берёт k.mu, затем b.mu, а Allow — только b.mu, поэтому взаимной блокировки нет. Сам main однопоточный, поэтому я отдельно прогнал под go run -race восемь горутин с запросами и параллельный Cleanup — замечаний не было.

В production обычно берут golang.org/x/time/rate: Limiter реализует token bucket ёмкости b с пополнением r в секунду, предлагает Allow, Reserve и Wait и безопасен для нескольких горутин. Свою реализацию пишут на собеседовании и для нестандартной семантики. Локальные ведра на N инстансах дают до N лимитов, поэтому общий лимит на API-ключ держат в общем хранилище. Документация Redis описывает лимитеры на INCR и EXPIRE: вариант с MULTI/EXEC и вариант с одним счётчиком, где есть гонка — ключ может остаться без срока жизни, — которую закрывают Lua-скриптом. Цена — сетевой запрос на каждый вызов и решение, что делать при недоступности Redis: пропускать или отклонять.

func (k *KeyedLimiter) Cleanup(idle time.Duration) int {
	k.mu.Lock()
	defer k.mu.Unlock()
	before := len(k.clients)
	for key, b := range k.clients {
		b.mu.Lock()
		if k.now().Sub(b.last) > idle {
			delete(k.clients, key)
		}
		b.mu.Unlock()
	}
	return before - len(k.clients)
}

func main() {
	demoBucket()
	clk := &fakeClock{t: time.Date(2026, 11, 7, 12, 0, 0, 0, time.UTC)}
	lim := &KeyedLimiter{rate: 1, burst: 2, now: clk.Now, clients: map[string]*Bucket{}}
	h := lim.Middleware(http.HandlerFunc(func(http.ResponseWriter, *http.Request) {}))
	for _, key := range []string{"alice", "alice", "alice", "bob"} {
		req := httptest.NewRequest("GET", "/api/cards", nil)
		req.Header.Set("X-API-Key", key)
		rec := httptest.NewRecorder()
		h.ServeHTTP(rec, req)
		fmt.Printf("%-5s %d Retry-After=%q\n", key, rec.Code, rec.Header().Get("Retry-After"))
	}
	clk.Advance(10 * time.Minute)
	h.ServeHTTP(httptest.NewRecorder(), httptest.NewRequest("GET", "/api/cards", nil))
	fmt.Println("удалено:", lim.Cleanup(5*time.Minute), "осталось:", len(lim.clients))
}

• pkg.go.dev: golang.org/x/time/rate
• Redis: INCR, pattern Rate limiter

Как отвечать на собеседовании и что повторить

На system design начните с требований: лимит на кого — ключ, пользователя или IP, какие числа и всплески, жёсткий или мягкий отказ, один инстанс или кластер. Затем назовите алгоритм и его подвох, место хранения состояния, ответ клиенту с 429 и Retry-After и поведение при сбое хранилища. На live coding проговорите гонку данных, ленивое пополнение и тестирование через внедрённые часы — это отличает рабочий код от учебного.

Для повторения пригодятся вопросы по Go и по HTTP, а распределённую часть удобно связать с паттернами Redis из разбора cache-aside.

• 100 вопросов по Go на собеседовании с ответами
• 36 вопросов по HTTP и REST API на собеседовании
• Redis Cache-Aside: защита от stampede
• Подготовка к собеседованию по Go

Коротко

Частые вопросы